Hash Tables & Sets

The problem: look up by key, instantly

You have a million user records and need to find the one whose email is ada@example.com. In a list you scan: O(n). If the list were sorted by email you could binary search: O(log n), but keeping it sorted makes inserts O(n). Arrays give O(1) access, but only by integer position.

The hash table's idea is beautifully simple: turn the key into an integer position. Compute a number from the key, reduce it to an index into an array, and store the record there. To find it again, compute the same number and look in the same place. No scanning.

The hash-function idea

A hash function maps a key of any size to a fixed-size integer, its hash. A hash table then maps that integer into one of m buckets (array slots), usually with hash % m, or hash & (m − 1) when m is a power of two (a bit mask is cheaper than division).

What makes a hash function good for a hash table?

• Deterministic: the same key always gives the same hash (within one program run).
• Consistent with equality: keys that are equal must hash equally.
• Uniform: keys spread evenly over the buckets, so no bucket gets crowded.
• Fast: it runs on every lookup.

Note what is not required: hash tables do not need cryptographic strength or uniqueness. Different keys may share a hash; that is a collision, and every hash table must handle it.

Summing character codes ignores order, so every anagram collides. A polynomial hash weighs each position differently. Python's real string hash is stronger still, as the next section explains.

hash() in Python, and PYTHONHASHSEED

The built-in hash(obj) calls obj.__hash__() and returns a 64-bit signed integer on 64-bit platforms. Some details worth knowing:

• Small integers hash to themselves: hash(42) == 42. Larger ints are reduced modulo the prime 2⁶¹ − 1 (sys.hash_info.modulus).
• hash(-1) == -2, because CPython's C API uses −1 to signal an error.
• Numbers that compare equal hash equally across types: hash(1) == hash(1.0) == hash(True). That is why {1: "a", 1.0: "b"} has only one key.
• Tuples combine the hashes of their items; lists, dicts, and sets are unhashable because they are mutable.
• str and bytes hashes are randomised per process.

Why string hashes vary between runs

If an attacker knows your hash function, they can craft thousands of keys that all land in the same bucket. A web framework that puts request parameters into a dict would then do O(n²) work per request: a hash-flooding denial-of-service attack, demonstrated against many languages in 2011. Python's defence (default since 3.3) is to hash str and bytes with SipHash, a fast keyed hash, using a random key chosen at interpreter start-up. The attacker can't predict the buckets, so they can't flood one.

The PYTHONHASHSEED environment variable controls the key: unset or random means random; an integer fixes it (and 0 disables randomisation), which is occasionally useful for reproducing a bug.

pixi run python -c "print(hash('abc'))"      # differs each run
pixi run python -c "print(hash('abc'))"
PYTHONHASHSEED=0 pixi run python -c "print(hash('abc'))"   # same every run

The __hash__ / __eq__ contract

A hash table finds a key by going to the bucket for its hash, then checking candidates with ==. For that to work, one rule must hold:

If a == b, then hash(a) == hash(b).

The reverse is not required (collisions are allowed). A second rule follows: an object's hash must not change while it is in a hash table, otherwise it sits in the bucket for its old hash and lookups look in the wrong place. In practice, that means hash only immutable state.

Python enforces part of this for you. By default, objects compare and hash by identity. If a class defines __eq__ but not __hash__, Python sets __hash__ = None, making instances unhashable, because the inherited identity hash would break the rule.

The object is still in the set, but neither its new value nor its old value finds it: the new hash points at the wrong bucket, and the old value no longer compares equal. This is why mutable built-ins are unhashable.

Collisions are inevitable

If there are more possible keys than buckets (always), some keys must share a bucket: that is the pigeonhole principle. Collisions also arrive much sooner than intuition suggests. The birthday paradox says that with just 23 people, there is a better than even chance two share a birthday out of 365. In general, with m buckets, you expect the first collision after about √(πm/2) insertions.

So a hash table's real design question is not "how do we avoid collisions?" but "how do we resolve them cheaply?" There are two families of answers.

Separate chaining vs open addressing

Deletion in open addressing: tombstones

Suppose "cat" (slot 1) and "emu" (slot 2, displaced) are stored, and you delete "cat" by emptying slot 1. A lookup of "emu" starts at slot 1, sees empty, and stops: "not found". Wrong! Probing relies on an unbroken run. The fix is a tombstone (CPython calls it a dummy): a marker meaning "something was here; keep probing." Lookups skip tombstones; inserts may reuse them; a resize discards them.

Try all three strategies in the visualizer: chaining, linear probing, and Python's perturbed probing.

Load factor and resizing

The load factor α = n / m is the number of entries divided by the number of buckets. It controls performance:

• Chaining: with a uniform hash, the average chain length is α, so an unsuccessful lookup inspects about α entries and a successful one about 1 + α/2. Chaining keeps working above α = 1, just more slowly.
• Linear probing: Knuth's classic analysis gives about ½(1 + 1/(1 − α)) probes for a successful search and ½(1 + 1/(1 − α)²) for an unsuccessful one. At α = 0.5 that is 1.5 and 2.5 probes; at α = 0.9 it is 5.5 and 50.5. Performance falls off a cliff as the table fills, because occupied slots clump into long runs (primary clustering).

So hash tables resize: when α passes a threshold (often 0.75 for chaining; CPython's dict uses 2/3), allocate a table about twice as large and rehash every entry into it, since each key's bucket depends on m. Rehashing is O(n), but geometric growth makes insertion amortized O(1), exactly the dynamic-array argument from M19.

How CPython's dict works

Since Python 3.6, CPython uses a compact dict (proposed by Raymond Hettinger). Instead of one sparse array of (hash, key, value) entries, it uses two arrays:

• a sparse indices array, the actual hash table, whose slots hold small integers: an index into the entries array, or EMPTY, or DUMMY (a tombstone). Each slot is 1, 2, 4, or 8 bytes depending on the table size, so small dicts use 1-byte indices.
• a dense entries array of (hash, key, value) records, appended in insertion order.

Benefits: memory drops sharply (the sparse part holds tiny integers instead of 24-byte entries), iteration is a tight loop over a dense array, and insertion order is preserved for free. Order preservation became a language guarantee in Python 3.7.

Lookup and perturbed probing

The table size is a power of two, so mask = size − 1 and the first slot is hash & mask, which uses only the hash's low bits. Linear probing would cluster badly for keys like consecutive integers (which hash to themselves), so CPython mixes in the higher bits as it probes:

# Simplified from Objects/dictobject.c
perturb = hash_value                      # treated as unsigned
i = hash_value & mask
while True:
    ix = indices[i]
    if ix == EMPTY:
        return NOT_FOUND                  # an empty slot ends the probe sequence
    if ix != DUMMY:
        h, k, v = entries[ix]
        if h == hash_value and (k is key or k == key):   # identity check first: fast path
            return v
    perturb >>= 5                          # PERTURB_SHIFT
    i = (i * 5 + perturb + 1) & mask

The recurrence i = 5i + 1 (mod 2ᵏ) on its own visits every slot exactly once before repeating, so the probe always finds an empty slot. Adding perturb lets every bit of the hash influence the path early on; after enough shifts perturb becomes 0 and the pure 5i + 1 sequence takes over. Note the comparison order: hash first (a cheap integer compare that rules out most non-matches), then identity, then ==.

Growth

A dict keeps its table at most 2/3 full ("usable" slots). When an insert would exceed that, it resizes to a larger power of two (based on about 3× the number of items) and rebuilds the indices, also discarding tombstones. The smallest table has 8 slots and 5 usable entries, which is why you see the size jump at the 6th key:

Sets and frozenset

A set is a hash table of keys with no values. It gives O(1) average membership, insertion, and removal, and fast set algebra. CPython's set has its own implementation tuned for membership tests: it tries a few adjacent slots (cheap, cache-friendly linear probes) before jumping with perturbation, and it does not preserve insertion order.

frozenset is the immutable, hashable version: use it as a dict key or as an element of another set.

Counter, defaultdict, and OrderedDict

from collections import Counter
c = Counter("mississippi")
c.most_common(2)          # [('i', 4), ('s', 4)]
c["z"]                    # 0, no KeyError
c.update("sip")           # add more counts
c.total()                 # sum of all counts

from collections import defaultdict
groups = defaultdict(list)
for word in ["apple", "avocado", "banana"]:
    groups[word[0]].append(word)
# {'a': ['apple', 'avocado'], 'b': ['banana']}

from collections import OrderedDict
lru = OrderedDict()
lru["a"] = 1; lru["b"] = 2; lru["c"] = 3
lru.move_to_end("a")        # a was used: now most recent
lru.popitem(last=False)     # evict least recent: ('b', 2)

Hash-based problem solving

A huge class of problems becomes O(n) once you ask: "what do I need to look up, and can I keep it in a dict or set?"

Pitfalls

• Mutable keys: lists can't be keys; convert to tuples. Custom classes must not hash mutable state.
• Defining __eq__ without __hash__ makes instances unhashable (by design).
• Mutating a dict while iterating raises RuntimeError: dictionary changed size during iteration. Iterate over list(d) if you must delete.
• Relying on hash() across runs, or on set order of strings. Use hashlib and sorted.
• 1, 1.0, and True are the same key.
• Float keys suffer from rounding: 0.1 + 0.2 is not the key 0.3. NaN never equals itself, so each NaN is a separate key.
• defaultdict reads insert keys.
• Worst case is O(n) per operation if many keys collide (bad custom __hash__, e.g. return 1).

Practice: build HashMap, then use hashing

class HashMap:
    def __init__(self, capacity=8):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self._size += 1

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def __getitem__(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

    def __setitem__(self, key, value):
        self.put(key, value)

    def __len__(self):
        return self._size

class HashMap:
    MAX_LOAD = 0.75

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

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]

    @property
    def load_factor(self):
        return self._size / len(self._buckets)

    def _resize(self, new_capacity):
        old = self._buckets
        self._buckets = [[] for _ in range(new_capacity)]
        for bucket in old:
            for k, v in bucket:
                self._bucket(k).append([k, v])

    def __setitem__(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self._size += 1
        if self.load_factor > self.MAX_LOAD:
            self._resize(2 * len(self._buckets))

    def __getitem__(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

    def __delitem__(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self._size -= 1
                return
        raise KeyError(key)

    def __contains__(self, key):
        return any(k == key for k, _ in self._bucket(key))

    def __iter__(self):
        for bucket in self._buckets:
            for k, _ in bucket:
                yield k

    def items(self):
        for bucket in self._buckets:
            for k, v in bucket:
                yield (k, v)

    def __len__(self):
        return self._size

TOMBSTONE = object()

class ProbingMap:
    def __init__(self, capacity=8):
        self._slots = [None] * capacity
        self._size = 0
        self._tombstones = 0

    def __len__(self):
        return self._size

    def _find(self, key):
        cap = len(self._slots)
        i = hash(key) % cap
        for _ in range(cap):
            slot = self._slots[i]
            if slot is None:
                return None
            if slot is not TOMBSTONE and slot[0] == key:
                return i
            i = (i + 1) % cap
        return None

    def _resize(self, new_capacity):
        live = [s for s in self._slots if s is not None and s is not TOMBSTONE]
        self._slots = [None] * new_capacity
        self._size = 0
        self._tombstones = 0
        for k, v in live:
            self._insert_new(k, v)

    def _insert_new(self, key, value):
        cap = len(self._slots)
        i = hash(key) % cap
        while self._slots[i] is not None and self._slots[i] is not TOMBSTONE:
            i = (i + 1) % cap
        if self._slots[i] is TOMBSTONE:
            self._tombstones -= 1
        self._slots[i] = (key, value)
        self._size += 1

    def put(self, key, value):
        i = self._find(key)
        if i is not None:
            self._slots[i] = (key, value)
            return
        if (self._size + self._tombstones + 1) / len(self._slots) > 2 / 3:
            self._resize(2 * len(self._slots))
        self._insert_new(key, value)

    def get(self, key, default=None):
        i = self._find(key)
        return default if i is None else self._slots[i][1]

    def delete(self, key):
        i = self._find(key)
        if i is None:
            raise KeyError(key)
        self._slots[i] = TOMBSTONE
        self._size -= 1
        self._tombstones += 1

from dataclasses import dataclass

@dataclass(frozen=True, repr=False)
class Money:
    amount: int
    currency: str

    def __post_init__(self):
        object.__setattr__(self, "currency", self.currency.upper())

    def __repr__(self):
        return f"Money({self.amount!r}, {self.currency!r})"

def two_sum(nums, target):
    seen = {}
    for j, x in enumerate(nums):
        if target - x in seen:
            return (seen[target - x], j)
        if x not in seen:
            seen[x] = j
    return None

def group_anagrams(words):
    groups = {}
    for w in words:
        groups.setdefault("".join(sorted(w)), []).append(w)
    return list(groups.values())

from collections import Counter

def dedupe(items):
    return list(dict.fromkeys(items))

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

Mini-project: a word-frequency analyzer

pixi init wordfreq
cd wordfreq
pixi add python=3.14 pytest matplotlib
pixi run python wordfreq.py book.txt --top 20

Quiz

Recap

• A hash table turns a key into an array index: hash, then reduce modulo the table size.
• Equal keys must hash equally; hashes must not change while stored. Mutable built-ins are unhashable.
• str/bytes hashes are randomised per process (SipHash, PYTHONHASHSEED); never persist hash().
• Collisions are inevitable: resolve with chaining or open addressing (with tombstones for deletion).
• Load factor drives performance; resizing geometrically keeps operations O(1) average and insertion amortized O(1).
• CPython's dict: sparse indices + dense ordered entries, perturbed probing, resize at 2/3.
• Sets are key-only hash tables; frozenset is hashable. Counter, defaultdict, and OrderedDict cover counting, grouping, and recency.
• "What do I need to look up?" turns many O(n²) problems into O(n).

Going further

• Data model: object.__hash__
• PYTHONHASHSEED and sys.hash_info
• collections: Counter, defaultdict, OrderedDict
• CPython's dictobject.c: the long comment at the top explains probing.
• PEP 412: key-sharing dictionaries
• Next: M24 Trees & Binary Search Trees, ordered structures that hash tables can't replace.