k独立ハッシュ

コンピュータサイエンスでは、ハッシュ関数の族は、族から関数をランダムに選択すると、指定されたk個のキーのハッシュコードが独立したランダム変数になることが保証される場合、k独立、 kごと独立、またはkユニバーサル[ 1 ^]であると言われます（正確な数学的定義は以下を参照）。このような族は、入力データが敵対者によって選択された場合でも、ランダム化アルゴリズムまたはデータ構造で良好な平均ケースパフォーマンスを可能にします。独立性の度合いとハッシュ関数の評価の効率との間のトレードオフは十分に研究されており、多くのk独立族が提案されています。

ハッシュの目的は通常、ある大きなドメイン（宇宙）からのキーを、ビン（ とラベル付けされる）などのより小さな範囲にマッピングすることです。ランダム化されたアルゴリズムとデータ構造の分析では、さまざまなキーのハッシュ コードが「ランダムに動作する」ことが望ましいことがよくあります。たとえば、各キーのハッシュ コードが で独立にランダムに選択されたものである場合、ビンあたりのキーの数はチェルノフ境界を使用して分析できます。決定論的ハッシュ関数では、敵対的な設定ではそのような保証を提供できません。敵対者は、キーがビンの正確に原像になるように選択する可能性があるためです。さらに、決定論的ハッシュ関数では再ハッシュが許可されません。入力データがハッシュ関数に適さないことが判明する場合（衝突が多すぎるなど）があり、ハッシュ関数を変更したい場合があります。 ${\displaystyle U}$${\displaystyle m}$${\displaystyle [m]=\{0,\dots ,m-1\}}$${\displaystyle [m]}$

これらの問題の解決策は、ハッシュ関数の大きなファミリーから関数をランダムに選択することです。ハッシュ関数を選択する際のランダム性は、任意のキーのハッシュコードの望ましいランダムな動作を保証するために使用できます。この方向の最初の定義はユニバーサルハッシュであり、指定された2つのキーの衝突確率が低いことを保証します。1981年にウェグマンとカーターによって導入された-独立ハッシュの概念^[2]は、指定されたキーのファミリーに対するランダムな動作の保証を強化し、ハッシュコードの均一な分布の保証を追加します。 ${\displaystyle k}$${\displaystyle k}$

最も厳密な定義は、ウェグマンとカーター^[2]が「強く普遍的なハッシュファミリー」という名前で導入したもので、次のようになります。ハッシュ関数のファミリーは、任意の異なるキーと任意のハッシュコード（必ずしも異なるとは限らない）に対して、次が成り立つ場合、-独立です。 ${\displaystyle _{k}}$${\displaystyle H=\{h:U\to [m]\}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle (x_{1},\dots ,x_{k})\in U^{k​​}}$${\displaystyle k}$${\displaystyle (y_{1},\dots ,y_{k})\in [m]^{k}}$

${\displaystyle \Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}}$

この定義は次の 2 つの条件に相当します。

1. 任意の固定された に対して、からランダムに抽出された は内で一様に分布します。${\displaystyle x\in U}$${\displaystyle h}$${\displaystyle H}$${\displaystyle h(x)}$${\displaystyle [m]}$
2. 任意の固定された個別のキー に対して、 がからランダムに抽出される は、独立したランダム変数です。${\displaystyle x_{1},\dots ,x_{k}\in U}$${\displaystyle h}$${\displaystyle H}$${\displaystyle h(x_{1}),\dots ,h(x_{k})}$

多くの場合、丸めの問題により、の完全な結合確率を達成するのは不便です。以下に示すように、 ^[3]は次を満たす -独立な族を 定義します。${\displaystyle m^{-k}}$${\displaystyle (\mu,k)}$

${\displaystyle \forall}$明確に区別され、${\displaystyle (x_{1},\dots ,x_{k})\in U^{k​​}}$${\displaystyle \forall (y_{1},\dots ,y_{k})\in [m]^{k}}$${\displaystyle ~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}}$

が 1 に近い場合でも、はもはや独立したランダム変数ではないことに注意してください。これは、ランダム化アルゴリズムの分析でよく問題になります。したがって、丸めの問題に対処するためのより一般的な代替手段は、ハッシュ ファミリが統計的距離で -独立ファミリに近いことを証明することです。これにより、独立性プロパティのブラック ボックス使用が可能になります。 ${\displaystyle \mu}$${\displaystyle h(x_{i})}$${\displaystyle k}$

カーターとウェグマンによって提案されたk独立ハッシュ関数を構築するための元々の手法は、大きな素数p を選択し、pを法とするk個の乱数を選択し、これらの数をk − 1次多項式の係数として使用し、pを法とする値がハッシュ関数の値として使用されるというものでした。 p を法とする指定された次数の多項式はすべて等確率であり、任意の多項式は異なる引数を持つ任意のk組の引数と値のペアによって一意に決定されます。このことから、任意の k 組の異なる引数は、任意の k 組のハッシュ値に等確率でマッピングされることがわかります。 [ 2 ^]

一般に多項式は任意の有限体で評価できる。素数を法とする体のほかに、サイズ の体も人気のある選択肢であり、これは現代のコンピュータで高速な有限体演算をサポートする。これはダニエル・ルミアとオーウェン・ケーサーがCLHashで採用したアプローチである。^[4]${\displaystyle 2^{n}}$

タブレーションハッシュ法は、各キーをバイトに分割し、各バイトを乱数テーブル（バイト位置ごとに異なるテーブル）のインデックスとして使用し、これらのテーブルルックアップの結果をビット単位の排他的論理和演算で組み合わせることで、キーをハッシュ値にマッピングする手法です。したがって、多項式法よりも初期化にランダム性が必要になりますが、遅くなる可能性のある乗算操作を回避できます。タブレーションハッシュ法は3独立ですが、4独立ではありません。^[5]タブレーションハッシュ法のバリエーションでは、入力キーのビットの重複組み合わせに基づいてテーブルルックアップを実行するか、単純なタブレーションハッシュ法を繰り返し適用することで、より高い独立性を実現できます。^{[6] [7]}

k独立性の概念は、操作ごとに一定の予想時間を保証するために必要な独立性のレベルに応じて、ハッシュテーブル内の さまざまな衝突解決を区別するために使用できます。

たとえば、ハッシュ連鎖は、 2 独立なハッシュ関数ファミリーでも一定の予想時間がかかります。これは、特定のキーの検索を実行する予想時間が、そのキーが関与する衝突の予想数によって制限されるためです。期待値の線形性により、この予想数は、ハッシュ テーブル内の他のすべてのキーについて、特定のキーと他のキーが衝突する確率の合計に等しくなります。この合計の項には 2 つのキーが関与する確率イベントのみが含まれるため、2 独立性があれば、この合計が真にランダムなハッシュ関数の場合と同じ値になることが保証されます。^[2]

ダブルハッシュは、独立性の度合いが低いハッシュ法の1つです。これは、2つのハッシュ関数を使用するオープンアドレッシングの一種です。1つはプローブシーケンスの開始を決定し、もう1つはプローブシーケンス内の位置間のステップサイズを決定します。これらが両方とも2独立である限り、この方法では操作ごとに一定の予想時間が得られます。^[8]

一方、ステップサイズが常に1であるオープンアドレッシングのより単純な形式である線形プロービングは、5つの独立したハッシュ関数を使用して操作ごとに一定の期待時間で動作することが保証されます。 ^[9]また、操作ごとに対数時間がかかる4つの独立したハッシュ関数も存在します。^[10]

カッコウハッシュ法では、必要なk独立性は2021年現在不明です。2009年には、 k独立性で十分であり、少なくとも6独立性が必要であることが示されました^[11] 。別のアプローチは、6独立ではないタブレーションハッシュ法を使用することですが、2012年^[12]には、カッコウハッシュ法に十分な他の特性があることが示されました。2014年の3番目のアプローチ^[13]は、いわゆるスタッシュを使用してカッコウハッシュテーブルをわずかに変更することであり、これにより、2独立ハッシュ関数のみを使用できるようになります。 ${\displaystyle O(\log n)}$

ケイン、ネルソン、デビッド・ウッドラフは2010年に個別要素問題に対するフラジョレ・マーティンアルゴリズムを改良した。 ^[14]正解の近似値を 得るためには、 -独立ハッシュ関数が必要である。 ${\displaystyle \epsilon }$${\displaystyle {\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}}$

次元削減のためのカウントスケッチアルゴリズムには、2独立ハッシュ関数 1 つと4 独立ハッシュ関数 1 つの 2 つが必要です。

MAX-3SAT問題のKarloff-Zwick アルゴリズムは、 3つの独立したランダム変数 を使用して実装できます。

MinHashアルゴリズムは、 1999年にPiotr Indykによって証明されたように、独立ハッシュ関数を使用して実装することができる^[15]${\displaystyle \log {\tfrac {1}{\epsilon }}}$

• モトワニ、ラジーブ、ラガヴァン、プラバカール (1995)。ランダム化アルゴリズム。ケンブリッジ大学出版局。p. 221。ISBN 978-0-521-47465-8。