Rehashing

Growing by a constant c means a rehash every c inserts, and each pass touches every key already stored, so n inserts do roughly n squared over 2c work and a single insert costs O(n) on average. Doubling makes the passes exponentially rarer as the table grows: their sizes are n, n/2, n/4 and so on, under 2n moves in total. That total divided over n inserts is where the amortized O(1) comes from.

With linear probing an unsuccessful lookup costs about (1 + 1/(1-a)^2)/2 probes for load factor a: roughly 6 probes at 0.7 but roughly 50 at 0.9. The cost is not proportional to how full the table is, it blows up as the last slots disappear, so open addressing has to resize well before the table fills. Chaining degrades gently, since the average chain length is just a, which is why a chained table can sit at 1.0 or higher and only pay a slightly longer walk.

Under open addressing you cannot blank a slot on delete, because a probe that walked past that slot to place a later key would now stop at the gap and report the key missing. The usual fix is a tombstone, a marker meaning keep probing, but tombstones lengthen probes while counting as neither live keys nor free space, so a table churned by inserts and deletes gets slow at a load factor that still looks small. The cure is a rehash into a table of the same capacity, which is the reminder that not every rehash is a growth.

One insert in every n pays for the whole pass, so a table holding a million keys has one insert that moves a million keys. That shows up as a latency spike, and averaging it away is exactly what a request budget, a game frame or an audio callback cannot do. Code with a deadline either sizes the table up front, with HashMap.newHashMap(n) or reserve or make(map[K]V, n), or spreads the move across many operations instead of doing it in one. Watch the Java form: the HashMap(n) constructor takes a bucket count, not a key count, so passing the number of keys you expect still resizes once you pass 0.75 of it, which is why newHashMap was added.