這個散列探測方法是如何二次的？

Question

我有一個區分二次和線性探測算法的問題。當我在閱讀概念性解釋時，我看到我^ ^被重複添加到最後一個索引的嘗試。這裏的情況如何？線性探測會將此變爲什麼？從我正在閱讀的內容來看，下面的方法實現了二次探測。

private int findPosQuadratic(AnyType x) 
{ 
    int offset = 1; 
    int currentPos = myhash(x); 

    while(array[ currentPos ] != null && 
      !array[ currentPos ].element.equals(x)) 
    { 
     currentPos += offset; // Compute ith probe 
     offset += 2; 
     if(currentPos >= array.length) 
      currentPos -= array.length; 
    } 

    return currentPos; 
} 

Answer 1

這裏產生的指標是：

H // offset : 1 

H + 1 // offset : 3 

H + 4 // offset : 5 

H + 9 // offset : 7 

. 
. 
. 

由於n^2 = 1 + 3 + 5 + ... + (n * 2 - 1)，這實際上是功能H(n) = H + n^2，所以它是二次探測。