A C++ implementation of a fast hash map and hash set using hopscotch hashing
hopscotch-mapは、ホップスコッチハッシングを用いたC++高速ハッシュマップおよびハッシュセットの実装です。オープンアドレッシング方式を採用し、優れたキャッシュ性能と高いメモリ効率を提供します。std::unordered_mapと比較して、多くのシナリオでより高速な挿入、検索、削除を実現します。
背景メモ
- **hopscotch hashing** は、2008年にHerlihyらが提案したハッシュテーブルのアルゴリズム。テーブルの各バケットに「近傍領域（neighborhood）」を定義し、衝突時に要素をその範囲内でずらして再配置することで、検索・挿入の最悪計算量をO(1)に近づける。キャッシュ効率が良く、現代のCPUに有利。
- **Tessil/hopscotch-map** は、この手法をC++11で実装したヘッダオンリーライブラリ。作者Tessil（Tibor Vass）の他の作品（robin-map、sparse-map、hat-trie等）と同様、実用に特化した高速データ構造として知られる。
- 標準ライブラリの `std::unordered_map` よりも高速なケースが多く、ゲームエンジン、データベース、リアルタイムシステムなど、C++で低レイテンシが求められる現場で採用される。
- 本件はあくまで個人がメンテナンスするオープンソースのライブラリであり、商用製品ではないが、GitHub上で高いパフォーマンス評価を得て、C++コミュニティで広く使われている。