AlgoScope

Double Hashing

Each key probes with its own stride, 1 + key mod (size - 1), so keys with the same home follow different paths.

Data structures, data structure, advanced
Probing slot 5, which holds empty. It is free.012345678910probe

Hash Table: Double hashing, a stride per key

Decision, step 4 of 21

Slot 5 is empty, so 5 goes here.

How hash table works

Cost

Insert
O(1) expected
Search
O(1) expected
Worst case op
O(n)
Space
O(capacity)

Taught by the same lesson

Hash Table covers these too, in the same run.