AlgoScope

Rehashing

When the load factor exceeds a threshold, double the buckets and reinsert every key.

Hashing, algorithm, intermediateAlso called resize
Insert 12 at slot 2. The load factor is 0.20, under the limit.0112234probe
Insert 12 at slot 2. The load factor is 0.20, under the limit.0112234probe

Rehashing: One rehash

Decision, step 2 of 12

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.

Taught by the same lesson

Rehashing covers these too, in the same run.