Collision Resolution

The previous lesson showed that collisions are unavoidable: if the key space is larger than the table, at least two keys fall into the same bucket. This lesson covers what to do when they do.

There are two families of solutions, and both are widely used. The distinction comes down to a single question: is the colliding element stored inside the bucket, or at another location in the table?

Chaining

In chaining, every bucket holds a list of the elements that fall into it. The table is an array of lists; inserting means appending to the relevant list.

class ChainedTable:
    def __init__(self, bucket_count: int = 8) -> None:
        self._buckets: list[list] = [[] for _ in range(bucket_count)]
        self.comparisons = 0                    # for measurement

    def _location(self, key) -> int:
        return hash(key) % len(self._buckets)

    def put(self, key, value) -> None:
        bucket = self._buckets[self._location(key)]
        for i, (existing, _) in enumerate(bucket):
            if existing == key:
                bucket[i] = (key, value)        # existing key is updated
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self._buckets[self._location(key)]
        for existing, value in bucket:
            self.comparisons += 1
            if existing == key:
                return value
        raise KeyError(key)

    def delete(self, key) -> None:
        bucket = self._buckets[self._location(key)]
        for i, (existing, _) in enumerate(bucket):
            if existing == key:
                bucket.pop(i)                    # removing from the list is enough
                return
        raise KeyError(key)


table = ChainedTable()
for name, measurement in [("north", 12), ("south", 18), ("east", 7), ("west", 25)]:
    table.put(name, measurement)

print(table.get("east"))       # 7
table.delete("east")
print(table.get("west"))       # 25

Notice that deletion is simple: the element is removed from the list, and nothing else is affected.

The cost of chaining is the average number of elements per bucket — that is, the load factor. Search is finding the bucket (constant) plus scanning the list in the bucket ($O(\alpha)$). As long as the load factor is kept constant, average cost is constant.

In chaining, the load factor can exceed $1$: because buckets hold lists, the table never “fills up”. This flexibility allows resizing to be delayed.

Open Addressing

In open addressing, every element sits in the table’s own slots. When a collision occurs, another slot is tried according to a fixed rule; these attempts are called probing.

The plainest rule is linear probing: look at the next slot; if it is full, the one after that; wrap around to the beginning once the end of the table is reached.

EMPTY = object()       # a slot that has never been used
DELETED = object()     # a deleted slot (tombstone)

class OpenTable:
    def __init__(self, capacity: int = 8) -> None:
        self._slots: list = [EMPTY] * capacity
        self.probes = 0

    def _location(self, key) -> int:
        return hash(key) % len(self._slots)

    def put(self, key, value) -> None:
        i = self._location(key)
        while self._slots[i] is not EMPTY and self._slots[i] is not DELETED:
            if self._slots[i][0] == key:
                break                                    # update
            i = (i + 1) % len(self._slots)                # linear probing
            self.probes += 1
        self._slots[i] = (key, value)

    def get(self, key):
        i = self._location(key)
        while self._slots[i] is not EMPTY:                # search ends on seeing EMPTY
            self.probes += 1
            if self._slots[i] is not DELETED and self._slots[i][0] == key:
                return self._slots[i][1]
            i = (i + 1) % len(self._slots)
        raise KeyError(key)

    def delete(self, key) -> None:
        i = self._location(key)
        while self._slots[i] is not EMPTY:
            if self._slots[i] is not DELETED and self._slots[i][0] == key:
                self._slots[i] = DELETED                  # a tombstone is left
                return
            i = (i + 1) % len(self._slots)
        raise KeyError(key)


table = OpenTable()
for name, measurement in [("north", 12), ("south", 18), ("east", 7)]:
    table.put(name, measurement)
print(table.get("south"))      # 18
table.delete("south")
print(table.get("east"))       # 7

The Deletion Problem

In open addressing, deletion cannot be done by merely marking the slot “empty”. Because search stops upon seeing the first empty slot, a deleted slot cuts off the search path: elements further along the same chain become unreachable.

The solution is to fill the deleted slot with a separate marker — a tombstone. Search continues past a tombstone, while insertion may write into it.

The cost is accumulation: after many deletions, the table fills with tombstones and searches grow longer. Implementations rebuild the table once the tombstone ratio exceeds a threshold.

Clustering

Linear probing’s well-known weakness is primary clustering: consecutive blocks of full slots form, and every new collision extends the block. As a block grows, the number of probes for every key that lands in that region increases; the growth feeds on itself.

Two alternative rules reduce this:

• Quadratic probing: The step size is not fixed but an increasing sequence of squares. Consecutive blocks do not form; however, keys starting from the same location follow the same sequence (secondary clustering).
• Double hashing: The step size is computed from a second hash function. Every key follows a different sequence; clustering is minimized, at the cost of a second hash computation.

Linear probing has one advantage, and it is not negligible: looking at consecutive slots means staying within a cache line. The locality observation from the How Computers Work course makes linear probing competitive here against alternatives that are theoretically better.

Comparing the Two Families

Criterion	Chaining	Open addressing
Load factor limit	Can exceed $1$	Cannot exceed $1$; threshold kept lower
Memory	Node/list overhead	No extra structure, but has empty slots
Cache behavior	Weak (scattered list)	Good (contiguous slots)
Deletion	Direct	Requires a tombstone
Worst case	Long list in one bucket	Long probe traversing the table
Structure inside bucket can be changed	Yes (tree instead of list)	No

The last row opens the door to a practical security measure: if a bucket’s length exceeds a threshold, a balanced tree is used instead of a list, and the worst case becomes $O(\log n)$ instead of $O(n)$. This design has become widespread as a defense against deliberate collision attacks.

Cost Table

Structure	Average search	Worst-case search	Deletion
Chaining	$O(1 + \alpha)$	$O(n)$	$O(1 + \alpha)$
Chaining (tree bucket)	$O(1 + \alpha)$	$O(\log n)$	$O(\log n)$
Open addressing	$O\left(\frac{1}{1-\alpha}\right)$	$O(n)$	$O(1)$ with a tombstone*

* Degrades as tombstone accumulation grows.

The expression in the third row shows why cost rises sharply as the load factor approaches $1$: for $\alpha = 0.9$, about ten probes are needed on average. This is why the threshold in open addressing is kept lower.

Summary

• In chaining, colliding elements are stored in a list within the bucket; in open addressing, they are stored in other slots of the table.
• In chaining, average cost depends on the load factor, and the load factor can exceed $1$.
• In open addressing, deletion requires a tombstone; otherwise the search path is cut off.
• Linear probing produces primary clustering; quadratic probing and double hashing reduce it.
• Linear probing’s cache behavior compensates in practice for its theoretical disadvantage.
• Converting the structure inside a bucket to a tree makes the worst case logarithmic and defends against collision attacks.

Next Step

A hash table establishes a key–value mapping. Some problems do not need a value; only the question “does this element exist” is asked. The next lesson covers set structures built around this question, and a highly efficient implementation built with bit-level operations for small universes.