1.2 Hash tables and collision strategies

Once ADTs, pointers, and basic node structures are in place, the next question is how to support dictionary-style operations efficiently. A hash table is one of the standard answers: instead of preserving sorted order, it applies a hash function to jump directly to a bucket.

That jump is powerful, but it is never perfect. The whole chapter exists to explain what the jump can guarantee, where collisions come from, and how the implementation recovers when multiple keys land in the same location.

Motivation

Start with the dictionary operations the table must support:

• insert a value under a key,
• look up the value for a key,
• delete an existing key-value entry.

So the logical object is a dictionary or symbol table. The hash table is only one implementation strategy for that ADT.

This definition already implies two different design questions:

• how keys are converted into bucket indices,
• what the implementation does when two keys map to the same index.

What a hash function is supposed to do

A good hash function should have four properties:

• it must always return a legal bucket index,
• it should reduce collisions,
• it should distribute keys reasonably evenly,
• it should be quick to compute.

The last point matters because a beautifully distributed hash rule is not very useful if every lookup spends too long computing the bucket index itself.

int Hash(char *s, int nBuckets) {
   int h = 0;
   while (*s != '\0') {
      h += *s;
      s++;
   }
   return h % nBuckets;
}

Collision is unavoidable, not exceptional

The most important conceptual shift is that collisions are not a rare bug. They are a normal consequence of sending a large key space into a fixed set of buckets.

If the bucket count is fixed and the key space is large, collisions are inevitable. So the real implementation question is not “how do we avoid every collision?” but “how do we recover from collisions without breaking dictionary correctness?”

Watch collision handling preserve dictionary correctness

The short visual below keeps the ADT contract visible while comparing the two main recovery patterns. Hashing only chooses where to start; chaining and probing explain how the table keeps different keys from being confused after a collision.

Chaining keeps colliding keys in one bucket list

Chaining handles a collision by retaining the entries in a bucket-side list.

This design fits the pointer-and-node model from the previous section very naturally.

typedef struct cellT {
   char *key;
   void *value;
   struct cellT *next;
} cellT;

Each bucket head points to the first node in its chain. Lookup therefore has two layers:

1. hash the key to choose a bucket,
2. scan only that bucket’s chain instead of the whole table.

Open addressing uses probing instead of linked chains

Open addressing keeps all entries inside the table. Instead of storing a linked list in each bucket, it keeps probing other slots when the preferred one is occupied.

Typical probing styles include:

• linear probing,
• quadratic probing,
• double hashing.

The key difference from chaining is where the extra work lives:

• chaining keeps multiple entries in a bucket-side list,
• open addressing keeps searching for another empty slot in the main table.

This means clustering and probe-sequence design become central implementation issues. Deletion needs an additional rule that preserves probe paths. This section names delete as an ADT operation without developing that separate invariant.

That is why the collision policy belongs in the conceptual explanation, not as an implementation afterthought.

Why load factor matters

Even a good hash function degrades if the table is too full.

For n stored entries and m buckets, the load factor is usually written as

For chaining, n may exceed m, so $\alpha$ may exceed 1. For open addressing, each slot contains at most one live entry, so $0 \le \alpha \le 1$; inserting a new key requires $\alpha < 1$ and a probe sequence that can actually reach an empty slot.

Theorem/Proposition

Proof sketch or proof idea

Under separate chaining, the bucket chains partition the n stored entries: every entry belongs to exactly one chain. Summing all chain lengths therefore counts every entry once and gives $\sum_j \ell_j=n$; dividing by m gives the average occupancy $\alpha$.

This is a deterministic counting identity, not by itself a constant-time lookup guarantee. An expected bound such as $O(1+\alpha)$ additionally needs a suitable hash-function or key-distribution assumption. Without that assumption, even a small load factor can coexist with one long chain.

As the table becomes more heavily loaded:

• the exact average chain occupancy is $\alpha$, although individual chain lengths depend on how keys are distributed;
• open-addressing probe sequences tend to become longer as $\alpha$ approaches 1, and probe-coverage conditions still matter;
• average-case lookup moves away from the ideal constant-time picture unless the distribution and load remain controlled.

So resizing is not just a practical optimization. It is part of protecting the performance model promised by the data structure.

Generic pointers make the ADT reusable

The following C interface uses void * values to keep the ADT independent of the concrete value type.

typedef struct hashtableCDT *hashtableADT;

hashtableADT EmptyHashtable();
void Enter(hashtableADT table, char *key, void *value);
void *Lookup(hashtableADT table, char *key);

The table does not need to know the concrete value type. It only stores the association between a key and an opaque pointer to some client-owned data.

That makes the same hashtable ADT usable for many different applications, as long as the client also knows how to interpret the returned pointer correctly.

Common mistakes

Quick checks

Exercises

Reading the implementation more closely

Read the ADT contract before examining the bucket layout. It specifies the operations that any storage strategy must implement.

That overwrite behavior is easy to miss, but it is one of the reasons the ADT is a dictionary rather than a multiset.

Why key comparison still matters after hashing

Hashing narrows the search to a bucket, but it does not finish the job. Finding the right bucket does not yet establish that the requested key is present.

If two keys hash to the same bucket, the table still has to compare the stored key with the query key. Otherwise it would not know whether the match is exact or only accidental.

Chaining is flexible because it stores collision structure separately

The simplest collision strategy here is chaining. It is easy to reason about because each bucket has its own list of entries.

This gives the implementation a useful freedom: it can add new entries at the front of the list, the back of the list, or in another consistent order. The dictionary contract does not care about that local ordering as long as lookup and overwrite behave correctly.

Open addressing keeps the search inside the table

Instead of attaching a list to each bucket, open addressing keeps searching for another slot inside the table itself.

The cost of a collision therefore moves into the probing rule.

• linear probing checks the next slot, then the next, and so on;
• quadratic probing jumps by square offsets;
• double hashing uses a second hash function to generate a step size.

Linear probing tends to create long runs of filled buckets. That effect is called primary clustering, and it degrades the performance of the table because future probes are more likely to collide with the same dense region.

Quadratic probing is one response to that problem.

For a table of size 10 with h(k) = k % 10 and second hash $s(k)=7-(k\bmod 7)$, key 23 has step $s(23)=7-(23\bmod 7)=5$. Starting at bucket 3, the probes alternate between 3 and 8 because $\gcd(5,10)=5$; if both are occupied, the search cycles without reaching other empty slots. A well-chosen second hash can spread probes better, but the table size and step rule must be designed together.

Rehashing is the cost of changing the table shape

When the bucket count changes, the reduction from a hash code to a bucket index changes too. Even if the underlying hash-code computation stays the same, every stored entry has to be placed again under the new bucket rule. That process is called rehashing.

Rehashing may be rare in a fixed-capacity implementation, but it is conceptually important because it explains why a growing hash table cannot be treated as a fixed pile of memory locations forever.

How to choose between chaining and probing

No collision strategy is universally best. The useful comparison is the set of tradeoffs each strategy makes visible.

• Chaining is easier to explain and naturally handles collisions with a linked list.
• Linear probing keeps the table compact but can form primary clustering.
• Quadratic probing reduces that clustering but needs stricter load-factor control.
• Double hashing usually distributes probes better, but it is more expensive because it depends on two hash functions.

If you are reading code, the safest question is not “Which strategy is faster in abstract?” The safer question is “Which strategy matches the table size, the expected load, and the update pattern of this program?”

Summary

When you look at a hashtable implementation in C, use this compact checklist:

1. What counts as the key, and what counts as the stored value?
2. What does Enter do if the key already exists?
3. Does lookup compare the stored key after hashing?
4. Where do collision results live: in a chain, in a probe sequence, or in both?
5. What happens when the table gets too full?

If those five answers are clear, the rest of the implementation becomes much less mysterious.

More exercises