这个哈希探测方法是如何二次的

Question

我有一个问题区分二次和线性探测算法。当我阅读概念解释时，我看到I^2被反复添加到最后一次尝试的索引中。这里的情况如何呢?线性探测会把它变成什么?从我读到的，下面的方法实现了二次探测。

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，所以它是二次探测。