Other Probing Strategies

  • Describe other probing strategies (quadratic, double hashing, ... for open address hash table.

Another probing strategy is double hashing, where the interval between probes is computed by a second hash function:

int index = getIndex(key);
// if table[index] is occupied, then
for(int i = 0; i < M; i++) { 
  index = (getIndex(key) + hash(key) * i) % M; 
  // stop the loop when table[index] is available!
}

Here, hash(key) != key.hashCode() and hash(key) != 0. (And, of course, the second hash function must also be a "good" hash function.)

How is the second hash function implemented?

In practice, the second hash function usually uses the first one (key.hashCode()) to produce another hash value.

The general form for this practice is as follows: index=[h1(k) + j×h2(k)] mod M\text{index} = [h_1(k) + j\times h_2(k)] \space \text{mod} M looping over j ∈[1,M)j \in [1,M) until a position is found.

Let’s assume that the keys are already hash keys (i.e. kk is key.hashCode) then h1h_1 is what I defined earlier as getIndex: h1(k)= k mod Mh_1(k) = k \text{mod} M and the second hash function is h2(k)= q −(k mod q)h_2(k) = q - (k \text{mod} q) where q<Mq<M.

For double hashing to probe all positions, you must select qq and MM as two mutual primes (their greatest common divisor is 11)

The advantage of double hashing is that the probe sequence depends on the "key" (rather than a fixed pattern). Double hashing avoids (both primary and secondary) clustering.

There are many, more sophisticated, techniques based on open addressing. Examples include:

Cuckoo Hashing Demo

This section should be considered as an optional reading; we will go over it if time allows!