C++ Standard Library C++ STL Library

C++ unordered_multimap - rehash() Function



The C++ unordered_multimap::rehash function is used to set the number of buckets in the unordered_multimap 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_multimap 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

void rehash (size_type n);

Parameters

n Specify the minimum number of buckets for the container hash table.

Return Value

None.

Time Complexity

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

Example:

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

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

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

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

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

  return 0;
}

The output of the above code will be:

uMMap 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:Toronto CAN:Ottawa 

Number of buckets is changed using rehash function.

uMMap contains 7 buckets:
The bucket #0 contains: USA:Washington 
The bucket #1 contains: 
The bucket #2 contains: 
The bucket #3 contains: IND:Delhi 
The bucket #4 contains: 
The bucket #5 contains: 
The bucket #6 contains: CAN:Toronto CAN:Ottawa 

❮ C++ <unordered_map> Library