Why does a hash table's rehash at the load-factor threshold not break amortized O(1) insert?

## The apparent contradiction A hash table is advertised as constant-time insert, yet periodically it stops and rebuilds itself: it allocates a larger bucket array and re-places every stored entry into it, because each entry's position depends on the table size. That rebuild touches every element, so it costs `Theta(n)`. How can a structure that occasionally does linear work per insert be described as constant-time? The answer is that it is the dynamic-array argument wearing different clothes, and recognising the shared shape is the point of the question. ## The shared ingredient: multiplicative capacity growth A hash table rebuilds when its **load factor** — entries divided by buckets — crosses a threshold. The critical detail is that the threshold is a *fraction of capacity*, not an absolute number of entries, and that crossing it *multiplies* capacity. So if a rebuild happens at some size, the next one cannot happen until the entry count has grown by the same multiplicative factor. That gives exactly the structure that makes a growth-doubling buffer amortized constant: - The rebuilds happen at exponentially spaced entry counts. - Each rebuild costs proportionally to the entry count at that moment. - Cost per rebuild grows at the same rate that rebuild frequency falls. Sum the rebuild costs across n inserts and you get a geometric series whose terms roughly double: it is bounded by a constant multiple of its largest term, so total rebuild work is `O(n)`. Add the n inserts themselves and the total for the whole sequence is still `O(n)`; divide by n and the amortized cost per insert is constant. Nothing about hashing enters this part of the argument — it is pure geometry of the growth schedule, which is why the same reasoning covers any structure that rebuilds itself when it fills. ## The part that is *not* the same A dynamic array's append has one source of variability: the resize. A hash table has two, and conflating them is the most common way to get the claim wrong. **Resize cost is amortized.** It is bounded by the geometric argument above and holds against any sequence of operations, with no probabilistic assumption. **Collision cost is expected.** Where an entry lands depends on how the hash function distributes the particular keys inserted. Under a good distribution, the work to place or find an entry is constant *in expectation*. Under a poor distribution — or under keys chosen deliberately to collide — many entries pile into one bucket and a lookup or insert degrades toward linear in the number of entries there. Growing the table does not repair that: the colliding keys collide in the new table too, because they hash to the same place regardless of how many buckets exist. So the precise sentence to say in an interview is **"insert is `O(1)` expected and amortized; worst case is linear"**, and it is worth being able to attribute each qualifier to its cause. Saying "hash insert is `O(1)`, full stop" is the answer that gets marked down, and "rehashing makes it `O(n)`" over-corrects in the other direction. ## Why the growth must stay multiplicative It is instructive to break the argument on purpose. Suppose a table added a fixed number of buckets at each rebuild instead of multiplying capacity. Then rebuilds would fire at a constant interval of inserts forever, while each rebuild's cost kept climbing with the entry count. The rebuild costs would form an arithmetic rather than a geometric series, the total would be quadratic in n, and the per-insert amortized cost would grow linearly with table size. This is precisely the additive-growth failure that ruins a dynamic buffer, and the fact that it transfers unchanged shows the argument was never about arrays or hashing — it is about the relationship between how often you rebuild and how much each rebuild costs. Equivalently: keeping the trigger at a fixed *fraction* of capacity is what makes the growth multiplicative in the first place. A trigger at a fixed *count* of entries above the previous rebuild would be the additive policy in disguise. ## The transferable test When you meet any structure that periodically rebuilds — a growable buffer, a hash table, a compacting log, a rebuilt index — ask one question: *does the work between rebuilds grow in proportion to the cost of a rebuild?* If yes, the total telescopes into a geometric series and the amortized per-operation cost is constant. If no, you have quadratic total work waiting to appear at scale. That single test is the reusable content behind both the array and the hash-table answer, and being able to state it in the general form is what separates having memorised two facts from understanding one idea.