Handling Hash Collisions in std::unordered_map

std::unordered_map handles hash collisions using a technique called chaining. When multiple keys hash to the same bucket, the container stores them in a linked list or a similar data structure within that bucket. This allows multiple elements to coexist in the same bucket.

When a collision occurs, the container uses the equality comparison function (operator== or a custom comparator) to find the desired element within the bucket.

Here's an example that demonstrates hash collisions:

1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5struct Person {
6  std::string name;
7  int age;
8
9  bool operator==(const Person& other) const {
10    return name == other.name && age == other.age;
11  }
12};
13
14namespace std {
15template <>
16struct hash<Person> {
17  size_t operator()(const Person& person) const {
18    return std::hash<std::string>{}(person.name);
19  }
20};
21}
22
23int main() {
24  std::unordered_map<Person, int> peopleMap;
25
26  peopleMap[Person{"Alice", 25}] = 1;
27  peopleMap[Person{"Bob", 30}] = 2;
28
29  // Collision with "Alice" key
30  peopleMap[Person{"Alice", 30}] = 3;
31
32  for (const auto& [person, id] : peopleMap) {
33    std::cout
34      << "Name: " << person.name
35      << ", Age: " << person.age
36      << ", ID: " << id << '\n';
37  }
38
39  std::cout << "Bucket count: "
40    << peopleMap.bucket_count() << '\n';  
41  std::cout << "Load factor: "
42    << peopleMap.load_factor() << '\n';    
43}

1Name: Alice, Age: 30, ID: 3
2Name: Alice, Age: 25, ID: 1
3Name: Bob, Age: 30, ID: 2
4Bucket count: 8
5Load factor: 0.375

In this example, the Person type uses only the name member for hashing. As a result, Person{"Alice", 25} and Person{"Alice", 30} collide because they have the same name.

The container resolves the collision by storing both elements in the same bucket. When accessing elements, it uses the equality comparison function to distinguish between the colliding elements.

The bucket_count() function returns the number of buckets in the container, and load_factor() returns the average number of elements per bucket. A higher load factor indicates more collisions.

To minimize collisions and improve performance, you can:

• Use a good hash function that distributes keys evenly across buckets.
• Increase the number of buckets by calling rehash() with a higher bucket count.
• Adjust the maximum load factor using max_load_factor() to trigger automatic rehashing when the load factor exceeds a certain threshold.

1// Increase bucket count to 10
2peopleMap.rehash(10);
3
4// Set maximum load factor to 0.75
5peopleMap.max_load_factor(0.75);

By understanding how std::unordered_map handles collisions using chaining and taking steps to minimize collisions, you can optimize the performance of your unordered map and ensure efficient key-value lookups.