Hash Tables: Collisions, Load Factor, and Swiss Tables

Imagine you want to look up a user by email in one step. An array gives you that already: users[i] is a single memory access, no search. The catch is that arrays are indexed by small integers, and your key is a string.

A hash table is the trick that bridges the two. A hash function turns any key into an integer, and you reduce that integer into a valid slot index:

slot = hash(key) % len(table)

Now table[slot] is one access again. The entire subject of hash tables is what happens when two different keys land on the same slot, because with a finite table that is not a rare accident. It is guaranteed.

If you have more possible keys than slots, some keys must share a slot. That is the pigeonhole principle, and it applies no matter how good your hash function is.

What is less obvious is how quickly collisions arrive. The birthday problem says that among 23 randomly chosen people, there is roughly a 50% chance two share a birthday, despite there being 365 days. The same arithmetic governs hash tables: collisions appear when the number of keys is near the square root of the number of slots, not when the table is nearly full.

So a hash table is never "an array with no collisions". It is an array plus a collision strategy, and that strategy is what you are really choosing when you pick an implementation.

Chaining makes each slot a container. A collision appends to the list hanging off that slot, so the array holds pointers and the entries live elsewhere on the heap.

Open addressing keeps everything inside the array. If slot 3 is taken, you probe onward by a rule, linear probing tries 4, then 5, and store the entry in the first free slot you find.

The consequence is memory layout. Chaining follows a pointer per lookup, which can be a cache miss. Open addressing walks neighbouring slots that are usually on the same cache line. That single difference explains most of the performance gap between real implementations.

Load factor is the ratio of stored entries to slots. Everything about hash table performance is a function of it.

For chaining, the average chain length is exactly the load factor, so a table at 0.75 has chains averaging under one link and lookups stay near constant. For open addressing the picture is harsher: as the table approaches full, probe sequences lengthen sharply, because each insertion makes the remaining gaps rarer and further apart.

This is why implementations resize. When the load factor crosses a threshold, the table allocates a larger array and reinserts every entry. Java's HashMap uses a default load factor of 0.75, chosen as a compromise between wasted space and collision cost.

Rehashing every entry sounds ruinous. A single insertion that triggers a resize touches every element already stored, so its cost is proportional to the table size.

The rescue is that this happens rarely, and the standard analysis is amortised cost. If you double capacity each time, then inserting n items triggers resizes at 1, 2, 4, 8 and so on. The total copying work is bounded by roughly 2n, so the cost per insertion averages out to a constant even though individual insertions vary wildly.

Doubling is what makes this work. Growing by a fixed amount instead, say 100 slots at a time, would make the total copying quadratic. The intro-to-big-o lesson covers the notation; the point here is that a rare expensive operation can still be cheap on average.

A hash table degrades to a linked list if every key collides. Normally that needs bad luck, but if an attacker can choose the keys and knows your hash function, they can produce collisions deliberately and turn every lookup linear. Sending such keys as form fields or JSON was a practical denial-of-service technique against web frameworks.

Two defences are now standard. The first is a randomly seeded hash, so the mapping from key to slot differs per process and cannot be precomputed. The second is a fallback structure: OpenJDK's HashMap converts a bucket into a red-black tree once it holds 8 entries, provided the table has at least 64 buckets, so a maximally attacked bucket costs logarithmic time rather than linear.

Note this is not cryptographic hashing. A table hash optimises for speed and spread, not for being infeasible to invert.

Modern open-addressed tables attack the probing cost directly. Google's Abseil Swiss tables, described in the project's design notes, split the table into a small array of control bytes stored separately from the keys and values.

Each control byte encodes whether its slot is empty and a short fingerprint taken from the hash. Control bytes are laid out contiguously in groups of 16, which is exactly one SIMD register. A lookup loads 16 control bytes, compares all of them against the incoming fingerprint in a handful of SSE instructions, and gets back a bitmask of candidate slots.

The effect is that most probes are rejected without ever touching the keys, so a deep probe chain costs far less than its length suggests. Rust's standard HashMap is built on this design via hashbrown, and Go adopted Swiss tables for its built-in maps in Go 1.24.

Chaining deletes cleanly: unlink the node and the structure is unchanged.

Open addressing cannot. Suppose key A hashed to slot 3, collided, and landed in slot 4. If you delete whatever sits in slot 3 and mark it empty, a later lookup for A probes slot 3, sees empty, and concludes A is absent, even though it is sitting in slot 4. The probe chain has been cut.

The standard fix is a tombstone: mark the slot deleted rather than empty. Probes treat a tombstone as occupied and keep walking; insertions may reuse it. The cost is that tombstones accumulate and lengthen probe chains, so a table with heavy churn must periodically rehash to clear them out. This is a real operational gotcha: a table that only ever grows behaves very differently from one with a delete-heavy workload.

The constant-time lookup comes at a price: a hash destroys order. Two keys that are adjacent in sorted order land in unrelated slots, which rules out a whole class of queries.

You cannot ask a hash table for the smallest key, for the keys between two bounds, or for the next key after this one, without scanning everything. Iteration order is arbitrary and, with randomised seeding, may differ between runs.

When the workload needs any row from the lower half of that table, you want the structure in the next lesson.

In almost every language the built-in map is a well-tuned hash table, and you should use it. The decisions that remain are these.

Reserve capacity when you know the size. Building a table of a million entries from empty triggers about twenty resizes; presizing avoids all of them.

Make your keys cheap to hash and compare. A key that hashes slowly turns every operation into that cost, and a hash that ignores part of the key clusters entries into a few slots.

Keep hash and equality consistent. If two objects compare equal, they must hash equal, or lookups fail unpredictably. Mutating a key after insertion breaks the same invariant, because the entry is now filed under a hash that no longer matches.