我在区分二次和线性探测算法时遇到了问题。当我阅读概念性解释时,我看到 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;
}
最佳答案
这里生成的索引是:
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
,所以它是二次探测。
关于java - 这个散列探测方法是如何二次的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16366040/