Handling Hash Collisions

A hash collision occurs when two or more keys in a hash table produce the same hash value, resulting in them being mapped to the same index in the underlying array. Collisions are inevitable in hash tables because the number of possible keys is typically much larger than the size of the array.

When a collision occurs, there are different strategies to handle it and store the colliding elements. The two most common strategies are:

Separate Chaining:

• In separate chaining, each slot of the hash table is a linked list or another collection that can store multiple elements.
• When a collision occurs, the colliding elements are stored in the same linked list at the corresponding index.
• During lookup, the hash function is applied to the key to find the appropriate index, and then the linked list at that index is traversed to find the desired element.

Open Addressing:

• In open addressing, when a collision occurs, the hash table probes for the next empty slot in the array to store the colliding element.
• The probing can be done using different techniques, such as linear probing, quadratic probing, or double hashing.
• During lookup, the hash function is applied to the key, and the resulting index is probed until the desired element is found or an empty slot is encountered.

Here's an example of handling collisions using separate chaining:

1#include <iostream>
2#include <list>
3#include <vector>
4
5class HashTable {
6 private:
7  std::vector<std::list<int>> table;
8  int size;
9
10 public:
11  HashTable(int tableSize)
12    : size(tableSize) { table.resize(size); }
13
14  void insert(int key) {
15    int index = hashFunction(key);
16    table[index].push_back(key);  
17  }
18
19  bool search(int key) {
20    int index = hashFunction(key);
21    auto& list = table[index];
22    return std::find(
23      list.begin(), list.end(), key
24    ) != list.end();
25  }
26
27 private:
28  int hashFunction(int key) {
29    return key % size; }
30};
31
32int main() {
33  HashTable hashTable(10);
34
35  // Inserting elements
36  hashTable.insert(5);
37  hashTable.insert(15);  // Collision with 5
38  hashTable.insert(25);  // Collision with 5
39
40  std::cout
41    << "Search for 15: "
42    << (hashTable.search(15)
43      ? "Found" : "Not Found")
44    << '\n';
45  std::cout
46    << "Search for 20: "
47    << (hashTable.search(20)
48      ? "Found" : "Not Found")
49    << '\n';
50}

1Search for 15: Found
2Search for 20: Not Found

In this example, when a collision occurs (e.g., keys 5, 15, and 25 produce the same hash value), the colliding elements are stored in a linked list at the corresponding index. During search, the linked list is traversed to find the desired element.

Handling collisions effectively is crucial for maintaining the performance and efficiency of hash tables. The choice of collision resolution strategy depends on factors such as the expected number of elements, the distribution of keys, and the desired trade-offs between memory usage and lookup time.