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

approach is important if space is tight and it is not possible just to declare a
huge hash table.
This completes the discussion of basic searching algorithms. In Chapter 21
we examine the binary heap, which implements the priority queue and thus
supports efficient access of the minimum item in a collection of items.
key concepts
collision The result when two or more items in a hash table hash out to the
same position. This problem is unavoidable because there are more items
than positions. (775)
double hashing A hashing technique that does not suffer from secondary cluster-
ing. A second hash function is used to drive the collision resolution. (797)
hash function A function that converts the item into an integer suitable to
index an array where the item is stored. If the hash function were one to
one, we could access the item by its array index. Since the hash function
is not one to one, several items will collide at the same index. (774)
hash table A table used to implement a dictionary in constant time per
operation. (774)
hashing The implementation of hash tables to perform insertions, deletions,
and finds. (773)
linear probing A way to avoid collisions by sequentially scanning an array
until an empty cell is found. (779)
load factor The number of elements in a hash table divided by the size of the
hash table array, or the fraction of the table that is full. In a probing hash
table, the load factor ranges from 0 (empty) to 1 (full). In separate chain-
ing hashing, it can be greater than 1. (780)
lazy deletion The technique of marking elements as deleted instead of physically
removing them from a hash table. It is required in probing hash tables. (780)
primary clustering Large clusters of occupied cells form during linear probing,
making insertions in the cluster expensive (and then the insertion makes
the cluster even larger) and affecting performance. (781)
quadratic probing A collision resolution method that examines cells 1, 4, 9,
and so on, away from the original probe point. (784)
secondary clustering Clustering that occurs when elements that hash to the
same position probe the same alternative cells. It is a minor theoretical
blemish. (797)
separate chaining A space-efficient alternative to quadratic probing in which
an array of linked lists is maintained. It is less sensitive to high load fac-
tors and exhibits some of the trade-offs considered in the array versus
linked list stack implementations. (797)