これは、C++23 で最も適切な連想コンテナ (辞書) を選択する方法に関するシリーズの第 2 部です。 第 1 部では順序付きコンテナについて説明しましたが、このパートでは順序なしコンテナについて詳しく説明します。

順序付けされていないコンテナ

これらのコンテナは、キーの順序を定義していません。さらに、キーの順序は変更ごとに変わる可能性があるため、プログラムではそれに依存しないでください。このようなコンテナは常にハッシュ マップとして実装されます。

一般に、キーを追加、削除、または検索する場合、ハッシュ マップは最初にハッシュ関数を使用してそのキーから整数ハッシュ値を計算します。ハッシュ (またはその一部) は、連続する事前割り当て配列へのインデックスとして使用されます。この配列の各エントリはバケットと呼ばれます。配列の一部のエントリは空で、一部は 1 つの要素を含み、一部はハッシュ衝突のために複数の要素にマップされる場合があります。これは、異なるキーが同じ配列インデックスを指すハッシュ値を持つ場合に発生します。ハッシュ マップは、ハッシュ衝突に対処するためにさまざまな戦略を利用します (この Wikipedia の記事を参照)。ハッシュ マップ内の要素数を配列の合計サイズで割ったものを負荷係数と呼びます。負荷係数が高くなるほど、新しく挿入された要素ごとにハッシュ衝突が発生する可能性が高くなります。

順序付きコンテナとは対照的に、ハッシュ マップは範囲クエリ、ランク付け/選択操作、キーの順序付けによる反復、および指定されたキーよりも小さい/大きいキーの検索をサポートしません。その代わりに、ハッシュ マップは達成可能な最高のパフォーマンスを実現します。検索/挿入/削除操作の時間計算量は償却O(1)です。ここで「償却」と言うのは、要素の数が大きくなりすぎると、ハッシュ マップは負荷係数を減らすためにその内容を再ハッシュする必要があるためです (実質的にバケット配列が大きくなります)。再ハッシュの時間計算量はO(n)です。ただし、これはめったに発生しないと予想されるため、平均すると、各操作は依然としてO(1)です。パフォーマンスが低下する可能性があるもう 1 つの理由は、ハッシュ関数の分散が不十分で、衝突の頻度が高くなることです。

標準ハッシュマップ

C++11 以降、標準ライブラリは次のハッシュ マップを提供します: std::unordered_map ( link )、 std::unordered_set ( link )、 std::unordered_multimap ( link )、 std::unordered_multiset ( link )。マップはキーと値を関連付けますが、セットはキーのみを格納し、キーがコンテナー内に存在するかどうかを確認するのに役立ちますが、関連付けられた値を取得することはできません。マルチコンテナーでは、複数の重複キーを格納できます。

すべての標準の順序なしコンテナはノードベースで、ハッシュ衝突に対処するためにセパレート チェーンを使用します。つまり、各キーまたはキーと値のペアを個別のリンク リスト ノードに格納します。新しいノードごとにメモリが個別に割り当てられるため、特に効率的ではありません。また、各キー アクセスには追加の間接参照が必要になるため、データ構造は CPU キャッシュに適していません。unordered_map unordered_map内部構造は次のようになります。

左側には、固定サイズ (この例では8 ) に事前割り当てされたバケットの配列があります。最初は、すべてのバケットは空です。ハッシュ マップに要素を追加し始めると、いくつかのバケットが占有されます。上記の例では、キー10の要素 (バケット1に取得) と、キー50と256の 2 つの要素があり、ハッシュ値が衝突したため、両方とも同じバケット3に取得されました。キー3の要素もあり、これはバケット6に取得されました。各バケットはリンク リストを指し、理想的には 1 つ以上の要素を含みません。バケット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も提供します。内部構造は、オープン アドレッシング バリアントとは異なります。

内部構造の詳細については、こちらのブログ投稿をご覧ください。

ノードベースのコンテナー ( boost::unordered_node_set 、 boost::unordered_node_map ) は、バケットによってポイントされるノードを引き続き使用します。これらのコンテナーは、 stdコンテナーと同じ反復子と参照の安定性を保証し、ノード操作用の同じ API (つまり、 extractメソッド) も提供します。

フラット コンテナー ( boost::unordered_flat_set 、 boost::unordered_flat_map ) では、キーと値はバケット配列に直接格納されます。フラット コンテナーは最も効率的ですが、保証は最も弱く、再ハッシュが発生すると、反復子とすべての要素への参照が無効になります。ノード操作 API はまったく提供されていません。フラット コンテナーは、特にキーまたは値のsizeofが大きい場合、ノードベースのコンテナーよりも多くのメモリを使用する可能性があります。

オープン アドレス コンテナーを実装する別のサードパーティ ライブラリは、 Folly F14 (Meta 提供) です。上記の Boost ライブラリ コンテナーに非常に近い辞書バリアントがいくつかあります。

• 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 ブログ投稿をご覧ください。

Abseil Swiss Tablesライブラリ(Google 提供) も、オープン アドレス指定のノードベースおよびフラット ハッシュ コンテナを実装しています: absl::flat_hash_map 、 absl::flat_hash_set 、 absl::node_hash_map 、 absl::node_hash_set 。これらは Boost や F14 のものと似ています。詳細については、こことここを参照してください。

あまり知られていないankerlライブラリ ( github ) は、ほとんどのシナリオで非常に効率的であると主張しています。このライブラリの作者は、さまざまなユースケースでの多くのハッシュマップの広範なベンチマーク結果を提供しています (ブログ投稿)。これらの結果に従うことはできますが、鵜呑みにしないでください。選択したハッシュマップは必ず実稼働環境でテストしてください。ベンチマークは常に合成であり、CPU とメモリがハッシュマップ操作以外の作業を行うケースはカバーされません。ベンチマークでは、ハッシュマップメモリのさまざまな部分が CPU キャッシュにない場合もカバーされませんが、これは実際のプログラムで頻繁に発生します。

ハッシュ関数の品質

ハッシュ関数の品質は、検索操作の時間計算量をO(1)に保つために重要です。フラットハッシュマップはハッシュ関数の品質に特に敏感です。理想的なハッシュ関数は次のように定義できます。キーの 1 ビットが変更されると、対応するハッシュ値のビットの半分がランダムに変更されます。このようなハッシュ関数はアバランシングと呼ばれます。

残念ながら、整数およびポインタ ハッシュ関数の C++ 標準ライブラリ実装の一部は非アバランシングです。たとえば、 libstdc++ 、追加の変換を行わずに、ポインタまたは整数値を直接返します: github 。

boostやF14実装などの高度なハッシュ テーブルでは、 hash_is_avalanching特性を導入することでこの問題に対処しています。ハッシュ関数が avalanching であると宣言しない場合、ハッシュ テーブルはハッシュの品質を向上させるために追加の混合手順を実行します。これには余分なコストがかかります。カスタム ハッシュ関数を実装し、それが適切な品質であることがわかっている場合は、 この例に示すように avalanching としてマークできます。boost はis_avalanchingプロパティ名を使用し、F14 プロパティはfolly_is_avalanchingという名前です。理想的には、両方を追加する必要があります。

すぐに使用できるサポートされているキー タイプ (例: string 、 int 、ポインター) とboostまたはF14によって提供されるデフォルトのハッシュ関数を使用する場合、それらはすでに必要に応じて正しくマークされているため、カスタム キー タイプを実装してカスタム ハッシュ関数を必要とする場合を除き、これについて考える必要はありません。

スレッドの安全性

上記のコンテナはすべて一般にスレッドセーフではないため、あるスレッドがハッシュ マップにアクセスしたときに別のスレッドがハッシュ マップを変更する可能性がある場合は、外部同期 (たとえば、ミューテックスの使用) を実装する必要があります。

すべてのスレッドがマップのみを読み取る場合、同期は必要ありません。 constでマークされたメソッドのみを呼び出すようにしてください。すべての非constメソッドはコンテナーを変更する可能性があります。operator 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.Unordered ライブラリのboost::concurrent_flat_setとboost::concurrent_flat_mapです。Boost コンテナーは、C++ 標準ライブラリによって提供される API とは大きく異なる、訪問ベースの API を提供します。
• もう一つの選択肢はfolly::ConcurrentHashMap ( github ) です。Folly は、API を C++ 標準の順序なしコンテナーにできるだけ近づけようとします。
• 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 ではキーを事前ハッシュすることでハッシュ コストを節約できます。
• 上記のすべてのポイントは、シングルスレッド コンテナーの使用 (または同時変更のないマルチスレッド読み取りアクセス) に適用されます。マルチスレッドの変更が必要な場合は、上記のスレッドセーフ オプションのいずれかを選択します。実際の運用コードではパフォーマンスが異なる可能性があるため、アプリケーションでテストして結果を比較することを検討してください。