Rehashing
When the load factor exceeds a threshold, double the buckets and reinsert every key.
Rehashing: One rehash
insert 12. 12 mod 5 = 2 and slot 2 is free. Load 1 / 5 = 0.20, under 0.70.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Amortized O(1) per insert.
Before this
Related
Taught by the same lesson
Rehashing covers these too, in the same run.