Функция хеша линейного зондирования не работает?

Question

Что я делаю не так с моей функцией линейного зондирования?

bool HashTable_lp::insert( const string & x )
{
    // Insert x as active
    int currentPos = findPos( x );
    if( isActive( currentPos ) )
        return true;
    array[ currentPos ] = HashEntry( x, ACTIVE );

    if( ++currentSize > array.size( ) / 2 )
        rehash( );
    return false;
}

Answer 1

Обычно вы хотите использовать цикл while, пока не найдете пустой слот. Другая проблема заключается в том, что вы приравниваете ячейку, в которой ваша строка хешируется, к значению, означающему, что ячейка содержит то же значение, которое вы пытаетесь вставить. В общем, вам нужно проверить значение вашего ключа для вставки по сравнению с существующими записями. Возможно, стоит сделать версию для вставки, которая не выполняет эту проверку, для случаев, когда пользователь может гарантировать, что элемент еще не находится в хэш-таблице, чтобы избежать этих сравнений ...

bool HashTable_lp::insert( const string & x )
{
    // Insert x as active
    int currentPos = findPos( x );
    while( isActive( currentPos ) ){
        // here key gets out of array[currentPos] the string key
        if(key(currentPos)==x) return true; // already in hash
        currentPos++; // linearly probe to next guy
    }
    // at this point we know currentPos is empty 
    array[ currentPos ] = HashEntry( x, ACTIVE );

    if( ++currentSize > array.size( ) / 2 ) // ensure load factor is .5 to guarantee probing works!
        rehash( );
    return false;
}