как этот метод хеширования является квадратичным?

У меня проблема с различием между квадратичными и линейными алгоритмами зондирования. Когда я читаю концептуальные объяснения, я вижу, что 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;
}

java hashmap quadratic-probing
person rcj    schedule 03.05.2013    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Генерируемые здесь индексы:

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, так что это квадратичное зондирование.

person zw324    schedule 03.05.2013
comment
Что бы я изменил, чтобы сделать его линейным? Удалить offset += 2 ? - person rcj; 03.05.2013
comment
Да, так как это стало бы H(n) = H + n - person zw324; 03.05.2013