Chained-table lookups spike for one tenant while average load factor reads 0.7 — how do you diagnose it?

## Why the average lies A chained hash table's headline metric is its load factor, entries over buckets. It is the *mean* chain length. Under the uniform-hashing assumption the mean is a good summary because the distribution around it is tight. When that assumption fails, the mean becomes almost useless: entries can pile into a handful of buckets while the arithmetic mean sits comfortably below the resize threshold, so the table never even considers growing — and growing would not help anyway. Picture a multi-tenant service holding a table keyed by tenant identifier plus record identifier. One tenant is misconfigured and emits records whose keys differ only in a field the hash never reaches — say the key object's hash is derived from the tenant portion alone, or the reduction step masks the low bits and every one of that tenant's identifiers shares those bits. Every one of that tenant's records lands in the same bucket. The table now contains a chain thousands of nodes long, and a lookup against that tenant walks it. Meanwhile the other tenants are spread across the remaining buckets and the reported load factor reads 0.7. ## The symptom shape This failure has a recognizable fingerprint, and recognizing it is most of the interview answer: - Latency is **bimodal, not uniformly degraded** — most requests are fast, one slice is catastrophically slow. - The slow slice **correlates with a key attribute** (one tenant, one prefix, one region), not with time of day or table size. - Aggregate health metrics are **green**: load factor normal, memory normal, no errors. Correctness is unaffected; only latency moved. - Growing the table **does not fix it**, and may not even trigger, since the mean never crosses the threshold. ## How to confirm it Stop looking at the mean and measure the shape of the distribution. The three numbers that matter are the **longest chain**, the **chain-length histogram**, and the **fraction of entries in the busiest bucket**. A healthy table under uniform hashing at `alpha = 0.7` has a longest chain in the low single digits; a table whose longest chain holds thousands of entries is not a hash table any more, it is a linked list with an index in front of it. If you cannot instrument the table itself, the shape can be inferred: measure comparison counts or lookup latency grouped by key attribute, and the offending group separates immediately. ## The decisive distinction Once skew is confirmed, one question determines the fix: do the offending keys produce **identical hash values**, or merely values that *collide after reduction* into the current bucket count? - **Identical hash values.** Growing the bucket array is useless — identical values reduce to the same index at every table size, so the chain survives every resize intact. The problem is upstream, in how the key's hash is derived: it is ignoring the part of the key that actually varies. The fix is to include the distinguishing field, or to key the table differently. - **Distinct values that collide after reduction.** Here the values differ but the reduction throws away the bits that differ — for example masking to the low bits when the keys vary only in the high bits. A mixing step that diffuses high bits into low ones before the reduction, or a reduction that does not simply drop bits, separates them. This class *is* repaired by a better mix, and often by a different table size. Stating this distinction unprompted is what marks a senior answer. Most candidates propose "make the table bigger", which addresses only the second case and is worth nothing in the first. ## Why the table still returns correct answers Worth saying explicitly: nothing is broken. Chaining's correctness does not depend on distribution at all — a chain of ten thousand nodes returns exactly the right entry, just slowly. That is why this incident presents as a latency problem with no error signal, and why it can survive in production for a long time. It also means the mitigation is never urgent for correctness and always urgent for the tail-latency budget, which is a different conversation with a different owner. ## The lesson to carry Chaining converts bad key distribution into slow lookups rather than failures. That is a genuine robustness property — the gentle degradation is a feature — but it means the aggregate metric everyone watches is exactly the metric that cannot see the problem. If a service's latency depends on a hash table's chain lengths, then chain lengths, not load factor, are what belongs on the dashboard.