Collisions and collision handling

What is a collision?

A collision happens when different keys are assigned to the same storage bucket. It is normal: the set of possible keys is much larger than the table’s finite set of buckets. A correct hash map must keep the entries separate and still be able to find each one.

We will use separate chaining first. Each bucket holds a list of key–value pairs. A collision adds another pair to that list. Lookup scans the selected bucket and compares keys. Updating a key changes its existing value; inserting a different key adds a new pair.

Another approach is open addressing. Each table slot holds one entry. If the first slot is occupied by a different key, insertion checks other slots according to a rule, called probing. Lookup must follow the same rule. You do not need to mix these two approaches: the visual and runnable lab use separate chaining.

How does it work?

1. Insert both colliding keys.

   10 % 8 and 18 % 8 both equal 2. Store [(10, "Maya"), (18, "Ravi")] in bucket 2. The collision changes the amount of search work, not which name belongs to which ID.

2. Find by comparing the real keys.

   To find 18, reject key 10 and then match key 18. To find 26, check the same bucket because 26 % 8 = 2, but reject both keys and report that 26 is missing.

3. Update or delete only the matching pair.

   Updating 18 keeps two entries, with a new value for 18. Deleting 10 removes the pair for 10 and leaves the pair for 18 reachable.

Work through an example

Bucket 2 begins as [(10, "Maya"), (18, "Ravi")]. Lookup 18 makes two key comparisons and returns "Ravi". Lookup 26 also visits bucket 2, but neither stored key matches, so it must not return either name.

After updating 18 to "Ravi Kumar", the bucket is [(10, "Maya"), (18, "Ravi Kumar")]. After deleting 10, it is [(18, "Ravi Kumar")]. This is why overwriting the entire bucket or clearing it on deletion would be wrong.

For comparison, linear probing could store 10 in slot 2 and 18 in slot 3. Finding 18 would check slot 2, then slot 3. If a deleted slot means “stop searching,” simply emptying slot 2 would hide key 18. A deletion marker, often called a tombstone, tells lookup to keep searching. This issue applies to that probing design; the chained lab removes a pair from its list.

Time and space complexity

If the selected chained bucket contains b pairs, searching it takes O(b + 1) time, including the bucket calculation. With well-distributed hashes and a controlled number of entries per bucket on average, expected search, update, insertion, and deletion take O(1). If all n entries collide, these operations can take O(n).

The table uses O(n + m) space for n entries and m buckets. Traversing a bucket needs O(1) extra space. A collision does not require a whole second hash map; it adds one more entry to the selected bucket in this model.

Why it works

Every stored key can still be reached using the same search path used during insertion. Different keys remain separate entries even when they share a bucket. Deletion must preserve the path to all remaining keys.

Common mistakes

• Never use a matching bucket as proof that the keys match.
• In separate chaining, deleting one pair must not delete every pair in the bucket.
• In open addressing, lookup must follow the insertion’s probing rule and distinguish never-used slots from deleted slots.

Chapter lab · Python implementation

The code below builds the same teaching table shown above: eight buckets, integer keys, and a list of pairs in each bucket. make_table creates the buckets; put inserts or updates; get finds a value; remove deletes one pair; resize moves pairs into a new table. This is separate chaining, one possible hash-table implementation. Its simple key % capacity rule makes collisions visible; Python’s real dict uses its own hashing and storage rules. This small table does not resize automatically. Run the assertions to see that two colliding keys stay separate and that updates do not create duplicates. The final two functions apply Python dictionaries to Two Sum and frequency counting.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def make_table(capacity=8):
    if capacity <= 0:
        raise ValueError("capacity must be positive")
    return [[] for _ in range(capacity)]


def put(table, key, value):
    bucket = table[key % len(table)]
    for position, (stored_key, stored_value) in enumerate(bucket):
        if stored_key == key:
            bucket[position] = (key, value)  # Update this key.
            return
    bucket.append((key, value))  # A new key, even if its bucket is used.


def get(table, key):
    bucket = table[key % len(table)]
    for stored_key, value in bucket:
        if stored_key == key:
            return value
    raise KeyError(key)  # No matching key in this bucket.


def remove(table, key):
    bucket = table[key % len(table)]
    for position, (stored_key, value) in enumerate(bucket):
        if stored_key == key:
            bucket.pop(position)
            return value
    raise KeyError(key)


def resize(table, capacity):
    new_table = make_table(capacity)
    for bucket in table:
        for key, value in bucket:
            # Existing keys are unique, so no duplicate-key scan is needed.
            new_table[key % capacity].append((key, value))
    return new_table


def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        needed = target - value
        if needed in seen:
            return seen[needed], index
        seen[value] = index
    return None


def count_values(values):
    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

table = make_table()
put(table, 10, "Maya")
put(table, 18, "Ravi")
assert table[2] == [(10, "Maya"), (18, "Ravi")]
assert get(table, 10) == "Maya"
assert get(table, 18) == "Ravi"

put(table, 18, "Ravi Kumar")
assert get(table, 18) == "Ravi Kumar"
assert sum(len(bucket) for bucket in table) == 2

larger = resize(table, 16)
assert larger[10] == [(10, "Maya")]
assert larger[2] == [(18, "Ravi Kumar")]
assert get(larger, 10) == "Maya"
assert get(larger, 18) == "Ravi Kumar"
assert remove(table, 10) == "Maya"
assert get(table, 18) == "Ravi Kumar"
assert table[2] == [(18, "Ravi Kumar")]

try:
    get(table, 26)  # Same bucket, but this key was never inserted.
    raise AssertionError("missing keys must not return another value")
except KeyError:
    pass

try:
    remove(table, 10)  # Already removed.
    raise AssertionError("a missing key cannot be removed")
except KeyError:
    pass

try:
    make_table(0)
    raise AssertionError("zero buckets cannot hold a table")
except ValueError:
    pass

assert two_sum([2, 7, 11, 15], 9) == (0, 1)
assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([3], 6) is None
assert count_values([1, 2, 1]) == {1: 2, 2: 1}
assert count_values([]) == {}