Hash Tables

An array gives you O(1) access to any element if you know the integer index. The challenge is that real-world keys — strings, tuples, objects — are not integers in [0, n). A hash function h: U → {0, 1, …, m-1} bridges this gap by mapping any key from a universe U to a slot in an array of size m.

Think of it as an address-computation scheme. When you store a value, you ask: "which slot does this key belong in?" When you retrieve it, you ask the same question and go directly there. This is only possible because h is deterministic: the same key always yields the same slot.

The array backing a hash table is called a hash table or hash array, and each slot is often called a bucket. The entire structure stores n key-value pairs in an array of m buckets. When n ≈ m, most buckets have one element; when n >> m, many buckets accumulate multiple elements (collisions), degrading performance.

Critical properties a hash function must satisfy:

1. Determinism: h(k) is always the same for the same k.
2. Speed: computing h(k) should be O(1) or O(|k|) for variable-length keys.
3. Uniformity: ideally, keys spread evenly across the m buckets, minimizing collisions.

No hash function achieves perfect uniformity for all possible inputs — that is why collision resolution is necessary.

# Conceptual skeleton — pure Python
class NaiveHashTable:
    def __init__(self, m=8):
        self.m = m
        self.buckets = [None] * m   # array of m slots

    def _hash(self, key):
        return hash(key) % self.m   # built-in hash, reduced mod m

    def put(self, key, value):
        i = self._hash(key)
        self.buckets[i] = (key, value)  # ignores collisions for now!

    def get(self, key):
        i = self._hash(key)
        entry = self.buckets[i]
        if entry and entry[0] == key:
            return entry[1]
        raise KeyError(key)

A hash function maps keys to integers. For practical use, it must be fast, deterministic, and produce outputs that look uniformly random even for structured inputs. The last property is the hardest to achieve.

Division method: h(k) = k mod m. Simple, but fragile — if keys cluster near multiples of m (e.g., all even keys with m=8), many land in the same bucket. Choosing m to be a prime far from a power of 2 helps.

Multiplication method: h(k) = ⌊m · (k·A mod 1)⌋ where A ≈ (√5 − 1)/2 ≈ 0.618 (the golden ratio). CLRS covers this; it spreads keys better than division for many key distributions.

Polynomial rolling hash (for strings): treat a string s as a polynomial in a prime base p: h(s) = (s[0]·p^(n-1) + s[1]·p^(n-2) + … + s[n-1]) mod m Common choices: p = 31 or 37 (for lowercase ASCII), m = a large prime. This is the basis of Rabin-Karp string search.

Cryptographic hash functions (MD5, SHA-256) have excellent distribution, but are far too slow for hash tables. Production tables use non-cryptographic hashes tuned for speed: MurmurHash3, xxHash, FNV-1a, SipHash (Python 3.6+, used precisely because it resists denial-of-service attacks where an adversary crafts inputs that all collide).

What does "uniform" mean rigorously? For a randomly chosen key k from U, we want Pr[h(k) = i] = 1/m for all i ∈ {0, …, m-1}. No practical function achieves this for all key distributions, but a good function approximates it for the distributions we encounter.

# Polynomial rolling hash for strings
def poly_hash(s: str, m: int, p: int = 31) -> int:
    h = 0
    for c in s:
        h = (h * p + ord(c)) % m
    return h

# FNV-1a — compact, fast, good distribution
def fnv1a_32(data: bytes) -> int:
    FNV_PRIME = 0x01000193
    OFFSET_BASIS = 0x811c9dc5
    h = OFFSET_BASIS
    for byte in data:
        h ^= byte
        h = (h * FNV_PRIME) & 0xFFFFFFFF  # keep 32 bits
    return h

Chaining is the most conceptually straightforward collision resolution strategy: each bucket holds not a single item but a linked list (or dynamic array) of all items that hash to that bucket.

Insertion: compute h(k), append (k, v) to the list at bucket h(k). O(1) amortized (assuming list append is O(1)). Lookup: compute h(k), traverse the list at bucket h(k) comparing keys. O(length of chain). Deletion: same as lookup, then remove the node.

Why does this work? If h distributes keys uniformly and we store n items in m buckets, the expected length of any chain is n/m — the load factor α = n/m. When α is bounded by a constant (say α ≤ 1), each operation takes O(1 + α) = O(1) expected time. That is the intuitive proof of the O(1) claim.

Worst case: an adversary who knows your hash function can craft n keys that all hash to the same bucket, making every operation O(n). This is why Python switched to SipHash (a keyed hash, seeded randomly at interpreter startup) — the adversary cannot predict the hash values without knowing the secret seed.

Memory layout: chaining uses extra memory for pointers. Java's HashMap traditionally uses chaining; since Java 8, long chains (>8 elements) are converted to balanced BSTs (O(log n) worst case instead of O(n)) for adversarial resilience.

class ChainingHashTable:
    def __init__(self, m=8):
        self.m = m
        self.buckets = [[] for _ in range(m)]  # list of lists
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.m

    def put(self, key, value):
        b = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[b]):
            if k == key:            # update existing key
                self.buckets[b][i] = (key, value)
                return
        self.buckets[b].append((key, value))   # new key
        self.size += 1

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

    def delete(self, key):
        b = self._hash(key)
        chain = self.buckets[b]
        for i, (k, v) in enumerate(chain):
            if k == key:
                chain.pop(i)
                self.size -= 1
                return
        raise KeyError(key)

Open addressing stores all elements inside the array itself — no auxiliary lists. When a collision occurs, we probe for another empty slot according to a predetermined sequence.

Linear probing: if slot h(k) is occupied, try h(k)+1, h(k)+2, … (mod m). Simple but suffers from primary clustering: long runs of occupied consecutive slots form, making future insertions slower.

Quadratic probing: probe h(k)+1², h(k)+2², h(k)+3², … (mod m). Reduces primary clustering, but causes secondary clustering: two keys with the same initial hash follow identical probe sequences.

Double hashing: probe h(k), h(k)+h'(k), h(k)+2h'(k), … (mod m) where h'(k) is a second hash function. When h'(k) and m are coprime (guaranteed if m is prime and 0 < h'(k) < m), the probe sequence visits every slot — this eliminates both clustering forms and is the best open addressing strategy.

Lookup with open addressing must differentiate between an empty slot (key was never here → stop search) and a deleted slot (key may have been here; continue probing). This requires a tombstone marker for deletions, which complicates the logic and can degrade performance over many deletions.

Cache behavior: because all data is in one contiguous array, open addressing has excellent cache locality — a significant practical advantage over chaining's pointer-chasing across heap allocations. This is why C++'s robin_hood::unordered_map and many high-performance tables prefer open addressing.

# Linear probing — illustrative
EMPTY, DELETED = None, object()  # sentinel values

class LinearProbingTable:
    def __init__(self, m=8):
        self.m = m
        self.slots = [EMPTY] * m
        self.size = 0

    def _probe(self, key):
        # yields slot indices in probe order
        i = hash(key) % self.m
        for _ in range(self.m):
            yield i
            i = (i + 1) % self.m

    def put(self, key, value):
        first_deleted = None
        for i in self._probe(key):
            if self.slots[i] is EMPTY:
                target = first_deleted if first_deleted is not None else i
                self.slots[target] = (key, value)
                self.size += 1
                return
            if self.slots[i] is DELETED:
                if first_deleted is None:
                    first_deleted = i
            elif self.slots[i][0] == key:   # update
                self.slots[i] = (key, value)
                return
        raise RuntimeError("Table full")

    def get(self, key):
        for i in self._probe(key):
            if self.slots[i] is EMPTY:
                raise KeyError(key)
            if self.slots[i] is not DELETED and self.slots[i][0] == key:
                return self.slots[i][1]
        raise KeyError(key)

The load factor α = n/m (number of stored items / number of buckets) is the single most important parameter governing hash table performance. Understanding why requires a brief probabilistic argument.

For chaining: Assume the Simple Uniform Hashing Assumption (SUHA) — each key is equally likely to hash to any of the m buckets, independently. Then the expected length of any chain is α. A lookup operation examines the chain at the target bucket: expected cost O(1 + α). If α ≤ c for some constant c, this is O(1).

For open addressing: The expected number of probes for a successful lookup is at most (1/α) · ln(1/(1−α)), and for an unsuccessful lookup (or insertion) it is at most 1/(1−α). As α → 1, this blows up (→ ∞); the table must be kept well below full. Typical practice: resize when α exceeds 0.5 (open addressing) or 0.75 (chaining).

The birthday paradox connection: In a table of m=365 buckets with n=23 keys, there is already a ~50% chance of a collision. Collisions are inevitable at practical load factors; what matters is that they are rare and handled cheaply.

Amortized O(1) insertion with resizing: insertion is O(1) expected when there is no resize, plus occasional O(n) resizes. With doubling (each resize doubles m), the amortized cost per insertion remains O(1) — the total cost across n insertions is O(n). This is the same argument as for dynamic arrays (e.g., Python lists).

# Load factor monitoring and resize trigger
def load_factor(self):
    return self.size / self.m

def put(self, key, value):
    self._put_internal(key, value)
    if self.load_factor() > 0.75:   # standard threshold for chaining
        self._resize(self.m * 2)

def _resize(self, new_m):
    old_buckets = self.buckets
    self.m = new_m
    self.buckets = [[] for _ in range(new_m)]
    self.size = 0
    for chain in old_buckets:       # rehash every element
        for k, v in chain:
            self._put_internal(k, v)
            self.size += 1

When the load factor exceeds a threshold, the table must resize: allocate a larger array and rehash — reinsert every existing key into the new array. This is necessary because slot assignments depend on m (via the modulo), so they change when m changes.

Why double? If we increase m by a fixed amount (say +100), resizing happens O(n) times total, and the total work is O(n²). If we double (m → 2m), resizing happens O(log n) times, and the total work is O(n) — a geometric series argument. This gives amortized O(1) per insertion.

Shrinking: to avoid wasting memory, tables may also shrink (halve m) when α falls below a lower threshold (e.g., 0.125). The thresholds must be separated (e.g., grow at 0.75, shrink at 0.25) to prevent thrashing — repeatedly adding and removing one element around the threshold.

Incremental resizing (used in Redis): to avoid a sudden O(n) pause, Redis hashes maintain two tables during resize. New writes go to the larger table; reads check both. Elements are gradually migrated from old to new table over many operations, amortizing the cost without any single large pause.

Prime vs. power-of-two sizes: powers of two make % m a single bitwise AND (& (m-1)), which is faster. However, they amplify patterns in poor hash functions (since low bits of integers often correlate with input structure). Good hash functions (MurmurHash, SipHash) mitigate this, so Python and many C++ libraries use power-of-two sizes.

// C-style illustration of doubling resize
void resize(HashTable *ht, int new_capacity) {
    Entry **new_buckets = calloc(new_capacity, sizeof(Entry*));
    for (int i = 0; i < ht->capacity; i++) {
        Entry *e = ht->buckets[i];
        while (e) {
            Entry *next = e->next;
            int new_idx = e->hash % new_capacity;  // rehash
            e->next = new_buckets[new_idx];
            new_buckets[new_idx] = e;
            e = next;
        }
    }
    free(ht->buckets);
    ht->buckets = new_buckets;
    ht->capacity = new_capacity;
}

The O(1) expected time analysis assumes Simple Uniform Hashing — that keys are random. Real keys are not random; they come from programs and users with structure and patterns. Can we guarantee good performance without assuming anything about the keys?

Universal hash families (Carter & Wegman, 1979) provide exactly this. A family H of hash functions from U to {0,…,m-1} is universal if for any two distinct keys x ≠ y: Pr_{h ∈ H}[h(x) = h(y)] ≤ 1/m where the probability is over a random choice of h from H.

If we pick h randomly from a universal family at table-creation time, then for any fixed set of keys (even adversarially chosen), the expected number of collisions for any key x is at most n/m = α. Thus expected O(1 + α) lookup holds for any key set — no SUHA needed.

A classic construction: fix a prime p ≥ |U|. For random a ∈ {1,…,p-1} and b ∈ {0,…,p-1}, define: h_{a,b}(k) = ((ak + b) mod p) mod m The family {h_{a,b}} is universal. The proof uses properties of linear functions over Z_p.

k-independent hashing: stronger guarantees (e.g., 2-independent = pairwise independent) enable tighter analysis and are used in streaming algorithms, sketches, and randomized data structures. Tabulation hashing achieves 3-independence with extraordinary speed (just a few table lookups).

This is the theoretical bedrock explaining why Python's randomly seeded SipHash and Java's HashMap give probabilistic O(1) guarantees against any realistic key set.

# Universal hash family h_{a,b}(k) = ((a*k + b) mod p) mod m
import random

def make_universal_hash(m: int, p: int = 10**9 + 7):
    """Return a random member of the universal family."""
    a = random.randint(1, p - 1)
    b = random.randint(0, p - 1)
    def h(k: int) -> int:
        return ((a * k + b) % p) % m
    return h

# Each table instantiation picks a fresh random (a, b)
h = make_universal_hash(m=16)
print(h(42), h(99), h(42))   # h(42) consistent within this instance

For a static set of n keys (known in advance and never changing), we can build a perfect hash table with O(1) worst-case (not just expected) lookup and O(n) space.

Fredman-Komlós-Szemerédi (FKS) hashing (1984) achieves this with a two-level scheme:

• Level 1: Hash n keys into m = n buckets using a universal h. By birthday-paradox counting, the total number of collisions is O(n) in expectation.
• Level 2: For each bucket i containing b_i keys, allocate a secondary table of size b_i² and choose a hash function h_i (by trying random members of a universal family) until there are zero collisions within that bucket. With quadratic space, the probability of zero collisions is ≥ 1/2 per trial, so expected O(1) trials suffice.

Lookup: apply h(k) to find the bucket, apply h_i(k) to find the exact slot — two hash evaluations, zero collisions, guaranteed O(1).

Total space: ∑ b_i² = O(n) in expectation (the sum of squares of collision counts is O(n) with a good level-1 hash).

Applications: perfect hashing is used in compilers (keyword tables for fixed languages), network routers (fixed IP rule tables), and embedded systems where lookup latency must be deterministic. Python's frozenset internally uses a form of optimized static hashing. The gperf tool generates perfect hash functions for fixed string sets (e.g., C language keywords).

# FKS two-level perfect hashing — conceptual sketch
def build_perfect_hash(keys):
    n = len(keys)
    m = n  # level-1 table size
    while True:
        h1 = make_universal_hash(m)
        # partition keys into buckets
        buckets = [[] for _ in range(m)]
        for k in keys:
            buckets[h1(k)].append(k)
        # build level-2 tables (size b_i^2, no collisions)
        level2 = []
        ok = True
        for bucket in buckets:
            b = len(bucket)
            if b == 0:
                level2.append((None, {}))
                continue
            s2 = b * b  # quadratic size guarantees collision-free
            for _ in range(50):  # try random h2
                h2 = make_universal_hash(s2)
                slots = {}
                collision = False
                for k in bucket:
                    idx = h2(k)
                    if idx in slots:
                        collision = True; break
                    slots[idx] = k
                if not collision:
                    level2.append((h2, slots))
                    break
            else:
                ok = False; break
        if ok:
            return h1, level2
        # retry level-1 if total collisions too high

Standard linear probing suffers from variance: some keys get very short probe sequences, others very long. Robin Hood hashing (Celis, 1986) reduces this variance with a simple insight: during insertion, if the key being inserted has probed more steps than the key currently occupying the slot, swap them. The displaced key then continues probing. This "steals from the rich, gives to the poor" — rich = short probe count, poor = long probe count.

Probe length (PSL) = number of slots examined from the key's home slot. Robin Hood minimizes the maximum PSL across all keys, improving worst-case lookup performance and enabling a key insight: during lookup, if the probe length of the searched key exceeds the PSL of the current slot's occupant, the key is definitely absent — no need to continue probing.

Backward shift deletion: Robin Hood tables can delete without tombstones. When a key is deleted, shift subsequent entries backward to fill the gap (as long as they are not at their home slot), maintaining the invariant. This avoids tombstone accumulation degrading performance.

Swiss Tables (Google, 2017, now in Abseil and used in CPython 3.11+ internals): store only the lower 7 bits of each key's hash in a dense metadata byte array (one byte per slot). SIMD instructions scan 16 metadata bytes in one CPU instruction, filtering candidates before comparing full keys. This achieves near-ideal cache performance and is 2–4× faster than traditional open-addressing tables in practice.

Hopscotch hashing (Herlihy et al., 2008): each slot has a neighborhood of H consecutive slots; a key always lives within its neighborhood, enabling O(1) worst-case lookup and efficient concurrent variants.

// Robin Hood insertion — C pseudocode
void rh_insert(Table *t, int key, int value) {
    int psl = 0;
    int home = hash(key) % t->m;
    int i = home;
    while (true) {
        if (t->slots[i].empty) {
            t->slots[i] = {key, value, psl};
            return;
        }
        // Robin Hood swap: steal from the rich
        if (t->slots[i].psl < psl) {
            swap(&t->slots[i], &(Entry){key, value, psl});
        }
        i = (i + 1) % t->m;
        psl++;
    }
}

Understanding real-world implementations solidifies the theory.

Python dict (CPython 3.6+): uses open addressing with a compact key-value array. The key insight since 3.6: indices into a separate compact "key-value" array are stored in the hash table slots, keeping insertion order (order-preserving dict). Uses SipHash-1-3 seeded at interpreter startup for string keys, preventing hash-collision DoS attacks. Load factor threshold: 2/3. Growth: doubles to next power of two.

Java HashMap: chaining with an array of Entry nodes. Since Java 8, chains exceeding 8 entries convert to red-black trees (O(log n) worst case). Load factor default: 0.75. Capacity always a power of two; hashCode() is supplemented by a bit-mixing step: (h = key.hashCode()) ^ (h >>> 16) to spread high bits into low bits (since slot = hash & (capacity-1) uses only low bits).

C++ std::unordered_map: standard does not mandate an implementation, but virtually all standard libraries use chaining. The reserve(n) method pre-allocates for n elements avoiding resizes. std::unordered_map famously has poor constant factors due to per-node heap allocation; absl::flat_hash_map (Swiss Tables) and robin_hood::unordered_map are commonly preferred in performance-critical C++.

Key design choices to know:

• Always override both hashCode and equals (Java) / __hash__ and __eq__ (Python) together — if two objects are equal, they must have equal hashes (but not vice versa).
• Mutable objects should not be used as hash keys if their hash-relevant fields can change; Python's list is unhashable precisely because it is mutable.
• Hash collisions with user-controlled input can be a security vulnerability (hash flooding); use randomized / keyed hashes in web-facing code.

# Python: __hash__ and __eq__ contract
class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

    def __hash__(self):
        # Must be consistent with __eq__
        # Use a tuple hash — Python handles distribution well
        return hash((self.x, self.y))

p1 = Point(1, 2)
p2 = Point(1, 2)
assert p1 == p2          # True
assert hash(p1) == hash(p2)   # Must be True
d = {p1: "origin-ish"}
print(d[p2])             # "origin-ish" — lookup by p2 finds p1's entry

Hash tables have O(1) expected time under SUHA or with universal hashing, but the worst case is O(n) per operation — all n keys land in the same bucket. For most applications this is acceptable, but for security-sensitive code, it is a real vulnerability.

Hash flooding attacks: in 2011, researchers demonstrated that web frameworks (PHP, Python, Java) could be crashed with carefully crafted HTTP POST parameters where all parameter names had the same hash. A single request could consume minutes of CPU. The fix: randomized (keyed) hash functions like SipHash.

Algorithmic complexity attacks: a similar issue for any system that accepts untrusted keys. Mitigations: (1) use randomized hashing, (2) cap chain length and fall back to a tree (Java 8), (3) rate-limit or validate inputs.

When to prefer BSTs over hash tables: if you need ordered traversal, range queries, or predictable worst-case time, a balanced BST (AVL, red-black) gives O(log n) worst-case for all operations and supports in-order iteration. C++'s std::map and Java's TreeMap are BST-backed. Hash tables give O(1) average with no ordering.

Cuckoo hashing: achieves O(1) worst-case lookup (unlike other open-addressing schemes) using two tables and two hash functions. Each key lives in one of two possible slots; insertion displaces existing keys, which then find their alternative slot (like a cuckoo bird). Lookup checks exactly two slots — always O(1) worst case. Insertion may cycle (rare); detected by bounding displacement chain length and rebuilding with new hash functions.

# Demonstrating worst-case with a bad hash function
class BadHashTable:
    """All keys hash to bucket 0 — worst case O(n) lookup."""
    def __init__(self, m=8):
        self.m = m
        self.buckets = [[] for _ in range(m)]

    def _hash(self, key):
        return 0  # catastrophically bad: all keys go to slot 0

# With n items, every lookup scans the entire list — O(n)
# This is exactly what an adversary achieves with hash flooding