15.3. Resolving collisions¶

Since we know that perfect hash functions are not generally possible except in limited cases, we must assume that sometimes a hash function will generate the same value for two different objects.

For example, in our simple hash table example, if we need to add another value that collides with an existing entry, then how can we store it?

There are two general approaches:

Open hashing: The hash table stores data structures that each holds multiple items.
Closed hashing The keys are stored directly in the table. This requires finding an open bucket in the table for each value.

Historically, one of the most common approaches to dealing with collisions has been to use fixed size buckets, for example an array that can hold up to k (some small constant) elements. The problem with this approach is if we get more than \(k\) collisions at the same location, then we still need to fall back to some other technique.

More to Explore

General purpose hash function algorithms