Linear Probing
On a collision, walk forward one slot at a time until a free one turns up.
Decision · step 3 of 8Hash Table: Insert that walks past a collision
Slot 1 holds 12, not 45. Walk on to slot 2.
What you will see
The key hops slot by slot until it lands; clusters form and are visible.
Cost
| insert | O(1) expected |
|---|---|
| search | O(1) expected |
| worst case op | O(n) |
| Space | O(capacity) |
Performance degrades sharply as load factor approaches 1 (primary clustering).
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Hash Table covers these too, in the same run.