Collision Resolution: Chaining

1. What is a Hash Collision?

A hash collision occurs when two or more distinct keys produce the same hash value, meaning they map to the same index in the hash table's underlying array.

It's tempting to think that a "smarter" hash function could prevent all collisions. While better hash functions can reduce them, collisions are a mathematical certainty when you map a large (or infinite) set of possible keys to a small, fixed number of array slots.

The following video explains why collisions are not just possible, but inevitable.

The Birthday Paradox

The likelihood of collisions is often explained using an analogy called the Birthday Paradox. It asks: how many people do you need in a room for there to be a greater than 50% chance that at least two of them share a birthday?

The answer is surprisingly low: just 23 people. With only 23 "keys" (people) and 365 "slots" (birthdays), a collision is already more likely than not. This illustrates that even with a sparsely populated hash table, collisions happen frequently.

2. The Solution: Separate Chaining

Since we can't prevent collisions, we must manage them. The most common strategy is called separate chaining. The idea is simple but powerful: instead of storing just one value at each array index, we store a collection of all values that hash to that index.

Each slot in the hash table array acts as a "bucket." When a key-value pair is inserted, it's placed into the bucket corresponding to its hash index. If another key hashes to the same index, its key-value pair is simply added to the same bucket.

Typically, these buckets are implemented using linked lists, a data structure you're familiar with from Module 7. Each slot in the array holds the head of a linked list. All items that collide at that index are stored as nodes in that list.

This is why the strategy is called "separate chaining"—each bucket is a separate "chain" of nodes. It is also known as closed addressing, because a key that hashes to index i is always stored within the data structure at index i.

The following resources provide a clear walkthrough of this strategy.

3. How Chaining Works in Practice

Let's make this more concrete with a simplified Python example. Imagine our hash table is an array where each element is a list (acting as our linked list).

First, we initialize our hash table as a list of empty lists.

# Our simple hash function from the last lesson
def simple_hash(key_string, table_size):
    hash_value = 0
    for char in key_string:
        hash_value += ord(char)
    index = hash_value % table_size
    return index

TABLE_SIZE = 11



# A list of lists. Each inner list is a "bucket" or "chain".
hash_table = [[] for _ in range(TABLE_SIZE)]

print("Initial empty hash table:")
print(hash_table)

Now, let's define an insert function. It calculates the index, then simply appends the (key, value) pair to the list at that index.

def insert(table, key, value):
    """Inserts a key-value pair into the hash table using chaining."""
    index = simple_hash(key, len(table))
    



    # Before inserting, check if the key already exists to update it.
    # This prevents storing duplicate keys.
    for i, (k, v) in enumerate(table[index]):
        if k == key:
            table[index][i] = (key, value) # Update the value
            print(f"Updated key '{key}' at index {index}.")
            return




    # If key is not found, append the new pair to the chain.
    table[index].append((key, value))
    print(f"Inserted key '{key}' at index {index}.")




# --- Let's insert some data, including our colliding keys ---
insert(hash_table, "Mia", "ID-001")
insert(hash_table, "Tim", "ID-002")
insert(hash_table, "Sue", "ID-003") # Collides with "Mia"

print("\nHash table after insertions:")
for i, chain in enumerate(hash_table):
    if chain: # Only print non-empty buckets
        print(f"Index {i}: {chain}")

If you run this code, you will see that "Mia" and "Sue" both land at index 4. But instead of an error, they now coexist peacefully in the list at that position: Index 4: [('Mia', 'ID-001'), ('Sue', 'ID-003')].

What about retrieving data? The search function calculates the index and then does a simple linear search through the small list (the chain) at that index.

def search(table, key):
    """Searches for a key and returns its value."""
    index = simple_hash(key, len(table))
    chain = table[index]
    



    # Linearly search the chain for the key
    for k, v in chain:
        if k == key:
            return v
    



    # If the loop finishes, the key was not found
    return None




# --- Let's search for our keys ---
print("\n--- Searching for values ---")
print(f"Value for 'Mia': {search(hash_table, 'Mia')}")
print(f"Value for 'Sue': {search(hash_table, 'Sue')}")
print(f"Value for 'Zoe': {search(hash_table, 'Zoe')}") # A key that doesn't exist

As you can see, we can successfully retrieve the distinct values for both "Mia" and "Sue", even though they collided.

Conclusion

In this lesson, we tackled the critical problem of hash collisions. You've learned that they are an unavoidable consequence of hashing and saw how a clever strategy, separate chaining, elegantly solves the problem.

Key Takeaways:

• A collision happens when two different keys hash to the same array index.
• Collisions are mathematically inevitable when mapping a large keyspace into a fixed-size array.
• Separate Chaining resolves collisions by having each array index point to a data structure (usually a linked list) that holds all the key-value pairs for that index.
• When using chaining, an insertion involves adding an item to a list, and a search involves looking through a (hopefully short) list.

Preview of the Next Lesson:

The performance of our search function now depends on the length of the chains. If a good hash function distributes keys evenly, the chains will be very short, and operations will be fast. But what if all our keys hash to the same index? The chain becomes a long list, and our search slows down to O(n).

In the next lesson, we will formalize this by analyzing the average O(1) and worst-case O(n) time complexity of hash table operations.