Why does a compact open-addressed hash table usually out-run node-per-entry chaining on lookups?

## Two layouts for the same abstraction **Node-per-entry chaining.** The table is an array of bucket heads. Each occupied bucket points at a separately allocated node holding the key, the value, the cached hash and a pointer to the next node in that bucket. Collisions extend the chain. **Compact open addressing.** There is no node. Entries live directly in one flat array of slots, plus a parallel array of small per-slot metadata — commonly one byte encoding "empty", "deleted", or a handful of bits taken from the entry's hash. A collision does not allocate; it probes forward to the next candidate slot. Both give expected constant-time operations, and both degrade to linear when a hash concentrates keys. Asymptotics do not separate them. What separates them is what the processor has to wait for. ## Counting stalls in a symbol-table lookup Take the concrete workload this leaf is built around: an interpreter resolving identifiers, doing a lookup per name reference, with short keys carrying cached hashes and a very high hit rate. *Chained lookup.* Compute the index, read the bucket head — a fetch from a large array indexed pseudo-randomly, so assume it is not resident. Now dereference the pointer to reach the first node. The node was allocated separately, possibly long ago, so its address is unrelated to the bucket array and this is a second fetch — and it is *dependent*: the address could not be computed before the head arrived, so the two waits are serial and cannot overlap. If the first node's key does not match, the next node's address is only known once the first node has arrived: a third serial wait. A bucket holding three candidates costs about four serial waits. *Compact lookup.* Compute the index, read the metadata for a group of slots — one fetch pulls in many neighbouring bytes at once. Compare the hash fragment against every byte in the group; every slot whose fragment differs is rejected without reading its key. Usually exactly one candidate remains, so the entry itself is fetched and its key compared: two fetches, and the probing continues in neighbouring memory rather than jumping to unrelated addresses. The instruction counts are similar. The difference is that one design serialises waits on unrelated addresses and the other batches a rejection test into a single nearby read. ## What the compact layout costs you This is the half that separates a senior answer from an enthusiastic one. - **Deletion is not the inverse of insertion.** A probe sequence stops at an empty slot, so blanking a slot in the middle of a sequence would hide every entry inserted after it. You mark a tombstone instead, which keeps probe sequences long and must be reclaimed by a rehash, or you back-shift subsequent entries, which is only correct for some probing schemes and costs writes. Chaining just unlinks a node. - **The load factor ceiling is lower.** For linear probing, expected probes for an unsuccessful search grows with the square of `1/(1 - load)`, so the curve turns sharply upward near capacity. Grouped-metadata designs push the usable ceiling higher but still cap it well below full. A chained table degrades gracefully instead: average chain length is simply the load factor, so running it above one is unpleasant but not cliff-shaped. - **Memory is reserved, not consumed.** Slot width times capacity is paid whether slots are used or not, so wide entries at a modest load factor waste real memory. Chaining pays a per-node header and next-pointer per *element*, so it wins when entries are large or occupancy is low. The crossover depends on entry width. - **Nothing stays put.** Growth rehashes and physically moves entries, so any reference, pointer or iterator into the table is invalidated. Chained nodes can keep stable addresses across a resize, which some designs rely on. - **A degenerate bucket cannot be re-shaped.** A chained design can bound a pathologically long chain by converting that one bucket to an ordered structure with logarithmic search. Open addressing has no per-bucket container to convert; its answer to a bad distribution is a better hash. ## Where each one wins A lookup-dominated table of small keys — the symbol table, an interning table, a routing table sized once and then mostly read — is exactly the shape a compact layout was designed for. A table of large values, one whose entries are referenced from elsewhere, one that runs near or above a load factor of one, or one with heavy churn that would litter tombstones, argues for chaining. Production runtimes have made both calls deliberately: Java's hash map chains separately allocated nodes and converts an overlong bucket into an ordered structure, while Rust's default hash map and Go's maps store entries in flat groups with a byte or so of hash metadata per slot. Neither camp is wrong; they optimise for different key sizes, different growth behaviour and different guarantees about entry stability. ## How to answer at interview Lead with the stall count rather than the word "cache-friendly", because the phrase is free and the count is not. Then volunteer the costs — tombstones, load-factor ceiling, reserved width, invalidated references — and finish by naming the workload you would pick each for. A candidate who claims flat layouts are simply faster has learned a slogan; one who says "faster for small entries in a read-heavy table, and here is what I give up" has done the work.