3

線形プローブ衝突解決法を使用して、ハッシュ テーブルの適切な削除関数を作成しようとしています。

ハッシュ テーブルからいくつかのレコードを削除するテスターを実行します。特定の時点で、検索機能が削除する要素を見つけることができません。ただし、それはまだテーブルにあるはずです。remove() で再ハッシュを間違った方法で行っていると思います。

クラスHashTableには membertable型の構造体の配列が含まれます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