java - HashMap 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;
        }
    }
    //...
}

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

Answer 1

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

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

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

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

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

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

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

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

最后是 MIN_TREEIFY_CAPACITY = 64。

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

---

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

它旨在防止不良的 hashCode 实现，还提供针对 collision attacks 的基本保护，在这种情况下，不良行为者可能会通过故意选择占用相同存储桶的输入来降低系统速度。