0

Java での HashTables の実装を理解しようとしています。以下は私のコードです：

    Hashtable<Integer, String> hTab = new Hashtable<Integer, String>();
    hTab.put(1, "A");
    hTab.put(1, "B");
    hTab.put(2, "C");
    hTab.put(3, "D");

            Iterator<Map.Entry<Integer, String>> itr = hTab.entrySet().iterator();
    Entry<Integer, String> entry;

    while(itr.hasNext()){
        entry = itr.next();
        System.out.println(entry.getValue());
    }

実行すると、以下の出力が得られます: D C B

これは、Key = 1; の衝突が発生したことを意味します。そして実装に従って：

「hashTable で衝突が発生するたびに、特定のバケットに対応する linkedList に新しいノードが作成され、EntrySet(Key, Value) のペアがノードとしてリストに格納され、新しい値がリストの先頭に挿入されます。特定のバケットについて」。そして、私はこの実装に完全に同意します。

しかし、これが本当なら、hashTable からエントリセットを取得しようとしたとき、「A」はどこに行ったのでしょうか?

繰り返しますが、独自の HashCode と equals メソッドを実装することで、これを理解するために以下のコードを試しました。そして驚くべきことに、これは HashTable の実装に従って完璧に機能します。以下は私のコードです：

public class Hash {

    private int key;

    public Hash(int key){
        this.key = key;
    }

    public int hashCode(){
        return key;
    }

    public boolean equals(Hash o){
        return this.key == o.key;

    }

    }

    public class HashTable1 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Hashtable<Hash, String> hTab = new Hashtable<Hash, String>();

        hTab.put(new Hash(1), "A");
        hTab.put(new Hash(1), "B");
        hTab.put(new Hash(2), "C");
        hTab.put(new Hash(3), "D");

        Iterator<Map.Entry<Hash, String>> itr = hTab.entrySet().iterator();
        Entry<Hash, String> entry;

        while(itr.hasNext()){
            entry = itr.next();
            System.out.println(entry.getValue());
        }
    }
}

出力 : D C B A

これは完璧です。Java での HashTable の動作におけるこのあいまいさを理解できません。

アップデート

@garrytan と @Brian: 返信ありがとうございます。しかし、私にはまだ少し疑問があります。

私の2番目のコードでは、正常に動作します。新しいキーである 2 つのオブジェクトを作成しました。これらは 2 つのオブジェクトであるため、この場合キーの衝突は発生せず、正常に動作します。私はあなたの説明に同意します。ただし、最初のコード セットで単純に「1」ではなく「new Integer(1)」を使用すると、まだ機能しませんが、現在 2 つのオブジェクトを作成しており、それらは異なるはずです。以下の簡単な行を書いてクロスチェックしました：

            Integer int1 = new Integer(1);
            Integer int2 = new Integer(1);
            System.out.println(int1 == int2);

これは「False」を返します。つまり、キーの衝突は解決されているはずです。しかし、それでもうまくいきません。どうしてこれなの？

4

3 に答える 3

4

設計上、ハッシュテーブルは重複キーを格納するためのものではありません。

「ハッシュ衝突」と「キー衝突」の間で混乱していると思います。簡単に言えば、ハッシュ テーブルは、リンクされたリスト (つまり、バケット) のコレクションで構成されます。新しいキーと値のペア (KVP) を追加すると、キーのハッシュ値によってバケットに分散されます。「ハッシュ衝突」は、2 つのキーが同じハッシュになる場合に発生します (したがって、それらは同じバケットに入れられます)。

優れたハッシュ関数とは、キーを多数のバケットに均等に分散するものであり、キー検索のパフォーマンスが向上します。

于 2013-01-10T06:31:53.597 に答える
1

2番目の例は、equalsの実装が正しくないため、必要な動作を示しています。

署名は

public boolean equals(Object o) {}

いいえ

public boolean equals(Hash h) {}

したがって、作成したのはハッシュ衝突です。2つのオブジェクトは同じハッシュコード（キー）を持っていますが、equalsメソッドでは等しくありません（署名が間違っているため、これはまだ==演算子を使用しており、これは使用していません） .key == h.keyコード）。最初の例のように、オブジェクトが両方とも同じhashCodeを持ち、等しい場合のキーの衝突とは対照的です。2番目の例のコードを修正して実際のequals(Object o)メソッドを実装すると、値から「A」が再び欠落していることがわかります。

于 2013-01-10T06:57:01.363 に答える
0

2 番目の例では、次のシグネチャを使用しているため、元の equals 関数をオーバーライドしていません。

public boolean equals(Hash h) {}

したがって、パラメーターとしてオブジェクトを使用した元の equals 関数は引き続き使用され、挿入ごとに新しいオブジェクト ハッシュを作成すると、そのオブジェクトは他のオブジェクトとは異なるため、A と B のキーは等しくありません。

さらに、HashTable は各キーに対して 1 つの値を持つように設計されています。そして、キーは実際に比較される equals 関数に依存しています。

2 つの新しい整数を使用した例については、それらを .equals() と比較してみてください。また、hashCode 関数をオーバーライドして、オブジェクトごとに異なる hashCode を生成することも、生成しないこともできます。同じオブジェクトは同じコードにハッシュする必要があります。

于 2013-01-10T07:05:05.190 に答える