AlgoScope

Quadratic Probing

Probe i jumps i^2 slots from the home slot, so a run of taken slots is left behind instead of growing.

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

Hash Table: Quadratic probing leaves the cluster

Decision, step 4 of 24

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.