C++11 の std::unordered_map コンテナーでパフォーマンス ベンチマークを実行しようとしています。
コンテナーの負荷率が挿入のパフォーマンスにどのように影響するかを確認したいと考えています。具体的には、膨大な数のセットでペアを見つけるための基本データ構造としてハッシュ テーブルを使用することに興味があるためです。
ドキュメントを理解しているので、これは不可能のようです。でバケットの量を設定できますが、これはを超えるとrehash()自動的に行われます。max_load_factor
を設定することはできますmax_load_factorが、私が理解しているように、これは再ハッシュがいつ実行されるかを決定するだけであり、テーブルに大きな負担をかけることはできません。これは私がやりたいことです。
ハッシュ テーブル内のバケットの量を厳密に制限する方法はありますか?
これが良い答えかどうかはわかりませんが、それが不可能な理由の説明です。
オープン アドレッシングを使用している場合は、する必要がありますがresize、これは実装上の詳細です。チェーン衝突解決を使用して実装を行い、チェーンの長さに制限を設け、違反した場合はサイズを変更できます。ボンネットの下で多くのことが起こる可能性があります。
つまり、ユーザーの観点からは、一部の実装が爆発する可能性があるため、バケットの数を安全に修正できるという保証はありません。負荷率を高くしても、ターゲット バケットがいっぱいになるとテーブルのサイズを変更しなければならない場合があり、それ以外の場合は要素を受け入れることができません。これは、負荷率が比較的低い場合でも発生する可能性があります。
もちろん、一部の実装では、任意に大きな負荷係数を処理できますが、これは一般的なプロパティではありません。
要するに、バケットの数を固定することは、一般的にはあまり意味がありません。とにかく、サイズ変更のポイントまでしか実験できません。これは、キーの配布に応じて、さまざまな負荷要因に必要になる場合があります。基本的に、実装ごとに任意の高負荷をテストすることはできません。