java - 如果 keySet() 维护 HashMap 的顺序,为什么我们需要 LinkedHashMap?

标签 java collections hashmap linkedhashmap keyset

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;
    }
}

如果你在上面的例子中看到,我已经明确地让 hashcode() 在所有情况下都返回 1,以检查当 hashmap 中的 key.hashcode() 发生冲突时会发生什么。发生了什么,为这些 Map.Entry 对象维护了一个链表,例如

1(key.hashcode()) will link to <2,false> will link to <10,true>

(据我所知,因为在真值之后输入了假值)。

但是当我执行 keySet() 时,先返回 true 再返回 false,而不是先返回 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 哈希码方法以返回一个赞时

@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

现在又让我想知道,为什么订单以排序的方式出现。?谁能详细解释一下 hashmap 的 keySet()、entrySet() 方法是如何工作的?

最佳答案

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() 函数非常糟糕,而且对于单字符字符串来说特别糟糕。这是字符串的 hashCode() specification .本质上它是一个加法和乘法,但对于单字符字符串,它只是 char 的 Unicode 值。所以上面单字符串的哈希码是65, 66, ... 90。 HashMap 的内表总是2的幂,在本例中它有64个条目。使用的表条目是键的 hashCode() 值右移 16 位并与自身异或,以表大小为模。 ( See the code here 。)因此,这些单字符字符串最终出现在 HashMap 表中的顺序存储桶中,位于数组位置 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)]

同样,由于实现的巧合, key 按顺序出现,但原因与上述不同。

但是等等!在 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 的单次运行中是稳定的。此外,HashMap 等现有集合将其迭代顺序随机化。)

关于java - 如果 keySet() 维护 HashMap 的顺序,为什么我们需要 LinkedHashMap?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37744345/

相关文章:

Java8 : Map<X, Y> 到 Map<X, Z> 使用 RxJava

java - 我应该如何本地化数据库中始终必须为英文的系统字符串?

java - 命令行参数被忽略

java - Android MPChart 重置scrollingX

arrays - Swift 中数组、集合和字典的区别

Java 8 将 Map<K, List<V>> 转换为 Map<V, List<K>>

spring - 如何在 JAVA 的 rest API 中将图像返回给浏览器?

java - 如何比较2个Maps Java的值

Java 从每个键的一个项目中获取所有可能的组合

hash - 内部哈希和外部哈希之间的区别