C++ STLのunordered_multimap::rehash()関数の使い方を徹底解説

C++ STLのunordered_multimap（およびunordered_map）が提供するrehash(N)関数は、コンテナ内のバケット数を引数n以上に設定するためのメンバ関数です。引数nが現在のバケット数よりも大きい場合、再ハッシュ（rehash）が強制的に実行され、新しいバケット数はnと等しいか、それ以上の値になります。

一方、引数nが現在のバケット数以下である場合は、バケット数に変化が生じず、再ハッシュも強制されません。つまり、この関数は「最低でもn個のバケットを確保する」という指示であり、戻り値は返しません。

構文

void rehash(size_type n);

パラメータ

• n: コンテナのハッシュテーブルに確保するバケット数の最小値を指定します。

動作のポイント

• nが現在のバケット数より大きい → バケット数が増やされ、全要素が再配置される（再ハッシュ発生）。
• nが現在のバケット数以下 → 何も起こらない可能性がある。
• 計算量は平均O(n)、最悪ケースでは要素数に比例する。

アルゴリズム

Begin
    空のマップコンテナmを宣言する。
    rehash()関数を呼び出し、コンテナのバケット数の下限を設定する。
    バケット数と同等以上のキーと値のペアをコンテナに挿入する。
    マップコンテナの要素を出力する。
End.

サンプルコード

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
   unordered_map<char, int> m;

   // バケット数の最小値を1に設定
   m.rehash(1);
   m.insert(pair<char, int>('b', 10));
   m.insert(pair<char, int>('a', 20));

   cout << "サイズ: " << m.size();
   cout << "\nキーと値: ";
   for (auto it = m.begin(); it != m.end(); it++) {
      cout << "{" << it->first << ", " << it->second << "} ";
   }
   return 0;
}

実行結果

サイズ: 2
キーと値: {a, 20} {b, 10}

コードの解説

まず空のunordered_mapコンテナmを宣言し、m.rehash(1)によってバケット数の最小値を1に設定しています。その後、2つのキーと値のペアを挿入すると、必要に応じてコンテナ側で自動的にバケットが拡張されます。最後に、範囲ベースのループでイテレータを使い、格納されたすべてのキーと値のペアを出力しています。

補足：関連する便利な関数

• bucket_count(): 現在のバケット数を取得できます。
• load_factor(): 要素数をバケット数で割った負荷率を確認できます。
• max_load_factor(): 再ハッシュが発生する負荷率の上限を設定・取得できます。

大量のデータを挿入することが事前に分かっている場合は、rehash()やreserve()を活用することで、挿入時の不要な再ハッシュを減らし、パフォーマンスを向上させることができます。