Deduplicating a billion analytics records with a hash set — which expected-O(1) assumption breaks first?

## The question behind the question Asking which assumption breaks first at scale is really asking whether you know what the O(1) is counting. It is not counting nanoseconds. It is counting operations in the unit-cost RAM model, where fetching any address costs the same as fetching any other. That model is an excellent approximation while the working set fits in cache and a poor one once it does not — and "once it does not" is precisely what a billion-key table guarantees. ## Ruling out the two usual suspects **Collision pileups.** The expected number of entries sharing a bucket is the load factor, and a growth policy holds the load factor roughly constant regardless of `n`. So a table of `10^9` entries has the same expected probe count as one of `10^6`. The longest chain does grow, but only as `log n / log log n` under the uniform model — from single digits to low double digits across three orders of magnitude. Unless the hash is failing to mix the keys, collisions are not what changed. **Growth re-placement.** Every live entry is re-placed each time the table grows, and that feels alarming at a billion entries. But with constant-factor growth the total across all inserts is linear — the sum `1 + 2 + 4 + ... + n` is under `2n` — so growth adds a constant factor to the whole load, not a new asymptotic term. Worth knowing, not the first thing that bites. ## What actually breaks: the cost model Start with arithmetic, because this is the number an interviewer wants to see you produce unprompted. A billion entries with, say, 32 bytes per stored entry is 32 GB before any table overhead; add empty slots implied by the load factor and per-entry metadata and the real figure is meaningfully larger. Two consequences follow. First, if that exceeds available memory, the analysis is over — the process either fails or starts paging, and a paging hash table is thousands of times slower than the one you analysed, because its access pattern is the worst possible one for a pager. Second, even when it fits, locality collapses. A hash function's entire purpose is to scatter keys, which means consecutive lookups touch unrelated addresses. With a table far larger than the last-level cache, essentially every probe is a cache miss; probing several slots in a run means several independent misses. The operation is still O(1) — one or two probes, exactly as analysed — but each probe now costs on the order of a hundred nanoseconds instead of a few. Nothing about the complexity claim is wrong; it simply was never a statement about time on a memory hierarchy. ## What "expected" quietly assumes about your keys The second-order answer, and the one that separates a strong candidate: expected O(1) assumes the stored keys scatter across buckets, and that is about **distinct** keys. A dedupe workload has a specific and helpful property — heavy duplication of a few values. Duplicates do not create collisions or entries; they resolve to the existing entry. So a billion records with only fifty million distinct keys is a fifty-million-entry problem, and the first measurement worth taking is the distinct cardinality, not the record count. Getting that backwards, and sizing for a billion entries when the data holds a twentieth of that, is the most expensive mistake available here. ## The engineering answer Budget before you benchmark. Estimate the distinct cardinality, multiply by realistic bytes per entry including overhead, and compare against the ceiling you are allowed. If it fits with headroom, the expected-O(1) structure is the right call and you should expect memory-bound rather than compute-bound behaviour, judging progress in records per second against memory bandwidth rather than against instruction counts. If it does not fit, the structure is not the problem and no tuning of it will help: partition the key space by a hash prefix into passes that each fit, dedupe within each pass, and pay one extra sequential read of the input — trading a random-access problem you cannot afford for a sequential one you can. If exactness is negotiable, a probabilistic membership structure cuts the memory by an order of magnitude at the price of a bounded false-positive rate, and whether that is acceptable is a product decision rather than an algorithmic one. The throughline: the asymptotics were never wrong. The claim held; the machine model underneath it stopped being a good description of the machine.