在C++中实现哈希表（插入和惰性删除）

Question

我正在C++中实现一个Hashtable类。 我使用的冲突解决方法是带有延迟删除的线性探测法。 我看到了一些实现，但对于插入方法有一个问题。 哈希表的每个单元格都有一个状态（活动状态、已删除状态和空状态）。 由于某种原因，在我看到的实现中，当插入新元素时，它们会先计算哈希值，然后在哈希表中进行探查，直到找到一个空单元格（或者找到一个已经包含相同键的单元格）。

示例代码:

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；否则插入元素。

- ejw

Answer 1

该关键字本可以插入更深的位置，稍后可以将介于其间的某个单元标记为已删除。然后再插入相同关键字的重复实例。

- Thomas Padron-McCarthy

Answer 2

可能你的参考代码没有实现延时删除，或者是将“已删除”状态添加到现有的实现中。是的，你可以安全地为你的键“撤销删除”。但是请确保这个算法被一致地使用，以避免 @Thomas 回答中描述的情况发生。

- Alex Cohn