Step 4 of 4
Dynamic Load-Factor Rehashing
You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.
As more entries are added to a fixed bucket array, chain lengths grow longer, degrading lookup performance from $O(1)$ down to $O(n)$.
To maintain constant-time guarantees, the hash map must dynamically rehash:
- After inserting a new key, check the load factor: $\alpha = \frac{\text{size}}{\text{capacity}}$.
- If $\alpha \ge 0.75$:
- Double the capacity ($2 \times \text{capacity}$).
- Allocate new empty buckets.
- Re-insert all existing entries so their positions are recomputed under the new capacity.
Your build
Running is free — Submit is what records the step. Or press ⌘↩
Tests
2 cases| call | type | expected | result |
|---|---|---|---|
| runOps(4, [["capacity"],["set","k1",1],["set","k2",2],["capacity"],["set","k3",3],["capacity"],["get","k1"],["get","k2"],["get","k3"],["size"]]) | triggers rehash when load factor reaches 0.75 | [4,null,null,4,null,8,1,2,3,3] | — |
| runOps(2, [["set","a",1],["set","b",2],["set","c",3],["set","d",4],["capacity"],["get","a"],["get","b"],["get","c"],["get","d"],["size"]]) | maintains correctness through multiple rehashes | [null,null,null,null,8,1,2,3,4,4] | — |
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left