HashMap Java 8 实现

dictionary hashmap java java-8

2022-08-31 09:27:50

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

首先

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

如何使用？我只想要一个算法的解释。

答案 1

HashMap包含一定数量的存储桶。它用于确定要将这些放入哪个存储桶。为了简单起见，把它想象成一个模量。hashCode

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

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

但你不能依靠人们来实现良好的哈希函数。人们经常会写出糟糕的哈希函数，这将导致非均匀分布。也有可能我们的输入会很不幸。

这种分布越少，我们从 O（1）操作向 O（1）操作移动得越远，向 O（n）操作移动得越近。

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

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

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

最后，还有 .MIN_TREEIFY_CAPACITY = 64

当哈希映射的大小增加时，它会自动调整自身大小以拥有更多存储桶。如果我们有一个小的HashMap，我们得到非常满桶的可能性是相当高的，因为我们没有那么多不同的桶来放入东西。最好有一个更大的HashMap，以及更多不那么满的桶。这个常数基本上说，如果我们的HashMap非常小，就不要开始将桶变成树 - 它应该首先调整大小以变得更大。

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

它旨在防止不良实现，并提供针对碰撞攻击的基本保护，其中不良行为者可能试图通过故意选择占用相同存储桶的输入来减慢系统速度。hashCode

答案 2

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

这些属性依赖于许多内部事物，在直接移动到它们之前，这些内容将非常难以理解。

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

在具有 Integer.MAX_VALUE 条目的存储桶/箱中搜索条目最多需要 32 个步骤。

下一个主题的一些介绍。为什么条柱/桶的数量总是 2 的幂？至少有两个原因：比模运算快，负数上的模数将为负数。而且您不能将条目放入“负”桶中：

 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被“开玩笑”为：快速，快速，快速，懒惰。还有其他实现 - 搜索无暂停哈希映射...

现在，UNTREEIFY_THRESHOLD在重新散列后发挥作用。此时，某些条目可能会从此条柱移动到其他条柱（它们会向计算中再添加一位 - 因此可能会移动到其他存储桶），并且可能会到达此条柱。在这一点上，将 bin 保留为没有回报，而是作为一个，就像(n-1)&hashUNTREEIFY_THRESHOLDred-black tree nodeLinkedList

 entry.next.next....

MIN_TREEIFY_CAPACITY是将某个存储桶转换为树之前的最小存储桶数。