I'm trying to write a proper remove function for my hash table using linear probing collision resolution method.
I run a tester that removes several records from my hash table. At certain point, my find function cannot find an element to delete. However, it supposed to be still in the table. I think that I'm doing my rehash in remove() in a wrong way.
Class HashTable contains member table, an array of structures of type Record
template <class TYPE>
struct Record{
string key;
TYPE value = NULL;
Record(){
key = "";
value = 0;
}
Record(const char* key_, TYPE value_){
key = key_;
value = value_;
}
Record(string key_, TYPE value_){
key = key_;
value = value_;
}
};
template <class TYPE>
bool HashTable<TYPE>::remove(const char* key){
int tvalue; //temporary unused value to make find work
if (find(key, tvalue))
{
table[lastFoundIdx].key = ""; //lastFoundIdx - index of element that contains a key
table[lastFoundIdx].value = 0;
numRec--; //reduce number of records in table
int startIdx = lastFoundIdx; //rehash will stat form start Index
int i;
if (lastFoundIdx == maxSize - 1)
i = 0;
else
i = lastFoundIdx + 1;
while (table[i].key != ""&&i != maxSize){ // rehash starts here
std::size_t h1 = std::hash<std::string>()(table[i].key);
int hash = h1%maxSize;
if (hash < i&&hash >= startIdx){
table[startIdx].key = table[i].key;
table[startIdx].value = table[i].value;
table[i].key = "";
table[i].value = 0;
startIdx = i;
}
i++;
}
return true;
}
else return false;
}
Here's also my find function which seems to be working fine but I could be wrong
template <class TYPE>
bool HashTable<TYPE>::find(const char* key, TYPE& value){
std::size_t h1 = std::hash<std::string>()(key);
int hash = h1%maxSize;
int startIdx = hash;
while (table[hash].key != "" && table[hash].key != key){
hash = (hash + 1) % maxSize;
if (hash == startIdx)
return false;
}
if (table[hash].key == "")
return false;
else{
lastFoundIdx = hash;
value = table[hash].value;
return true;
}
}
Could you please help me to determine if I'm doing remove in a right way for linear probing?
