ホップスコッチハッシングを用いた高速ハッシュマップとハッシュセットのC++実装

ホップスコッチハッシングを用いた高速ハッシュマップとハッシュセットのC++実装。hopscotch-mapライブラリは、オープンアドレス指定とホップスコッチハッシングを使用して衝突を解決する、高速なハッシュマップとハッシュセットのC++実装です。これはキャッシュフレンドリーなデータ構造で、ほとんどの場合std::unordered_mapよりも優れたパフォーマンスを提供し、google::dense_hash_mapに非常に似ていますが、メモリ使用量が少なく、より多くの機能を提供します。 ライブラリは以下の主要なクラスを提供します：tsl::hopscotch_map、tsl::hopscotch_set、tsl::hopscotch_pg_map、tsl::hopscotch_pg_set。最初の2つは高速で2のべき乗成長ポリシーを使用し、後の2つは代わりに素数成長ポリシーを使用し、貧弱なハッシュ関数にもよりよく対応できます。ハッシュの下位ビットに繰り返しパターン（例：同一性ハッシュ関数を持つポインタを格納している場合）がある可能性がある場合は、素数バージョンを使用してください。詳細はGrowthPolicyを参照してください。 これらのクラスに加えて、ライブラリはtsl::bhopscotch_map、tsl::bhopscotch_set、tsl::bhopscotch_pg_map、tsl::bhopscotch_pg_setも提供します。これらのクラスはキーに追加の要件（LessThanComparableであること）がありますが、より優れた漸近的上限を提供します。詳細は例を参照してください。ただし、特定の要件（ハッシュDoS攻撃のリスクなど）がない場合、tsl::hopscotch_mapとtsl::hopscotch_setはほとんどの場合で十分であり、一般的にパフォーマンスが優れているためデフォルトの選択肢とすべきです。 ホップスコッチハッシングの概要と実装の詳細は、こちらを参照してください。tsl::hopscotch_mapと他のハッシュマップのベンチマークは、こちらで確認できます。このページでは、ユースケースに試すべきハッシュテーブル構造に関するアドバイスも提供されています（tsl名前空間の複数のハッシュテーブル実装に少し戸惑っている場合に役立ちます）。 主要機能 ヘッダーオンリーライブラリ。インクルードディレクトリをインクルードパスに追加するだけで準備完了です。CMakeを使用している場合、CMakeLists.txtからエクスポートされたtsl::hopscotch_mapターゲットも使用できます。 高速ハッシュテーブル。数値についてはベンチマークを参照してください。 ムーブオンリーおよびデフォルト構築不可能なキー/値のサポート。 異なる型のKeyでfindを使用できる異種ルックアップのサポート（例：std::unique_ptr<foo>をキーとして使用するマップがある場合、std::unique_ptr<foo>を構築せずにfoo*またはstd::uintptr_tをキーパラメータとしてfindに使用できます。例を参照）。 キーから番兵値を予約する必要はありません。 ハッシュまたはキーの比較関数が高価な場合に、高速なリハッシュとルックアップのために挿入時にハッシュ値を格納する可能性（StoreHashテンプレートパラメータを参照）。 ルックアップ前にハッシュがわかっている場合、ルックアップを高速化するためにパラメータとして渡すことができます（APIのprecalculated_hashパラメータを参照）。 tsl::bhopscotch_mapとtsl::bhopscotch_setは、ルックアップと削除で最悪の場合O(log n)を提供し、これらのクラスをハッシュテーブルのサービス拒否（DoS）攻撃に対して耐性を持たせます（詳細は例を参照）。 ライブラリは、例外を無効にした状態（ClangおよびGCCでは-fno-exceptionsオプション、MSVCでは/EHオプションなし、またはTSL_NO_EXCEPTIONSを定義するだけ）で使用できます。例外が無効な場合、throw命令の代わりにstd::terminateが使用されます。 APIはstd::unordered_mapおよびstd::unordered_setに非常に似ています。 std::unordered_mapとの違い tsl::hopscotch_mapはstd::unordered_mapに似たインターフェースを持とうとしますが、いくつかの違いがあります。挿入時のイテレータ無効化の動作が異なります。一般に、eraseを除くハッシュテーブルを変更する操作は、すべてのイテレータを無効にします（詳細はAPIを参照）。マップ内のキーまたは値への参照およびポインタは、挿入時にこれらのキーと値へのイテレータと同じ方法で無効になります。イテレータの場合、operator*()とoperator->()は、std::pair<const Key, T>ではなく、const std::pair<Key, T>への参照とポインタを返します。これにより、値Tは変更できません。値を変更するには、イテレータのvalue()メソッドを呼び出してミュータブルな参照を取得する必要があります。例： tsl::hopscotch_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}}; for(auto it = map.begin(); it != map.end(); ++it) { //it->second = 2; // Illegal it.value() = 2; // Ok } ムーブオンリー型は、nothrowムーブコンストラクタを持っている必要があります（オープンアドレス指定では、ムーブコンストラクタが例外をスローする可能性がある場合、リハッシュで強い例外保証を維持することはできません）。 一部のバケット関連メソッド（bucket_size、bucketなど）はサポートされていません。 これらの違いは、std::unordered_setとtsl::hopscotch_setの間にも適用されます。 スレッドセーフティと例外保証はstd::unordered_map/setと同じです（つまり、書き込みがなければ複数のリーダーが可能です）。 成長ポリシー ライブラリは、GrowthPolicyテンプレートパラメータを通じて複数の成長ポリシーをサポートしています。ライブラリによって3つのポリシーが提供されていますが、必要に応じて独自のポリシーを簡単に実装できます。 tsl::hh::power_of_two_growth_policy。tsl::(b)hopscotch_map/setでデフォルトで使用されるポリシーです。このポリシーは、ハッシュテーブルのバケット配列のサイズを2のべき乗に保ちます。この制約により、ポリシーはハッシュをバケットにマッピングするための遅い剰余演算の使用を回避し、hash % 2nの代わりにhash & (2n - 1)を使用します（高速剰余を参照）。高速ですが、2のべき乗での剰余は最終的に最上位ビットをマスクするだけなので、貧弱なハッシュ関数では多くの衝突を引き起こす可能性があります。 tsl::hh::prime_growth_policy。tsl::(b)hopscotch_pg_map/setでデフォルトで使用されるポリシーです。このポリシーは、ハッシュテーブルのバケット配列のサイズを素数に保ちます。ハッシュをバケットにマッピングする際に素数を剰余として使用すると、貧弱なハッシュ関数でもハッシュのバケット全体への分布が向上します。コンパイラが剰余演算を最適化できるように、ポリシーは定数素数の剰余を持つルックアップテーブルを使用します（APIで詳細を参照）。tsl::hh::power_of_two_growth_policyよりも遅いですが、より安全です。 tsl::hh::mod_growth_policy。このポリシーは、パラメータで渡されたカスタマイズ可能な成長ファクターによってマップを成長させます。そして、ハッシュをバケットにマッピングするために剰余演算子を使用します。遅いですが、より柔軟です。 パフォーマンスが低い場合は、overflow_size()を確認してください。ゼロでない場合は、多くのハッシュ衝突が発生している可能性があります。ハッシュ関数をより均一なものに変更するか、別の成長ポリシー（主にtsl::hh::prime_growth_policy）を試してください。残念ながら、衝突から身を守ることは困難な場合があります（例：ハッシュマップに対するDoS攻撃）。必要に応じて、ルックアップでO(n)ではなく最悪の場合O(log n)を提供するtsl::bhopscotch_map/setも確認してください。詳細は例を参照してください。 独自のポリシーを実装するには、以下のインターフェースを実装する必要があります。 struct custom_policy { // ハッシュテーブルの構築とリハッシュ時に呼び出されます。min_bucket_count_in_outは、ハッシュテーブルが必要とする最小のバケット数です。 // ポリシーは必要に応じてより高いバケット数に変更でき、ハッシュテーブルはこの値をバケット数として使用します。0バケットが要求された場合、値は常に0である必要があります。 explicit custom_policy(std::size_t& min_bucket_count_in_out); // ハッシュが属するバケット[0, bucket_count())を返します。 // bucket_count()が0の場合、常に0を返す必要があります。 std::size_t bucket_for_hash(std::size_t hash) const noexcept; // 次の成長で使用すべきバケット数を返します。 std::size_t next_bucket_count() const; // ポリシーでサポートされる最大バケット数 std::size_t max_bucket_count() const; // ポリシーが0のバケット数で作成されたかのように成長ポリシーをリセットします。 // clear後、bucket_for_hash()が呼び出されたときにポリシーは常に0を返す必要があります。 void clear() noexcept; } インストール hopscotch-mapを使用するには、インクルードディレクトリをインクルードパスに追加するだけです。これはヘッダーオンリーライブラリです。CMakeを使用している場合、target_link_librariesと共にCMakeLists.txtからエクスポートされたtsl::hopscotch_mapターゲットも使用できます。 # Example where the hopscotch-map project is stored in a third-party dir