c++ - 在 C++ 中实现哈希表(插入和延迟删除)

Question

我正在用 C++ 实现一个 Hashtable 类。我使用的冲突解决方法是带有惰性删除的线性探测。我已经看到了这个的实现，但对插入方法有疑问。哈希表的每个单元格都有一个状态(事件、删除、空)。出于某种原因，我在插入新元素时看到的实现中，他们对键进行哈希处理，然后探测表，直到找到 EMPTY 单元格(或直到找到已经包含相同键的单元格)。

示例代码:

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) 以便当我们找到带有键的单元格或第一个删除/空单元格时循环结束。然后在插入中，测试单元格的状态。如果 active 条目已经存在，则返回 false；否则插入元素。

Answer 1

key 可能已被进一步插入，随后其中一个中间单元格可能已被标记为已删除。然后您将插入同一键的重复实例。