C++ unordered_map - rehash() Function

The C++ unordered_map::rehash function is used to set the number of buckets in the unordered_map container to specified number (n) or more. If n is greater than the current number of buckets in the container (its bucket_count), a rehash is forced. The new bucket count will be either equal to or greater than n. A rehash may not be forced, if n is less than the current number of buckets in the container. A rehash is the reconstruction of the hash table in which all elements of the container is rearranged according to their hash values into the new set of buckets.

As an unordered_map is implemented using hash table where a bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value. The number of buckets directly influences the load_factor of the container's hash table. The container automatically increases the number of buckets to keep the load_factor below its max_load_factor which causes rehash whenever the number of buckets is increased.

Syntax

• C++11

void rehash (size_type n);

Parameters

Return Value

None.

Time Complexity

Average case: Linear i.e, Θ(n).
Worst case: Quadratic i.e, Θ(n²).

Example:

In the example below, the unordered_map::rehash function is used to set the number of buckets in uMap container.

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main (){
  unordered_map<string, string> uMap;
  uMap = {{"CAN", "Ottawa"}, {"USA", "Washington"}, {"IND", "Delhi"}};

  cout<<"uMap contains "<<uMap.bucket_count()<<" buckets:";
  for(unsigned int i = 0; i < uMap.bucket_count(); i++) {
    cout<<"\nThe bucket #"<<i<<" contains: ";   
    for(auto it = uMap.begin(i); it != uMap.end(i); ++it) {
      cout<<it->first<<":"<<it->second<<" ";
    } 
  }  

  cout<<"\n\nNumber of buckets is changed using rehash function.\n\n";
  uMap.rehash(5);

  cout<<"uMap contains "<<uMap.bucket_count()<<" buckets:";
  for(unsigned int i = 0; i < uMap.bucket_count(); i++) {
    cout<<"\nThe bucket #"<<i<<" contains: ";   
    for(auto it = uMap.begin(i); it != uMap.end(i); ++it) {
      cout<<it->first<<":"<<it->second<<" ";
    } 
  } 

  return 0;
}

The output of the above code will be:

uMap contains 13 buckets:
The bucket #0 contains: 
The bucket #1 contains: 
The bucket #2 contains: 
The bucket #3 contains: 
The bucket #4 contains: 
The bucket #5 contains: 
The bucket #6 contains: 
The bucket #7 contains: 
The bucket #8 contains: 
The bucket #9 contains: 
The bucket #10 contains: USA:Washington 
The bucket #11 contains: IND:Delhi 
The bucket #12 contains: CAN:Ottawa 

Number of buckets is changed using rehash function.

uMap contains 5 buckets:
The bucket #0 contains: 
The bucket #1 contains: 
The bucket #2 contains: CAN:Ottawa IND:Delhi 
The bucket #3 contains: USA:Washington 
The bucket #4 contains: