ホップスコッチハッシュ

ホップスコッチハッシュ法は、オープンアドレッシングを使用してテーブル内のハッシュ関数の値のハッシュ衝突を解決するコンピュータプログラミングの方式です。また、並行ハッシュテーブルの実装にも適しています。ホップスコッチハッシュ法は、2008年にMaurice Herlihy、Nir Shavit 、Moran Tzafrirによって導入されました。^[1]この名前は、テーブルの挿入アルゴリズムを特徴付けるホップのシーケンスに由来しています（子供のゲームについてはHopscotchを参照してください）。

このアルゴリズムでは、 n 個のバケットの単一の配列を使用します。各バケットの近傍は、 H個の連続するバケット (つまり、元のハッシュ バケットに近いインデックスを持つバケット)の小さなコレクションです。近傍の望ましい特性は、近傍のバケット内でアイテムを検索するコストが、バケット自体内でアイテムを検索するコストに近いことです (たとえば、近傍のバケットが同じキャッシュ ライン内に入るようにする)。近傍のサイズは、最悪の場合でも対数個のアイテムを収容できるほど十分である必要があります (つまり、log( n ) 個のアイテムを収容する必要があります)。ただし、平均では定数のみです。一部のバケットの近傍がいっぱいになると、テーブルのサイズが変更されます。

ホップスコッチ ハッシュでは、カッコウ ハッシュと同様に、線形プローブとは異なり、特定のアイテムは常にハッシュ バケットの近傍に挿入され、その近傍で見つかります。言い換えると、元のハッシュ アレイ エントリ内、または次のH −1 個の隣接エントリの 1 つ内に常に見つかります。たとえば、 H は一般的なマシン ワード サイズである 32 になります。近傍は、固定サイズで次のH −1 個のバケットと重複する「仮想」バケットです。検索を高速化するために、各バケット (アレイ エントリ) には「ホップ情報」ワード、つまり次のH −1 個のエントリのどれに現在のエントリの仮想バケットにハッシュされたアイテムが含まれているかを示すHビットのビットマップが含まれています。このように、ワードを見てどのエントリがバケットに属しているかを確認し、次に定数個のエントリをスキャンすることで、アイテムをすばやく見つけることができます (最新のプロセッサのほとんどは、「ホップ情報」ビットマップの検索を非常に高速にする特別なビット操作をサポートしています)。

ハッシュされたアイテムx をバケットiに追加する方法は次のとおりです。

1. バケットiのホップ情報ワードが、このバケットにすでにH個の項目があることを示している場合、テーブルはいっぱいです。ハッシュ テーブルを拡張して再試行してください。
2. エントリiから始めて、線形プローブを使用してインデックスjの空のエントリを検索します。(空のスロットが存在しない場合は、テーブルがいっぱいです。)
3. ( j − i ) mod n ≥ Hである間、空のスロットを次のようにi の方向に移動します。
   1. jの前のH −1スロットを検索し、ハッシュ値kがjのH −1以内、つまり( j − k )modn < Hであるアイテムyを探します。(これはホップ情報ワードを使用して行うことができます。)
   2. 範囲内にそのような項目y が存在しない場合は、テーブルがいっぱいになります。
   3. y をjに移動して、 iに近い新しい空きスロットを作成します。
   4. yによって空になった空きスロットにj を設定し、繰り返します。
4. x をスロットjに格納して戻ります。

ホップスコッチ ハッシュの考え方は、「空のスロットを目的のバケットの方向に移動する」というものです。この点が、ホップスコッチ ハッシュを、空のスロットが見つかった場所にそのまま残し、元のバケットから遠く離れている可能性がある線形プローブや、空きバケットを作成するためにターゲット配列内の目的のバケットの 1 つからアイテムを移動し、その後で移動したアイテムを新しい場所で探すカッコウ ハッシュと区別するものです。

テーブルからアイテムを削除するには、テーブル エントリからアイテムを削除するだけです。近隣のバケットがキャッシュに揃えられている場合は、整列を改善するために、アイテムを空になった場所に移動する再編成操作を適用できます。

ホップスコッチ ハッシュの利点の 1 つは、テーブル負荷係数が非常に高い場合 (0.9 を超える場合も含む) でも優れたパフォーマンスを発揮することです。この効率性の一部は、元の線形プローブ ハッシュ テーブル アルゴリズムのようにすべての検索で線形プローブを使用するのではなく、挿入時に空きスロットを見つけるためだけに線形プローブを使用するためです。もう 1 つの利点は、任意のハッシュ関数 (特に、ユニバーサルに近い単純なもの) を使用できることです。

この論文ではホップスコッチハッシュ方式のいくつかのバリエーションも紹介されている。^[1]

高度なアプローチでは、ポインタスキームを使用してホップ情報ワード (基本的なケースではホップ情報ビットマップ) を実装します。これにより、ホップ情報ワードを任意の (ただし固定の) サイズにすることができます。

基本的なケースと高度なアプローチは順次実行されるように設計されていますが、それぞれに 同時実行のバリエーションもあります。

ロックフリーの変種は、2020年にロバート・ケリー、バラク・A・パールマッター、フィル・マグワイアによって導入されました。^[2]

• カッコウハッシュ
• ハッシュ衝突
• ハッシュ関数
• リニアプローブ
• オープンアドレス
• 完璧なハッシュ
• 二次プロービング
• 石けり遊び

• libhhash - C ホップスコッチハッシュ実装
• hopscotch-map - ホップスコッチハッシュを使用したハッシュマップの C++ 実装
• Goossaert, Emmanuel (2013 年 8 月 11 日). 「Hopscotch hashing」 . 2019 年10 月 16 日閲覧。詳細な説明と実装例。