AlgoScope

Linear Probing

On a collision, walk forward one slot at a time until a free one turns up.

Data structures, data structure, intermediate
Probing slot 1, which holds 12. It does not match, so the probe moves on.0121232133445678910probe12 < 45

Hash Table: Insert that walks past a collision

Decision, step 3 of 8

Slot 1 holds 12, not 45. Walk on to slot 2.

How hash table works

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).

Leads to

Topics that need this one first.

Taught by the same lesson

Hash Table covers these too, in the same run.