在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)以便当我们找到具有键的单元格或第一个删除/空单元格时循环结束.然后在插入中,测试细胞的状态.如果激活该条目已存在,则返回false; 否则插入元素.

Answer 1

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