二次プロービング

二次プロービングは、ハッシュ テーブル内のハッシュ衝突を解決するためのコンピュータ プログラミングにおけるオープン アドレス指定方式です。二次プロービングは、元のハッシュ インデックスを取得し、空きスロットが見つかるまで 任意の二次多項式の連続した値を追加することで動作します。

二次プローブを使用したシーケンスの例は次のとおりです。

${\displaystyle H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}}$

二次プロービングはクラスタリングが少ないため、線形プロービングの代替として推奨されることが多い。^{[1]二次プロービングは、}連鎖などの他の多くのハッシュテーブルよりも参照の局所性が優れている。しかし、クエリの場合、二次プロービングは線形プロービングほど局所性が高くないため、設定によっては線形プロービングの方が高速になることがある。^[2]

二次プロービングは1968年にウォード・ダグラス・マウラーによって初めて導入されました。^[3]

h ( k ) をハッシュ関数とし、要素k を[0, m −1]の整数に マッピングする。ここでm はテーブルのサイズである。値kのi^番目のプローブ位置は関数

${\displaystyle h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod {m}}}$

ここで、c ₂ ≠ 0 です（c ₂ = 0 の場合、h ( k , i ) は線形プローブに低下します）。与えられたハッシュテーブルでは、 c ₁とc ₂の値は一定のままです。

例:

• の場合、プローブ配列は${\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}$${\displaystyle h(k),h(k)+2,h(k)+6,...}$
• m = 2 ⁿの場合、定数の適切な選択はc ₁ = c ₂ = 1/2 です。これは、  [0,  m −1] 内のiに対するh ( k , i )の値がすべて異なるためです (実際、これは [0, m −1]上の順列です^[4] )。これにより、値が 1、2、3、... と増加する(三角数)のプローブシーケンスが得られます。${\displaystyle h(k),h(k)+1,h(k)+3,h(k)+6,...}$
• 素数m > 2 の場合、 c ₁とc ₂のほとんどの選択により、 iが [0, ( m −1)/2]の範囲内にある場合、 h ( k , i ) が別個になります。このような選択には、 c ₁ = c ₂ = 1/2、c ₁ = c ₂ = 1、c ₁ = 0、c _{2 = 1 などがあります。ただし、特定の要素には}m /2 個の異なるプローブしかないため、負荷係数が 1/2 を超える場合に挿入が成功することを保証するには、他の手法が必要になります。
• （ m、n、pは2以上の整数（p = 1のときは線形プローブに低下する））の場合、すべての異なるプローブのサイクルが与えられます。これはループで次のように計算できます。${\displaystyle m=n^{p}}$${\displaystyle h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}}$${\displaystyle h(k,0)=h(k)}$${\displaystyle h(k,i+1)=(h(k,i)+2in+n+1){\pmod {m}}}$
• 任意のmについて、二次プローブによる完全なサイクルは、 m を最も近い 2 の累乗に切り上げ、プローブ インデックスを計算し、の場合は反復をスキップすることで実現できます。スキップされる反復は最大で であり、これらの反復はメモリを参照しないため、ほとんどの最新プロセッサで高速に動作します。 m の切り上げは次のように計算できます。${\displaystyle h(k,i)=h(k)+((i^{2}+i)/2){\pmod {roundUp2(m)}}}$${\displaystyle h(k,i)>=m}$${\displaystyle roundUp2(m)-m<m/2}$

uint64_troundUp2 ( uint64_t v ) { v -- ; v |= v >> 1 ; v |= v >> 2 ; v |= v >> 4 ; v |= v >> 8 ; v |= v >> 16 ; v |= v >> 32 ; v ++ ; v を返します。}  
	
	    
	    
	    
	    
	    
	    
	
	 

オフセットの符号が交互になっている場合 (例: +1、-4、+9、-16 など)、およびバケットの数が3 を法として 4 と合同な素数である場合 (例: 3、7、11、19、23、31 など)、最初のオフセットは一意になります (法)。^{[詳細な説明が必要]}つまり、0 から までの順列が得られ、その結果、少なくとも 1 つ存在する限り、空きバケットが常に見つかります。 ${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p-1}$

• チュートリアル/二次プロービング