c++ - 线性探测哈希函数不起作用？

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 循环，直到找到一个空槽。另一个问题是您将字符串散列的单元格等同于处于事件状态，这意味着该单元格包含您尝试插入的相同值。通常，您需要根据现有条目检查要插入的 key 的值。对于用户可以保证该项目不在哈希表中以避免这些比较的情况，可能值得制作一个不执行此检查的插入版本......

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;
}