Hashing - Advanced Topics in Java: Core Concepts in Data Structures - page 296

In general, we can perform a search for key and, if not found, insert it at the end of the list with this pseudocode:
k = H(key) //H is the hash function
if (hash[k].num == Empty) {
hash[k].num = key
hash[k].next = -1
}
else {
curr = k
prev = -1
while (curr != -1 && hash[curr].num != key) {
prev = curr
curr = hash[curr].next
}
if (curr != -1) key is in the list at location curr
else { //key is not present
hash[free].num = key //assume free list is not empty
hash[free].next = -1
hash[prev].next = free
free = hash[free].next
} //end else
} //end else
10.3.4 Linear Probing with Double Hashing 1
In Section 10.3.1, we saw that using loc = loc + k , where k is a constant greater than 1, does not give us a better
performance than when k is 1. However, by letting k vary with the key, we can get excellent results since, unlike linear
and quadratic probing, keys that hash to the same location will probe different sequences of locations in searching for
an empty one.
The most natural way to let k vary with the key is to use a second hash function. The first hash function will
generate the initial table location. If there is a collision, the second hash function will generate the increment, k . If the
table locations run from 1 to n , we can use the following:
convert key to a numeric value, num (if it is not already numeric)
loc = num % n + 1 //this gives the initial hash location
k = num % (n - 2) + 1 //this gives the increment for this key
We mentioned before that it is wise to choose n (the table size) as a prime number. In this method, we get even
better results if n-2 is also prime (in this case, n and n-2 are called twin primes , for example 103/101, 1021/1019).
Apart from the fact that k is not fixed, the method is the same as linear probing . We describe it in terms of two
hash functions, H1 and H2. H1 produces the initial hash location, a value between 1 and n , inclusive. H2 produces
the increment, a value between 1 and n - 1 that is relatively prime to n ; this is desirable so that, if required, many
locations will be probed. As discussed earlier, if n is prime, any value between 1 and n - 1 will be relatively prime to it.
In the previous example, the second hash function produces a value between 1 and n-2 . Here is the algorithm:
//find or insert 'key' using "linear probing with double hashing"
loc = H1(key)
k = H2(key)
1 The technique is sometimes referred to as open addressing with double hashing .