Quadratic Probing and Double Hashing

Quadratic Probing and Double Hashing attempt to find ways to reduce the size of the clusters that are formed by linear probing.

Quadratic Probing

Quadratic Probing is similar to Linear probing. The difference is that if you were to try to insert into a space that is filled you would first check $1^2 = 1$ element away then $2^2 = 4$ elements away, then $3^2 =9$ elements away then $4^2=16$ elements away and so on.

With linear probing we know that we will always find an open spot if one exists (It might be a long search but we will find it). However, this is not the case with quadratic probing unless you take care in the choosing of the table size. For example consider what would happen in the following situation:

Table size is 16. First 5 pieces of data that all hash to index 2

• First piece goes to index 2.
• Second piece goes to 3 ((2 + 1)%16
• Third piece goes to 6 ((2+4)%16
• Fourth piece goes to 11((2+9)%16
• Fifth piece dosen't get inserted because (2+16)%16==2 which is full so we end up back where we started and we haven't searched all empty spots.

In order to guarantee that your quadratic probes will hit every single available spots eventually, your table size must meet these requirements:

• Be a prime number
• never be more than half full (even by one element)

Double Hashing

Double Hashing is works on a similar idea to linear and quadratic probing. Use a big table and hash into it. Whenever a collision occurs, choose another spot in table to put the value. The difference here is that instead of choosing next opening, a second hash function is used to determine the location of the next spot. For example, given hash function H1 and H2 and key. do the following:

• Check location hash1(key). If it is empty, put record in it.
• If it is not empty calculate hash2(key).
• check if hash1(key)+hash2(key) is open, if it is, put it in
• repeat with hash1(key)+2hash2(key), hash1(key)+3hash2(key) and so on, until an opening is found.

like quadratic probing, you must take care in choosing hash2. hash2 CANNOT ever return 0. hash2 must be done so that all cells will be probed eventually.