A memory-pressured fleet wants its hash tables to grow at 0.95 occupancy instead of 0.75 — how do you decide?
answer
- Both columns of the ledger need numbers
- Slots per entry at each threshold
- Ask what fraction of memory the buckets hold
- The cost is not uniform across tables
- Watch the tail, not the mean
basics
~20 sQuantify both sides first. The change removes only about a fifth of the bucket slots — often a small share of total memory — while the cost lands on every lookup and hits open-addressed tables hardest. Decide per table, not fleet-wide.
solid answer
~50 sI would treat it as a trade with an unbalanced ledger and insist on numbers for both columns. On the memory side, slots needed go from `n/0.75` to `n/0.95` — about 21% fewer — and a slot is typically a reference while an entry carries key, value and overhead, so the fleet-level saving is often single-digit percent. On the cost side, the penalty is paid on every lookup and is not uniform: a chained table's expected chain moves from 0.75 to 0.95, barely noticeable, while an open-addressed table near 0.95 sits on the steep part of its probe curve, and key skew or weak hashing amplifies the tail. So profile where the memory actually is, group the tables by collision scheme and delete rate, change only the safe group, and validate p99 against production key distributions.
go deeper
Understand the shape of the trade: a fuller table needs fewer buckets but makes each lookup do more work. Knowing that the growth threshold is a tunable policy, not a fixed law, is what matters here.
Be able to compute both sides. Slots per entry go from about 1.33 to about 1.05, roughly a fifth fewer, and expected work per lookup rises — mildly under chaining, sharply under open addressing near saturation.
Demonstrate that you would validate with production key distributions and tail percentiles rather than averages, and that you would separate the tables by collision scheme, delete rate and key provenance before changing anything.
Own the decision unit and the aftermath. A global default is a contract with every future table and every engineer who never read this thread; argue for a conservative default with measured, owned overrides, a monitored tail metric and a written rollback trigger.
## Why this is a judgment call and not a lookup The proposal has the shape of a good engineering idea — a single configuration knob, a measurable memory win, no code changes. That is exactly what makes it dangerous: it applies uniformly to tables whose cost curves are not uniform, and it converts a latency risk that nobody is monitoring into a memory saving that everybody can see on a dashboard. Your job is to make both columns of the ledger legible before the trade is made. ## Column one: how much memory does this actually save? Bucket slots required is `entries / threshold`: - at 0.75: 1.333 slots per entry - at 0.95: 1.053 slots per entry That is a **21% reduction in bucket slots** — the headline number, and the one the proposal will quote. Two corrections usually shrink it: 1. **Slots are the cheap part.** A slot is normally one reference or index. An entry carries a key, a value, per-entry overhead, and under chaining a node with a next-reference. For tables of non-trivial entries the bucket array is a minority of the footprint, so a 21% cut of it can be a low single-digit cut of the total. 2. **Realised occupancy is not the threshold.** Bucket counts typically double, so a growing table oscillates between roughly half its threshold and the threshold. Average occupancy under a 0.75 policy is nearer 0.55; under 0.95 it is nearer 0.7. The saving is real but the mental model of "tables sitting at 95% full" is wrong, and so is "tables sitting at 75% full". So the first action is a heap profile: **is the memory even in the bucket arrays?** In my experience it is frequently in duplicated keys, oversized values, tables that were pre-sized for a peak that never arrives, or tables that grew during an incident and never shrank. Each of those has a better fix than running hotter. ## Column two: what does it cost, and to whom? The cost is not one number, because it depends on the table: - **Chained tables** move from an expected 0.75 extra inspections per lookup to 0.95. That is a small linear change, genuinely close to free. - **Open-addressed tables** move onto the steep part of their curve, where expected probes scale with the reciprocal of the free fraction: the difference between one free slot in four and one in twenty is large, and clustering makes the real behaviour worse than the model. - **Delete-heavy open-addressed tables** are worse still, because removed entries leave markers that consume probe steps while storing nothing. Their effective occupancy already exceeds the reported figure; a 0.95 policy can push them into pathological territory. - **Tables with skewed or adversarial keys.** The clean curves assume uniform scattering. If keys are attacker-influenced — anything derived from request input — high occupancy amplifies a collision-flooding attack, turning a latency question into an availability one. And the change is invisible in complexity terms: expected lookup remains O(1), worst case remains O(n). Anyone arguing from big-O in either direction has missed that the whole effect lives in constants and, above all, in the **tail**. ## How I would run the decision 1. **Profile first.** Establish what share of resident memory the bucket arrays hold. If it is under a few percent, the proposal is answered without any latency discussion. 2. **Inventory the tables.** Group by collision scheme, entry size, delete rate, and whether keys come from outside the system. The answer differs per group; a fleet-wide setting is the wrong granularity for a per-table property. 3. **Establish the latency baseline that matters.** p99 and p999 on the paths that touch these tables, measured with **production key distributions**. Synthetic uniform keys will show no problem and prove nothing. 4. **Change the safe group first**, behind a rollout you can reverse, and watch the tail rather than the mean. 5. **Compare against the alternatives** on equal footing: correct pre-sizing, releasing tables that have outlived their peak, shrinking entries, a more compact structure for the hottest tables, or simply more memory. The threshold knob competes with these on cost-of-change and blast radius, and it frequently loses. ## The organisational half A global default is a contract with every future engineer who adds a table without reading this discussion. A per-table override is a contract with whoever maintains that table. That asymmetry matters more than the twenty percent: I would rather ship a conservative default plus three documented, measured overrides than a fleet-wide 0.95 that nobody can attribute a latency regression to six months from now. If the change ships, it needs an owner, a monitored tail metric, and a written rollback trigger — otherwise it is not a decision, it is a bet. ## The one-line answer "Show me where the memory actually is. If it is in bucket arrays, the honest saving is about a fifth of that array, the honest cost is tail latency concentrated in the open-addressed and delete-heavy tables, and the right unit of decision is a table with an owner — not a fleet."
- The team insists on one fleet-wide number. What do you push for?The conservative one, with a documented override path. A single global setting must be safe for the worst table in the fleet, and that table is an open-addressed, delete-heavy one with externally supplied keys. I would ship the safe default, then approve a small number of measured per-table overrides where the memory win is large and the tail is monitored. Uniformity is cheap to reason about; a fleet-wide latency regression is not.
- How would you detect after rollout that the change had hurt you?Instrument the thing that actually moves: probe or chain length per operation, exported as a distribution rather than a mean, alongside p99 and p999 latency on the affected paths. Watch table-level occupancy and, for open-addressed tables, the share of slots holding deletion markers. Any regression should map to a specific table and reverse when the threshold does — if it does not, the change was not the cause and you have learned that cheaply.
- When is a higher threshold genuinely the right call?When the table is chained, its entries are small enough that the bucket array dominates the footprint, the key distribution is well understood and internally generated, deletes are rare, and the workload is not tail-sensitive — a large, mostly static lookup table held in memory for the process lifetime, for instance. There the memory is real, the cost curve is linear and gentle, and the risk of a surprise is genuinely low.
saying these in an interview costs you the question
- Accepts a fleet-wide change without profiling memory first
- Quotes the 21% slot saving as the total memory saving
- Applies one threshold to chained and open-addressed tables alike
- Validates with uniformly random synthetic keys
- Argues from big-O, which the change does not alter
- Ignores externally supplied keys and collision-flooding risk
- Overlooks deletion markers inflating effective occupancy