Load Factor & Collisions

Anatomy of a hash map

A hash map is an array of buckets. Each bucket is either empty or holds one or more entries. The hash function h(key) takes the key, computes an integer, and maps it to a bucket index, typically h(key) % n_buckets for chaining or by some open-addressing probe sequence.

To insert: hash, find the bucket, place the entry. To look up: hash, find the bucket, compare entries until a match is found or the bucket is exhausted. To delete: hash, find the bucket, remove the entry (or mark it as a tombstone in open addressing).

Collision resolution

Two keys can hash to the same bucket. Two strategies handle this; both are O(1) on average but with very different worst cases.

Chaining

Each bucket holds a linked list (or, in modern implementations, a small array or a balanced tree above a threshold). Inserting appends to the list; looking up walks it.

• Fast when load factor stays low, most buckets have ≤1 entry.
• Tolerates load factor > 1 (more entries than buckets) gracefully, operations slow down but don't break.
• Memory overhead per entry (the linked-list pointer). Modern Java's HashMap switches to a red-black tree per bucket once the chain length exceeds 8, achieving O(log n) worst case.

Open addressing

No per-bucket lists. On collision, probe the next bucket (linear probing), the next-by-some-step (quadratic probing), or a position determined by a second hash (double hashing). Cuckoo hashing uses two hash functions and bumps existing entries on collision.

• Better cache performance, entries live in a contiguous array, no pointer chasing.
• Sensitive to load factor, performance collapses past 0.7 or so.
• Deletion needs tombstones (a "slot was used but is empty" marker) so probe sequences don't break.

Python's dict uses open addressing with random probing. C++'s std::unordered_map uses chaining. Java's HashMap is chaining with a tree fallback. The choice depends on the language's broader trade-offs.

The load factor

Load factor α = (number of entries) / (number of buckets). At α = 0.5, an open-addressing map's expected probes per lookup is ~1.5; at α = 0.7, ~3; at α = 0.9, ~10; at α → 1, the probes go to infinity. The 0.7 threshold most languages use is the empirical sweet spot, beyond it, operations slow down faster than memory savings justify.

When α exceeds the threshold, the map reallocates: typically a 2× larger bucket array, then rehash every existing entry into it. The rehash is O(n). Inserting n entries from empty triggers log₂ n rehashes that touch a total of n + n/2 + n/4 + … < 2n entries, so the average insertion cost is O(1) amortised, even though individual insertions can be O(n).

The cost of hashing

"Hash maps are O(1)" silently assumes the hash function itself is O(1). That's true for fixed-size keys (integers, fixed-length structs). It's NOT true for variable-length keys: hashing a string of length L is O(L), so a hash-map lookup keyed on long strings is O(L), not O(1).

For most applications this distinction is academic. For tight inner loops with long string keys, it's the difference between fast and slow. If you're hashing URLs in a hot loop, the hash dominates the lookup, and reducing string allocations matters more than hash-map tuning.

Adversarial keys

If an attacker can choose your keys, they can construct n keys that all hash to the same bucket. Operations that should be O(1) become O(n), and total work becomes O(n²) for n insertions. This was a real-world denial-of-service attack circa 2003.

The defence is randomised hashing: at process start, the runtime picks a secret seed; the hash function mixes the seed into the result. Adversaries can't construct collisions without knowing the seed. Python, Java, and most modern runtimes ship this by default; older systems didn't.

For application code, you usually don't need to think about this, but if you're building a server that hashes user-controlled keys and you're on an old runtime, check whether random hashing is enabled.

Implementing a hash map from scratch

Useful as an exercise; never as production code. The skeleton:

class MyHashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(16)]   # chaining; small fixed start

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

    def put(self, key, value):
        b = self._bucket(key)
        for i, (k, v) in enumerate(b):
            if k == key:
                b[i] = (key, value)
                return
        b.append((key, value))
        # Real impl: check load factor, resize if needed.

    def get(self, key):
        b = self._bucket(key)
        for k, v in b:
            if k == key:
                return v
        return -1

    def remove(self, key):
        b = self._bucket(key)
        for i, (k, v) in enumerate(b):
            if k == key:
                b.pop(i)
                return

Missing pieces from a production implementation: load-factor monitoring with resize, tombstones for open-addressing deletion, secure hash mixing for adversarial-key resistance, and a tree fallback for pathological collision chains. Each of these adds 50-200 lines of careful code; together, they're why language-standard implementations exist.

When NOT to use a hash map

• You need ordered iteration. Use a sorted map (Java's TreeMap, Python's sortedcontainers.SortedDict). O(log n) per op but ordered.
• You need range queries ("all keys between A and B"). Hash maps can't answer this; sorted maps and BSTs can.
• The keys are dense small integers. A plain array indexed directly by the integer is faster and simpler.
• You need worst-case O(1) for real-time systems. Hash-map worst case is O(n) (rehash). Use perfect hashing or pre-sized open-addressing maps.
• Memory is tight and approximate counts suffice. Count-Min Sketch gives sublinear memory at the cost of bounded error.

Where beginners go wrong

• Mutating a key after inserting. The hash is computed at insertion; mutating the key changes the hash; the map can no longer find the entry. Always use immutable keys (tuples, strings, frozensets in Python).
• Assuming iteration order is consistent. Python 3.7+ preserves insertion order in dict; but sets and other languages don't make that promise. Code that relies on iteration order is fragile.
• Storing computed hashes alongside keys. Premature optimisation that hides bugs, if the key changes (it shouldn't), the stored hash is stale.
• Using a hash map for membership when a set would do. map[key] = True instead of set.add(key) wastes memory on the value column.

What to read next

The Seen-So-Far Pattern exercises hash maps on the most common problem shape. The Trees module covers BSTs as the alternative when ordered access matters. And the Complexity Is a Contract essay applies the framework above to several other "amortised" data structures.