문제

I'm having a problem distinguishing between quadratic and linear probing algorithms. When I'm reading conceptual explanations, I see I^2 being repeatedly added to the last index tried. How is that the case here? What would linear probing change this into? From what I'm reading, the method below implements quadratic probing.

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;
}
도움이 되었습니까?

해결책

The indices generated here are:

H // offset : 1

H + 1 // offset : 3

H + 4 // offset : 5

H + 9 // offset : 7

.
.
.

Since n ^ 2 = 1 + 3 + 5 + ... + (n * 2 - 1), this is actually the function H(n) = H + n ^ 2, so it is quadratic probing.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top