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; } } //... }
它是如何使用的？ 我只想要一个algorithm的解释 。
HashMap包含一定数量的桶。 它使用hashCode来确定将这些放入哪个存储区。 为了简单起见，把它想象成一个模数。
如果我们的哈希码是123456，我们有4个桶， 123456 % 4 = 0所以物品进入第一个桶，桶1。
如果我们的哈希码function是好的，它将提供一个均匀的分布，所以所有的桶都将被平等地使用。 在这种情况下，存储区使用链接列表来存储值。
但是你不能依靠人来实现好的散列函数。 人们经常会写不好的哈希函数，这将导致不均匀的分布。
这个分布越不均匀，我们从O（1）操作越远，越接近O（n）操作。
Hashmap的实现试图通过将一些桶组织成树而不是链接列表来缓解这个问题，如果桶变得太大的话。 这是TREEIFY_THRESHOLD = 8的用途。 如果一个桶包含八个以上的项目，它应该成为一棵树。
树首先按散列码进行sorting。 如果哈希码相同，则使用compareTo方法（如果对象实现该接口），否则使用身份哈希码。
如果从映射中删除条目，则存储区中条目的数量可能会减less，从而不再需要此树结构。 这就是UNTREEIFY_THRESHOLD = 6 。 如果一个桶中的元素数量低于6，我们不妨回到使用链表。
最后是MIN_TREEIFY_CAPACITY = 64 。
当一个哈希映射的大小增长，它会自动调整自己有更多的桶。 如果我们有一个小的哈希映射，我们得到非常满的桶的可能性是相当高的，因为我们没有多less不同的桶投入。 拥有更大的哈希映射要好得多，而更多的桶不足。 这个常量基本上说，如果我们的哈希映射非常小，就不要开始把树做成树，而是应该先调整大一些。
为了回答你关于性能增益的问题，增加了这些优化以改善最坏的情况。 我只是猜测，但是如果你的hashCode函数不是很好，你可能只会看到明显的性能提升。
图像是我的（感谢MSPaint）。 不pipe你喜欢重复使用它们。
简单一些（尽可能简单些）+一些更多的细节。
这些属性取决于很多内部的东西，这些东西在理解之前会很酷 – 在直接转向它们之前。
TREEIFY_THRESHOLD – >当一个桶到达这个（并且总数超过MIN_TREEIFY_CAPACITY ）时，它被转换成完全平衡的红/黑树节点 。 为什么？ 由于search速度。 用不同的方式思考：
最多需要32个步骤才能使用Integer.MAX_VALUE条目search桶/条目内的条目。
一些介绍下一个话题。 为什么桶/桶的数量总是2的幂 ？ 至less有两个原因：比模运算更快，并且对负数取模将是负数。 你不能把一个条目放到一个“负面”的桶里：
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<>();
在上面的例子中，根据你的hashcode 的最后4位来决定进入的地方。
这是把桶放大的地方。 在某些情况下（需要花费很多时间来详细解释），水桶的尺寸会增加一倍。 为什么？ 当水桶大小增加一倍时，还有一点起作用 。
所以你有16个桶 – 最后4位的散列码决定了一个入口的位置。 你加倍桶：32桶 – 最后5位决定进入哪里。
因此，这个过程被称为重散列。 这可能会变慢。 那就是（对于那些关心的人），因为HashMap被“开玩笑”地说成： 快速，快速，快速，斯洛柯 。 还有其他的实现 – search暂停散列表 …
现在UNTREEIFY_THRESHOLD在重新哈希之后发挥作用。 在这一点上，有些条目可能会从这个bin移动到另外一个（他们再向(n-1)&hash计算中增加一个位 – 并且这样的migth移动到其他的 bucket），并且可能达到UNTREEIFY_THRESHOLD 。 在这一点上，它并没有回报保持斌作为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.
你需要可视化它：说有一个只有hashCode（）函数重写的类键总是返回相同的值
public class Key implements Comparable<Key>{ private String name; public Key (String name){ this.name = name; } @Override public int hashCode(){ return 1; } public String keyName(){ return this.name; } public int compareTo(Key key){ //returns a +ve or -ve integer } }
然后在别的地方，我将9个条目插入到一个HashMap中，所有的键都是这个类的实例。 例如
Map<Key, String> map = new HashMap<>(); Key key1 = new Key("key1"); map.put(key1, "one"); Key key2 = new Key("key2"); map.put(key2, "two"); Key key3 = new Key("key3"); map.put(key3, "three"); Key key4 = new Key("key4"); map.put(key4, "four"); Key key5 = new Key("key5"); map.put(key5, "five"); Key key6 = new Key("key6"); map.put(key6, "six"); Key key7 = new Key("key7"); map.put(key7, "seven"); Key key8 = new Key("key8"); map.put(key8, "eight"); //Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure eg key1 -> key2-> key3 -> ...so on. but when I insert one more entry Key key9 = new Key("key9"); map.put(key9, "nine"); threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. eg key1 / \ key2 key3 / \ / \
树遍历比LinkedList {O（n）}更快{O（log n）}，随着n的增长，差异变得更加重要。
HashMap实现的改变是添加了JEP-180 。 目的是：
通过使用平衡树而不是链接列表来存储映射条目，从而提高在高散列冲突条件下的java.util.HashMap的性能。 在LinkedHashMap类中实现相同的改进
然而，纯粹的performance并不是唯一的收获。 在使用哈希映射来存储用户input的情况下，这也将防止 HashDoS攻击 ，因为用于存储数据的红黑树在O（log n）中具有最坏的插入复杂度。 在满足一定的标准之后使用树 – 参见Eugene的答案 。
