Linear probing

Resolve a collision by checking consecutive table slots, wrapping at the end.

Remember: Collision → try the next slot.

Example: Capacity 7: 10 takes slot 3; 17 tries 3 then takes 4.

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

Formula: probe(i) = (mod(key, m) + i) % m

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.