ダブルハッシュ

ダブル ハッシュは、ハッシュ テーブルでオープン アドレッシングと組み合わせて使用​​されるコンピュータ プログラミング手法であり、衝突が発生したときにキーの 2 次ハッシュをオフセットとして使用して、ハッシュ衝突を解決します。オープン アドレッシングを使用したダブル ハッシュは、テーブル上の古典的なデータ構造です。 ${\displaystyle T}$

二重ハッシュ法では、1 つのハッシュ値をテーブルへのインデックスとして使用し、目的の値が見つかるまで、空の位置に到達するまで、またはテーブル全体が検索されるまで、間隔を繰り返し進めます。ただし、この間隔は 2 番目の独立したハッシュ関数によって設定されます。線形プローブや二次プローブなどの代替の衝突解決方法とは異なり、間隔はデータによって異なるため、同じ位置にマッピングされる値は異なるバケット シーケンスを持ちます。これにより、衝突の繰り返しとクラスタリングの影響が最小限に抑えられます。

2 つのランダムで一様かつ独立したハッシュ関数と がある場合、バケットのハッシュ テーブル内の値 のバケット シーケンス内の 番目の位置は次のようになります。 一般に、と はユニバーサル ハッシュ関数のセットから選択され、は の範囲を持ち、 はの範囲を持つように選択されます。二重ハッシュはランダム分布を近似します。より正確には、ペアワイズ独立ハッシュ関数は、任意のキーのペアが同じバケット シーケンスに従う確率 を生成します。 ${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle i}$${\displaystyle k}$${\displaystyle |T|}$${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle h_{1}}$${\displaystyle \{0,|T|-1\}}$${\displaystyle h_{2}}$${\displaystyle \{1,|T|-1\}}$${\displaystyle (n/|T|)^{2}}$

二次ハッシュ関数にはいくつかの特性が必要です。 ${\displaystyle h_{2}(k)}$

• インデックスがゼロになることはありません。
• テーブル全体を循環するはずです。
• 計算は非常に高速になるはずです。
• それは からペアワイズ独立でなければなりません。${\displaystyle h_{1}(k)}$
• の分布特性は無関係です。これは乱数ジェネレータに類似しています。${\displaystyle h_{2}}$
• すべては| T | と互いに素でなければなりません。${\displaystyle h_{2}(k)}$

実際には:

• 両方の関数に除算ハッシュが使用される場合、除数は素数として選択されます。
• | T | が2の累乗の場合、最初と最後の要件は通常、常に奇数を返すことで満たされます。これには、1ビットの無駄により衝突の可能性が2倍になるという副作用があります。^[1]${\displaystyle h_{2}(k)}$

に格納されている要素数を とすると、の負荷係数は です。つまり、まず 2 つのユニバーサル ハッシュ関数と をランダムに、均一に、独立に選択して、二重ハッシュ テーブル を構築します。すべての要素は、と を使用した二重ハッシュによって に格納されます。キー が与えられた場合、-st ハッシュの位置は次のように計算されます。 ${\displaystyle n}$${\displaystyle T}$${\displaystyle T}$${\displaystyle \alpha =n/|T|}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle k}$${\displaystyle (i+1)}$

$${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$$

が固定の負荷係数 を持つものとします。Bradford とKatehakis ^[2]は、最初に選択したハッシュ関数を使用した場合、 での失敗した検索のプローブの期待数は、入力の分布に関係なく になることを示しました。ハッシュ関数のペアワイズ独立性で十分です。 ${\displaystyle T}$${\displaystyle \alpha :1>\alpha >0}$${\displaystyle T}$${\displaystyle {\tfrac {1}{1-\alpha }}}$

他のすべてのオープン アドレス指定形式と同様に、ハッシュ テーブルが最大容量に近づくと、二重ハッシュは線形になります。通常のヒューリスティックは、テーブルの読み込みを容量の 75% に制限することです。最終的には、他のすべてのオープン アドレス指定方式と同様に、より大きなサイズへの再ハッシュが必要になります。

ピーター・ディリンジャーの博士論文^[3]は、ブルームフィルタのようにハッシュ関数が集合として扱われる場合、二重ハッシュによって望ましくない同等のハッシュ関数が生成されることを指摘しています。および の場合、および ハッシュの集合は 同一です。これにより、衝突の可能性が期待される の2倍になります。 ${\displaystyle h_{2}(y)=-h_{2}(x)}$${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)}$${\displaystyle h(i,y)=h(k-i,x)}$${\displaystyle \left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}}$${\displaystyle 1/|T|^{2}}$

さらに、大部分が重複するハッシュ セットが多数存在します。 および の場合、 であり、の追加ハッシュ値の比較 ( の範囲の拡張) は役に立ちません。 ${\displaystyle h_{2}(y)=h_{2}(x)}$${\displaystyle h_{1}(y)=h_{1}(x)\pm h_{2}(x)}$${\displaystyle h(i,y)=h(i\pm 1,x)}$${\displaystyle i}$

ハッシュ関数に二次項^[4]（三角数）または偶数項（トリプルハッシュ）^[5]を追加すると、ハッシュ関数はいくらか改善されますが^[4]、この問題は解決されません。 ${\displaystyle i^{2},}$ ${\displaystyle i(i+1)/2}$${\displaystyle i^{2}\cdot h_{3}(x)}$

${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),}$

${\displaystyle h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),}$そして

${\displaystyle h_{3}(y)=h_{3}(x).}$

それから

${\displaystyle {\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}}$

3次項 ^[4]または（四面体数）^[1]を追加すると、問題は解決します。これは拡張ダブルハッシュと呼ばれる手法です。これは前方差分によって効率的に計算できます。 ${\displaystyle i^{3}}$${\displaystyle (i^{3}-i)/6}$

struct key ; /// 不透明/// 必要に応じて他のデータ型を使用します。(ラッピングを保証するには符号なしである必要があります。) extern unsigned int h1 ( struct key const * ), h2 ( struct key const * ); 	

          


///拡張ダブルハッシュを使用して、
2 つの基礎ハッシュ関数 h1() と h2() から k 個のハッシュ値を計算します。戻り値として、 /// hashes[i] = h1(x) + i*h2( x ) + (i*i*i - i)/6 が返されます。 /// 
C の unsigned 型の自動ラッピング (モジュラー削減) を利用します。 
void ext_dbl_hash ( struct key const * x , unsigned int hashes [], unsigned int n ) { unsigned int a = h1 ( x ), b = h2 ( x ), i ;
          

	        

    hashes [ i ] = a ; for ( i = 1 ; i < n ; i ++ ) { a += b ; // 2次差を加算して3次を得るb += i ; // 1次差を加算して2次を得る// i++ は定数差を加算して1次を得るhashes [ i ] = a ; } }  
	        
		  	
		  	
		       	
		  
	

衝突問題を解決することに加えて、拡張ダブルハッシュ法は、の特性に対するダブルハッシュ法の数値的制限も取り除き、特性が に似ている（ただし からは独立している）ハッシュ関数を使用できるようにします。^[1]${\displaystyle h_{2}(x)}$${\displaystyle h_{1}}$

• カッコウハッシュ
• 2択ハッシュ

• キャッシュがハッシュに与える影響、G​​regory L. Heileman および Wenbin Luo 著、2005 年。
• ハッシュテーブルアニメーション
• klib は、二重ハッシュ機能を備えた C ライブラリです。