从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。所以，如果你坚持试图从这样的表中删除，你必须从这个散列的所有地方走到下一个空的地方，然后重新散列这些项目以找出它原来的位置来自并保证如果你删除了某些东西，那么这些链条中的每一条都可以从原始散列点始终保持原样到最终结束。

它是可能使这项工作 - 但它的不很容易。鉴于一般线性探测的工作情况如何，它不值得！