How open addressing can be used for collision resolution?
In open addressing, if a collision occurs, alternate cells are tried until an empty cell is found.
Linear Probing
- In linear probing, whenever there is a collision, cells are searched sequentially (with wraparound) for an empty cell.
- Fig. shows the result of inserting keys {5,18,55,78,35,15} using the hash function (f(key)= key%10) and linear probing strategy.
| |
Empty Table |
After 5 |
After 18 |
After 55 |
After 78 |
After 35 |
After 15 |
| 0 |
|
|
|
|
|
|
15 |
| 1 |
|
|
|
|
|
|
|
| 2 |
|
|
|
|
|
|
|
| 3 |
|
|
|
|
|
|
|
| 4 |
|
|
|
|
|
|
|
| 5 |
|
5 |
5 |
5 |
5 |
5 |
5 |
| 6 |
|
|
|
55 |
55 |
55 |
55 |
| 7 |
|
|
|
|
|
35 |
35 |
| 8 |
|
|
18 |
18 |
18 |
18 |
18 |
| 9 |
|
|
|
|
78 |
78 |
78 |
- Linear probing is easy to implement but it suffers from "primary clustering".
- When many keys are mapped to the same location (clustering), linear probing will not distribute these keys evenly in the hash table. These keys will be stored in neighborhood of the location where they are mapped. This will lead to clustering of keys around the point of collision.
Quadratic probing
- One way of reducing "primary clustering" is to use quadratic probing to resolve collision.
- Suppose the "key" is mapped to the location j and the cell j is already occupied. In quadratic probing, the location j, (j+1), (j+4), (j+9), ... are examined to find the first empty cell where the key is to be inserted.
- This table reduces primary clustering.
- It does not ensure that all cells in the table will be examined to find an empty cell. Thus, it may be possible that key will not be inserted even if there is an empty cell in the table.
Double Hashing
- This method requires two hashing functions f1 (key) and f2 (key).
- Problem of clustering can easily be handled through double hashing.
- Function f1 (key) is known as primary hash function.
- In case the address obtained by f1 (key) is already occupied by a key, the function f2 (key) is evaluated.
- The second function f2 (key) is used to compute the increment to be added to the address obtained by the first hash function f1 (key) in case of collision.
- The search for an empty location is made successively at the addresses f1 (key) + f2(key), f1 (key) + 2f2 (key), f1 (key) + 3f2(key),...
