3

我正在尝试使用线性探测冲突解决方法为我的哈希表编写一个正确的删除函数。

我运行了一个测试器，它从我的哈希表中删除了几条记录。在某些时候，我的查找功能找不到要删除的元素。但是，它应该仍在桌子上。我认为我正在以错误的方式在 remove() 中进行重新散列。

类HashTable包含 member table，一个类型的结构数组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;
}

这也是我的查找功能，它似乎工作正常，但我可能是错的

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;
        }
    }

你能帮我确定我是否以正确的方式进行线性探测吗？

4

0 回答 0