Linear Probing
You'll learn how linear probing resolves hash table collisions by checking the next available slot in sequence.
The Core Idea
When two keys hash to the same index (a collision), linear probing handles it by simply looking at the next slot in the array. If that slot is occupied too, check the one after that, and so on—moving consecutively through the table until you find an empty spot.
Think of it like parking: if your preferred parking space is taken, you drive to the next one, then the next, until you find an empty spot. You're "probing" linearly through the lot.
How It Works
When inserting a key:
- Hash the key to get an index
- If that slot is empty, place the key there
- If occupied (collision!), check
index + 1 - Still occupied? Try
index + 2, thenindex + 3, and so on - Wrap around to the beginning if you reach the end of the array
When searching:
- Hash the key and start at that index
- If the slot contains your key, found it!
- If empty, the key doesn't exist
- If it contains a different key, keep probing forward
Why "Linear"?
The probe sequence follows a simple arithmetic pattern: index, index + 1, index + 2, etc. Each step moves exactly one position forward—hence "linear."
This is the simplest form of open addressing you learned about previously.
Key Takeaway: Linear probing resolves collisions by checking consecutive slots one-by-one until finding an empty space, making it the most straightforward open addressing technique but prone to clustering issues.