A hash table computes an index for each key and stores its value there — but with a fixed number of buckets and a potentially unlimited number of possible keys, it's mathematically guaranteed that two different keys will sometimes hash to the same index. That's a collision, and every real hash table implementation needs a strategy for handling it without silently losing data.

There are two dominant strategies: chaining and open addressing. They solve the same problem in fundamentally different ways, each with its own tradeoffs.

Chaining: A Linked List per Bucket

With chaining, each bucket doesn't hold a single value — it holds a small collection (typically a linked list, sometimes a dynamic array) of all the key-value pairs that happened to hash to that index. On a collision, the new pair is simply appended to that bucket's list.

# A simplified hash table using chaining
class ChainedHashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]
        self.size = size

    def _index(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing key
                return
        bucket.append((key, value))        # append on collision

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

table = ChainedHashTable()
table.put("a", 1)
table.put("b", 2)
print(table.get("a"), table.get("b"))

Output:

1 2

Lookup still involves one hash computation, then a short scan through that one bucket's list — fast as long as the lists stay small.

Open Addressing: Probing for the Next Free Slot

Open addressing takes a different approach: every bucket holds at most one entry. On a collision, the table "probes" forward — checking the next slot, and the next, and so on (with some pattern) — until it finds an empty one. The simplest version, linear probing, just checks index + 1, index + 2, etc., wrapping around the end of the array.

Lookups follow the exact same probing sequence: if the key isn't in the first slot its hash points to, keep checking the probe sequence until you either find it or hit an empty slot (which means the key isn't present).

Tradeoffs: When to Prefer Each

Chaining handles a high load factor gracefully (buckets just grow longer, performance degrades smoothly) and never "runs out" of room in a conceptual sense, but each entry carries the overhead of a linked-list node and the memory isn't contiguous, which hurts cache performance.

Open addressing keeps everything in one contiguous array, which is far more cache-friendly and memory-efficient, but it degrades faster as the table fills up (clusters of probes get longer) and deletion is trickier — you can't just empty a slot, since that would break the probe chain for later entries, so deleted slots are typically marked with a special "tombstone" value instead.

In practice, most production hash tables (including the one behind Python's own dict) use open addressing for its performance characteristics, while keeping the load factor low enough — usually by resizing — that probe sequences stay short.