從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。所以，如果你堅持試圖從這樣的表中刪除，你必須從這個散列的所有地方走到下一個空的地方，然後重新散列這些項目以找出它原來的位置來自並保證如果你刪除了某些東西，那麼這些鏈條中的每一條都可以從原始散列點始終保持原樣到最終結束。

它是可能使這項工作 - 但它的不很容易。鑑於一般線性探測的工作情況如何，它不值得！