Collision Resolution Techniques in Hashing
When two keys hash to the same index in a hash table, a collision occurs. To handle collisions, we use collision resolution techniques. There are two main categories:
- Separate Chaining (Open Hashing)
- Open Addressing (Closed Hashing)
Separate Chaining (Open Hashing)
Instead of storing only one key per index, we store multiple keys in a linked list at the same index.
✔ Steps:
- Each index of the hash table contains a linked list (or another dynamic data structure).
- If multiple keys hash to the same index, they are inserted into the linked list at that index.
✔ Advantages:
- Efficient in handling collisions.
- No need to resize the table frequently.
- Deleting a key is simple because it only requires removal from a linked list.
✔ Disadvantages:
- Extra memory is needed for pointers in the linked list.
- Performance degrades if chains become long, searching in a long linked list becomes slow.
Example of Separate Chaining
Let’s consider a hash table of size 10 and use the following hash function:
h(key) = key mod 10
We will insert the keys: 101, 203, 309, 412, and 512.
| 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!) |
So, if table size = 10, the hash function ensures values are stored within the range 0-9
Here is the corrected hash table using Separate Chaining to handle collisions:
| Index | Chained Values (Linked List) |
|---|---|
| 0 | (empty) |
| 1 | → 101 |
| 2 | → 412 → 512 |
| 3 | → 203 |
| 4 | (empty) |
| 5 | (empty) |
| 6 | (empty) |
| 7 | (empty) |
| 8 | (empty) |
| 9 | → 309 |
Since 512 hashes to index 2, and 412 is already at index 2, we use a linked list to store both values.