从HashTable C++中删除

Question

你如何从基于数组的哈希表中删除？我需要准备从表中删除几个符号.如果我在固定大小的字符数组中转储我要删除的内容,那么如何找到"可能"删除的内容？

bool hashmap::get(char const * const symbol, stock& s) const
{
    int hashVal = this->hashStr( symbol );
    int initialHash = -1;

    while ( hashTable[hashVal].m_symbol != NULL )
    {   // try to find a match for the stock associated with the symbol.

        if ( initialHash == -1 )
        {
             initialHash = hashVal;
        }
        if ( strcmp( hashTable[hashVal].m_symbol, symbol ) == 0 )
        {
            s = &hashTable[hashVal];
            return true;
        }
        ++hashVal %= maxSize;
    }
    if ( hashTable[hashVal].m_symbol == NULL || hashVal == initialHash )
    {
         return false;
    }
    else return true;
}

bool hashmap::put(const stock& s, int& usedIndex, int& hashIndex, int& symbolHash)
{
    hashIndex = this->hashStr( s.m_symbol ); // Get remainder, Insert at that index.
    symbolHash = (int&)s.m_symbol;
    usedIndex = hashIndex;

    while ( hashTable[hashIndex].m_symbol != NULL )
    {
        ++usedIndex %= maxSize; // if necessary wrap index around
        if ( hashTable[usedIndex].m_symbol == NULL )
        {
            hashTable[usedIndex] = s;
            return true;
        }
        else if ( strcmp( hashTable[usedIndex].m_symbol , s.m_symbol ) == 0 )
        {
            return false; // prevent duplicate entry
        }
    }
    hashTable[hashIndex] = s; // insert if no collision 
    return true;
}

bool hashmap::remove(char const * const symbol)
{
    int hashVal = this->hashStr( symbol );
    int initialHash = -1;

    while ( hashTable[hashVal].m_symbol != NULL  )
    {
        if ( initialHash == -1 )
        {
            initialHash = hashVal;
        }
        if ( strcmp( hashTable[hashVal].m_symbol, symbol ) == 0 )
        {
            hashTable[hashVal].m_symbol = NULL;
            return true;
        }
        ++hashVal %= maxSize; // wrap around if needed
    }   // go to the next cell if not found

    if ( hashVal != initialHash && hashTable[hashVal].m_symbol != NULL )
    {
        return true;
    }
    return false;
}

int hashmap::hashStr(char const * const str)
{   
    size_t length = strlen( str );
    int hash = 0;
    for ( unsigned i = 0; i < length; i++ )
    {
         hash = 31 * hash + str[i];
    }
    return hash % maxSize;
 }

Answer 1

对于您正在使用的哈希冲突类型,删除最多也是有问题的.然而,这种散列方式也没有做任何其他事情 - 即使在相对较低的负载率下也会导致显着的聚类.

如果要支持删除,可能需要使用链接来解决冲突.在这种情况下,删除简单明了.您散列以查找正确的链接列表,搜索链接列表中的项目,以及(如果找到)将其从链接列表中删除.

编辑:删除比可能立即明显更难.例如,假设您要删除散列到表中N位置的内容,但是您在位置N + 3处找到它.然而,在N + 4位置可能存在某些东西(例如)可能最初在位置N-1处进行了散列.所以,如果你坚持试图从这样的表中删除,你必须从这个散列的地方一直走到表中的下一个空位,然后重新散列每个项目以找出它最初的位置来自,并确保如果你删除了某些东西,那么这些链中的每一个都会从其原始哈希点到最终的任何地方保持完整.

这是可能的,使这项工作-但它并不容易.鉴于一般情况下线性探测效果不佳,这是不值得的!