Linear Probing Collision Technique
Linear probing is a collision resolution technique used in open addressing for hash tables. When a collision occurs (two keys hash to the same index), linear probing finds the next available slot by linearly searching through the table.
If the end of the table is reached and no empty cell have been found, then the search is continued from the beginning of the table. It has a tendency to create cluster in the table.
In linear probing we get primary clustering problem. Primary Clustering Problem If the Hash table becomes half full and if a collision occurs, it is difficult to find an empty location in the hash table and hence an insertion or the deletion process takes a longer time.
Hash Function
A hash function h(k) maps a key k to an index in the hash table:
index = h(k) mod m, where m is the size of hash table.
Collision Resolution
If a collision occurs (i.e., the calculated slot is already occupied), linear probing searches for the next empty slot by checking subsequent indices in a cyclic manner:
index = ( h(k) + i ) mod m
Here, i = 1,2,3,… until an empty slot is found.
- h(k) mod size
- h(k) + 1 mode size
- h(k) + 2 mod size
Example of Linear Probing
Example: 1
Hash table size m = 7, hash function h(k)=k mod 7, and keys: 50, 700, 76, 85, 92, 73, 101.
Step 1: Insertion
50 : h(50) = 50 mod 7 = 1 → Insert at index 1.
700 : h(700) = 700 mod 7 = 0 → Insert at index 0.
76 : h(76) = 76 mod 7 = 6 → Insert at index 6.
85 : h(85) = 85 mod 7 = 1 → Collision! Check 2 → Insert at index 2.
92 : h(92) = 92 mod 7 = 1 → Collision! Check 3 → Insert at index 3.
73 : h(73) = 73 mod 7 = 3 → Collision! Check 4 → Insert at index 4.
101 : h(101) = 101 mod 7 = 3 → Collision! Check 5 → Insert at index 5.
Resulting Table:
| Key | Index |
|---|---|
| 0 | 700 |
| 1 | 50 |
| 2 | 85 |
| 3 | 92 |
| 4 | 73 |
| 5 | 101 |
| 6 | 76 |
Example: 2
Using the hash function key mod 7, insert the following sequence of keys in the hash table 76, 93, 40, 47, 10, and 55
Advantages of Linear Probing
- Simple Implementation: Easy to understand and implement.
- Cache Efficiency: Due to sequential access, it leverages spatial locality in memory.
Disadvantages of Linear Probing
Primary Clustering
When many keys hash to the same region, they form a "cluster," leading to long probe sequences and degraded performance.
Performance Degradation
As the load factor (α=n/m\alpha = n/mα=n/m, where nnn is the number of elements and mmm is the table size) increases, performance decreases significantly.
Deletion Complexity
Requires special handling to avoid breaking the search chain, typically by marking slots as "deleted."
Performance
Time Complexity
- Average Case: O(1) for insertion, search, and deletion when the load factor is low.
- Worst Case: O(n), if the hash table is nearly full or poorly hashed.
Optimal Load Factor: Keep α < 0.7 for efficient operations.
Numerical Questions of Linear Probing Collision Technique
- A hash table has m=10 slots and uses the hash function h(k) = k mod 10. Insert the following keys into the hash table using linear probing: 12,22,32,42,52 Show the final hash table after all insertions.
- A hash table with m = 7 slots has the following keys inserted using linear probing: 10,20,15,25,35 The hash function is h(k) = k mod 7.
- Find the position of the key 25.
- Determine the number of probes required to search for 15.
- A hash table of size m=5 uses the hash function h(k) = k mod 5. Insert the keys: 21,26,31,16,35,41
- Show the final hash table after all insertions.
- How many collisions occurred in total?