hopscotch map

石けり遊びハッシュを使用した高速ハッシュ マップとハッシュ セットの C++ 実装

石けり遊びマップ ライブラリは、オープン アドレッシングと石けり遊びハッシュを使用して衝突を解決する高速ハッシュ マップとハッシュ セットの 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 つは代わりにプライム成長ポリシーを使用し、貧弱なハッシュ関数にうまく対処できます。ハッシュの下位ビットでパターンが繰り返される可能性がある場合は、プライム バージョンを使用してください (たとえば、アイデンティティ ハッシュ関数を使用してポインターを保存している場合)。詳細については、「成長ポリシー」を参照してください。

これらのクラスに加えて、ライブラリは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>使用するマップがある場合、キー パラメーターとしてfoo*またはstd::uintptr_tを使用できます)。 std::unique_ptr<foo>を構築せずにfind 。例を参照してください)。
• キーからセンチネル値を予約する必要はありません。
• ハッシュまたはキー等価関数の計算にコストがかかる場合、再ハッシュと検索を高速化するために、挿入時にハッシュ値を保存する可能性があります (StoreHash テンプレート パラメーターを参照)。
• 検索前にハッシュがわかっている場合は、それをパラメータとして渡して検索を高速化できます (API のprecalculated_hashパラメータを参照)。
• tsl::bhopscotch_mapおよびtsl::bhopscotch_set検索および削除で最悪の場合 O(log n) を提供し、これらのクラスをハッシュ テーブルのサービス拒否 (DoS) 攻撃に耐性のあるものにします (例の詳細を参照)。
• このライブラリは、例外を無効にして使用できます (Clang および GCC では-fno-exceptionsオプションを使用するか、MSVC では/EHオプションを使用しないか、単にTSL_NO_EXCEPTIONS定義することによって)。 std::terminate例外が無効な場合にthrow命令の代わりに使用されます。
• 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> への参照とポインタを返すため、値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 % 2 nの代わりにhash & (2 n - 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 {
    // Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
    // that the hash table needs. The policy can change it to a higher number of buckets if needed 
    // and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
    // must stay at 0.
    explicit custom_policy (std:: size_t & min_bucket_count_in_out);
    
    // Return the bucket [0, bucket_count()) to which the hash belongs. 
    // If bucket_count() is 0, it must always return 0.
    std:: size_t bucket_for_hash (std:: size_t hash) const noexcept ;
    
    // Return the number of buckets that should be used on next growth
    std:: size_t next_bucket_count () const ;
    
    // Maximum number of buckets supported by the policy
    std:: size_t max_bucket_count () const ;
    
    // Reset the growth policy as if the policy was created with a bucket count of 0.
    // After a clear, the policy must always return 0 when bucket_for_hash() is called.
    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 directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map)  

プロジェクトがmake installによってインストールされている場合は、 add_subdirectoryの代わりにfind_package(tsl-hopscotch-map REQUIRED)を使用することもできます。

コードは、C++17 標準に準拠したコンパイラで動作する必要があります。

テストを実行するには、Boost Test ライブラリと CMake が必要です。

git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests 

使用法

API はここにあります。

すべてのメソッドはまだ文書化されていませんが、特に指定されていない限り、 std::unordered_mapおよびstd::unordered_setのメソッドの動作を複製します。

例

# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >

int main () {
    tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
    map[ " c " ] = 3 ;
    map[ " d " ] = 4 ;
    
    map. insert ({ " e " , 5 });
    map. erase ( " b " );
    
    for ( auto it = map. begin (); it != map. end (); ++it) {
        // it->second += 2; // Not valid.
        it. value () += 2 ;
    }
    
    // {d, 6} {a, 3} {e, 7} {c, 5}
    for ( const auto & key_value : map) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
        
    if (map. find ( " a " ) != map. end ()) {
        std::cout << " Found " a " . " << std::endl;
    }
    
    const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
    // If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
    if (map. find ( " a " , precalculated_hash) != map. end ()) {
        std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
    }
    
    
    /*
     * Calculating the hash and comparing two std::string may be slow. 
     * We can store the hash of each std::string in the hash map to make 
     * the inserts and lookups faster by setting StoreHash to true.
     */ 
    tsl::hopscotch_map<std::string, int , std::hash<std::string>, 
                       std::equal_to<std::string>,
                       std::allocator<std::pair<std::string, int >>,
                       30 , true > map2;
                       
    map2[ " a " ] = 1 ;
    map2[ " b " ] = 2 ;
    
    // {a, 1} {b, 2}
    for ( const auto & key_value : map2) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
    
    
    
    tsl::hopscotch_set< int > set;
    set. insert ({ 1 , 9 , 0 });
    set. insert ({ 2 , - 1 , 9 });
    
    // {0} {1} {2} {9} {-1}
    for ( const auto & key : set) {
        std::cout << " { " << key << " } " << std::endl;
    }
} 

異種ルックアップ

異種オーバーロードでは、使用される型がハッシュ可能でKeyと同等である限り、ルックアップおよび消去操作にKey以外の型を使用できます。

tsl::hopscotch_map/setで異種オーバーロードをアクティブにするには、修飾 ID KeyEqual::is_transparentが有効である必要があります。 std::map::findと同じように機能します。 std::equal_to<>を使用するか、独自の関数オブジェクトを定義することができます。

KeyEqualとHash両方とも、さまざまなタイプを処理できる必要があります。

# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >


struct employee {
    employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
    }
    
    // Either we include the comparators in the class and we use `std::equal_to<>`...
    friend bool operator ==( const employee& empl, int empl_id) {
        return empl. m_id == empl_id;
    }
    
    friend bool operator ==( int empl_id, const employee& empl) {
        return empl_id == empl. m_id ;
    }
    
    friend bool operator ==( const employee& empl1, const employee& empl2) {
        return empl1. m_id == empl2. m_id ;
    }
    
    
    int m_id;
    std::string m_name;
};

// ... or we implement a separate class to compare employees.
struct equal_employee {
    using is_transparent = void ;
    
    bool operator ()( const employee& empl, int empl_id) const {
        return empl. m_id == empl_id;
    }
    
    bool operator ()( int empl_id, const employee& empl) const {
        return empl_id == empl. m_id ;
    }
    
    bool operator ()( const employee& empl1, const employee& empl2) const {
        return empl1. m_id == empl2. m_id ;
    }
};

struct hash_employee {
    std:: size_t operator ()( const employee& empl) const {
        return std::hash< int >()(empl. m_id );
    }
    
    std:: size_t operator ()( int id) const {
        return std::hash< int >()(id);
    }
};


int main () {
    // Use std::equal_to<> which will automatically deduce and forward the parameters
    tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map; 
    map. insert ({ employee ( 1 , " John Doe " ), 2001 });
    map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
    map. insert ({ employee ( 3 , " John Smith " ), 2003 });

    // John Smith 2003
    auto it = map. find ( 3 );
    if (it != map. end ()) {
        std::cout << it-> first . m_name << " " << it-> second << std::endl;
    }

    map. erase ( 1 );



    // Use a custom KeyEqual which has an is_transparent member type
    tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
    map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });

    // 2004
    std::cout << map2. at ( 4 ) << std::endl;
} 

サービス拒否 (DoS) 攻撃

tsl::hopscotch_mapとtsl::hopscotch_setに加えて、ライブラリはさらに 2 つの「安全な」オプションtsl::bhopscotch_mapとtsl::bhopscotch_set (すべて対応するpgとともに) を提供します。

これら 2 つの追加では、検索と削除については最悪の漸近複雑度 O(log n) があり、挿入については償却された最悪のケースとして O(log n) になります (O(n) になる再ハッシュの可能性があるため償却されます)。 。ハッシュ関数がすべての要素を同じバケットにマッピングした場合でも、O(log n) は保持されます。

これにより、ハッシュ テーブルのサービス拒否 (DoS) 攻撃に対するセキュリティが提供されます。

これを実現するために、安全なバージョンではオーバーフロー要素に対して二分探索ツリーを使用するため (実装の詳細を参照)、要素がLessThanComparableである必要があります。追加のCompareテンプレート パラメータが必要です。

# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >

/*
 * Poor hash function which always returns 1 to simulate
 * a Deny of Service attack.
 */
struct dos_attack_simulation_hash {
    std:: size_t operator ()( int id) const {
        return 1 ;
    }
};

int main () {
    /*
     * Slow due to the hash function, insertions are done in O(n).
     */
    tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map. insert ({i, 0 });
    }
    auto end = std::chrono::high_resolution_clock::now ();
    
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
    
    
    
    
    /*
     * Faster. Even with the poor hash function, insertions end-up to
     * be O(log n) in average (and O(n) when a rehash occurs).
     */
    tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map_secure. insert ({i, 0 });
    }
    end = std::chrono::high_resolution_clock::now ();
    
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
} 

ライセンス

このコードは MIT ライセンスに基づいてライセンスされています。詳細については、LICENSE ファイルを参照してください。