HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

A C++ implementation of a fast hash map and hash set using hopscotch hashing (github.com)

95 pointsby gjvc16 コメント

要約

hopscotch-mapライブラリは、ホップスコッチハッシングとオープンアドレス指定を使用して衝突を解決する、高速なC++ハッシュマップおよびハッシュセットの実装です。std::unordered_mapよりも優れたパフォーマンスを提供し、google::dense_hash_mapに似ていますが、メモリ使用量が少なく、より多くの機能を提供します。このライブラリは、様々な成長ポリシーと高度な機能を提供し、柔軟な使用を可能にします。

全文翻訳

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

[画像: CI](https://github.com/Tessil/hopscotch-map/actions/workflows/ci.yml)

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攻撃のセクションを参照してください。ただし、特定の要件(ハッシュDoS攻撃のリスク)がない場合は、ほとんどの場合 tsl::hopscotch_map と tsl::hopscotch_set で十分であり、一般的により優れたパフォーマンスを発揮するため、これらをデフォルトで選択すべきです。

ホップスコッチハッシングの概要と実装の詳細については、こちらをご覧ください。

他のハッシュマップとのベンチマークはこちらで見つけることができます。このページには、ユースケースにどのハッシュテーブル構造を試すべきかについてのいくつかのアドバイスも記載されています(tsl 名前空間の複数のハッシュテーブル実装で迷っている場合に役立ちます)。

主な機能
  • ヘッダーオンリーライブラリです。include ディレクトリをインクルードパスに追加するだけで準備完了です。CMakeを使用している場合は、CMakeLists.txtからエクスポートされた tsl::hopscotch_map ターゲットを使用することもできます。
  • 高速なハッシュテーブルです。パフォーマンスについてはベンチマークを参照してください。
  • ムーブオンリー型およびデフォルト構築不可能なキー/値のサポート。
  • ヘテロジニアスルックアップ(heterogeneous lookups)のサポート。これにより、find 操作で Key とは異なる型を使用できます(例: std::unique_ptr<foo> をキーとして使用するマップで、foo* や std::uintptr_t を find のキーパラメータとして使用し、std::unique_ptr<foo> を構築せずに済みます。詳細は例を参照してください)。
  • キーからセンチネル値を予約する必要がありません。
  • ハッシュ値またはキーの等価性比較関数が高価な場合に、挿入時にハッシュ値を格納して、リハッシュやルックアップを高速化できます(StoreHashテンプレートパラメータを参照)。
  • ルックアップ前にハッシュ値がわかっている場合、それをパラメータとして渡すことでルックアップを高速化できます(APIのprecalculated_hashパラメータを参照)。
  • tsl::bhopscotch_map および tsl::bhopscotch_set は、ルックアップと削除において最悪でO(log n)の複雑さを持ち、これらのクラスはハッシュテーブルのサービス拒否(DoS)攻撃に対して耐性があります(例の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() メソッドを呼び出してミュータブルな参照を取得する必要があります。例:
ts l::hopscotch_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};
for(auto it = map.begin(); it != map.end(); ++it) {
    //it->second = 2; // 無効
    it.value() = 2; // OK
}
  • ムーブオンリー型は、例外を投げないムーブコンストラクタを持つ必要があります(オープンアドレス方式では、ムーブコンストラクタが例外を投げる可能性がある場合、リハッシュ時の強力な例外保証を維持することはできません)。
  • バケット関連のメソッド(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攻撃)から完全に保護することは難しい場合があります。必要に応じて、tsl::bhopscotch_map/set も確認してください。これらは、ルックアップにおいて最悪の場合O(log n)の複雑さを提供します(O(n)ではなく)。詳細は例のDoS攻撃を参照してください。

独自のポリシーを実装するには、以下のインターフェースを実装する必要があります。

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を使用するには、include ディレクトリをインクルードパスに追加するだけです。これはヘッダーオンリーライブラリです。

CMakeを使用している場合は、CMakeLists.txtからエクスポートされた tsl::hopscotch_map ターゲットを target_link_libraries で使用することもできます。

# hopscotch-map プロジェクトが third-party ディレクトリに保存されている例
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; // 無効です。
        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(map.find("a", precalculated_hash) != map.end()) {
        std::cout << "Found \"a\" with hash " << precalculated_hash << "." << std::endl;
    }
    
    
    /*
     * std::string のハッシュ計算と比較は遅い場合があります。
     * StoreHash を true に設定することで、ハッシュマップに各 std::string のハッシュ値を格納し、
     * 挿入とルックアップを高速化できます。
     */ 
    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;
    }
}
ヘテロジニアスルックアップ

ヘテロジニアスオーバーロード(Heterogeneous overloads)により、使用される型が Key とハッシュ可能かつ比較可能である限り、ルックアップおよび削除操作に Key 以外の型を使用できます。これは 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)) {
    }
    
    // ここでコンパレータをクラスに含めるか、別のクラスを実装します。
    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;
};

// ... または、従業員を比較するための別のクラスを実装します。
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() {
    // 型を自動的に推論して転送する std::equal_to<> を使用します。
    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);



    // is_transparent メンバー型を持つカスタム KeyEqual を使用します。
    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>

/*
 * サービス拒否攻撃をシミュレートするために、常に1を返す貧弱なハッシュ関数。
 */
struct dos_attack_simulation_hash {
    std::size_t operator()(int id) const {
        return 1;
    }
};

int main() {
    /*
     * ハッシュ関数のため低速。挿入は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;
    
    
    
    
    /*
     * より高速です。貧弱なハッシュ関数でも、挿入は
     * 平均でO(log n)になります(リハッシュが発生する場合はO(n))。
     */
    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ファイルを参照してください。