hopskotch-map ライブラリ

hopskotch-map

ライブラリは、open addressing および hopskotch 解析（ホップスコッチ・ハッシング） を採用した高速なハッシュマップとハッシュセットの C++ 実装です。

• 衝突解決: この手法により衝突を効率的に解決します。
• パフォーマンス: キャッシュフレンドリーなデータ構造であり、

  std::unordered_map

  よりも大多数のケースで優れたパフォーマンスを発揮します。
• 代替案:

  google::dense_hash_map

  と似た挙動を示しつつ、メモリ使用量の削減と多様な機能の提供を実現します。

クラス群と特徴

本ライブラリは以下のクラス群を提供します：

• tsl::hopscotch_map

  /

  tsl::hopscotch_set

• tsl::hopscotch_pg_map

  /

  tsl::hopscotch_pg_set

• tsl::bhopscotch_map

  /

  tsl::bhopscotch_set

• tsl::bhopscotch_pg_map

  /

  tsl::bhopscotch_pg_set

クラスの違い

クラス名	特徴	ポリシー	推奨用途
hopscotch (基本)	高速	冪乗 (Power of Two)	一般用途。デフォルトの選択として最適です。
hopscotch_pg (素数)	堅牢性向上	素数 (Prime)	ハッシュ関数が劣悪な場合や、ハッシュ値の下位ビットにパターンがある場合（例：ポインタ識別子）。
bhopscotch (バインド)	安全性向上	冪乗	DoS 攻撃対策。最悪ケースを $O(\log n)$ に抑えます。
bhopscotch_pg	安全性＋堅牢性	素数	DoS 防御かつ劣悪ハッシュへの耐性を両立します。

注意:

LessThanComparable

な追加の要件を持つ

bhopscotch_*

クラスは、検索および削除時の最上界（worst-case upper bound）を $O(\log n)$ に改善しますが、通常の攻撃がない限り

hopscotch_map

が十分であることが多いです。

メイン機能

• ヘッダーのみ (Header-only): インクルードディレクトリとパスに加えれば即座に使用可能。CMake ならエクスポートされたターゲットも利用できます。
• 高速なハッシュテーブル: ベンチマーク結果が示す通り非常に高速です。
• ムーブ・オンリー (Move-only) / デフォルト構築不可キー: ムーブのみおよびデフォルトで構築できないキー/バリューをサポートします。
• 不均一なルックアップ (Heterogeneous lookups):

  Key

  以外の型（例：ポインタ）で検索・削除が可能です（詳細は後述）。
• 哨兵値の予約不要: リスト末尾などの哨兵値を保持する必要がありません。
• ハッシュ値保存オプション (

  StoreHash

  ): ハッシュ計算コストが高い場合に、挿入時の計算を再使用してルックアップを高速化できます。
• 事前計算されたハッシュの利用: ルックアップ直前のハッシュ値をパラメータとして渡すことで検索を高速化できます（API の

  precalculated_hash

  パラメータ参照）。
• DoS 攻撃対策 (

  bhopscotch_*

  ): 最悪ケースを $O(\log n)$ に抑え、ハッシュテーブル型拒否サービス攻撃に耐性があります。
• 例外不使用環境での利用: Clang/GCC (

  -fno-exceptions

  ) や MSVC (

  /EH

  オプションなし)、または

  TSL_NO_EXCEPTIONS

  の定義により、例外無効化環境で動作します（

  throw

  代わりに

  std::terminate

  を使用）。
• API の親和性: インタフェースは

  std::unordered_map/set

  に非常に類似しています。

std::unordered_map との違い

tsl::hopscotch_map

は

std::unordered_map

に似たインターフェースを目指していますが、以下の違いがあります（

unordered_set

も同様）：

• 挿入時のイテレータ無効化: 変更操作（消去

  erase

  など）では、すべてのイテレータが無効化されます。

• 参照/ポインタの無効化: キーまたはバリューへのリファレンスおよびポインタも挿入時に無効化されます。

• イテレータ操作の変更:

  operator*()

  および

  operator->()

  は

  std::pair<const Key, T>

  ではなく、

  const std::pair<Key, 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;   // ❌ 無効
      it.value() = 2;     // ✅ 有効
  }
  

• ムーブ・オンリー型: ノズロシフト（nothrow）移動コンスルクターが必要です。再ハッシュ時に SGE (Strong Exception Guarantee) を保つために、例外を投げる移動コンスルクターは使用できません。

• バケット情報の不足:

  bucket_size

  ,

  bucket

  などのメソッドはサポートされていません。

成長ポリシー (Growth Policy)

GrowthPolicy

テンプレートパラメータを通じて以下のポリシーをサポートしています：

1. tsl::hh::power_of_two_growth_policy

   (デフォルト)
   • バケット配列サイズを冪数に保ちます。
   • modulo 代わりに

     hash & (2^n - 1)

     を使用して高速化します。
   • 弱点: 劣悪なハッシュ関数の場合、上位ビットのみをマスキングするため多数の衝突が起きる可能性があります。

2. tsl::hh::prime_growth_policy

   (

   *_pg

   クラス用)
   • バケット配列サイズを素数に保ちます。
   • modulo を使用してハッシュ値を均等に分布させます。
   • コンパイラ最適化のため定数の素数 modulo ルックアップテーブルを使用します。
   • メリット: 冪乗ポリシーより少し遅いですが、**頑健（堅牢）**です。

3. tsl::hh::mod_growth_policy

   • カスタマイズ可能な成長係数に応じて拡大し、単純な modulo を使用します。
   • 特徴: 遅いですが最も柔軟です。

警告: パフォーマンス低下（衝突多数）が疑われる場合は

overflow_size()

を確認してください。ハッシュ関数の改善や、主に

tsl::hh::prime_growth_policy

の採用を試してください。また、DoS 攻撃を防ぐには

bhopscotch_map/set

の検討を推奨します。

カスタムポリシーの実装例

独自のポリシーを実装するには、以下のインターフェースを実装してください：

struct custom_policy {
    // ハッシュテーブルの構築および再ハッシュ時に呼ばれます。min_bucket_count_in_out は必要な最小バケット数です。
    explicit custom_policy(std::size_t& min_bucket_count_in_out);
    
    // ハッシュに属するバケット [0, bucket_count()) を返します。
    std::size_t bucket_for_hash(std::size_t hash) const noexcept;
    
    // 次の成長時に使用すべきバケット数を返します。
    std::size_t next_bucket_count() const;
    
    // クリア後、bucket_for_hash() は常に 0 を返すようポリシーをリセットします。
    void clear() noexcept;
};

インストール方法

ヘッダーのみライブラリのため、単にインクルードディレクトリを含めるだけで使用可能です（CMake なら

add_subdirectory

または

find_package

で使用）。

CMake リスト例:

# third-party/hopscotch-map にプロジェクトを格納している場合
add_subdirectory(third-party/hopscotch-map)
target_link_libraries(your_target PRIVATE tsl::hopscotch_map)  

ビルドとテスト実行: コードは 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/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.insert({"e", 5});

    // 削除
    map.erase("b");

    // 値の修正（直接は不可、.value() で修正）
    for(auto it = map.begin(); it != map.end(); ++it) {
        // it->second += 2;   // ❌ 無効
        it.value() += 2;     // ✅ 有効
    }

    // ループ出力（順序はバケット配置に依存）
    for(const auto& [key, val] : map) {
        std::cout << "{" << key << ", " << val << "}" << std::endl;
    }

    // ハッシュを活用した高速検索
    const std::size_t precalculated_hash = std::hash<std::string>()("a");
    if(map.find("a", precalculated_hash) != map.end()) {
        std::cout << "\"a\" を見つけました。" << std::endl;
    }

    // StoreHash オプションでハッシュを内部保存（計算コストが高い場合）
    /* 
       6 つ目のテンプレート引数 (hasher), 7 番目 (equal_to), 8 番目 (allocator) の後、
       9 番目に初期サイズ 30, 10 番目に 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;

    tsl::hopscotch_set<int> set;
    set.insert({1, 9, 0}); // 要素追加
}

不均一なルックアップ (Heterogeneous Lookups)

検索・削除時に

Key

とは異なる型（例：ポインタ）を使用可能にする機能です。有効にするには、コンパレータに 限定 ID (qualified-id)

KeyEqual::is_transparent

を有している必要があります。

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

struct employee {
    int id;
    std::string name;
    
    // オプション：独自のコンパレータ
    friend bool operator==(const employee& e, int id) { return e.id == id; }
};

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

struct equal_employee {
    using is_transparent = void; // 必須
    
    bool operator()(const employee& e, int id) const { return e.id == id; }
    bool operator()(int id, const employee& e) const { return id == e.id; }
};

int main() {
    // 1. std::equal_to<> を使用（自動推論と転送）
    tsl::hopscotch_map<employee, int, hash_employee, std::equal_to<>> map; 
    map.insert({{1, "John"}, 2001});

    // ID で直接検索可能
    auto it = map.find(1);
    if(it != map.end()) {
        std::cout << it->name << " (" << it->id << ")" << std::endl;
    }

    // 2. カスタムコンパレータを使用
    tsl::hopscotch_map<employee, int, hash_employee, equal_employee> map2;
    map2.at(1); // 整数 ID で値アクセス可能
}

DoS 攻撃への対処

tsl::bhopscotch_map/set

（および

_pg

バージョン）は、ハッシュテーブル型拒否サービス (DoS) 攻撃に対して耐性があります。

• 通常の版 (

  hopscotch

  ): ハッシュ値の衝突が極端に多い場合、検索・削除が $O(n)$ になることがあります。
• 安全な版 (

  bhopscotch

  ): 最悪ケースも挿入時も $O(\log n)$ を維持します（内部にバイナリ検索木を使用）。

ベンチマーク例（劣悪ハッシュ関数での性能比較）：

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

struct dos_attack_simulation_hash {
    std::size_t operator()(int id) const { return 1; } // 常に同じハッシュ値
};

int main() {
    // --- 通常の版 (脆弱) ---
    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}); } // O(n) の挙動
    auto end = std::chrono::high_resolution_clock::now();
    
    // 約 110 ms (遅い)
    std::cout << "hopscotch_map: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() 
              << " ms" << std::endl;

    // --- 安全な版 (耐性あり) ---
    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}); } // O(log n) の挙動
    end = std::chrono::high_resolution_clock::now();
    
    // 約 2 ms (非常に速い)
    std::cout << "bhopscotch_map: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() 
              << " ms" << std::endl;
}

ライセンス

コードは MIT ライセンス で公開されています。詳細は LICENSE ファイルを参照してください。