Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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,

gather13156

The probing sequence is then computed as follows

displaymath62002

That is, the scatter tables is searched as follows:

eqnarray13158

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_inline61464 where tex2html_wrap_inline61570. We can define h' as the composition tex2html_wrap_inline62038, where

  equation13160

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_inline62000 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.