哈希映射 Java 8 实现

Question

根据以下链接文档： Java HashMap Implementation

我对 HashMap 的实现感到困惑（或者更确切地说，是 HashMap 的增强）。我的查询是：

首先

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

为什么以及如何使用这些常量？ 我想要一些明确的例子。 他们如何通过此实现性能提升？

第二

如果你在JDK中查看 HashMap 的源码，你会发现如下静态内部类：

 static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

    final HashMap.TreeNode<K, V> root() {
        HashMap.TreeNode arg0 = this;

        while (true) {
            HashMap.TreeNode arg1 = arg0.parent;
            if (arg0.parent == null) {
                return arg0;
            }

            arg0 = arg1;
        }
    }
    //...
}

它是如何使用的？ 我只想要算法的解释。

原文由 Hasnain Ali Bohra 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

HashMap 包含一定数量的桶。它使用 hashCode 来确定将这些放入哪个桶中。为简单起见，将其想象为模数。

如果我们的哈希码是 123456 并且我们有 4 个桶， 123456 % 4 = 0 那么该项目进入第一个桶，桶 1。

如果我们的 hashCode 函数是好的，它应该提供一个均匀的分布，这样所有的桶都会被平等地使用。在这种情况下，桶使用链表来存储值。

但是你不能指望人来实现好的散列函数。人们通常会编写糟糕的散列函数，这将导致分布不均匀。也有可能我们的输入不走运。

这种分布越不均匀，我们就越远离 O(1) 操作，越接近 O(n) 操作。

如果桶变得太大，HashMap 的实现试图通过将一些桶组织成树而不是链表来缓解这种情况。这就是 TREEIFY_THRESHOLD = 8 的用途。如果一个桶包含超过八个项目，它应该成为一棵树。

这棵树是一棵 红黑树，大概是因为它提供了一些最坏情况的保证而被选中的。它首先按哈希码排序。如果哈希码相同，它使用 compareTo 方法 Comparable 如果对象实现该接口，否则使用身份哈希码。

如果从映射中删除条目，则存储桶中的条目数可能会减少，从而不再需要此树结构。这就是 UNTREEIFY_THRESHOLD = 6 的用途。如果一个桶中的元素数量下降到 6 个以下，我们还不如回到使用链表。

最后，还有 MIN_TREEIFY_CAPACITY = 64 。

当哈希映射的大小增加时，它会自动调整自身的大小以拥有更多的桶。如果我们有一个小的 HashMap，我们得到非常满的桶的可能性非常高，因为我们没有那么多不同的桶来放入东西。拥有一个更大的 HashMap 和更多不那么满的桶要好得多。如果我们的 HashMap 非常小，这个常量基本上表示不要开始将桶制作成树 - 它应该先调整大小以使其变大。

---

为了回答您关于性能提升的问题，添加了这些优化以改善最坏的情况。如果您的 hashCode 功能不是很好，您可能只会因为这些优化而看到明显的性能改进。

它旨在防止不良 hashCode 实施，还提供基本保护以防止 碰撞攻击，不良行为者可能会通过故意选择占用相同桶的输入来尝试减慢系统速度。

原文由 Michael 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

简而言之（尽可能简单）+更多细节。

这些属性取决于很多内部的东西，这些东西在直接移动到它们之前理解起来会很酷。

TREEIFY_THRESHOLD -> 当 单个 bucket 达到此值（并且总数超过 MIN_TREEIFY_CAPACITY ）时，它被转化为一个 _完美平衡的红/黑树节点_。为什么？因为搜索速度。以不同的方式思考它：

在具有 Integer.MAX_VALUE 条目的 bucket/bin 中搜索条目 最多需要 32 步。

下一个主题的一些介绍。 为什么 bins/buckets 的数量总是 2 的幂？至少有两个原因：比模运算更快，并且对负数取模将是负数。而且您不能将 Entry 放入“负面”桶中：

  int arrayIndex = hashCode % buckets; // will be negative

 buckets[arrayIndex] = Entry; // obviously will fail

_相反_，使用了一个很好的技巧来代替模数：

  (n - 1) & hash // n is the number of bins, hash - is the hash function of the key

这在 _语义上与模运算相同_。它会保留低位。当您这样做时，这会产生一个有趣的结果：

 Map<String, String> map = new HashMap<>();

在上面的例子中，条目去向的决定 仅基于您的哈希码的最后 4 位。

这就是乘积桶发挥作用的地方。在某些情况下（需要花费大量时间来 详细 解释），桶的大小会加倍。为什么？ _当桶的大小增加一倍时，就会有更多的位发挥作用_。

所以你有 16 个桶——哈希码的最后 4 位决定条目的去向。您将存储桶加倍：32 个存储桶 - 最后 5 位决定条目的去向。

因此，此过程称为重新散列。这可能会变慢。那是（对于关心的人），因为 HashMap 被“开玩笑”为： fast, fast, fast, slooow 。还有其他的实现 ——search pauseless hashmap …

现在 UNTREEIFY_THRESHOLD 在重新散列后开始发挥作用。在这一点上，一些条目可能会从这个容器移动到其他容器（它们向 (n-1)&hash 计算添加一位 - 因此可能移动到 其他 桶）并且它可能达到这个 UNTREEIFY_THRESHOLD 。在这一点上，将 bin 保持为 red-black tree node 是没有回报的，而是作为 LinkedList ，例如

 entry.next.next....

MIN_TREEIFY_CAPACITY 是某个桶转化为树之前的最小桶数。

原文由 Eugene 发布，翻译遵循 CC BY-SA 3.0 许可协议