Hash tables - Data Structures and Problem Solving Using Java - page 787

if the table size was 16, the only alternative locations would be at distances 1, 4, or
9 from the original probe point. Again, size is not really an issue: Although we
would not have a guarantee of alternatives, we would usually have more
than we need. However, it is best to play it safe and use the theory to guide us in
selecting parameters. Furthermore, it has been shown empirically that prime num-
bers tend to be good for hash tables because they tend to remove some of the non-
randomness that is occasionally introduced by the hash function.
The second important consideration is efficiency. Recall that, for a load fac-
tor of 0.5, removing primary clustering saves only 0.5 probe for an average
insertion and 0.1 probe for an average successful search. We do get some addi-
tional benefits: Encountering a long probe sequence is significantly less likely.
However, if performing a probe using quadratic probing takes twice as long,
doing so is hardly worth the effort. Linear probing is implemented with a simple
addition (by 1), a test to determine whether wraparound is needed, and a very
rare subtraction (if we need to do the wraparound). The formula for quadratic
probing suggests that we need to do an addition by 1 (to go from to i ), a
multiplication (to compute i 2 ), another addition, and then a mod operation. Cer-
tainly this calculation appears to be much too expensive to be practical. How-
ever, we can use the following trick, as explained in Theorem 20.5.

M 2 ⁄

Quadratic probing
can be imple-
mented without
multiplications and
mod operations.
Because it does not
suffer from primary
clustering, it outper-
forms linear probing
in practice.

i - 1

Theorem 20.5

Quadratic probing can be implemented without expensive multiplications and divisions.

Proof

Let be the most recently computed probe ( is the original hash position) and
be the probe we are trying to compute. Then we have

H i H 0

- 1

H i

H i = H 0 + i 2 ( mod M )

(20.3)

H i = H 0 + ( i - 1 )

2

( mod M )

- 1

If we subtract these two equations, we obtain

(20.4) H i = H i + 2 i - 1 mod M ( )

- 1

Equation 20.4 tells us that we compute the new value from the previous value
H i - 1 without squaring i . Although we still have a multiplication, the multiplication is
by 2 , which is a trivially implemented bit shift on most computers. What about the mod
operation? That, too, is not really needed because the expression must be
smaller than M . Therefore, if we add it to H i - 1 , the result will be either still smaller
than M (in which case, we do not need the mod) or just a little larger than M (in which
case, we can compute the mod equivalent by subtracting M ).

H i

2 i - 1