C++ Standard Library C++ STL Library

C++ unordered_set - rehash() Function



The C++ unordered_set::rehash function is used to set the number of buckets in the unordered_set 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_set 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_set::rehash function is used to set the number of buckets in uSet container.

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main (){
  unordered_set<int> uSet{55, 25, 128};

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

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

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

  return 0;
}

The output of the above code will be:

uSet contains 3 buckets:
The bucket #0 contains: 
The bucket #1 contains: 25 55 
The bucket #2 contains: 128 

Number of buckets is changed using rehash function.

uSet contains 5 buckets:
The bucket #0 contains: 55 25 
The bucket #1 contains: 
The bucket #2 contains: 
The bucket #3 contains: 128 
The bucket #4 contains: 

❮ C++ <unordered_set> Library

5