Collisions: when two keys want the same slot

Collisions are guaranteed

A table with 8 slots can't give 9 keys a slot each. That is the pigeonhole principle, and it means collisions are not a sign that something went wrong: they are certain once there are more keys than slots.

They also arrive much sooner than intuition suggests. With 365 slots and keys spread at random, the chance that two of just 23 keys share a slot is better than one in two. It is the same arithmetic as the birthday paradox: each new key has to avoid every slot already taken, and those chances multiply.

So every hash table needs a rule for the second key that wants an occupied slot. There are two families of rules.

Two strategies

Chaining turns each slot into a list. Keys that land on the same slot are added to that slot's list, and a lookup walks the list comparing keys. Java's HashMap works this way. When one list grows past 8 entries in a large enough table, Java converts it into a small balanced tree, so a lookup in that slot takes logarithmic time instead of linear. C++'s std::unordered_map chains as well.

Open addressing keeps every entry in the array itself. When a key's slot is taken, the table tries other slots in a fixed order until it finds a free one. Python's dict and Rust's HashMap use open addressing. The simplest version, and the one in the trace above, is linear probing: try the next slot, then the one after it, wrapping around at the end of the array.

Linear probing, step by step

In the trace, "eve" sits in slot 4 and "bob" in slot 5. Using the string hash from the first lesson, "amy" hashes to 96,717, and 96,717 & 7 is 5, the slot that "bob" already holds. The table compares the keys, sees that "bob" is not "amy", and moves on to slot 6. Slot 6 is empty, so "amy" goes there.

A lookup follows exactly the same path. To find "amy", the table starts at slot 5, finds "bob", moves on, and finds "amy" in slot 6. To decide that a key is missing, it keeps walking until it reaches an empty slot. An empty slot is a guarantee: if the key had been inserted, it would have taken this slot or one before it, so the search can stop.

Why probing is fast

Linear probing touches neighboring slots, and neighbors in an array are neighbors in memory. A processor never fetches a single byte from main memory; it fetches a whole cache line, usually 64 bytes, which holds several slots at once. When the table moves from slot 5 to slot 6, slot 6 is almost always in the cache already, so the probe costs a few cycles instead of the hundred or more cycles that a trip to main memory takes.

Chaining doesn't get this for free. Each node in a chain is a separate allocation that can live anywhere in memory, so walking a chain can mean a cache miss at every step. That is why open addressing often wins on real hardware, even when it compares more keys.

Why probing slows down

Linear probing has one weakness: clustering. Every key that collides lands next to the run of occupied slots it collided with, which makes that run longer, which makes the next collision with it more likely. Runs merge and grow, and a lookup that lands anywhere in a long run has to walk to its end.

Donald Knuth worked out exactly how bad this gets. If a fraction α of the slots is occupied, a lookup for a missing key checks about ½(1 + 1/(1 − α)²) slots on average:

The growth is far from linear. Going from half full to 90% full makes misses about twenty times slower. That is the reason tables resize long before they are full, which is the subject of the next lesson.

Deleting needs a tombstone

Deletion is where open addressing gets subtle. Suppose you delete "bob" by simply emptying slot 5. Now look up "amy": the table starts at slot 5, finds it empty, and stops, reporting that "amy" doesn't exist, even though it is sitting in slot 6.

The usual fix is a tombstone. Instead of emptying the slot, the table marks it as deleted. Lookups treat a tombstone as "keep walking", and inserts may reuse it. Tombstones pile up over time and lengthen probe sequences, so tables clear them out whenever they resize. Some tables avoid tombstones altogether by shifting later entries back into the hole, which keeps runs compact at the cost of a more complicated delete.

The next lesson shows how tables keep that promise to stay well below full.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Collisions: when two keys want the same slot from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function two_sum_hash(nums, target):
    seen = empty_hash_map()
    for i from 0 to length(nums) - 1:
        need = target - nums[i]
        if need in seen:
            return (seen[need], i)
        seen[nums[i]] = i
    return (-1, -1)

#include <vector>
#include <unordered_map>
 
std::pair<int, int> twoSumHash(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    seen.reserve(nums.size() * 2);
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {-1, -1};
}

import java.util.*;
 
public class HashSolver {
    public static int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) return new int[]{seen.get(need), i};
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

def two_sum_hash(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return -1, -1

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.