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

我的线性探测功能出了什么问题？

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

最佳答案

通常需要一会儿循环，直到找到一个空插槽。另一个问题是，您将一个字符串散列表示为 Activity 的单元格等同于该单元格包含与您要插入的值相同的值。通常，您需要检查密钥的值以针对现有条目进行插入。对于用户可以保证该项目不在哈希表中以避免这种比较的情况，可能值得制作一个不执行此检查的插入版本...

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

关于c++ - 线性探测哈希函数不起作用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8381477/