为什么在HashMap已经可以维护keySet()的顺序的情况下还需要LinkedHashMap？

Question

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())将链接到<2,false>将链接到<10,true>

(因为我理解，false值在true值之后输入)。

但是，当我执行keySet()时，true先返回，然后才是false，而不是false先返回。

所以，我在这里的假设是，由于keySet()是一个集合，而集合维护顺序，我们在迭代时会得到true和false。但是，为什么我们不说哈希映射维护顺序，因为检索的唯一方式是按顺序进行的。或者为什么我们使用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

现在，当我添加更改hashcode方法以返回一个类似的值时。

@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()方法是如何工作的吗？

- dgupta3091

---

这是因为使用相同的哈希码添加的所有项都会最终进入同一个桶中，并且插入顺序得以保留，但如果您使用分布式哈希码，则情况并非如此。对于所有对象使用相同的哈希码是一个不好的想法。 - Mark Rotteveel

为什么在HashMap中使用keySet()维护顺序时还需要LinkedHashMap呢？哈希映射键的排序是未定义的；如果您看到它们按照您期望的顺序出现，那只是巧合，并不能保证始终如此。 - Andy Turner

你能让我理解keySet()的内部实现吗？在这个链接https://dev59.com/knI-5IYBdhLWcg3wYnSQ中提到，keySet总是按照输入顺序排列，尽管遍历它比遍历linkedHashMap更昂贵。 - dgupta3091

构建一个迭代顺序与插入顺序不同的示例非常简单，例如：http://ideone.com/SOe3Qh。*您不需要了解内部实现*。您只需要知道`HashMap`没有迭代顺序的保证即可。 - Andy Turner

如果你能构造一个例子来证明顺序被保留了，那也没关系：HashMap不保证元素的顺序，所以这只是巧合。你不能依赖于顺序被保留。 - Andy Turner

Answer 1

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()函数相当糟糕，对于单个字符的字符串尤其如此。这是String的hashCode()规范。本质上，它是一个加和乘法，但对于单个字符的字符串，它只是该char的Unicode值。因此，上面这些单个字符的字符串的哈希码分别为65、66、... 90。HashMap的内部表始终是2的幂，在这种情况下，它有64个条目。使用的表项是键的hashCode()值向右移动16位并与自身异或，然后对表大小取模。（在此处查看代码。）因此，这些单个字符的字符串最终以顺序方式出现在HashMap表中，数组位置为1、2、...26。

Key迭代按顺序通过桶进行，所以键最终按照放置的顺序出现。同样，这并不是保证的，只是由于上述各种实现部分的特性而发生了这种情况。

现在考虑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单次运行中，迭代顺序是稳定的。此外，现有的集合如HashMap不会随机化它们的迭代顺序。）

- Stuart Marks

---

我不同意String.hashCode是糟糕的，即使将视野缩小到单个字符的String。所有单个字符的String都有一个独特的哈希码，因此不清楚您还期望从中获得什么。对该值执行任意转换，希望特定的哈希映射实现获得好处？由于这是特定哈希映射实现的设计决策，使用2的幂作为大小，因此该哈希映射实现的任务也是执行适当的转换，特别是考虑到它已经经常更改了... - Holger

@Holger String.hashCode提供了不同的哈希码，所以在这方面是可以的，但它不能很好地分布在32位哈希码空间中。这就是它糟糕的地方。良好的分布对于诸如闭散列或者如果你想要将表格拆分用于并行处理等情况非常重要。HashMap尝试以各种方式进行位混合，但对于短字符串来说效果不佳，因为它们的哈希码中有很多零。 - Stuart Marks

@Stuart Marks：我不确定规范是否要求32位哈希码空间的良好分布（除了提供不同的值）。考虑到“字符串”的实际无限值空间，我并不惊讶短字符串的完美分布并不是一个优先事项。顺便提一下，在Java 7中尝试的替代哈希（murmur32）在我测试的所有实际情况中产生了更多的冲突... - Holger

再次阅读您的解释后，我有些疑虑。将值65到90与它们的高位（都是零）进行异或运算，将再次产生值65到90，应用模64（AND 63），则会产生值1到26。因此，它们恰好以与自然顺序相同的顺序连续地出现在同一桶中，这仍然是哈希算法的一个副产品，没有保证的顺序，但从性能角度来看是完美的。即使没有异或，它们也会在相同的桶中。那么对于这些字符串，String.hashCode有什么问题呢？ - Holger

@Holger 在 HashMap 碰撞方面，String.hashCode 是可以的。但在其他标准方面就不太好了。如果所有值都聚集在一起，那么如果将 HashMap 用作并行流的源，则会导致不平衡的分裂。或者，如果使用闭散列方案（例如 JDK 9 不可变集合和映射），则聚集性会导致线性探测的性能下降。 - Stuart Marks

Answer 2

Java doc 中 LinkedHashMap 的问题答案：

哈希表和链表实现了 Map 接口，并具有可预测的迭代顺序。这个实现与 HashMap 不同之处在于它维护了一个双向链表，该链表通过所有条目。这个链表定义了迭代顺序，通常是键被插入到映射中的顺序（插入顺序）。请注意，如果将键重新插入到映射中，则不会影响插入顺序。（如果在调用 m.containsKey(k) 返回 true 之前立即调用 m.put(k, v)，则键 k 将被重新插入到映射 m 中。）

这个实现避免了 HashMap（和 Hashtable）提供的未指定、通常混乱的排序，而不会增加 TreeMap 相关的成本。它可以用来生成一个与原始地图具有相同顺序的地图副本，而不管原始地图的实现方式如何：

 void foo(Map m) {
     Map copy = new LinkedHashMap(m);
     ...
 }

- shazin

---

我的问题是，在使用JDK 1.8时，我可以看到元素的顺序得到保留，无论我添加或删除多少次。这是怎么实现的呢？ - dgupta3091