これは、C++23 で最も適切な連想コンテナ (辞書) を選択する方法に関するシリーズの第 2 部です。 が、このパートでは順序なしコンテナについて詳しく説明します。 第 1 部では順序付きコンテナについて説明しました 順序付けされていないコンテナ これらのコンテナは、キーの順序を定義していません。さらに、キーの順序は変更ごとに変わる可能性があるため、プログラムではそれに依存しないでください。このようなコンテナは常にハッシュ マップとして実装されます。 一般に、キーを追加、削除、または検索する場合、ハッシュ マップは最初にハッシュ関数を使用してそのキーから整数ハッシュ値を計算します。ハッシュ (またはその一部) は、連続する事前割り当て配列へのインデックスとして使用されます。この配列の各エントリは と呼ばれます。配列の一部のエントリは空で、一部は 1 つの要素を含み、一部はハッシュ衝突のために複数の要素にマップされる場合があります。これは、異なるキーが同じ配列インデックスを指すハッシュ値を持つ場合に発生します。ハッシュ マップは、ハッシュ衝突に対処するためにさまざまな戦略を利用します ( を参照)。ハッシュ マップ内の要素数を配列の合計サイズで割ったものを と呼びます。負荷係数が高くなるほど、新しく挿入された要素ごとにハッシュ衝突が発生する可能性が高くなります。 バケット この Wikipedia の記事 負荷係数 順序付きコンテナとは対照的に、ハッシュ マップは範囲クエリ、ランク付け/選択操作、キーの順序付けによる反復、および指定されたキーよりも小さい/大きいキーの検索をサポートしません。その代わりに、ハッシュ マップは達成可能な最高のパフォーマンスを実現します。検索/挿入/削除操作の時間計算量は です。ここで「償却」と言うのは、要素の数が大きくなりすぎると、ハッシュ マップは負荷係数を減らすためにその内容を再ハッシュする必要があるためです (実質的にバケット配列が大きくなります)。再ハッシュの時間計算量は です。ただし、これはめったに発生しないと予想されるため、平均すると、各操作は依然として です。パフォーマンスが低下する可能性があるもう 1 つの理由は、ハッシュ関数の分散が不十分で、衝突の頻度が高くなることです。 償却 O(1) O(n) O(1) 標準ハッシュマップ C++11 以降、標準ライブラリは次のハッシュ マップを提供します: ( )、 ( )、 ( )、 ( )。 キーと値を関連付けますが、 キーのみを格納し、キーがコンテナー内に存在するかどうかを確認するのに役立ちますが、関連付けられた値を取得することはできません。 コンテナーでは、複数の重複キーを格納できます。 std::unordered_map link std::unordered_set link std::unordered_multimap link std::unordered_multiset link マップは セットは マルチ すべての標準の順序なしコンテナはノードベースで、ハッシュ衝突に対処するために を使用します。つまり、各キーまたはキーと値のペアを個別のリンク リスト ノードに格納します。新しいノードごとにメモリが個別に割り当てられるため、特に効率的ではありません。また、各キー アクセスには追加の間接参照が必要になるため、データ構造は CPU キャッシュに適していません。unordered_map 内部構造は次のようになります。 セパレート チェーン unordered_map 左側には、固定サイズ (この例では ) に事前割り当てされたバケットの配列があります。最初は、すべてのバケットは空です。ハッシュ マップに要素を追加し始めると、いくつかのバケットが占有されます。上記の例では、キー の要素 (バケット に取得) と、キー と の 2 つの要素があり、ハッシュ値が衝突したため、両方とも同じバケット に取得されました。キー の要素もあり、これはバケット に取得されました。各バケットはリンク リストを指し、理想的には 1 つ以上の要素を含みません。バケット 、 、 、 、および は空で、 を指します。 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr キー の値を見つける必要があるとします。 256 まず、マップはキーハッシュを計算し、ハッシュ値をバケットの合計数（この場合は ）で割った余りを取得します。この例では、余りの値は です。 8 3 次に、マップはバケット が指すリンク リストの要素の読み取りを開始します。 3 最初の要素のキーは ですが、これは探している と同じではないため、マップは反復処理を続けます。次の要素のキーは ですが、これはまさに必要なものです。対応する値は です。 50 256 256 xyz キーが辞書にない場合、マップは空のバケットに到達するか、リンクされたリストを最後まで反復処理します。どちらの場合も、マップはキーが存在しないことを示す 反復子を返します。 end 各リストの最後の要素が次のリストの最初の要素を指していることに気付くかもしれません。これは、反復の効率を向上させるために、一部の実装で行われます。すべてのハッシュ マップ要素を反復処理するときにバケットごとにチェックする代わりに、これらの接続を使用して、空でないリンク リストから別の空でないリンク リストからより高速にジャンプできます。 上記のハッシュ マップにさらに要素を追加し続けると、ある時点で 高くなりすぎ (たとえば、80%)、ハッシュ マップは再ハッシュを決定します。事前に割り当てられた配列が拡張され (たとえば、 要素から 要素に)、既存のすべての要素のハッシュが再計算され、要素が新しいバケットに配置されます。 負荷係数が 8 16 標準コンテナは参照と反復子の安定性を保証しますが、順序付きコンテナが提供するものよりも弱いです。既存の要素への参照が無効になることはありません。既存の要素への反復子は、新しい要素の追加によって再ハッシュが発生する場合、または再ハッシュが手動でトリガーされた場合にのみ無効にできます。 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; } C++17 以降、順序なしコンテナーではノード操作が可能になりました。つまり、キーと値をコピーせずに、あるマップからノードを取得して別のマップに移動することが可能になりました。 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } } 上記のプログラムでは次のことが起こります: ハッシュ衝突に対処するもう 1 つの戦略は、 と呼ばれます。オープン アドレッシング ハッシュ マップでは、各バケットには最大 1 つの要素が格納されます。バケットがすでに使用されている場合、同じハッシュ値を持つ要素は他の空きバケットに移動します。このようなハッシュ マップは、連続したメモリ ブロック内の要素をグループ化して効率を向上させ、データ構造を CPU キャッシュに適したものにします。C++ 標準ライブラリではオープン アドレッシング ハッシュ マップは提供されていませんが、サードパーティの代替手段は多数あります。 オープン アドレッシング サードパーティのハッシュマップ 幅広いハッシュ マップ実装を提供する優れたライブラリです。 Boost.Unordered は、 、 、 、 があり、これらは コンテナの類似物であり、上記のすべてが適用されます。これらのコンテナは、反復効率を向上させるために、「バケット グループ」を使用した少し複雑な内部構造を使用します。 boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std このライブラリは、オープン アドレッシング コンテナーである 、 、 、 も提供します。内部構造は、オープン アドレッシング バリアントとは異なります。 boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map 内部構造の詳細については、 ご覧ください。 こちらのブログ投稿を ノードベースのコンテナー ( 、 ) は、バケットによってポイントされるノードを引き続き使用します。これらのコンテナーは、 コンテナーと同じ反復子と参照の安定性を保証し、ノード操作用の同じ API (つまり、 メソッド) も提供します。 boost::unordered_node_set boost::unordered_node_map std extract フラット コンテナー ( 、 ) では、キーと値はバケット配列に直接格納されます。フラット コンテナーは最も効率的ですが、保証は最も弱く、再ハッシュが発生すると、反復子とすべての要素への参照が無効になります。ノード操作 API はまったく提供されていません。フラット コンテナーは、特にキーまたは値の が大きい場合、ノードベースのコンテナーよりも多くのメモリを使用する可能性があります。 boost::unordered_flat_set boost::unordered_flat_map sizeof オープン アドレス コンテナーを実装する別のサードパーティ ライブラリは、 (Meta 提供) です。上記の Boost ライブラリ コンテナーに非常に近い辞書バリアントがいくつかあります。 Folly F14 と同じであり、 と同じです。 folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map と同じであり、 と同じです。 folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / キー/値を連続した配列にパックして保持し、バケットにはその配列へのインデックスが含まれます。 folly::F14VectorMap folly::F14VectorSet / は包括的なクラスです。指定したパラメータ (キーや値の型など) に基づいて、最も効率的な実装 ( または ) を選択します。 folly::F14FastMap folly::F14FastSet F14Value F14Vector F14 ハッシュ マップの興味深い追加の効率化機能は、 です。たとえば、同じキーを複数回検索する必要があり、そのハッシュ化にコストがかかる場合 (キーが文字列の場合など)、事前に一度ハッシュし、その後のすべてのハッシュ マップ呼び出しで 使用して、同じキーを複数回再ハッシュすることを避けることができます。出発点は、 メソッド ( ) です。 事前ハッシュ F14HashToken prehash リンク F14 ハッシュ コンテナーの内部構造の詳細については をご覧ください。 、この FB ブログ投稿 (Google 提供) も、オープン アドレス指定のノードベースおよびフラット ハッシュ コンテナを実装しています: 、 、 、 。これらは Boost や F14 のものと似ています。詳細については、 と 参照してください。 Abseil Swiss Tables ライブラリ absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set ここ ここを あまり知られていない ライブラリ ( ) は、ほとんどのシナリオで非常に効率的であると主張しています。このライブラリの作者は、さまざまなユースケースでの多くのハッシュマップの広範なベンチマーク結果を提供しています ( )。これらの結果に従うことはできますが、鵜呑みにしないでください。選択したハッシュマップは必ず実稼働環境でテストしてください。ベンチマークは常に合成であり、CPU とメモリがハッシュマップ操作以外の作業を行うケースはカバーされません。ベンチマークでは、ハッシュマップメモリのさまざまな部分が CPU キャッシュにない場合もカバーされませんが、これは実際のプログラムで頻繁に発生します。 ankerl github ブログ投稿 ハッシュ関数の品質 ハッシュ関数の品質は、検索操作の時間計算量を に保つために重要です。フラットハッシュマップはハッシュ関数の品質に特に敏感です。理想的なハッシュ関数は次のように定義できます。キーの 1 ビットが変更されると、対応するハッシュ値のビットの半分がランダムに変更されます。このようなハッシュ関数は と呼ばれます。 O(1) アバランシング 残念ながら、整数およびポインタ ハッシュ関数の C++ 標準ライブラリ実装の一部は非アバランシングです。たとえば、 、追加の変換を行わずに、ポインタまたは整数値を直接返します: 。 libstdc++ github や 実装などの高度なハッシュ テーブルでは、 特性を導入することでこの問題に対処しています。ハッシュ関数が avalanching であると宣言しない場合、ハッシュ テーブルはハッシュの品質を向上させるために追加の混合手順を実行します。これには余分なコストがかかります。カスタム ハッシュ関数を実装し、それが適切な品質であることがわかっている場合は、 に示すように avalanching としてマークできます。boost は プロパティ名を使用し、F14 プロパティは という名前です。理想的には、両方を追加する必要があります。 boost F14 hash_is_avalanching この例 is_avalanching folly_is_avalanching すぐに使用できるサポートされているキー タイプ (例: 、 、ポインター) と または によって提供されるデフォルトのハッシュ関数を使用する場合、それらはすでに必要に応じて正しくマークされているため、カスタム キー タイプを実装してカスタム ハッシュ関数を必要とする場合を除き、これについて考える必要はありません。 string int boost F14 スレッドの安全性 上記のコンテナはすべて一般にスレッドセーフではないため、あるスレッドがハッシュ マップにアクセスしたときに別のスレッドがハッシュ マップを変更する可能性がある場合は、外部同期 (たとえば、ミューテックスの使用) を実装する必要があります。 すべてのスレッドがマップのみを読み取る場合、同期は必要ありません。 でマークされたメソッドのみを呼び出すようにしてください。すべての非 メソッドはコンテナーを変更する可能性があります。operator ではないため、コンテナーを変更することに注意してください。マルチスレッド コードの一般的な落とし穴は次のとおりです。 const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } 上記のコードでは、 に対応する値が であるかどうかを確認することが目標です。ただし、 を に 。新しく追加された値は、デフォルト (上記の例では ) に設定されます。つまり、このようなコードはスレッドセーフではなく、あまり最適ではありません。同じ条件を確認するためのより効率的でスレッドセーフな方法は次のとおりです。 key true map["key"] key map 追加します false if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... } ここでは、まず「キー」によって識別される要素への反復子を取得します。 次に、要素がマップ内に存在するかどうかを確認します ( )。 it != map.end() 一致する場合は、最終的にその値をチェックします ( )。 it->second == true この例では、 と マップを変更せず、検索はスレッドセーフになります。キーがマップ内に存在するかどうかを確認することだけが目的であれば、単に 呼び出すだけで済みます。 find end map.contains("key") スレッドセーフな順序なしマップ スレッドセーフなハッシュマップの実装はいくつかあります。 1 つのオプションは、 の と です。Boost コンテナーは、C++ 標準ライブラリによって提供される API とは大きく異なる、訪問ベースの API を提供します。 Boost.Unordered ライブラリ boost::concurrent_flat_set boost::concurrent_flat_map もう一つの選択肢は ( ) です。Folly は、API を C++ 標準の順序なしコンテナーにできるだけ近づけようとします。 folly::ConcurrentHashMap github ロックフリー ハッシュ マップの実装をいくつか提供する大規模なロックフリー コンテナー ライブラリーです (例: 、 、 、 、 )。このライブラリーはしばらく更新されておらず、詳細なドキュメントも提供されていませんが、このライブラリーが提供するコンテナーはユニークなので、引き続き共有しています。ハッシュ マップの競合が激しいユースケースの場合は、 が提供するこれらのロックフリー ディクショナリをお試しください。 libcds は、 MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds 効率が問題にならない場合は、ミューテックスを使用して、スレッドセーフでないマップへのアクセスを同期できます。または、同時アクセスを完全に回避することもできます。これは、スレッドセーフなコンテナを使用したり、同期を追加したりするよりも効率的です。 どれを使えばいいですか？ 最適なコンテナの選び方をまとめたポイントを見てみましょう。 キーを値に関連付ける必要がある場合は 選択し、それ以外の場合は を使用します。 map を set マップ内に重複したキーを保持する必要がある場合は、 コンテナーを使用します。 マルチ 可能な限り厳密な反復子と参照の安定性の保証が必要な場合は、 、 、 、または ノードベースのコンテナー ( 、 、 、または など) を使用します。 と 最も効率的である可能性があります。 std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly 反復子と参照の安定性が重要でない場合 (つまり、反復子、参照、またはマップ/セット要素へのポインターを外部に保存しないか、マップが変更された後もそれらが有効なままであるとは想定しない) は、フラット コンテナー ( や など) を選択します。 boost::unordered_flat_map folly::F14FastMap フラット コンテナーは、特にキーや値の 大きい場合に、ノード ベースのコンテナーよりも多くのメモリを使用します。メモリ使用量が問題になる場合は、代わりにノード ベースのコンテナーを使用します。 sizeof F14 コンテナーは、効率性をさらに高めるために事前ハッシュ機能を提供します。同一キーを複数回検索/追加/削除する場合、F14 ではキーを事前ハッシュすることでハッシュ コストを節約できます。 上記のすべてのポイントは、シングルスレッド コンテナーの使用 (または同時変更のないマルチスレッド読み取りアクセス) に適用されます。マルチスレッドの変更が必要な場合は、上記のスレッドセーフ オプションのいずれかを選択します。実際の運用コードではパフォーマンスが異なる可能性があるため、アプリケーションでテストして結果を比較することを検討してください。
