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

figure 20.7
A quadratic probing
hash table after each
insertion (note that
the table size was
poorly chosen
because it is not a
prime number).

hash ( 89, 10 ) = 9
hash ( 18, 10 ) = 8
hash ( 49, 10 ) = 9
hash ( 58, 10 ) = 8
hash ( 9, 10 ) = 9

After insert 89 After insert 18 After insert 49 After insert 58 After insert 9

0 49 49 49

1

2 58 58

3 9

4

5

6

7

8 18 18 18 18

9 89 89 89 89 89

We need to consider a few details before we write code.

In linear probing, each probe tries a different cell. Does quadratic
probing guarantee that, when a cell is tried, we have not already tried
it during the course of the current access? Does quadratic probing
guarantee that, when we are inserting X and the table is not full, X
will be inserted?

n

Linear probing is easily implemented. Quadratic probing appears to
require multiplication and mod operations. Does this apparent added
complexity make quadratic probing impractical?

n

If the table size is
prime and the load
factor is no larger
than 0.5, all probes
will be to different
locations and an
item can always be
inserted.

What happens (in both linear probing and quadratic probing) if the
load factor gets too high? Can we dynamically expand the table, as is
typically done with other array-based data structures?

n

Fortunately, the news is relatively good on all cases. If the table size is
prime and the load factor never exceeds 0.5, we can always place a new
item X and no cell is probed twice during an access. However, for these
guarantees to hold, we need to ensure that the table size is a prime number.
We prove this case in Theorem 20.4. For completeness, Figure 20.8 shows a