Java 8 Hashmap内部

Question

我已经完成了Java8 Hashmap的实现，并带着以下疑问来到这里。请帮我澄清一下：

1. 我在一篇文章中读到，具有相同哈希代码的节点将被添加到与链表相同的bucket中。它说，这个链表的新节点将被添加到head而不是tail中，以避免尾部遍历。但当我看到源代码时，新的节点被添加到尾部。对吗
2. 我没有完全理解这个变量的最小树容量。是不是经过这么多的计算，整个地图会被转换成树（从数组到树）

Answer 1

Peter Lawrey关于MIN_TREEIFY_容量的回应是错误的。

此常量默认为64，并在java.util.HashMap#treeifyBin方法中使用，如果存储桶的大小大于8（TREEIFY_THRESHOLD），则调用该方法。

在java.util.HashMap#treeifyBin方法中，如果哈希表大小小于64，则整个表是RESIZED-加倍的，否则，问题所在的桶是TREEIFIED-桶的DS-链表转换为二叉树。

关键是保持O（1）插入或查找——如果哈希表大小很小（64），我们可以通过加倍来轻松调整它的大小，因此存储桶的范围将加倍，哈希键的冲突将更少，每个存储桶的项目将更少。

如果表大小大于64，那么将哈希表大小加倍可能会很昂贵，最好将当前存储桶的链表转换为二叉树存储桶，这样搜索速度更快（链表搜索为O（n），而二元树状搜寻为O（log（n））。

Answer 2

但当我看到源代码时，新的节点被添加到尾部。对吗？

在旧版本中，它被添加到头部。然而，Java8中做了许多更改，而Java8确实做到了这一点。

class A {
    static class SameHash {
        final int n;

        SameHash(int n) {
            this.n = n;
        }

        @Override
        public int hashCode() {
            return 1;
        }

        @Override
        public String toString() {
            return "SameHash{" +
                    "n=" + n +
                    '}';
        }
    }

    public static void main(String[] args) {
        HashSet<SameHash> set = new HashSet<>();
        for (int i = 1; i <= 4; i++)
            set.add(new SameHash(i));
        System.out.println(set);
    }
}

印刷品

[SameHash{n=1}, SameHash{n=2}, SameHash{n=3}, SameHash{n=4}]

注意：密钥可以有不同的哈希代码，但可以在同一个存储桶中结束。

我没有完全理解这个变量MIN_TREEIFY_CAPACITY。是不是就像经过这么多计数后，整个地图将被转换为树（从数组到树）？

在此计数之后，如果密钥是可比较的，则桶将转换为树