Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Double Hashing

While quadratic probing does indeed eliminate the primary clustering problem, it places a restriction on the number of items that can be put in the table--the table must be less than half full. Double Hashing  is yet another method of generating a probing sequence. It requires two distinct hash functions,

gather13250

The probing sequence is then computed as follows

displaymath62269

That is, the scatter tables is searched as follows:

eqnarray13252

Since the collision resolution function is c(i)=ih'(x), the probe sequence depends on the key as follows: If h'(x)=1, then the probing sequence for the key x is the same as linear probing. If h'(x)=2, the probing sequence examines every other array position. This works as long as M is not even.

Clearly since c(0)=0, the double hashing method satisfies property 1. Furthermore, property 2 is satisfied as long as h'(x) and M are relatively prime. Since h'(x) can take on any value between 1 and M-1, M must be a prime number.

But what is a suitable choice for the function h'? Recall that h is defined as the composition of two functions, tex2html_wrap_inline61731 where tex2html_wrap_inline61837. We can define h' as the composition tex2html_wrap_inline62305, where

  equation13254

Double hashing reduces the occurrence of primary clustering since it only does a linear search if h'(x) hashes to the value 1. For a good hash function, this should only happen with probability 1/(M-1). However, for double hashing to work at all, the size of the scatter table, M, must be a prime number. Table gif summarizes the characteristics of the various open addressing probing sequences.

 

 

probing sequence primary clustering capacity limit size restriction
linear probing yes none none
quadratic probing no tex2html_wrap_inline62267 M must be prime
double hashing no none M must be prime
Table: Characteristics of the open addressing probing sequences.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.