Quadratic Probing
Probe i jumps i^2 slots from the home slot, so a run of taken slots is left behind instead of growing.
Hash Table: Quadratic probing leaves the cluster
Slot 5 is empty, so 5 goes here.
Cost
- Insert
- O(1) expected
- Search
- O(1) expected
- Worst case op
- O(n)
- Space
- O(capacity)
Before this
Related
Taught by the same lesson
Hash Table covers these too, in the same run.