AlgoScope

Load Factor

Entries divided by buckets. Drives expected probe length and when to rehash.

Hashing, analysis, intermediate
Insert 5 at slot 0. The load factor is 0.20, under the limit.501234probe
Insert 5 at slot 0. The load factor is 0.20, under the limit.501234probe

Rehashing: Collisions before the rehash

Decision, step 2 of 11

insert 5. 5 mod 5 = 0 and slot 0 is free. Load 1 / 5 = 0.20, under 0.70.

How rehashing works

Cost

Space
O(1)

Expected chaining lookup is O(1 + load factor).

Taught by the same lesson

Rehashing covers these too, in the same run.