Why can separate chaining's per-entry overhead exceed the payload for a table of tiny values?

## The accounting nobody does Engineers reason about hash tables in operations per second and almost never in bytes per entry. For a table holding a few thousand rich objects that is fine — the structural overhead disappears next to the payload. For a table holding tens of millions of *tiny* values it inverts, and the table's footprint is dominated by the machinery rather than the data. Take a fleet of services each holding a table of sensor identifiers mapped to a four-byte reading. Count what one entry actually costs under classic chaining on a 64-bit machine: | Component | Typical bytes | |---|---| | Key | 8 (a fixed-width identifier) | | Value (the reading) | 4 | | `next` pointer | 8 | | Cached hash value | 4-8 | | Object/allocation header | 8-16 | | Alignment and size-class rounding | 0-8 | | **Node total** | **~32-48** | | Share of the bucket pointer array | 8 / load factor | The payload is four bytes. The entry costs roughly forty. **Ten times the data is structure**, and at fleet scale that is the difference between a service that fits its memory ceiling and one that does not. ## Where each byte comes from **The next pointer** is chaining's defining cost. It exists so a bucket can hold more than one entry, and it is paid on every entry whether or not that bucket ever collides. **The allocation header and rounding** are the cost of each entry being a *separately allocated object*. General-purpose allocators keep per-allocation bookkeeping and round requests up to size classes, so a small node's real footprint is larger than the sum of its fields. Millions of small allocations also fragment the heap and cost allocation time on every insert. **The cached hash** is a deliberate time-for-space trade: it lets a walk skip expensive key comparisons and lets a resize rehash without recomputing hashes. Worth it for string keys, pure overhead for a fixed-width integer key. **The bucket array** is one pointer per bucket, and a *lower* load factor makes this term worse: at `alpha = 0.5` you carry two bucket pointers per stored entry, mostly null. ## The comparison that matters Storing entries **inline in one array**, as open addressing does, deletes two of those lines outright: there is no per-entry next pointer and no per-entry allocation header, because there are no per-entry allocations at all. A slot is just key plus value plus a small amount of state. The same four-byte reading might cost 16 bytes instead of 40. That saving is not free. Inline storage must keep spare slots to stay fast, so a lower usable load factor gives back some of what was saved, and deletion becomes more delicate because a slot cannot simply be cleared without breaking later lookups. It also changes what the memory *looks like*: a chained walk follows pointers into memory the previous node did not bring with it, so each hop is a dependent access, whereas an inline scan touches consecutive addresses. For a small fixed-size payload the inline layout usually wins on both bytes and access cost; for large or variable-size values, or where simple deletion matters, chaining's per-node cost buys real properties. This is a genuine fork in the road, not a settled question — mainstream runtimes disagree about it. Java's and C++'s standard hash maps are chaining-based (the C++ container's bucket interface effectively mandates it), while Python's and Rust's are open-addressed. Same concept, different bets about which cost matters more. ## The middle path Chaining is not obliged to allocate one node per entry. A bucket can hold a small **array of entries** — several key/value pairs packed together with a single overflow pointer for the rare bucket that exceeds them. One pointer and one allocation header then amortize over several payloads, and the packed entries are scanned consecutively rather than chased. This keeps chaining's easy deletion and gentle degradation while cutting the per-entry tax substantially, and it is why real high-performance chained tables rarely look like a textbook singly linked list. ## How to raise this in an interview The move that lands is to *quantify* rather than assert. "For four-byte values, chaining costs roughly forty bytes per entry — a next pointer, an allocation header, rounding, and a share of the bucket array — so about ninety percent of the table is structure. Inline storage would cut that to around sixteen at the cost of a lower usable load factor and a harder deletion path." That answer shows you can size a data structure against a memory budget, which is the judgment the question is really testing.