刪除C++時的hashkey碰撞

爲了使我搜索foreach「symbol」我想從我的hashTable中刪除，我選擇了生成我插入它的hashkey。但是，我看到在我的刪除功能的問題是，當我需要從發現碰撞的地方刪除一個符號它以前導致我的while循環條件測試錯誤，我不想。刪除C++時的hashkey碰撞

bool hashmap::get(char const * const symbol, stock& s) const 
{ 
    int hash = this->hashStr(symbol); 
    while (hashTable[hash].m_symbol != NULL) 
    {  // try to find a match for the stock associated with the symbol. 
     if (strcmp(hashTable[hash].m_symbol , symbol) == 0) 
     { 
      s = &hashTable[hash]; 
      return true; 
     } 
     ++hash %= maxSize; 
    } 
    return false; 
} 

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) // collision found 
    { 
     ++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; 
} 
// What if I need to remove an index i generate? 
bool hashmap::remove(char const * const symbol) 
{ 
    int hashVal = this->hashStr(symbol); 
    while (hashTable[hashVal].m_symbol != NULL) 
    { 
     if (strcmp(hashTable[hashVal].m_symbol, symbol) == 0) 
     { 
      stock temp = hashTable[hashVal]; // we cansave it 
      hashTable[hashVal].m_symbol = NULL; 
      return true; 
     } 
     ++hashVal %= maxSize; // wrap around if needed 
    }  // go to the next cell meaning their was a previous collision 
    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; 
}

我需要做什麼才能從前一次碰撞中從我的hashTable中刪除「符號」？我希望這不是直接在上面的Java公式。

來源

2009-10-15 user40120

您需要做的是創建一個代表「已刪除」項的虛擬哨兵值。在表中插入新值時，需要檢查元素是否爲NULL或「已刪除」。如果某個插槽包含此標記「已刪除」值或插槽爲空，則該插槽是用於插入的有效插槽。這就是說，如果你正在編寫這段代碼進行生產，你應該考慮使用boost::unordered_map，而不是滾動你自己的哈希映射實現。如果這是爲了學功，......祝你好運。

來源

2009-10-15 02:02:00

看起來你正在實現一個開放尋址哈希表，是嗎？該方案中的刪除有點棘手。參見http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf：

「刪除密鑰對於開放尋址是有問題的：如果有兩個碰撞的鍵x和y與h（x）= h（y），並且鍵x被插入到鍵y之前，刪除鍵x，這不能簡單地通過將T [h（x）]標記爲FREE來完成，因爲這樣y就不會被找到了。一種可能性是將T [h（x）]標記爲DELETED（另一個特殊條目），當搜索一個關鍵字時，它被跳過，標記爲DELETED的表格地點也可能被重新用於存儲另一個要插入的關鍵字z，如果你確信這個關鍵字z不在表格中（即通過到達關鍵字z的探測序列的末尾而沒有發現它），這種重複使用使得插入方法變得複雜，而且，帶有DELETED鍵的地方填滿了表格。「

來源

2009-10-15 02:02:00 Matt

刪除C++時的hashkey碰撞

回答

相關問題