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

Question

根据下面的代码,hashmap初始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树,这样在这种情况下它会在这里使用？

Answer 1

它应该保持插入顺序还是内部使用RB树,这样在这种情况下它会在这里使用？

没有"应该"; 在HashMap并不保证任何顺序.当前实现中实际发生的事情由两个常量决定,TREEIFY_THRESHOLD = 8并且MIN_TREEIFY_CAPACITY = 64.

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

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

无论是否有实际利益,这种转换总是会发生.由于对象具有相同的哈希码并且未实现Comparable,因此最终将使用其身份哈希码来确定顺序.这可能会导致订单发生变化(在我的环境中,它没有).

Answer 2

它独立于指定的哈希码数,即7,而且你的hascode是常量导致它.以下是原因:

我查看了HashMap的put方法的源代码,并且有一个常量TREEIFY_THRESHOLD决定何时将普通存储桶转换为树.

static final int 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_THRESHOLD容量,它就会调用treeifyBin()方法.

该方法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();

然后,resize方法根据它具有的多个条件检查相应地增加映射的大小.它主要通过负载系数增加容量.

如果没有,就像树木一样.树中的元素减少.使用UNTREEIFY_THRESHOLDie 6作为基础执行未授权操作.

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