16.3. Resolving collisions¶
Since perfect hash functions are only practical when the complete set of keys is known in advance, a general-purpose hash table must be prepared for collisions.
Two different keys collide when they map to the same bucket index. The keys may have the same hash value, or they may have different hash values that are reduced to the same bucket by the table's bucket-count calculation. After a bucket has been selected, the table still uses an equality predicate to decide whether a stored key is the key being searched for.
For example, in our simple hash table example,
93 % 10 == 3, so inserting 93 selects bucket 3. That bucket
already contains 23. How can the table store both values?
There are two general approaches. The terminology varies across textbooks, so both names are shown here:
Common name |
Storage and collision handling |
|---|---|
Each bucket refers to a collection that can hold all keys mapped to that bucket. A linked list is a traditional choice, but other containers are possible. |
|
Entries are stored directly in the table. When the home bucket is occupied, the table probes other slots according to a probe sequence. |
Separate chaining can grow a bucket's collection as needed, while open addressing must find an available slot in the table and therefore has a capacity limit. Both strategies select candidate locations using the hash value and then compare keys for equality.
Historically, one of the most common approaches to dealing with collisions
has been to use fixed-capacity buckets, for example an array that can hold up
to k elements at each location. This is a limited form of separate
chaining, not a complete solution by itself: if more than k keys map to
the same bucket, the table must resize the bucket or fall back to another
technique.
The following pages examine these strategies in detail.