Java Reference
In-Depth Information
FIGURE 21-6
A linear probe sequence (a) after adding an entry; (b) after
removing two entries; (c) after a search; (d) during the search
while adding an entry; (e) after an addition to a formerly
occupied location
(a)
52
53
54
55
56
Added entry
Blue
current entry
Light gray
removed entry
(b)
null
Dark gray
52
53
54
55
56
Removed entries
(c)
52
53
54
55
56
Unsuccessful search ends here
Successful search ends here
(d)
52
53
54
55
56
2. Search ends here
3. Add new entry here
1. Initial hash location
(e)
52
53
54
55
56
Most recent addition can be found faster in location
53 than if it were placed into location 54 or 56
Note:
Linear probing is apt to cause primary clustering. Each cluster is a group of
consecutive and occupied locations in the hash table. During an addition, any collision
with any location within a cluster causes the cluster to get larger.
