Tessil、C++用高速ハッシュマップライブラリ hopscotch-map を公開──std::unordered_map を上回る性能
オープンアドレッシングとホップスコッチハッシュを採用し、メモリ効率と実行速度を両立させたヘッダーオンリーの C++ ライブラリ。
リリース: 2025-11-02 · 読了 3 分記事の要約
1. 核心（What）
- Tessil が提供する C++ 用ハッシュマップ/セット実装で、ホップスコッチハッシュアルゴリズムを採用。
- 標準ライブラリの std::unordered_map と比較して、メモリ消費量を抑えつつ高速なルックアップを実現。
- tsl::hopscotch_map 等のクラスを提供し、ハッシュ関数の特性に応じた prime/power-of-two の成長ポリシーを選択可能。
- ヘッダーオンリーで提供され、CMake による統合もサポート。
2. 影響（Why）
- 標準マップの代替候補: std::unordered_map のメモリオーバーヘッドやキャッシュ性能に課題がある場合、置換のみで高速化が見込める。
- 国内 SaaS 開発への影響: C++ を用いた高頻度取引システムやゲームエンジン開発を行う国内中規模組織において、メモリ制約下での検索性能向上に寄与する。
3. 根拠・詳細（How）
- メモリレイアウトと衝突解決: オープンアドレッシング手法により、ノードごとのポインタ追跡を減らしキャッシュ効率を最大化。google::dense_hash_map と同等のメモリ効率を実現。
- 異種ルックアップの実装: std::unique_ptr<foo> をキーとするマップに対し、foo* 型の引数で find を実行可能。キーの構築コストを回避する設計。
4. 展望・課題（Next）
- DoS 攻撃への耐性: ハッシュ衝突を意図的に引き起こす DoS 攻撃への耐性が必要な場合は、LessThanComparable を要求する bhopscotch シリーズの利用を推奨。