Hash Tables in Python: Collisions, Load Factor and a Mini Build

Why does a dict with a million entries answer d[key] about as fast as one with ten? And why does a dict sometimes get slow anyway? Both answers come from the same small mechanism, and the quickest way to understand it is to build one. Our example is the software behind a parcel-locker kiosk: given a parcel code, find the locker number without scanning every locker.

From key to bucket

A hash table keeps an array of buckets. To store or find a key it computes hash(key), a large integer, and reduces it with the remainder operator to a valid slot number. The same key always lands in the same bucket, so you only ever look in one place.

key "PKG-007"
    |  hash()
    v
8341902774   (some big integer)
    |  % number_of_buckets (4)
    v
  index 2

 bucket 0 | []
 bucket 1 | [("PKG-003", 103)]
 bucket 2 | [("PKG-007", 107), ("PKG-011", 111)]
 bucket 3 | []

Two keys in bucket 2 is a collision: different keys that reduce to the same index. Collisions are normal and unavoidable, since there are far more possible keys than buckets. A table is judged by how it handles them.

Build it: separate chaining

The simplest strategy keeps a small list in every bucket and searches that list. This is called separate chaining. The LockerTable below also doubles its bucket count when the table gets too full. Save it as lockers.py; the next section imports it.

class LockerTable:
    """Maps parcel codes to locker numbers using separate chaining."""

    def __init__(self, buckets=4, max_load=0.75, hash_fn=hash):
        self.buckets = [[] for _ in range(buckets)]
        self.size = 0
        self.max_load = max_load
        self.hash_fn = hash_fn
        self.resizes = 0

    def _index(self, key):
        return self.hash_fn(key) % len(self.buckets)

    def put(self, key, value):
        chain = self.buckets[self._index(key)]
        for pair in chain:
            if pair[0] == key:          # same key: overwrite, size unchanged
                pair[1] = value
                return
        chain.append([key, value])
        self.size += 1
        if self.size / len(self.buckets) > self.max_load:
            self._grow()

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

    def _grow(self):
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        self.size = 0
        self.resizes += 1
        for chain in old:
            for k, v in chain:
                self.put(k, v)           # re-hash: bucket index depends on table length

    def longest_chain(self):
        return max(len(c) for c in self.buckets)

    def load(self):
        return self.size / len(self.buckets)


if __name__ == "__main__":
    table = LockerTable()
    for n in range(1, 21):
        table.put(f"PKG-{n:03d}", 100 + n)

    print("size:", table.size, "| buckets:", len(table.buckets), "| resizes:", table.resizes)
    print("load factor: %.2f" % table.load())
    print("PKG-007 ->", table.get("PKG-007"), "| PKG-999 ->", table.get("PKG-999", "not found"))

size: 20 | buckets: 32 | resizes: 3
load factor: 0.62
PKG-007 -> 107 | PKG-999 -> not found

Twenty parcels forced three doublings: 4 to 8 to 16 to 32 buckets. The reason _grow re-inserts every pair instead of copying chains across is subtle and worth remembering: the bucket index is hash % len(buckets), so changing the length changes where every key belongs.

Load factor: when to grow

The load factor is entries divided by buckets. At 0.62 the average chain is less than one item long; at 4.0 the average chain has four, and every lookup walks four entries. Real tables resize before chains get long, which keeps lookups O(1) on average. Resizing one big table is O(n), but because capacity doubles each time, the cost spread over all the inserts is a small constant per insert; that is why inserting is called amortized O(1).

A bad hash function defeats everything

Resizing cannot rescue you if the hash function sends keys to the same place. This script feeds the same 200 parcel codes through three hash functions. The built-in hash for strings is randomized per run, so we use deterministic functions to make the output repeatable.

import zlib

from lockers import LockerTable

keys = [f"PKG-{n:03d}" for n in range(1, 201)]


def by_length(key):
    return len(key)


def by_char_sum(key):
    return sum(ord(c) for c in key)


def by_crc(key):
    return zlib.crc32(key.encode())


for name, fn in [("len(key)", by_length), ("sum of chars", by_char_sum), ("crc32", by_crc)]:
    t = LockerTable(hash_fn=fn)
    for k in keys:
        t.put(k, 1)
    used = sum(1 for c in t.buckets if c)
    print(f"{name:13} buckets={len(t.buckets):4d} used={used:4d} longest chain={t.longest_chain():3d}")

len(key)      buckets= 512 used=   1 longest chain=200
sum of chars  buckets= 512 used=  19 longest chain= 19
crc32         buckets= 512 used= 184 longest chain=  2

Every code has length 7, so the first function puts all 200 keys in one bucket: the table grew to 512 buckets and still behaves like a single list. Summing characters is better but still clusters, because anagrams and similar strings add up to the same total. A function that mixes all the bits (here a CRC) spreads them almost evenly. Python's own string hash does this mixing for you, which is one more reason to rely on dict instead of rolling your own.

What makes a key valid

Dict keys and set members need two things: a hash that never changes during the key's lifetime, and an __eq__ consistent with that hash (equal objects must hash equally). Python enforces the first by making mutable built-ins unhashable.

# Keys must be hashable and equal keys must hash equally
seat = {("A", 12): "Ilse", ("B", 3): "Ravi"}
print(seat[("A", 12)])

try:
    bad = {["A", 12]: "Ilse"}
except TypeError as err:
    print("TypeError:", err)


class Coach:
    def __init__(self, code):
        self.code = code

    def __eq__(self, other):
        return self.code == other.code      # defined __eq__ without __hash__


try:
    {Coach("S1"): 1}
except TypeError as err:
    print("TypeError:", err)

# the 1 == 1.0 == True trap
d = {}
d[1] = "int"
d[1.0] = "float"
d[True] = "bool"
print(d)

Ilse
TypeError: unhashable type: 'list'
TypeError: unhashable type: 'Coach'
{1: 'bool'}

The last line surprises people: 1, 1.0 and True are equal and hash equally, so they are the same key, and the first key object is kept while the value is overwritten each time. For your own classes, define __hash__ together with __eq__, or use @dataclass(frozen=True), which generates both from the fields.

Common mistakes

• Using a list or dict as a key. Symptom: TypeError: unhashable type: 'list'. Convert to a tuple or frozenset.
• Defining `__eq__` and forgetting `__hash__`. Symptom: TypeError: unhashable type: 'Coach' as soon as you put the object in a set. Add __hash__ built from the same fields as __eq__.
• Mutating an object after using it as a key. Symptom: the entry exists but obj in the_set returns False, because the object now hashes to a different bucket. Make key objects immutable.
• Adding or removing keys while looping over a dict. Symptom: RuntimeError: dictionary changed size during iteration. Iterate over list(d) or build a new dict.
• Relying on string hash values. Symptom: results that change between runs. Python randomizes string hashing per process (unless PYTHONHASHSEED is set), so never store hash() output in a file or database, and never use it as an ordering.

How this shows up in real projects and interviews

In projects you will almost never write a hash table, but you will constantly choose keys: caches keyed by request parameters, de-duplication keyed by a normalised record, counters keyed by user ID. The real skill is deciding what makes two items "the same" and building a key that captures it. In interviews, the question "how does a hash map work?" expects the steps you just coded: hash, reduce to a bucket, handle collisions, resize on load. Follow-ups usually probe worst-case behaviour (all keys collide) and what happens during a resize. Applied problems such as finding two values that add up to a target, or counting frequencies, are solved by trading memory for lookup speed as shown in the Big-O lesson.