In separate chaining, we need extra memory for linked lists. Can we store everything in the hash table array itself by finding the next empty slot?
On collision, linear probing checks the next slot (index+1, +2, …) until an empty slot is found, wrapping around to the beginning if needed.
- Hash key to get initial index
- If slot is empty, insert there
- If occupied, check next slot (index+1)
- Continue until empty slot found (wrap around if needed)
- Search: check slots sequentially until key found or empty slot
- No extra memory for linked lists (all in array)
- Causes primary clustering (consecutive occupied slots)
- Probe sequence is: h(k), h(k)+1, h(k)+2, …
- Deletion tricky: need tombstone markers
- Built from: Hashing, Collision Resolution
- Builds into: Quadratic Probing, Double Hashing
- Related: Load Factor
- Contrasts with: Separate Chaining (in-table vs chains)
- Primary clustering: long runs of occupied slots form
- Performance drops sharply when load factor > 0.7
- Deletion needs tombstones (can’t just clear slot)
- Table must be resized when getting full