ejw ejw -4 years ago 132
C++ Question

Implementing hashtables in C++ (insertion and lazy deletion)

I am implementing a Hashtable class in C++.
The collision resolution method that I am using is linear probing with lazy deletion.
I have seen implementations of this but had a question with regards to the insert method.
Each cell of the hashtable has a state (active, deleted, empty). For some reason in the implementation I have seen when inserting a new element, they hash the key and then probe the table until an EMPTY cell is found (or until a cell already containing the same key is found).

Example Code:

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
}


My question is: Is there a reason not to stop and insert into a cell that has been tagged as deleted? In other words, in the
findPos
method, why not change the while statement to
while(data[currentPos].state==ACTIVE && data[currentPos].key!=key)
so that the loop ends either when we find the cell with the key or the first deleted/empty cell. Then in the insert, test the state of the cell. If active the entry already exists, so return false; else insert the element.

Answer Source

The key could have been inserted further on, and later one of the intervening cells could have been marked as deleted. Then you would insert a duplicate instance of the same key.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download