Before bulk-loading five million records into a hash table, how do you choose its initial capacity?

## The arithmetic A table resizes when `entries > load_factor x capacity`. To avoid ever crossing that line while loading n entries, you need `capacity >= n / load_factor` For a batch import of 5,000,000 catalog records into a table that grows at 0.75: `5,000,000 / 0.75 = 6,666,667 buckets` If the implementation requires a power-of-two capacity — common, because it lets the index reduction be a bit-mask instead of a division — round up to **8,388,608**. That is 1.68x the entry count in slot count, which is the price of never rehashing during the load. ## What skipping it costs Starting from a typical small default of 16 buckets, the table doubles until it can hold five million entries: 16 → 32 → … → 8,388,608, which is nineteen resizes. The entries moved at each resize is the count present at the time, about 0.75 of the capacity being outgrown, so the total is `0.75 x (16 + 32 + … + 4,194,304) ≈ 6.3 million entry moves` That is more re-placement work than the actual insertion work, plus nineteen allocations of ever-larger arrays, nineteen periods where two arrays are simultaneously live (the largest pair peaking near 12.5 million slots), and the memory churn all of that leaves behind. Pre-sizing removes every bit of it and replaces it with one allocation. ## The two mistakes **Sizing to the entry count.** Requesting five million buckets for five million entries puts the table at load factor 1.0, far past any mainstream growth threshold. It will resize at least once during the load — usually near the end, when the transfer is at its most expensive. Whatever number you compute, divide by the load factor before you pass it. **Getting the units wrong.** Container interfaces differ in what their sizing parameter means. Some take a raw bucket/capacity count; others take an *expected element count* and apply the load factor internally; a few take a target load factor as a second parameter. Passing an entry count to a bucket-count parameter leaves a resize in flight; passing an already-divided bucket count to an entry-count parameter over-allocates by another 1/load_factor. Read what the knob means before you set it — this is the single most common way a well-intentioned pre-size does nothing. ## When to stop over-sizing Pre-sizing is not free, and "round generously up" is not the right instinct: - **Memory.** Buckets cost space whether or not they hold anything, and most tables never shrink on their own. A table sized for a peak that arrives once holds that footprint for the life of the process. - **Cache and iteration.** A very sparse table spreads live entries across more cache lines, so lookups miss more often and a full iteration walks many empty slots. Under open addressing this is especially visible, since iteration is a linear scan of the whole slot array. - **Unknown n.** If you genuinely cannot estimate the final size, a bad guess is worse than the default: guess low and you keep the resizes anyway, guess high and you pay memory forever. Estimate from a real signal — a row count, a file size, a prior run — or don't pre-size. ## What pre-sizing does not fix It removes resize pauses. It does **not** improve the per-operation collision behaviour: a poor hash function that clusters keys still produces long chains or long probe sequences in a large table, because clustering is about how the hash spreads, not about how much room it has. Nor does it help a table whose growth is driven by unbounded key churn — a table that keeps accumulating new keys will eventually pass whatever capacity you chose. In that case the right answer is a bounded structure with eviction or expiry, not a bigger initial allocation. ## How to say it in an interview "Expected entries divided by the growth threshold, rounded up to the implementation's accepted capacity — so about 6.7 million buckets for five million records at 0.75, which rounds to 8.4 million if powers of two are required. I'd check whether the sizing parameter means buckets or expected entries before trusting it, and I'd verify by watching the table's capacity after the load rather than assuming the pre-size took."