How a Hash Map Grows — Rehashing
insert → load factor climbs → cross the threshold → double the buckets → every key gets a new index
Press Play or Step to insert the first key.
0 / 4 = 0.00
┆ threshold 0.75
set(key, value):
i = hash(key) % buckets.length
buckets[i].push([key, value]); n += 1
if n / buckets.length > 0.75: // load factor
grow()
grow():
old = buckets
buckets = new Array(old.length * 2) // double
for (k, v) in old: // EVERY entry
i = hash(k) % buckets.length // new modulus → new index
buckets[i].push([k, v])
What a Rehash Costs
| Operation | Cost | Why |
|---|
| Insert, no rehash | O(1) | hash, jump, push |
| The insert that triggers a rehash | O(n) | every existing entry is re-placed |
| Insert, amortised | O(1) | doubling means each key is moved ~twice over the whole build |
| Building a map of n items | O(n) | total, not O(n²) |
Doubling is what makes it amortised. Growing by a constant instead (m + 4) would rehash far more often and build in O(n²).