int a[N+1]; for i=1 to N1 { for j=i+1 to N { if (a[i] + a[j] == K) { print(a[i]+ " and "+a[j]); return; } } } print("no such integers");
int a[N+1]; boolean checked[K+1]; for i=0 to K { checked[i] = false; } for i=1 to N { checked[a[i]] = true; if (checked[Ka[i]]==true) { print(a[i]+" and "+(Ka[i])); return; } } print("no such integers");
checked[]
might be too large for the memory available. checked[]
will be empty.
int hashtable[M]; // M > N void store (int key, int value) { hashtable[h(key)] = value; } void get_value (int key) { return hashtable[h(key)]; } int h (int key) { return h % M; }
key
as the index, we use h(key)
.h
is a function that maps the universe U of possible keys to the indices of the hashtable.h : U > {0,1,2,...,M2,M1}
h_{i}(key) = h(key) + i
Problem: Clustering
Quadratic Probing
 If cell
x
is already taken, try x+1, x+4, x+9, x+16,..., until you find an empty cell. 
h_{i}(key) = h(key) + i*i

At least: No clustering anymore.

But if many keys are mapped to the same cell
x
, each key runs through the same sequence of cells until an empty cell is found.
Double Hashing
 On the
i
th try to find an empty cell for key
, use the hash function:
h_{i}(key) = (h(key) + i*h'(key)) mod m
.
Universal Hashing
 One problem remains: No matter which hash function you choose, there will always be a worstcase input where each key is hashed to the same slot.

Solution: Randomize the hash function!

Have a set of hash functions ready and choose from them after the program started.

A collection H of hash functions is called universal, if for each pair of distinct keys x,y, the number of hash functions for which h(x)=h(y) is exactly H/m.
Second Attempt: O(n)
t = new Hashtable;
for i=1 to N {
t.put(a[i],1);
if (t.get(Ka[i])!=NULL) {
print(a[i]+" and "+(Ka[i]));
return;
}
}
print("no such integers");
 The Java class Hashtable uses Open Hashing.
Mark Dettinger