std::unordered_map より高速—hopscotch ハッシングの C++ 実装入門

hopscotch-map とは—標準ライブラリの限界を超える設計

hopscotch-map は Tessil 氏によって開発・公開されている C++ 用のハッシュテーブル実装です（GitHub リポジトリ）。ハッシュマップは多くのアプリケーションで利用される基本的なデータ構造ですが、標準的な std::unordered_map は常にベストなパフォーマンスを発揮するわけではありません。

hopscotch-map は開放アドレス法と hopscotch ハッシングを組み合わせることで、キャッシュ局所性を大幅に改善し、std::unordered_map より高速な動作を実現しています。

hopscotch ハッシングの核となる考え方は、ハッシュ衝突を「ホップ」という操作で管理し、キー・バリューのメモリ配置を連続的に保つことです。これにより CPU キャッシュへのヒット率が向上し、結果としてメモリアクセス速度が改善されます。Google の dense_hash_map も同様の方針ですが、hopscotch-map はメモリ使用量をより削減しながら、さらに多くの機能を備えています。

複数のバリエーション—用途に応じた選択肢

hopscotch-map ライブラリは、4 つの主要なクラスを提供します。

ポイントは「どのバリアント を選ぶか」という判断です。ドキュメントでは、特別な要件がない限り tsl::hopscotch_map をデフォルトとすることを推奨しています。ただし、ハッシュ関数が不完全だったり、ポインタを直接キーにしたりする場合は、素数成長ポリシー版（pg）への切り替えが有効です。

実装面での工夫—プロダクション環境での利用を想定した設計

hopscotch-map には、実務的な視点からいくつかの考慮が組み込まれています。

• ヘッダオンリーライブラリ：インクルードディレクトリをパスに追加するだけで即座に利用可能。CMake を使う場合も提供されるターゲットを活用すれば統合が簡単です
• move-only・非デフォルトコンストラクタ対応：モダン C++ のキーや値型に柔軟に対応
• 異種型ルックアップ：例えば std::unique_ptr<foo> をキーとしながら、foo* や std::uintptr_t で検索可能。テンポラリオブジェクトの生成を避けられます
• ハッシュ値の事前計算オプション：キーの比較やハッシュ計算が重い場合、値をキャッシュしてリハッシュを加速できます
• 例外無効化対応：組み込みシステムや制約環境で -fno-exceptions でコンパイルする場合でも動作します

特に異種型ルックアップと事前計算ハッシュのサポートは、高パフォーマンスが求められるシステムにおいて実値があると感じます。

API は std::unordered_map に似ており、学習コストが低いのも利点です。ただし、反復子の無効化ルールが若干異なる点には注意が必要です。挿入時に反復子がすべて無効化される仕様のため、既存の std::unordered_map コードからの移行時は動作確認を十分に行うべきです。

ベンチマークと適用の判断

GitHub リポジトリには複数のハッシュテーブル実装に対するベンチマーク結果が掲載されており、どのシナリオで hopscotch-map が有効かの指針が示されています。キャッシュ局所性が重要な読み取り頻出ワークロードや、ハッシュ衝突が少ない通常の用途では顕著なパフォーマンス向上が期待できます。

一方、前述の参考記事「Shard your locks: benchmarking 6 Go cache designs」でも指摘されているように、マルチスレッド環境ではロック戦略全体の設計が重要です。hopscotch-map 自体はスレッドセーフではないため、並行アクセスが必要な場合は外部で同期を管理する必要があります。

今後の活用シーン

hopscotch-map のような高性能ハッシュテーブル実装は、クラウドネイティブアプリケーションやデータ処理パイプラインでの価値が高まると予想されます。BigQuery や Cloud Run 上で動作する C++ サービスでは、メモリとレイテンシの最適化が重要であり、こうした低レベルの データ構造選択が全体のパフォーマンスに波及します。

また、LLM エージェントがコード生成を支援する現在のトレンドを踏まえれば、実装の品質やパフォーマンス特性を理解した開発者の役割はむしろ増していくでしょう。標準ライブラリの選択肢だけでなく、こうしたオープンソース実装の特性を知識として持つことが、今後一層重要になると考えられます。