HASHING - Introduction to Java Programming: Comprehensive Version - page 990

To search for an entry in the hash table, obtain the index, say k , from the hash function
for the key. Check whether hashTable[k % N] contains the entry. If not, check whether
hashTable[(k+1) % N] contains the entry, and so on, until it is found, or an empty cell is
reached.
To remove an entry from the hash table, search the entry that matches the key. If the entry
is found, place a special marker to denote that the entry is available. Each cell in the hash table
has three possible states: occupied, marked, or empty. Note that a marked cell is also available
for insertion.
Linear probing tends to cause groups of consecutive cells in the hash table to be occupied.
Each group is called a cluster . Each cluster is actually a probe sequence that you must search
when retrieving, adding, or removing an entry. As clusters grow in size, they may merge into even
larger clusters, further slowing down the search time. This is a big disadvantage of linear probing.

search entry

remove entry

cluster

Pedagogical Note
For an interactive GUI demo to see how linear probing works, go to www.cs.armstrong.edu/
liang/animation/HashingLinearProbingAnimation.html , as shown in Figure 27.3.

linear probing animation on
Companion Website

27.4.2 Quadratic Probing
Quadratic probing can avoid the clustering problem that can occur in linear probing. Linear
probing looks at the consecutive cells beginning at index k . Quadratic probing, on the other
hand, looks at the cells at indices ( k

quadratic probing

j 2 ) % N , for j

+ Ú 0, that is, k % N ,( k + 1)% N ,( k + 4)

% n ,( k + 9)% N , and so on, as shown in Figure 27.4.

F IGURE 27.3

The animation tool shows how linear probing works.