Hash tables: chaining and open addressing

What this chapter covers

An array gives you O(1) access — but only by integer index. The hash table extends that superpower to any key at all: a string, a tuple, anything hashable. Run the key through a hash function to get an integer, fold it into a bucket, and you can find it again in constant time on average. The whole game is handling collisions, when two keys want the same bucket, and this chapter builds the two classic answers side by side — separate chaining and open addressing — then races both against the dict they reimplement.

A bit of history

Hashing was invented at IBM in the early 1950s. Hans Peter Luhn described the idea of hashing keys into buckets with chaining in an internal memo in 1953 — the same Luhn who invented the checksum on your credit card. Open addressing followed almost immediately: a team including Gene Amdahl worked it out in 1954 while building the assembler for the IBM 701, because the machine didn't have the memory to spare for chains and they needed everything to live in one table. So both techniques in this chapter are seventy years old and were born within a year of each other, out of the same problem — find a value by its key without scanning — and the same constraint, scarce memory. Every dictionary, database index, and cache since descends from that work.

The intuition

Imagine you want to store a value under the key "banana". You can't index an array with a string. So you make an index: feed "banana" to a hash function, which scrambles it into some integer, and take that integer modulo the number of buckets. Now you have a slot. Store the pair there; to look it up later, hash the key again and go straight to the same slot. No scanning — you compute the location.

The problem is that different keys can hash to the same bucket. That's not a rare accident; with fewer buckets than possible keys it's guaranteed. There are two ways to cope. Separate chaining keeps a little list in each bucket and appends colliders to it — when you look up a key, you scan just that one short list. Open addressing keeps everything in the table itself: if your slot is taken, you probe forward to the next free one, and to find the key later you retrace the same probe. Chaining is simpler and forgiving; open addressing is faster and more cache-friendly but fussier about staying empty enough.

Complexity: how it scales

Let $\alpha = n / m$ be the load factor — n items across m buckets. With a good hash function spreading keys evenly, separate chaining gives an expected chain length of exactly $\alpha$, so an average lookup does $O(1 + \alpha)$ work. Keep $\alpha$ below a constant (we resize at 0.75) and that's $O(1)$. Open addressing with linear probing is a little worse as the table fills — the expected number of probes for a successful search is about

which is why it needs a lower load factor (we resize at 0.5): at $\alpha = 0.9$ that's over five probes per lookup, and it explodes as $\alpha \to 1$. The worst case for either is $O(n)$ — every key colliding into one bucket — but with a decent hash and a bounded load factor that essentially never happens. The empirical chart below puts keys in and reads them all back:

All three lines are straight — linear total work, so O(1) per operation — which is the whole point: put in ten times the keys, wait ten times as long, never more.

What it's good at, what it isn't

The hash table is the workhorse of practical programming. When your access pattern is "find the value for this key," nothing beats average O(1), and the keys can be anything hashable. It's how you build a cache, an index, a set, a frequency count, a deduplicator — most of the next few chapters and half of real-world code lean on it.

What it gives up is order. A hash table scatters keys by their hash, so it has no notion of smallest, largest, next, or range — iterating one yields keys in a scrambled (or insertion) order, never sorted. If you need "all keys between X and Y" or "the smallest key," you want a tree, not a hash table. And the O(1) is an average: it rests on a good hash function and a bounded load factor.

The data, or the inputs

The face-off inserts a large set of distinct integer keys and then looks every one back up — the pure put-then-get workload where the O(1)-per-operation behaviour shows. The animation uses a tiny eight-bucket table and six hand-picked keys, three of which (3, 11, and 19) deliberately hash to the same bucket, so you can watch a collision chain form.

Build it, one function at a time

Everything starts with turning a key into a bucket index — hash, then modulo:

def _index(self, key):
    """Map a key to a bucket: hash it to an integer, fold into [0, capacity)
    with a modulo. A good hash spreads keys evenly so buckets stay balanced."""
    return hash(key) % self._cap

Put goes to the key's bucket, updates in place if the key is already there, otherwise appends — and grows the table when the load factor crosses 0.75 so chains stay short:

def put(self, key, value):
    """O(1) average: go straight to the key's bucket, update in place if the
    key is already there, else append. Grow when the load factor (items per
    bucket) crosses 0.75 so the chains never get long."""
    bucket = self._buckets[self._index(key)]
    for i, (k, _) in enumerate(bucket):
        if k == key:
            bucket[i] = (key, value)
            return
    bucket.append((key, value))
    self._n += 1
    if self._n > 0.75 * self._cap:
        self._resize(self._cap * 2)

Get is the payoff: hash to the bucket and scan only that bucket, which holds O(1) items while the load factor is bounded:

def get(self, key, default=None):
    """O(1) average: hash to the bucket and scan only that bucket. While the
    load factor is bounded the bucket holds O(1) items, so this is constant."""
    for k, v in self._buckets[self._index(key)]:
        if k == key:
            return v
    return default

Resize is the part that keeps put O(1) on average — more buckets, rehash everything, rare because we double, so it amortizes away exactly like the dynamic array:

def _resize(self, new_cap):
    """O(n): allocate more buckets and rehash every entry into them. Doubling
    makes this rare, so it amortizes away — the same argument as the dynamic
    array, and the reason average put stays O(1)."""
    old = self._buckets
    self._cap = new_cap
    self._buckets = [[] for _ in range(new_cap)]
    self._n = 0
    for bucket in old:
        for k, v in bucket:
            self.put(k, v)

Open addressing replaces the chains with probing. Instead of a list per bucket, one flat array; on a collision, walk forward to the next free slot:

def _slot(self, key):
    """Linear probing: start at hash(key); if that slot holds a different key,
    step to the next one, wrapping around, until we find the key or an empty
    slot. Every collision just walks forward in the same array."""
    i = hash(key) % self._cap
    while self._keys[i] is not self._EMPTY and self._keys[i] != key:
        i = (i + 1) % self._cap
    return i

Watch it work

Here's separate chaining filling an eight-bucket table. Each row is a bucket; each frame hashes one key and drops it in. Watch bucket 3: the keys 3, 11, and 19 all hash to it (they're all 3 mod 8), so they stack up into a chain of three while the other buckets hold one each. A lookup for 19 would hash to bucket 3 and scan that short chain — three comparisons, not a scan of the whole table. That's a collision, handled:

The complete code

Both versions in one place — flip between them. The from-scratch tab has both tables: separate chaining and open addressing. The library tab is dict, which is itself a heavily optimized open-addressing hash table written in C — the exact structure you're building, and the one you'll actually use.

"""A hash table — the structure that makes lookup by key O(1) on average.

Arrays give O(1) access by integer index. A hash table extends that to any key:
run the key through a hash function to get an integer, fold it into a bucket
index, and store it there. The catch is collisions — two keys landing in the same
bucket — and the two classic ways to handle them are the two implementations here:
separate chaining (a list per bucket) and open addressing (probe for the next
free slot). Both keep lookups O(1) as long as the table isn't too full.
"""


class HashTable:
    """Separate chaining: each bucket holds a small list of (key, value) pairs.
    Collisions extend the list; a bounded load factor keeps every list short."""

    def __init__(self, capacity=8):
        self._cap = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._n = 0

    # region: hash
    def _index(self, key):
        """Map a key to a bucket: hash it to an integer, fold into [0, capacity)
        with a modulo. A good hash spreads keys evenly so buckets stay balanced."""
        return hash(key) % self._cap
    # endregion

    # region: put
    def put(self, key, value):
        """O(1) average: go straight to the key's bucket, update in place if the
        key is already there, else append. Grow when the load factor (items per
        bucket) crosses 0.75 so the chains never get long."""
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self._n += 1
        if self._n > 0.75 * self._cap:
            self._resize(self._cap * 2)
    # endregion

    # region: get
    def get(self, key, default=None):
        """O(1) average: hash to the bucket and scan only that bucket. While the
        load factor is bounded the bucket holds O(1) items, so this is constant."""
        for k, v in self._buckets[self._index(key)]:
            if k == key:
                return v
        return default
    # endregion

    # region: delete
    def delete(self, key):
        """O(1) average: find the key in its bucket and drop it."""
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._n -= 1
                return True
        return False
    # endregion

    # region: resize
    def _resize(self, new_cap):
        """O(n): allocate more buckets and rehash every entry into them. Doubling
        makes this rare, so it amortizes away — the same argument as the dynamic
        array, and the reason average put stays O(1)."""
        old = self._buckets
        self._cap = new_cap
        self._buckets = [[] for _ in range(new_cap)]
        self._n = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)
    # endregion

    def __len__(self):
        return self._n

    def load_factor(self):
        return self._n / self._cap

    def buckets_snapshot(self):
        return [list(b) for b in self._buckets]


class OpenAddressingHashTable:
    """Open addressing: no chains — every entry lives in the table itself. On a
    collision, probe linearly to the next slot. Better cache behaviour (one array,
    no pointer-chasing) but it demands a lower load factor to stay fast."""

    _EMPTY = object()

    def __init__(self, capacity=8):
        self._cap = capacity
        self._keys = [self._EMPTY] * capacity
        self._vals = [None] * capacity
        self._n = 0

    # region: probe
    def _slot(self, key):
        """Linear probing: start at hash(key); if that slot holds a different key,
        step to the next one, wrapping around, until we find the key or an empty
        slot. Every collision just walks forward in the same array."""
        i = hash(key) % self._cap
        while self._keys[i] is not self._EMPTY and self._keys[i] != key:
            i = (i + 1) % self._cap
        return i
    # endregion

    def put(self, key, value):
        if self._n > 0.5 * self._cap:      # keep it half-empty: probing degrades fast
            self._resize(self._cap * 2)
        i = self._slot(key)
        if self._keys[i] is self._EMPTY:
            self._n += 1
        self._keys[i] = key
        self._vals[i] = value

    def get(self, key, default=None):
        i = self._slot(key)
        return self._vals[i] if self._keys[i] == key else default

    def _resize(self, new_cap):
        items = [(k, v) for k, v in zip(self._keys, self._vals) if k is not self._EMPTY]
        self._cap = new_cap
        self._keys = [self._EMPTY] * new_cap
        self._vals = [None] * new_cap
        self._n = 0
        for k, v in items:
            self.put(k, v)

    def __len__(self):
        return self._n

"""Python's `dict` is a hash table — one of the most heavily optimized in any
language. It uses open addressing (a variant called perturbation probing) with a
compact, insertion-ordered layout, all in C. Every time you write `d[key] = value`
you're using exactly the structure this chapter builds.

So the face-off is our hash table against the `dict` it reimplements, on the same
put-then-get workload.
"""


# region: dict_build
def build_dict(pairs):
    """Insert (key, value) pairs into a dict — the O(1)-average put."""
    d = {}
    for k, v in pairs:
        d[k] = v
    return d
# endregion


# region: dict_get
def get_all_dict(d, keys):
    """Look up every key — the O(1)-average get."""
    total = 0
    for k in keys:
        v = d.get(k)
        if v is not None:
            total += v
    return total
# endregion

Scratch vs library

All three are O(1) per operation, so this is a story about the constant — and the constant is large, because a hash table does real work per operation (hash, index, compare) and ours does it in Python. Putting and getting 160000 keys took our chaining table about 278 ms, our open-addressing table about 165 ms, and the dict about 18 ms. Two things are worth reading off that. First, open addressing beats chaining even in pure Python — one flat array with no per-bucket list objects means far less allocation and far friendlier cache behaviour, which is exactly why real hash tables (including dict) use open addressing. Second, the dict is another order of magnitude beyond both, because it's C doing what we're doing in interpreted bytecode. You would never ship either of ours; you build them to know what d[key] costs and why it's usually free.

Where you'll actually meet it

You meet a hash table every time you write {} or set(). It's the dict holding your objects' attributes, the index that makes a database WHERE key = ? fast, the cache in front of a slow API, the seen set that deduplicates a stream, the counter tallying word frequencies. It's the symbol table in every compiler and the routing table in every router. When a problem reduces to "have I seen this before" or "what's the value for this key," the answer is almost always a hash table, and the reason it's the right answer is the O(1) this chapter earns.

Takeaways

A hash table maps keys to buckets with a hash function, giving average $O(1)$ get, put, and delete — as long as you keep the load factor bounded, which is what the resize is for. Collisions are inevitable and handled two ways: chaining (a list per bucket, forgiving and simple) or open addressing (probe in one array, faster and cache-friendly, the choice of real implementations). The cost you pay is order: a hash table has none.

That last point sets up the rest of the tier and beyond. The next chapter looks harder at the hash function itself — the thing this chapter took for granted — because a table is only as good as the hash spreading keys across it. And when you do need order along with fast lookup, the tree chapters later give it back, at the price of O(log n) instead of O(1).