5

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

4

2 回答 2

3

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

于 2012-09-16T16:47:38.093 回答
0

Probably your reference code did not have lazy delete, or the DELETED state was added to an existing implementation. Yes you can safely "undelete" an entry for your key. But make sure this algorithm is used consistently, to avoid the situation described in @Thomas' answer.

于 2012-09-16T18:04:59.787 回答