Linear Probing Explained with Example
Definition:
Linear Probing is a collision resolution technique in open addressing where, when a collision occurs, we check the next available slot (one position at a time) in a sequential manner.
The step size is fixed at 1, meaning we move to the next index repeatedly until we find an empty slot.
Formula for Linear Probing
hash(key) = (h(key)+i) mod table_size
Where:
- h(key) = Primary hash function (initial index).
- i = Probing attempt number (0, 1, 2, …).
- mod table size ensures wrapping around in a circular manner.
Example of Linear Probing
Given:
- Hash Table Size: 10
- Hash Function: h(key) = key % 10
- Keys to Insert: 43, 23, 34, 45, 27
Step-by-Step Insertion:
| Key | Hash Code (key % 10) | Stored At Index |
|---|---|---|
| 101 | 101 % 10 = 1 | 1 |
| 203 | 203 % 10 = 3 | 3 |
| 309 | 309 % 10 = 9 | 9 |
| 412 | 412 % 10 = 2 | 2 |
| 512 | 512 % 10 = 2 | 2 (Collision occurs!) |
In Linear Probing, when a collision occurs at an index, we check the next available index sequentially (moving forward by 1 step at a time) in a circular manner.
Steps to find the next available index:
- Compute the initial hash index using:
- hash(key) = key % table_size
- For 512
- 512 % 10 = 2
- → So, initial index = 2.
- Check if index 2 is occupied:
- 412 is already stored at index 2.
- Collision occurs! → We must find the next free index.
- Use Linear Probing (step size = 1):
- Check index 3 → Occupied by 203
- Check index 4 → Empty!
- Store 512 at index 4.
Thus, the next available index for 512 is 4.
Step-by-Step Application of the Formula
- Compute the initial index using
- h (512) = 512 % 10 = 2
- So, the first probe (i=0) checks index 2.
- Index 2 is occupied by 412 → Collision occurs!
- Apply the formula to find the next index:
- (2+1) % 10 = 3
- The second probe (i=1) checks index 3.
- Index 3 is occupied by 203 → Collision occurs again!
- Apply the formula again:
- (2+2) % 10 = 4
- The third probe (i=2) checks index 4.
- Index 4 is empty → Store 512 at index 4.
3 mod 10 = 3
Explanation:
When you take 3 % 10 (read as “3 mod 10”), it means dividing 3 by 10 and taking the remainder.
- 3 ÷ 10 = 0 (quotient) with a remainder of 3.
- Since 3 is smaller than 10, the remainder is just 3.
So:
3 mod 10 = 3