Java8 哈希映射在返回常量哈希码的情况下重新哈希处理

hashmap java java-8

2022-09-03 00:52:08

根据下面的代码，哈希映射的初始dafault容量为16，LF为0.75，因此当我输入第13个元素时，应该进行重新哈希处理，并且由于我提供了一个恒定的哈希码，因此它在内部维护一个链接列表以维护插入顺序。因此，直到第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树，那么在这种情况下，它在这里使用哪种遍历？

答案 1

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

没有“应该”;不保证任何订单。在当前实现中实际发生的情况由两个常量和确定。HashMapTREEIFY_THRESHOLD = 8MIN_TREEIFY_CAPACITY = 64

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

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

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

答案 2

它独立于指定的哈希码编号，即7，而是您的hascode是常量，导致它。原因如下：

我浏览了HashMap的放置方法的源代码，有一个常量决定何时将普通桶转换为树。TREEIFY_THRESHOLD

静态最终整数 TREEIFY_THRESHOLD = 8;

put 方法的代码片段如下（Put 方法调用 putVal 方法）：

.
.
.

                for (int binCount = 0; ; ++binCount) {

                    if ((e = p.next) == null) {

                        p.next = newNode(hash, key, value, null);

                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                            treeifyBin(tab, hash);

                        break;

                    }
.
.
.

记下包含条件的行。一旦发现存储桶已填满容量，它就会调用方法。if (binCount >= TREEIFY_THRESHOLD - 1)TREEIFY_THRESHOLDtreeifyBin()

此方法反过来仅在满足时才调用该方法。resize()MIN_TREEIFY_CAPACITY

 final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;

            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

在上面的代码段中查找以下条件

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();

然后，调整大小方法会根据其具有的多个条件检查相应地增加地图的大小。它基本上通过负载系数增加了容量。

就像树化一样，如果没有。树中的元素减少。取消初始化操作是使用即 6 作为基数来执行的。UNTREEIFY_THRESHOLD

我引用了这个链接来浏览Hashmap代码。