Double Hashing
On collision, step by a value from a SECOND hash function (unique to the key), rather than a fixed or formula-based step — different keys follow different probe sequences even from the same home slot, minimising clustering.
- Category
- Hashing
- Time complexity
- O(1) avg
- Space complexity
- O(n)
Pseudocode
step = hash2(key) (must never be 0) i = 0 while table[(home + i*step) % size] occupied: i += 1
Reference implementation
step = hash2(key) # nonzero
i = 0
while table[(home + i*step) % size] is not None:
i += 1
table[(home + i*step) % size] = key