Hash tables, collisions and load factor

Hash functions map keys to integers; indexing maps those integers to buckets. Equal hashes do not imply equal keys, so equality must still be checked. Hashing is not encryption, and collisions must not destroy data.

Chaining stores a bucket collection. Open addressing searches a probe sequence using linear, quadratic or double hashing. Clearing a deleted slot as if it had never been occupied can break searches; tombstones or correct backshift deletion are needed. Load factor α=n/m affects probe costs and triggers rehashing.

With suitable distribution, bounded load and hashing assumptions, access is expected O(1), but worst-case O(n) is possible. First hashing a long string depends on key length. Consider hash-flooding for untrusted inputs; changing a stored mutable key's hash/equality can make it unreachable.

Trace collision handling by hand

With five buckets and h(k)=k mod 5, keys 2,7,12 all hash to bucket two. Chaining may need three comparisons. Linear probing can place them in slots 2,3,4. Marking slot three EMPTY after deleting seven makes a search for twelve stop early; a DELETED tombstone keeps the probe alive.

Chaining load factor α=n/m may exceed one; open addressing requires spare slots. Rehashing recomputes positions for the new capacity. Expected O(1) under distribution assumptions can coexist with O(n) worst-case collision behaviour. Hash randomisation and balanced-tree buckets provide model-specific defences.

Equality and hashing must agree: equal keys must have equal hashes. Mutating fields used in key equality can break lookup. A hash is not a unique identifier; compare keys to resolve collisions. Cryptographic hashing has different goals from dictionary hashing and is not itself a password-storage scheme.

Foundation: Trace insertion, lookup and deletion of 2,7,12. Intermediate: Include tombstones in a resizing policy. Advanced: Measure p95 latency under skew and adversarial inputs, and state the source of randomness behind an expected bound.

def chain_insert(table, key, value):
    bucket = table[key % len(table)]
    for i, (k, _) in enumerate(bucket):
        if k == key:
            bucket[i] = (key, value)
            return
    bucket.append((key, value))
table = [[] for _ in range(5)]
chain_insert(table, 7, "A")
chain_insert(table, 12, "B")
assert len(table[2]) == 2