Double hashing

Resolve collisions using a second hash to choose the probe stride. The stride must be coprime to table capacity.

Remember: First hash starts; second hash steps.

Example: Capacity 7, key 17: start 3, stride 6 → probe 3,2,1,0,…

Time: Expected O(1) / key. Auxiliary space: O(m).

Formula: probe(i) = (h1(key) + i × h2(key)) % m; h2 = 1 + mod(key, m − 1)

m is capacity. Prime capacities keep double-hash strides coprime to m. Duplicate keys use set semantics; expected O(1) assumes bounded load and suitable distribution. Worst case is linear. Deletion is not part of this lesson.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.