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

sequences of length 4, 5, and 6, even in a hash table that is half empty.
(Determining the expected longest probe sequence is a challenging calcu-
lation.) Primary clustering not only makes the average probe sequence
longer, but it also makes a long probe sequence more likely. The main
problem with primary clustering therefore is that performance degrades
severely for insertion at high load factors. Also, some of the longer probe
sequences typically encountered (those at the high end of the average) are
made more likely to occur.
To reduce the number of probes, we need a collision resolution scheme
that avoids primary clustering. Note, however, that, if the table is half empty,
removing the effects of primary clustering would save only half a probe on
average for an insertion or unsuccessful search and one-tenth a probe on aver-
age for a successful search. Even though we might expect to reduce the prob-
ability of getting a somewhat lengthier probe sequence, linear probing is not a
terrible strategy . Because it is so easy to implement, any method we use to
remove primary clustering must be of comparable complexity. Otherwise, we
expend too much time in saving only a fraction of a probe. One such method
is quadratic probing .

quadratic probing

20.4

Quadratic probing is a collision resolution method that eliminates the pri-
mary clustering problem of linear probing by examining certain cells away
from the original probe point. Its name is derived from the use of the for-
mula to resolve collisions. Specifically, if the hash function eval-
uates to H and a search in cell H is inconclusive, we try cells ,
, , , (employing wraparound) in sequence. This
strategy differs from the linear probing strategy of searching

Quadratic probing
examines cells 1, 4,
9, and so on, away
from the original
probe point.

Fi () = i 2

H 1 2 +

H 2 2 + H 3 2 + … H 2 +

H 1 + , H 2 + ,

H 3 + , … , Hi + .

Figure 20.7 shows the table that results when quadratic probing is used
instead of linear probing for the insertion sequence shown in Figure 20.5.
When 49 collides with 89, the first alternative attempted is one cell away.
This cell is empty, so 49 is placed there. Next, 58 collides at position 8. The
cell at position 9 (which is one away) is tried, but another collision occurs.
A vacant cell is found at the next cell tried, which is positions
away from the original hash position . Thus 58 is placed in cell 2. The same
thing happens for 9. Note that the alternative locations for items that hash
to position 8 and the alternative locations for the items that hash to posi-
tion 9 are not the same. The long probe sequence to insert 58 did not affect
the subsequent insertion of 9, which contrasts with what happened with
linear probing.

Remember that
subsequent probe
points are a qua-
dratic number of
positions from the
original probe point.

2 2 = 4