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