Java 8 Hashmap内部

Question

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

1. 我在一篇文章中看到，具有相同哈希码的节点将作为链接列表添加到同一个桶中。它说，新的节点将添加到这个链接列表的头部，而不是尾部，以避免尾部遍历。但是当我看到源代码时，新的节点将被添加到尾中。对吗？
2. 我没有完全理解这个变量MIN_TREEIFY_CAPACITY。就像在这么多计数之后，整个映射将被转换为树(从数组到树)吗？

Answer 1

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

它被添加到头部，在旧版本。但是，在Java 8中做了许多更改。

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}]

注意:键可以有不同的hashCodes，但最终可能在同一个桶中。

我没有完全理解这个变量MIN_TREEIFY_CAPACITY。就像在这么多计数之后，整个映射将被转换为树(从数组到树)吗？

在此计数之后，如果密钥为Comparable，则桶将转换为树。

Answer 2

彼得·劳瑞对MIN_TREEIFY_CAPACITY的回应是错误的。

这个常量默认为64，并在java.util.HashMap#treeifyBin方法中使用，如果桶的大小大于8 (TREEIFY_THRESHOLD)，则调用该方法。

在java.util.HashMap#treeifyBin方法中，如果哈希表的大小小于64，则整个表的大小将增加一倍，否则，所讨论的桶是TREEIFIED的DS链接列表将转换为二叉树。

重点是保持O(1)插入或查找--如果哈希表的大小很小(64)，我们可以通过加倍来轻松地调整它的大小，这样存储桶的范围将加倍，哈希键的冲突也会更少，每个桶的项也会更少。

如果表的大小大于64，而不是将哈希表的大小增加一倍，则最好将当前桶的链接列表转换为二叉树桶，这样搜索速度更快(链接列表搜索为O(n)，而二叉树搜索为O(log(n))。