3
public class HashMapKeySet {

public static void main(String[] args) {
    Map<HashCodeSame,Boolean> map=new HashMap();

    map.put(new HashCodeSame(10),true);
    map.put(new HashCodeSame(2),false);

    for(HashCodeSame i:map.keySet())
        System.out.println("Key: "+i+"\t Key Value: "+i.getA()+"\t Value: "+map.get(i)+"\t Hashcode: "+i
                .hashCode());

    System.out.println("\nEntry Set******");
    for(Map.Entry<HashCodeSame, Boolean> i:map.entrySet())
        System.out.println("Key: "+i.getKey().getA()+"\t Value: "+i.getValue()+"\t Hashcode: "+i.hashCode());

    System.out.println("\nValues******");
    for(Boolean i:map.values())
        System.out.println("Key: "+i+"\t Value: "+map.get(i)+"\t Hashcode: "+i.hashCode());

}

static class HashCodeSame{

    private int a;

    public int getA() {
        return a;
    }

    public void setA(int a) {
        this.a = a;
    }

    HashCodeSame(int a){
        this.a=a;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        HashCodeSame that = (HashCodeSame) o;

        return a == that.a;

    }

    @Override
    public int hashCode() {
        return 1;
    }
}

}

上記の例でわかるように、hashmap で key.hashcode() の衝突が発生した場合に何が起こるかを確認するために、すべてのケースで hashcode() が 1 を返すように明示的に設定しました。何が起こるか、これらの Map.Entry オブジェクトのリンクされたリストが維持されます。

1(key.hashcode()) は <2,false> にリンクし、<10,true> にリンクします

(私が理解しているように、真の値の後に偽の値が入力されるため)。

しかし、keySet() を実行すると、最初に false が返されるのではなく、最初に true が返され、次に false が返されます。

したがって、ここで想定しているのは、keySet() はセットであり、セットは順序を維持するため、反復中に true と false を取得します。しかし、繰り返しになりますが、取得する唯一の方法は順序によるものであるため、hashmap は順序を維持しているとは言えません。または、LinkedHashMap を使用する理由は何ですか?

 Key: DS.HashMapKeySet$HashCodeSame@1    Key Value: 10   Value: true     Hashcode: 1
Key: DS.HashMapKeySet$HashCodeSame@1     Key Value: 2    Value: false    Hashcode: 1

Entry Set******
Key: 10  Value: true     Hashcode: 1230
Key: 2   Value: false    Hashcode: 1236

Values******
Key: true    Value: null     Hashcode: 1231
Key: false   Value: null     Hashcode: 1237

ここで、chsnge を追加して hashcode メソッドを追加すると、like が返されます

@Override
    public int hashCode() {
        return a;
    }

逆順になります。さらに追加で

    map.put(new HashCodeSame(10),true);
    map.put(new HashCodeSame(2),false);
    map.put(new HashCodeSame(7),false);
    map.put(new HashCodeSame(3),true);
    map.put(new HashCodeSame(9),true);

受け取った出力は、

    Key: DS.HashMapKeySet$HashCodeSame@2     Key Value: 2    Value: false    Hashcode: 2
Key: DS.HashMapKeySet$HashCodeSame@3     Key Value: 3    Value: false    Hashcode: 3
Key: DS.HashMapKeySet$HashCodeSame@7     Key Value: 7    Value: false    Hashcode: 7
Key: DS.HashMapKeySet$HashCodeSame@9     Key Value: 9    Value: true     Hashcode: 9
Key: DS.HashMapKeySet$HashCodeSame@a     Key Value: 10   Value: true     Hashcode: 10

Entry Set******
Key: 2   Value: false    Hashcode: 1239
Key: 3   Value: false    Hashcode: 1238
Key: 7   Value: false    Hashcode: 1234
Key: 9   Value: true     Hashcode: 1222
Key: 10  Value: true     Hashcode: 1221

Values******
Key: false   Value: null     Hashcode: 1237
Key: false   Value: null     Hashcode: 1237
Key: false   Value: null     Hashcode: 1237
Key: true    Value: null     Hashcode: 1231
Key: true    Value: null     Hashcode: 1231

今でも疑問に思っています, なぜ順序がソートされているのですか.? ハッシュマップのkeySet()、entrySet()メソッドがどのように機能するかを詳しく説明してもらえますか?

4

2 に答える 2

6

HashMap には反復順序が定義されておらず、反復順序が指定されてLinkedHashMap ます。

の難しさHashMapは、反復順序が非常に予測可能で、かなり安定している単純な例を簡単に作成できることです。ただし、これは保証されていません。

たとえば、次のようにしたとします。

    Map<String, Boolean> map = new HashMap<>();
    String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = 0; i < str.length(); i++) {
        map.put(str.substring(i, i+1), true);
    }
    System.out.println(map.keySet());

結果は

[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]

おい!それらは順調です!その理由は、String の hashCode() 関数がかなりお粗末であり、1 文字の文字列に対しては非常にお粗末だからです。これが String のhashCode() 仕様です。基本的には加算と乗算ですが、単一文字の文字列の場合は、その Unicode 値にすぎませんchar。したがって、上記の単一文字列のハッシュコードは 65、66、... 90 です。 の内部テーブルHashMapは常に 2 のべき乗であり、この場合は 64 エントリの長さです。使用されるテーブル エントリは、キーのhashCode()値を 16 ビット右シフトし、テーブル サイズを法としてそれ自体と XOR 演算したものです。(コードはこちらを参照してくださいHashMap。) したがって、これらの 1 文字の文字列は、テーブル内の配列位置 1、2、... 26の連続したバケットになります。

キーの反復処理はバケットを介して順次進行するため、キーは配置された順序と同じ順序で出力されます。繰り返しますが、これは保証されていません。実装のさまざまな部分の特性により、たまたまこのように機能するだけです。上記のように。

ここHashCodeSameで、hashCode()関数が毎回 1 を返す場所を考えてみましょう。これらのオブジェクトのいくつかを に追加するHashMapと、それらすべてが同じバケットに入れられます。反復はリンクされたリストを順番にトラバースするため、順番に出てきます。

    Map<HashCodeSame, Boolean> map = new HashMap<>();
    for (int i = 0; i < 8; i++) {
        map.put(new HashCodeSame(i), true);
    }
    System.out.println(map.keySet());

toString()(明らかなことを行うメソッドを追加しました。) 結果は次のとおりです。

[HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(5), HCS(6), HCS(7)]

繰り返しになりますが、キーは実装の偶然の一致により順番に出てきますが、上記とは異なる理由があります。

ちょっと待って!JDK 8 ではHashMap、同じバケットに含まれるエントリが多すぎる場合に、線形リンク リストからバランス ツリーにバケットを変換します。これは、8 つを超えるエントリが同じバケットに入った場合に発生します。それを試してみましょう:

    Map<HashCodeSame, Boolean> map = new HashMap<>();
    for (int i = 0; i < 20; i++) {
        map.put(new HashCodeSame(i), true);
    }
    System.out.println(map.keySet());

結果は次のとおりです。

[HCS(5), HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(6),
HCS(18), HCS(7), HCS(11), HCS(16), HCS(17), HCS(15), HCS(13),
HCS(14), HCS(8), HCS(12), HCS(9), HCS(10), HCS(19)]

肝心なのは、定義された反復順序を維持してHashMapないということです。特定の反復順序が必要LinkedHashMapな場合は、または などのソート マップを使用する必要がありますTreeMap。残念ながら、HashMapにはかなり安定した予測可能な反復順序があります。実際には、実際にはそうではない場合でも、その順序が明確に定義されていると人々を思い込ませるのに十分なほど予測可能です。


この問題に対処するために、JDK 9 では、新しいハッシュベースのコレクションの実装により、実行ごとに反復順序がランダム化されます。例えば:

    Set<String> set = Set.of("A", "B", "C", "D", "E",
                             "F", "G", "H", "I", "J");
    System.out.println(set);

JVM のさまざまな呼び出しで実行すると、次のように出力されます。

[I, H, J, A, C, B, E, D, G, F]
[C, B, A, G, F, E, D, J, I, H]
[A, B, C, H, I, J, D, E, F, G]

(反復順序は、JVM の 1 回の実行内では安定しています。また、 などの既存のコレクションでは、反復順序がランダム化されHashMapていません。)

于 2016-06-10T20:33:32.677 に答える