1

私は割り当てに取り組んでおり、10,000個の数値をロードサイズ.1、.2 .3 ....〜.9のハッシュテーブルにハッシュする必要がありました。私の問題は、ハッシュ関数がオーバーフローなどを発生させていることです。36077（mod）20,000のように負荷率が.5のテーブルのハッシュを実行している場合、キーとして16070が返されます。これは、負荷率を超える数値でのみ発生します。これは私のハッシュ関数のコードです。

    public int linearHash(int in){
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        hashKey += 1;
    }
    return hashKey;
}

ありがとうございました。

4

2 に答える 2

0

ループ内hashTableArrayののインデックス境界を超えていることを確認していません。whileあなたができること：

while (hashKey < hashTableArray.length && this.hashTableArray[hashKey] != 0){
于 2012-11-02T21:23:42.650 に答える
0

Reimeusは、OutOfBoundの問題を指摘し、解決策を提供しました。衝突を処理する方法について何かを追加したいと思います。

あなたの関数はオープンアドレッシングアプローチのように見えます。おそらくあなたの代わりにhashKey += 1;あなたはin

 public int linearHash(int in){   
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        in ++;
        hashKey = in%hashTableArray.length;
    }
    return hashKey;
}

上記のサンプルコードは、ハッシュテーブルのオーバーフローをチェックしませんでした。自動インクリメントは複数hashTableArray.length回発生しないようにする必要があります。そうしないと、プログラムがデッドループに陥ります

hashTableArray[hashKey] != 0また、スロットが空いているかどうかを確認して判断するのは安全ではないことに注意してください。0たとえば、数と20000要素にはどうでしょうか。

于 2012-11-02T21:59:52.213 に答える