This is the 13th Part of Tutorial series on unordered_map.

The Load Factor of an unordered_map in C++ is a measure that indicates how full the hash table is. Its important in balancing between memory usage and the efficiency of the hash table’s operations, such as insertion, deletion, and lookup.

The Load Factor is calculated as the ratio of the number of elements in the hash table to the number of buckets (slots) available in the hash table. Mathematically, it’s expressed as:

Load Factor = Number of elements in the hash table / Number of buckets

Why is Load Factor Important?

  1. Performance Optimization: A high load factor means more elements are stored in each bucket, leading to potential collisions and longer search times. A lower load factor reduces collisions but uses more memory.
  2. Balancing Memory and Speed: The right load factor helps maintain an efficient balance between memory usage and operation speed.
  3. Auto-Resizing: When the load factor crosses a certain threshold, the unordered_map automatically resizes by increasing the number of buckets, rehashing the elements into these new buckets to distribute them more evenly.

Managing Load Factor in Unordered_Map

The C++ Standard Library provides functions to manage and check the load factor of an unordered_map. You can check the current load factor using the load_factor() function:

#include <iostream>
#include <unordered_map>
#include <string>

int main() 
{
    std::unordered_map<std::string, int> wordFrequency;

    // Adding elements to the map
    wordFrequency["Why"]   = 11;
    wordFrequency["Where"] = 22;
    wordFrequency["How"]   = 33;

    std::cout << "Current Load Factor: " << wordFrequency.load_factor() << std::endl;

    return 0;
}

Output:

Current Load Factor: 0.230769

Here, you have 3 elements. If the number of buckets in the map is, say, 5, the load factor would be `3 / 5 = 0.6“.

What is Maximum Load Factor?

When the load factor of an unordered_map exceeds its maximum load factor (which is modifiable and usually set to 1.0 by default), the hash table undergoes a process called rehashing.

What is Rehashing?

  • The number of buckets in the hash table is increased, typically to the next prime number or a power of two.
  • All existing elements are rehashed (i.e., their position in the hash table is recalculated) to fit into the new bucket structure.

Impact of Rehashing on Performance:

  • Rehashing can momentarily affect performance since it is a relatively expensive operation.
  • However, it ensures that the performance of the hash table remains efficient in the long run by reducing the likelihood of collisions.

What happens after Rehashing?

  • The new load factor will be lower as the same number of elements are now distributed over a larger number of buckets.
  • This improves the performance of operations like insertion, deletion, and searching.

You can get and set this value of Maximum Load Factor of an unordered_map object using max_load_factor():

// Getting the maximum load factor
std::cout << "Default Maximum Load Factor: " << wordFrequency.max_load_factor() << std::endl;

// Setting a new maximum load factor
wordFrequency.max_load_factor(0.75);  // Set to 0.75
std::cout << "New Maximum Load Factor: " << wordFrequency.max_load_factor() << std::endl;

Output:

Default Maximum Load Factor: 1
New Maximum Load Factor: 0.75

Summary

The load factor of an unordered_map is an important metric determining the hash table’s efficiency and memory usage.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.