Collision Handling: Chaining

In our exploration of hash tables, we've encountered a remarkable promise: O(1) average-time access to any element. We've learned how hash functions transform arbitrary keys into array indices, seemingly giving us instant lookup capabilities. But there's a fundamental problem lurking beneath this elegant abstraction—a problem that every hash table implementation must confront.

What happens when two different keys produce the same hash index?

This isn't a rare edge case or a sign of a poorly designed hash function. It's a mathematical certainty that will occur in any real-world hash table. Understanding why collisions happen, how to detect them, and how to handle them gracefully is essential knowledge for any engineer working with hash-based data structures.

Let's set the stage with a concrete example. Imagine we have a hash table with 10 slots (indices 0-9) and a simple hash function that uses the modulo operation:

hash(key) = key % 10

Now, let's insert some integer keys:

The problem is now clear. When we attempt to insert key 35, our hash function computes the index as 5—the same index already occupied by key 15. Both keys are distinct and valid, yet they're competing for the same slot.

This is a hash collision: two or more distinct keys mapping to the same index in the hash table's underlying array.

Why can't we just make the hash table bigger?

This is a natural first instinct—if collisions happen because we're cramming keys into limited slots, why not allocate more slots? While this helps reduce collision frequency, it can never eliminate collisions entirely for several reasons:

1. Memory is finite: A hash table storing strings can't have 2^64 slots for every possible string hash.
2. Key space is often infinite: Consider all possible strings, or all possible URLs, or all possible file paths.
3. Even with more slots, collisions still occur: The mathematics guarantee it, as we'll see with the pigeonhole principle.

The inevitability of hash collisions is rooted in a simple but profound mathematical principle: the Pigeonhole Principle.

If you have more pigeons than pigeonholes, and every pigeon must be placed in a hole, then at least one hole must contain more than one pigeon.

In the context of hash tables:

• Pigeons = Keys to be stored
• Pigeonholes = Available array slots (indices)

Applying the Pigeonhole Principle to Hash Tables:

Consider these realistic scenarios:

The Key Insight:

The key space (all possible keys you might want to store) is almost always vastly larger than any practical hash table size. When you hash a string, you're reducing potentially gigabytes of possible inputs down to a few billion output values (for a 32-bit hash) or a few quintillion (for a 64-bit hash). Either way, you're mapping a larger space to a smaller space.

This compression is what makes hash tables useful (constant-time access regardless of input size), but it's also what makes collisions unavoidable.

The pigeonhole principle tells us collisions are inevitable when we have more keys than slots. But here's what surprises many engineers: collisions occur with high probability long before you've filled half the table.

This phenomenon is illustrated by the famous Birthday Paradox:

In a room of just 23 people, there's a greater than 50% chance that two people share a birthday.

With 365 possible birthdays and only 23 people (far less than half of 365), why is a collision so likely? The answer reveals something crucial about how collisions accumulate in hash tables.

The Mathematics of Birthday Collisions:

The probability that 23 people all have different birthdays is:

P(no collision) = 365/365 × 364/365 × 363/365 × ... × 343/365
                ≈ 0.493

Therefore:

P(at least one collision) = 1 - 0.493 ≈ 0.507 (50.7%)

Each new person reduces the pool of "safe" birthdays, and these reductions compound multiplicatively.

The Implication for Hash Table Design:

This mathematical reality has profound implications:

1. You cannot rely on 'probably won't collide': Even very sparse hash tables will experience collisions.
2. Collision handling is not optional: Every production hash table implementation must handle collisions from day one.
3. Good hash functions help but don't solve the problem: Even a perfectly uniform hash function produces birthday-paradox collision rates.
4. Testing with small data sets is dangerous: Your test with 100 items may work fine, but the production system with 100,000 items will behave very differently.

Let's trace through exactly what happens when a collision occurs, step by step. We'll use a hash table with 8 slots, storing key-value pairs where keys are strings and values are integers.

Step 1: Insert ("apple", 100)

Assume our hash function computes hash("apple") % 8 = 3.

The table now looks like:

Step 2: Insert ("banana", 200)

hash("banana") % 8 = 6. No collision, insertion succeeds:

Step 3: Insert ("cherry", 300)

hash("cherry") % 8 = 3. COLLISION! Index 3 is already occupied by "apple".

The Collision Creates a Fundamental Problem:

Without collision handling:

• Insert fails: "cherry" cannot be stored
• Data loss occurs: We either lose "cherry" or overwrite "apple"
• Lookup becomes ambiguous: If we find something at index 3, is it "apple" or "cherry"?

With proper collision handling (which we'll explore in detail with chaining):

• Both "apple" and "cherry" are stored
• Both can be looked up correctly
• No data loss occurs
• Performance remains acceptable

Before we can handle collisions, we must first detect them. Collision detection is straightforward but essential—we check whether the target slot is already occupied before inserting.

Here's how collision detection works in a basic hash table implementation:

The Collision Detection Algorithm:

1. Compute the hash index for the new key
2. Check if the slot at that index is occupied
3. If occupied, compare the existing key with the new key:
   • Same key: Update the value (not a collision)
   • Different key: Collision detected - resolve it
4. If not occupied, insert directly

This simple check is the foundation upon which all collision resolution strategies build.

Not all collisions are created equal. As we'll see when exploring collision resolution strategies, it's useful to distinguish between two types of collisions:

Why This Distinction Matters:

Primary collisions are unavoidable—they're inherent to hashing. Secondary collisions are a consequence of how we handle collisions and can be influenced by our choice of resolution strategy.

The chaining approach (which we'll explore in depth) eliminates secondary collisions entirely because each slot contains a collection of entries. Open addressing, by contrast, must deal with both types.

Understanding this distinction helps explain why different collision resolution strategies have different performance characteristics, especially as the table fills up.

Collisions don't just complicate insertion—they affect every hash table operation. Let's examine the impact on each core operation:

The Lookup Challenge:

Lookup becomes particularly interesting with collisions. Consider looking up "cherry" when it shares index 3 with "apple":

The Delete Challenge:

Deletion with collisions is even trickier, especially in open addressing schemes (which we'll cover in a later module). With chaining, deletion is relatively straightforward—find the entry in the chain and remove it. With open addressing, deletion requires special "tombstone" markers to avoid breaking probe sequences.

This complexity is one reason many engineers prefer chaining: it keeps the mental model simpler.

We've now thoroughly explored the collision problem—the fundamental challenge that every hash table must address. Let's consolidate the key insights:

What's Next:

Now that we understand why collisions happen and what problems they create, we're ready to explore the most common solution: chaining with linked lists. In the next page, we'll see how chaining elegantly resolves collisions by storing multiple entries at each slot, maintaining O(1) average-case performance while handling any number of collisions gracefully.