c++ - 誤った値を返す二重ハッシュ関数

原文 c++ dictionary hash double-hashing

ダブルハッシュマップを作成していますが、挿入後に削除機能が機能しません。インデックスを増やす場合も同じ形式に従いますが、正しいインデックスにヒットしません。

class RHHM {
    unsigned int hash2( int key ) {

        return key % (M-1) + 1;

    }

    //Private variables

    hashNode ** map;        //Backing array
    unsigned int M;   //Capacity of array

    //If index that key hashes to is empty, insert. Else, replace value at hashed index.
    int insert( int key, char value ) {

        int f = hash( key );
        int f2 = hash2 ( key );
        int p = 0;
        int h = f + (p * f2) % M;

        while( map[h] != NULL ) {

            if( p == M )
                return -1 * p;

            if( map[h]->key == key ) {
                map[h]->value = value;
                return p;
            }
            else {
                ++p;
                h = f + (p * f2) % M;
            }
        }

        map[h] = new hashNode( key, value );
        return p;
    }

int remove( int key, char &value) {

        int f = hash( key );
        int f2 = hash2 ( key );
        int p = 0;                         //Keeps track of how many indexes have been checked
        int h = f + (p * f2) % M;

        while( map[h] != NULL ) {

            if( p  == M )              //If item is not found in table, return false
                return -1 * p;

            if( key == map[h]->key )        //If key is found, break out of loop
                break;
            else {
                ++p;
                h = f + (p * f2) % M;  //Wrap around array if necessary
            }

        }

        if( map[h] == NULL )                //If end of cluster reached, return false
            return -1 * p;

        value = map[h]->value;              //Stores the value of the item to be deleted
        delete map[h];                      //Delete the item the user specified
        map[h] = NULL;
        ++p;
        h = f + (p * f2) % M;
        for( ; map[h] != NULL; h = f + (p * f2) % M) {     //While still in the cluster, remove and     reinsert all items
            int tempKey = map[h]->key;
            char tempValue = map[h]->value;
            delete map[h];
            map[h] = NULL;
            insert(tempKey, tempValue);
            ++p;
        }
        return p;

    }

}


そして、これが私のメインです:

RHHM bh(10);
bh.insert(0, 'A');
bh.insert(10, 'B');
bh.insert(20, 'C');
bh.print(std::cout);


出力:

<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>


ご覧のとおり、最初のインデックスは0にハッシュされます。 10キーは0と衝突するため、ダブルハッシュ(10)は1にハッシュする必要がありますが、そのハッシュは2です。
なぜ間違った値を返すのですか?
答え
これは、hash2関数がキー10の値2を返すためです。hash2(10)の場合、hash2は次のように表示されます。

return 10 % (10-1) + 1


これは、演算子の優先順位によって、値2 asに評価されます。

return (10 %(10-1))+1


挿入機能では、衝突が発生したときに、ハッシュ値にhash2値を追加して、評価される新しいインデックスを取得します。

h= f + ( P * f2 ) % M
h= 0 + (1 * 2 ) % 10 \\ this evaluates to 2.


そのため、新しいインデックスは2になります。

編集:コードには、演算子の優先順位に関するいくつかの問題があります。
最初
h = f +(p * f2)%M; //必要に応じて配列をラップします

これは配列をラップしません。 %が+よりも優先されるためです。 fには[0-M-1]の範囲の値があり、(p * f2)%Mには[0-M-1]の範囲の値があります。したがって、上記の式は[0-2 * M-2]の範囲の値に評価される場合があります。これは、コード内の他のそのような式にも当てはまります。これが、ハッシュテーブルで一部のキーが欠落している理由です。
関連記事

c++ - OpenCVでのレーン検出器分割線C++

c++ - Qtでマウスイベントが発生したときに呼び出される関数の宣言

c++ - リンクリストで変更されたデータはメモリに反映されません

c++ - C++とFortranの並列MM速度差ループタイリング

c++ - カスタムデータ型は、可変サイズの効率のための可能で実行可能なオプションですか?

c++ - このC++プログラムにコマンドライン入力を与える方法

c++ - C++プロキシDLL(64ビット)

java - Android Gstreamer SDKでANativeWindow_lockがエラー-22を返す

c++ - doxygenの「ファイルドキュメント」リストから「README.md」を除外します

java - 最小の「XOR」演算でバイナリマトリックスを再作成する