Hash Tables Under the Hood: Hashing, Collisions, and Resizing

A hash table is often summarized as a data structure with average $O(1)$ lookup. That expected bound comes from maintaining invariants while imperfect hashes map a large key space into a smaller table, collisions accumulate, entries are deleted, and capacity changes.

The central thesis is that a hash table is a policy bundle, not one algorithm. Hashing, equality, collision resolution, load-factor limits, deletion semantics, and resizing must agree. A locally reasonable choice in one layer can break another: changing a key after insertion makes it unreachable, clearing an open-addressed slot can hide later entries, and copying entries to the same indices during a resize ignores that bucket selection depends on capacity.

This article derives those interactions, compares separate chaining with open addressing, and works through a linear-probing table so its guarantees can be verified rather than assumed.

Define the Map Contract and Its Invariants #

A map stores at most one value for each logical key. Its basic operations are get, set, has, and delete, but their correctness depends on a relation between hashing and equality. If two keys are equal according to the map, they must produce the same hash value:

The reverse is not required. Different keys may hash to the same value; that is a collision, and every correct table must resolve it. Equality answers whether two stored keys represent the same mapping. Hashing only chooses where to begin looking.

Three invariants capture most of the design:

1. Every live entry is reachable by the search procedure starting from its key’s home bucket.
2. A search stops only when it has found an equal key or reached evidence that the key could not occur later.
3. After mutation or resizing, there is still at most one live entry for each logical key.

Keys therefore need stable hash and equality behavior for as long as they remain in the table. Suppose an object is hashed from its email field, inserted, and then its email changes. A lookup computes a new home bucket while the entry remains near the old one. The map has not necessarily lost the bytes, but it has lost the route to them. Immutable keys, identity hashing, or copying the hashed fields at insertion prevents this class of bug.

The advertised complexity also needs precise language. With a well-distributed hash and controlled load, lookup, insertion, and deletion take expected $O(1)$ time. Worst-case time is $O(n)$ because all keys can collide. Some runtimes randomize string hashing or replace long chains with balanced trees to make intentional collision attacks harder, but no table gets a worst-case constant-time guarantee merely by being called a hash map.

Turn a Hash into a Bucket Safely #

A hash function converts a key into a fixed-width integer. A table then reduces that integer to an index in [0, capacity). For a general capacity, mathematical modulo is the obvious reduction:

The second modulo handles languages in which % returns a negative remainder. Tables with power-of-two capacities often use hash & (capacity - 1), which is fast but exposes weak low bits. A mixing step should spread information from high bits into low bits before masking.

Good table hashes are stable for the table’s lifetime, cheap, and well distributed for the expected keys. They must include every equality field: hashing only tenantId for (tenantId, orderId) is correct but makes all orders in one tenant collide. Sequential integers may need only simple mixing, whereas attacker-controlled strings justify a keyed per-process seed. That seed blocks precomputed collision sets but makes iteration order nondeterministic between processes.

For large immutable keys, caching the mixed hash avoids recomputation during probes and resizes and can reject unequal hashes before expensive equality. Never reuse that cache after key mutation or under a different seed.

Choose Chaining or Open Addressing #

Separate chaining stores each bucket as a collection of entries. On collision, another entry joins that bucket, commonly in a linked list, compact vector, or small tree. Search computes one bucket and compares keys within it. With $n$ entries and $m$ buckets, the load factor is

Under uniform hashing, an unsuccessful chained lookup examines roughly $\alpha$ entries after reaching the bucket, while a successful lookup examines a portion of a chain. Chaining can operate above load factor 1 because a bucket holds multiple entries. It also gives simple deletion: remove the matching node without changing reachability elsewhere.

Open addressing stores entries directly in the table array. A collision triggers a probe sequence of alternative slots. Linear probing checks consecutive slots; quadratic probing changes the step by a quadratic formula; double hashing derives a step from a second hash. Every lookup must follow exactly the sequence insertion would have followed for that key.

Open addressing often wins for small entries because contiguous probes use cache lines efficiently and avoid node allocation. Chaining is attractive when stable addresses or simple deletion matter. Key distribution, equality cost, iteration requirements, and mutation mix decide the better fit.

Probe policy changes the failure shape. Linear probing suffers primary clustering: one occupied run attracts insertions whose home buckets lie anywhere near it, making the run grow. Quadratic probing reduces that effect but must be paired carefully with capacity to ensure enough slots are visited. Double hashing spreads probes more broadly, although its extra arithmetic and scattered memory accesses may cost more than a few contiguous comparisons.

Work Through a Linear-Probing Example #

Consider a table of capacity 8 with index = hash(key) & 7. We insert four keys whose already-mixed hashes are:

Insert A into slot 2. B also starts at 2, sees A, and moves to slot 3. C starts at 3, sees B, and moves to slot 4. D starts at 2 and walks through 2, 3, and 4 before occupying 5. The resulting cluster is:

index: 0  1  2  3  4  5  6  7
slot:  .  .  A  B  C  D  .  .

Looking up C must start at 3, compare with B, then compare with C at 4. It cannot stop at the first unequal key because collisions deliberately place unrelated keys on the same route. Looking up a missing key E with home index 2 examines the cluster and stops at empty slot 6. That empty slot is proof that E was never inserted along this probe sequence: insertion would have occupied it.

Displacement is the distance between an entry’s home and actual slot; probe length is the number of inspected slots. Average load alone hides a long cluster, so diagnostics should sample tail probe lengths. A lookup loops for at most capacity steps, stops at empty, skips deleted, and returns only when both stored hash and key equality match. The bound prevents an infinite loop in a full table; comparing hashes first is only an optimization.

Delete Without Breaking Reachability #

Now delete B from slot 3. Replacing it with an ordinary empty slot would produce:

index: 0  1  2  3  4  5  6  7
slot:  .  .  A  .  C  D  .  .

A later lookup for C starts at 3 and stops immediately at the new empty slot, falsely reporting absence. C and D have become unreachable. The empty marker carries historical information: it means no uninterrupted insertion path crosses this position. Deletion cannot invent that claim.

The simplest repair is a tombstone, represented by the deleted state in the code. Searches pass tombstones because a desired key may occur later. Insertions remember the first tombstone they encounter, continue probing to check whether an equal key already exists, and reuse that tombstone only if the key is absent. Stopping and inserting immediately at a tombstone can create duplicate logical keys when the existing key lies farther in the cluster.

Tombstones preserve correctness but degrade performance. They count as occupied for search and available for storage, so a table needs two counters: live entries and used slots, where used slots include tombstones. Growth policy should consider used-slot load; otherwise a table with few live entries and many tombstones appears healthy while unsuccessful searches traverse most of the array.

An alternative for linear probing is backward-shift deletion. After removing an entry, scan forward through the cluster and move entries backward when the hole lies on their legal probe path. This restores an actual empty slot and avoids tombstone accumulation, but deletion becomes more complex and can move many entries. Some high-performance designs use control bytes and group-wise probing, leading to specialized deletion rules. The invariant remains the same: every surviving entry must stay reachable from its home under the lookup algorithm.

Resize by Rehashing, Not by Copying Indices #

As load rises, collisions become more frequent. An open-addressed table must grow before it is full, because a full table has no terminating empty slot and insertion cannot succeed. A typical threshold may lie around 0.7 to 0.9, depending on probe strategy and layout. Chained tables tolerate higher loads but still resize when chains make comparison costs unacceptable.

Resizing allocates a new table and reinserts every live entry. Entries cannot simply remain at their old numeric indices. With capacity 8, hash 10 maps to 2; with capacity 16, it maps to 10. Even entries whose home index does not change may need movement because their old position resulted from collisions that unfold differently in the larger table. Reinsertion also naturally removes tombstones.

A full resize costs $O(n)$, so one set operation can be expensive even though a sequence of insertions has amortized $O(1)$ cost. If capacity doubles, the work across previous resizes forms a geometric series:

Charging a small amount of migration work to each successful insertion accounts for the occasional rebuild. The amortized bound is not a latency bound, however. A pause to move millions of entries may violate a request deadline.

Incremental resizing keeps old and new tables temporarily and migrates bounded work per operation. Search new then old, insert only into new, and mark migrated buckets so old-table lookup cannot return stale duplicates. This limits pauses at the cost of temporary memory and more states. Shrinking needs hysteresis: widely separated grow and shrink thresholds, plus a capacity floor, prevent resize thrashing around one load level.

No growth threshold is universally optimal. Linear probing becomes sharply more expensive as empty slots disappear, while chaining degrades more gradually and can tolerate a load above one. The threshold should account for probe policy, entry size, equality cost, and latency targets. A table optimized for read-heavy integer keys may safely run denser than one storing large strings under frequent deletion.

Migration also needs an ownership rule for every key. Once an old bucket is marked migrated, lookup must not trust entries left there, and deletion must remove the authoritative new-table copy. If an operation helps migrate an entry that already exists in the new table, it must merge or discard the old copy rather than create a duplicate. Completion is safe only after every old search region has an unambiguous migrated state.

Tests should force growth at probe-cluster boundaries, delete keys before and during migration, and query each key from both sides of the migration cursor. Those cases distinguish a correct two-table protocol from one that merely survives insertion-only examples.

Understand Failure Modes and Tradeoffs #

Big-O summaries conceal operational failures. Attacker-selected keys plus a predictable weak hash can produce collision attacks; seeded hashing, input limits, collision monitoring, and hardened buckets are complementary defenses. Equality mistakes are subtler: approximate floating-point equality is not transitive, and case-insensitive or normalized strings must use exactly the same transformation for hashing and equality.

Iteration order depends on capacity, seed, and mutation history. Code producing signatures, snapshots, or user-visible output must sort keys or use an ordered map rather than depend on bucket order.

Memory overhead also differs from entry count. Chaining pays for bucket heads, node metadata, allocator fragmentation, and pointers. Open addressing reserves empty capacity and may carry hashes and control bytes. Large values can make copying during resize expensive; storing references reduces copying but adds indirection and ownership concerns. Benchmark memory and lookup distributions with representative keys rather than choosing from a generic load-factor rule.

Concurrency requires a separate design. A reader racing with an in-place resize may observe partially migrated state, while two writers can claim the same empty slot. A global lock is often the correct starting point. Sharded locks, immutable snapshots, read-copy-update, or specialized concurrent tables trade simplicity for throughput. Adding atomics to the slot array without a proof of publication, deletion, and resize ordering does not create a concurrent map.

Verify the Table as a State Machine #

Example-based tests should cover empty lookup, insert, overwrite, collision, wraparound, delete, tombstone reuse, growth, and keys whose new bucket changes after resize. Use a deliberately controllable hash function in tests so collisions are guaranteed rather than hoped for. Verify both the returned values and internal invariants where the implementation permits it.

Property-based testing is especially effective. Generate random sequences of set, get, has, and delete, run them against both the custom table and a trusted reference map, and compare results after every operation. Include a tiny initial capacity to force frequent wrapping and resizing. Generate all-equal hashes to exercise the worst collision path, then varied hashes to exercise migration between buckets.

Useful structural assertions include:

• Every live slot can be found by a normal lookup of its key.
• The number of reachable live entries equals the recorded size.
• No two live entries compare equal.
• An open-addressed search always terminates within capacity probes.
• After migration, each live key exists in exactly one authoritative location.
• Resizing and tombstone cleanup preserve every key-value pair.

In production, expose capacity, live and used-slot load, resize and collision counts, and sampled probe lengths. A sustained rise in tail probes or tombstone ratio can reveal a workload or hash-quality change; raw keys should not be logged for diagnosis.

Hashing proposes a start, equality confirms identity, and collision policy defines alternative locations. Deletion preserves those search paths; resizing rebuilds them for a new capacity. Those explicit, measurable invariants are the real source of expected constant-time behavior.