カッコウハッシュ

カッコウハッシュ法は、最悪の場合でも一定の検索時間で、テーブル内のハッシュ関数の値のハッシュ衝突を解決するためのコンピュータプログラミングのスキームです。この名前は、カッコウのいくつかの種の行動に由来しています。カッコウの雛は、孵化すると、他の卵や幼鳥を巣から押し出すという、托卵と呼ばれる行動の一種です。同様に、カッコウハッシュテーブルに新しいキーを挿入すると、古いキーがテーブル内の別の場所に押し出されることがあります。

カッコウハッシュは、2001年の会議論文でラスムス・パグとフレミング・フリッシュ・ロドラーによって初めて説明されました。 ^{[1]この論文は、2020年に}ヨーロッパアルゴリズムシンポジウムのTest-of-Time賞を受賞しました。 ^{[2] : 122}

カッコウハッシュ法はオープンアドレッシングの一種で、ハッシュテーブルの空でない各セルにキーまたはキーと値のペアが含まれます。ハッシュ関数は各キーの位置を決定するために使用され、テーブル内のそのキーの存在 (またはそれに関連付けられた値) は、テーブルのそのセルを調べることで確認できます。ただし、オープンアドレッシングでは衝突が発生します。衝突は、複数のキーが同じセルにマップされている場合に発生します。カッコウハッシュ法の基本的な考え方は、ハッシュ関数を 1 つだけではなく 2 つ使用して衝突を解決することです。これにより、ハッシュテーブル内の各キーの位置が 2 つ可能になります。このアルゴリズムのよく使用されるバリエーションの 1 つでは、ハッシュテーブルが同じサイズの 2 つの小さなテーブルに分割され、各ハッシュ関数がこれら 2 つのテーブルのいずれかにインデックスを提供します。また、両方のハッシュ関数が 1 つのテーブルにインデックスを提供することも可能です。^{[1] : 121-122}

カッコウハッシュ法では、2つのハッシュテーブルとを使用します。各テーブルの長さを とすると、2つのテーブルのハッシュ関数は と定義されます。ここで はキーであり、 はまたはに格納されているキーを持つセットです。検索操作は次のようになります。[ ^{1] : 124}${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle r}$${\displaystyle h_{1},\ h_{2}\ :\ \cup \rightarrow \{0,...,r-1\}}$${\displaystyle \forall x\in S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle h_{1}(x)}$${\displaystyle T_{1}}$${\displaystyle h_{2}(x)}$${\displaystyle T_{2}}$

論理和（）は、キーの値がまたは のいずれかにあることを示し、最悪の場合には となる。^{[1] : 123}${\displaystyle \vee}$${\displaystyle x}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle O(1)}$

削除はプローブを必要としないため、時間内に実行されます。これにより、テーブルがまばらすぎる場合の縮小操作のコストは無視されます。^{[1] : 124-125}${\displaystyle O(1)}$

キー を持つ新しい項目を挿入する場合、最初のステップでは、表 のスロット が占有されているかどうかを調べます。占有されていない場合は、そのスロットに項目が挿入されます。ただし、スロットが占有されている場合は、既存の項目が削除され、に挿入されます。次に、同じ手順に従って が表 に挿入されます。このプロセスは、キーを挿入する空の位置が見つかるまで続行されます。 ^{[1] : 124-125}無限ループを回避するために、しきい値が指定されます。反復回数がこの固定しきい値を超えると、との両方が新しいハッシュ関数で再ハッシュされ、挿入手順が繰り返されます。以下は、挿入の擬似コードです。 ^{[1] : 125}${\displaystyle x}$${\displaystyle h_{1}(x)}$${\displaystyle T_{1}}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle T_{1}[h_{1}(x)]}$${\displaystyle x'}$${\displaystyle T_{2}}$${\displaystyle {\text{Max-Loop}}}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$

10行目と15行目では、 を占める他のキーをキックする「カッコウアプローチ」が、すべてのキーが独自の「ネスト」を持つまで、つまり、アイテムが2つのテーブルのいずれかの空きスロットに挿入されるまで繰り返されます。表記は、スワッピングとを表します。^{[1] ：124-125}${\displaystyle T_{1,2}[h_{1,2}(x)]}$${\displaystyle x}$${\displaystyle x\leftrightarrow y}$${\displaystyle x}$${\displaystyle y}$

キーの数がハッシュテーブルの容量の半分以下、つまり負荷率が50%以下であれば、テーブルを再構築する必要がある可能性を考慮しても、挿入は予想される定数時間^[1]で成功します。

これを証明する 1 つの方法は、ランダム グラフの理論を使用する方法です。つまり、 「カッコウ グラフ」と呼ばれる無向グラフを形成します。このグラフは、ハッシュ テーブルの各位置に対応する頂点と、ハッシュされた各値に対応する辺を持ち、辺の端点は値の 2 つの可能な位置になります。次に、カッコウ ハッシュ テーブルに値のセットを追加するための貪欲挿入アルゴリズムは、この値のセットのカッコウ グラフが疑似フォレスト、つまり各接続コンポーネントに最大 1 つのサイクルを持つグラフである場合にのみ成功します。頂点よりも辺の数が多い頂点誘導サブグラフは、ハッシュ テーブルに十分な数のスロットがないキーのセットに対応します。ハッシュ関数がランダムに選択される場合、カッコウ グラフはエルデシュ-レーニ モデルにおけるランダム グラフです。負荷係数が 1/2 未満の場合 (エッジ数と頂点数の比率が 1/2 未満に制限されているランダム グラフに対応)、グラフは疑似フォレストであり、カッコウ ハッシュ アルゴリズムはすべてのキーを配置することに成功する可能性が高くなります。同じ理論により、カッコウ グラフの接続コンポーネントの予想サイズが小さいことも証明されており、各挿入には一定の予想時間がかかることが保証されます。ただし、負荷係数が 1/2 を超えると、 2 つ以上のサイクルを持つ巨大なコンポーネントが生成され、データ構造が失敗してサイズ変更が必要になる可能性も高くなります。^[3]

理論上のランダムハッシュ関数は実際の使用には大きすぎるスペースを必要とするため、どの実用的なハッシュ関数がカッコウハッシュに十分であるかが重要な理論的問題となる。 1 つのアプローチは、k 独立ハッシュを使用することである。 2009 年には、k 独立で十分であり、少なくとも 6 独立が必要であることが示された[ ^4]。 別のアプローチは、6 独立ではないタブレーションハッシュを使用することであるが、2012 年^[5]には、カッコウハッシュに十分な他の特性があることが示された。 2014 年の 3 番目のアプローチ^[6]は、いわゆるスタッシュを使用してカッコウハッシュテーブルをわずかに変更することであり、これにより、2 独立ハッシュ関数のみを使用できるようになる。 ${\displaystyle O(\log n)}$

実際には、カッコウハッシュ法は、一般的なアプローチの中で最も高速な線形プローブ法よりも約 20～30% 遅くなります。 ^[1] その理由は、カッコウハッシュ法では、キーが格納されている可能性のある 2 つの場所を確認するために、検索ごとに 2 回のキャッシュ ミスが発生することが多いのに対し、線形プローブ法では通常、検索ごとに 1 回のキャッシュ ミスしか発生しないからです。ただし、検索時間に関する最悪のケースが保証されるため、カッコウハッシュ法は、リアルタイムの応答速度が必要な場合でも価値があります。

次のハッシュ関数が与えられます (基数 11 の k の最下位 2 桁)。

${\displaystyle h\left(k\right)=k{\bmod {1}}1}$
${\displaystyle h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1}$

次の 2 つの表は、いくつかのサンプル要素の挿入を示しています。各列は、時間の経過に伴う 2 つのハッシュ テーブルの状態に対応しています。新しい値ごとに挿入可能な場所が強調表示されています。最後の列は、サイクルが原因で挿入が失敗したことを示しています。詳細は以下を参照してください。

要素 45 を挿入しようとすると、循環に入り、失敗します。表の最後の行では、最初と同じ初期状況が再び表示されます。

${\displaystyle h\left(45\right)=45{\bmod {1}}1=1}$
${\displaystyle h'\left(45\right)=\left\lfloor {\frac {45}{11}}\right\rfloor {\bmod {1}}1=4}$

カッコウハッシュのいくつかのバリエーションが研究されてきましたが、その主な目的は、許容できる負荷係数を基本アルゴリズムの 50% しきい値よりも高い数値に増加させることで、スペースの使用率を改善することです。これらの方法のいくつかは、カッコウハッシュの失敗率を下げるためにも使用でき、データ構造の再構築の頻度を大幅に減らすことができます。

2つ以上の代替ハッシュ関数を使用するカッコウハッシュの一般化は、検索と挿入の速度を犠牲にしながら、ハッシュテーブルの容量の大部分を効率的に利用することが期待できます。3つのハッシュ関数を使用するだけで、負荷は91％に増加します。^[7]

カッコウハッシュの別の一般化であるブロックカッコウハッシュは、バケットごとに複数のキーとバランスのとれた割り当て方式を使用します。バケットごとに2つのキーを使用するだけで、80%を超える負荷係数が可能になります。^[8]

研究されているカッコウハッシュの別のバリエーションは、スタッシュ付きカッコウハッシュです。このデータ構造のスタッシュは、定数個のキーの配列であり、構造のメインハッシュテーブルに正常に挿入できないキーを格納するために使用されます。この変更により、カッコウハッシュの失敗率は、スタッシュサイズを増やすことで任意に大きくできる指数を持つ逆多項式関数にまで下がります。ただし、スタッシュが大きいほど、存在しないキーやスタッシュ内にあるキーの検索が遅くなります。スタッシュは、2つ以上のハッシュ関数と組み合わせて使用​​したり、ブロックされたカッコウハッシュと組み合わせて使用​​することで、高い負荷係数と低い失敗率の両方を実現できます。^[9]スタッシュ付きカッコウハッシュの分析は、ハッシュの理論的分析で一般的に使用されるランダムハッシュ関数モデルだけでなく、実際のハッシュ関数にも適用されます。^[10]

一部のCPUキャッシュでは、カッコウハッシュの単純化された一般化である歪んだ連想キャッシュを推奨する人もいます。^[11]

カッコウ ハッシュ テーブルの別のバリエーションであるカッコウ フィルタは、カッコウ ハッシュ テーブルに格納されているキーを、別のハッシュ関数をキーに適用して計算されたはるかに短いフィンガープリントに置き換えます。これらのフィンガープリントをカッコウ フィルタ内で移動できるようにするには、フィンガープリントのビット単位の排他的論理和演算、またはフィンガープリントのハッシュを使用して、各フィンガープリントの 2 つの位置を相互に計算します。このデータ構造は、ブルーム フィルタとほぼ同じ特性を持つ近似セット メンバーシップ データ構造を形成します。キー セットのメンバーを格納し、クエリ キーがメンバーであるかどうかをテストできます。偽陽性(セットの一部であると誤って報告されたクエリ) が発生する可能性はありますが、偽陰性はありません。ただし、ブルーム フィルタよりも複数の点で優れています。メモリ使用量が定数倍小さく、参照の局所性が高く、(ブルーム フィルタとは異なり) 追加のストレージ ペナルティなしでセット要素を高速に削除できます。^[12]

Zukowski らによる研究^[13]では、現代のプロセッサ上の小さなキャッシュ常駐ハッシュテーブルでは、カッコウハッシュが連鎖ハッシュよりもはるかに高速であることが示されています。 Kenneth Ross ^{[14] は}、スペース使用率が高い場合、カッコウハッシュのバケット化バージョン (複数のキーを含むバケットを使用するバリアント) が、大規模なハッシュテーブルでも従来の方法よりも高速であることを示しました。 バケット化されたカッコウハッシュテーブルのパフォーマンスは Askitis ^[15]によってさらに調査され、 そのパフォーマンスが他のハッシュスキームと比較されました。

Mitzenmacher ^[7]による調査では、2009年時点でカッコウハッシュに関連する未解決の問題が提示されています。

カッコウハッシュはTikTokの推奨システムで使用され、モデルの品質低下につながる可能性がある「埋め込みテーブルの衝突」の問題を解決します。TikTokの推奨システム「モノリス」は、カッコウハッシュの衝突解決を利用して、異なる概念が同じベクトルにマッピングされるのを防ぎます。^[16]

• 完璧なハッシュ
• ダブルハッシュ
• 二次プロービング
• ホップスコッチハッシュ

• 従来のハッシュ テーブルに代わるクールで実用的な代替手段。Wayback Machineに 2019-04-07 にアーカイブ。U. Erlingsson、M. Manasse、F. Mcsherry、2006 年。
• 大学生のためのカッコウハッシュ、2006 年、R. Pagh、2006 年。
• カッコウハッシュ、理論と実践（パート 1、パート 2、パート 3）、Michael Mitzenmacher、2007 年。
• Naor, Moni; Segev, Gil; Wieder, Udi (2008)。「履歴に依存しないカッコウハッシュ」。国際オートマトン、言語、プログラミング会議 (ICALP)。レイキャビク、アイスランド。2008年 7 月 21 日閲覧。
• 高速並行カッコウハッシュのアルゴリズムの改善、X. Li、D. Andersen、M. Kaminsky、M. Freedman。EuroSys 2014。

• C++ で書かれた並列高性能 Cuckoo ハッシュテーブル
• C++ で書かれたカッコウハッシュマップ
• C/C++ 用の静的カッコウハッシュテーブルジェネレーター
• Haskell で書かれたカッコウハッシュテーブル
• Go のカッコウハッシュ