在C++中實現哈希表（插入和延遲刪除）

我正在C++中實現一個哈希表類。我正在使用的衝突解決方法是使用延遲刪除的線性探測。我已經看到了這個實現，但有一個關於插入方法的問題。散列表的每個單元格都有一個狀態（活動的，刪除的，空的）。出於某種原因，我在實現中看到了插入新元素時，他們散列密鑰，然後探測表，直到找到EMPTY單元（或直到找到包含相同密鑰的單元）。在C++中實現哈希表（插入和延遲刪除）

示例代碼：

int findPos(const string &key){ 
    int currentPos=hash(key); 
    while(data[currentPos].state!=EMPTY && data[currentPos].key!=key){ 
     currentPos++; 
     if (currentPos>=data.size()) 
      currentPos-=data.size() 
     } 
     return currentPos; 
} 

bool insert(const string &key){ 
    int currentPos=findPos(key); 
    if (isActive(currentPos)) 
      return false; //already exists 
    data[currentPos]=hashEntry(key,ACTIVE); 
    if (++currentSize>data.size()/2) 
      rehash(); 
    return true; //element inserted 
}

我的問題是：有沒有理由不停止，並插入到爲刪除已標記的細胞？換言之，在findPos方法中，爲什麼不將while語句更改爲while(data[currentPos].state==ACTIVE && data[currentPos].key!=key)，以便循環在我們找到帶有鍵或第一個刪除/空單元格的單元格時結束。然後在插入中測試單元格的狀態。如果活動條目已經存在，那麼返回false;否則插入元素。

來源

2012-09-16 ejw

該鍵可能已被插入，並且稍後其中一個插入單元可能已被標記爲已刪除。然後你會插入同一個鍵的重複實例。

來源

2012-09-16 16:47:38

可能您的參考代碼沒有延遲刪除，或DELETED狀態已添加到現有實施中。是的，您可以安全地「取消刪除」您的密鑰條目。但要確保這個算法的使用是一致的，以避免@Thomas的回答中所描述的情況。

來源

2012-09-16 18:04:59

在C++中實現哈希表（插入和延遲刪除）

回答

相關問題