HashMap Java 8实现
根据以下链接文档：Java HashMap实现
我对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;
}
}
//...
}
它是如何使用的？ 我只想要一个算法的解释 。
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 。
当哈希映射的大小增大时，它会自动调整自己以拥有更多的桶。 如果我们有一个小的哈希映射，我们获得非常满的桶的可能性非常高，因为我们没有多少不同的桶来投入。 拥有更大的哈希映射要好得多，而更多的桶不够满。 这个常量基本上说，如果我们的哈希映射非常小，就不要开始把树做成树 - 它应该调整为首先变大。
为了回答你关于性能增益的问题，增加了这些优化以改善最坏的情况。 我只是猜测，但如果你的hashCode函数不是很好，你可能只会看到明显的性能改进，因为这些优化。
图像是我的（感谢MSPaint）。 不管你喜欢重复使用它们。
简单一点（尽可能简单一些）+更多细节。
这些属性取决于很多内部的东西，在理解之前会非常酷 - 在直接转向它们之前。
TREEIFY_THRESHOLD - >当一个桶到达这个位置（并且总数超过MIN_TREEIFY_CAPACITY ）时，它会转换为完全平衡的红/黑树节点。 为什么？ 由于搜索速度。 用不同的方式思考它：
最多需要32个步骤才能使用Integer.MAX_VALUE条目搜索桶/条目中的条目。
一些介绍下一个主题。 为什么桶/桶的数量总是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被“开玩笑”为： 快速，快速，快速，斯洛索 。 还有其他的实现 - 搜索暂停的hashmap ...
现在UNTREEIFY_THRESHOLD在重新哈希之后发挥作用。 在这一点上，一些条目可能会从这个bin移动到其他条目（它们会为(n-1)&hash计算再添加一位(n-1)&hash并且可能会移动到其他存储桶中，并且可能会达到UNTREEIFY_THRESHOLD 。 在这一点上，它并没有让bin保持为red-black tree node ，而是像LinkedList那样
entry.next.next....
MIN_TREEIFY_CAPACITY是特定桶转换为树之前的最小桶数。
TreeNode是另一种存储属于HashMap的单个分箱的条目的方法。 在较早的实现中，箱的条目被存储在链接列表中。 在Java 8中，如果bin中的条目数量超过阈值（ TREEIFY_THRESHOLD ），则它们将存储在树结构中，而不是原始链接列表中。 这是一个优化。
从实施：
/*
* Implementation notes.
*
* This map usually acts as a binned (bucketed) hash table, but
* when bins get too large, they are transformed into bins of
* TreeNodes, each structured similarly to those in
* java.util.TreeMap. Most methods try to use normal bins, but
* relay to TreeNode methods when applicable (simply by checking
* instanceof a node). Bins of TreeNodes may be traversed and
* used like any others, but additionally support faster lookup
* when overpopulated. However, since the vast majority of bins in
* normal use are not overpopulated, checking for existence of
* tree bins may be delayed in the course of table methods.