Java8 Hashmap 在返回常量哈希码的情况下重新哈希

Question

按照下面的代码，hashmap 的初始默认容量是 16，LF 是 0.75，所以当我输入第 13 个元素时，应该会发生重新散列，因为我提供了一个常量 hashcode，它在内部维护一个链表来维护插入顺序。所以，直到第 10 个元素它按预期工作但是当我输入第 11 个元素时，它会打乱顺序。 谁能帮助我理解为什么它只在第 11 个元素插入时发生。

class A{
    int a;

    A(int a){
        this.a = a;
    }
    @Override
    public int hashCode() {
        return 7;
    }
    @Override
    public String toString() {
        return "" + a + "";
    }
}
class Base {
    public static void main(String[] args) {
        Map<Object, Integer> m = new HashMap<Object, Integer>();
        m.put(new A(1), 1);
        m.put(new A(2), 1);
        m.put(new A(3), 1);
        m.put(new A(4), 1);
        m.put(new A(5), 1);
        m.put(new A(6), 1);
        m.put(new A(7), 1);
        m.put(new A(8), 1);
        m.put(new A(9), 1);
        m.put(new A(10), 1);
        //m.put(new A(11), 1);
        System.out.println(m);
    }
}

直到第 10 个元素我得到的输出:

{1=1, 2=1, 3=1, 4=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1}

输入第 11 个元素后得到的输出:

{4=1, 1=1, 2=1, 3=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1, 11=1}

它应该维护插入顺序，或者如果它在内部使用 RB 树，那么在这种情况下它在这里使用哪种遍历？

Answer 1

It should maintain insertion order or if it is using RB tree internally so which traversal it is using here in this case?

没有“应该”； HashMap 不保证任何顺序。当前实现中实际发生的情况由两个常量决定，TREEIFY_THRESHOLD = 8 和 MIN_TREEIFY_CAPACITY = 64。

当一个桶中的项目数超过前者时，桶将转换为节点树，除非 map 的总容量小于后者常量，在这种情况下，容量将增加一倍。

因此，当您插入第 9 个对象时，容量将从 16 增加到 32，插入第 10 个会使容量从 32 增加到 64，然后，插入第 11 个元素将导致桶转换为树。

这种转换总会发生，无论是否有实际好处。由于对象具有相同的哈希码并且未实现 Comparable，因此最终将使用它们的标识哈希码来确定顺序。这可能会导致顺序发生变化(在我的环境中，不会)。