共计 2092 个字符，预计需要花费 6 分钟才能阅读完成。
传统 HashMap 的缺点
JDK 1.8 以前 HashMap 的实现是 数组 + 链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题
JDK1.8 中 HashMap 的数据结构
HashMap 是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）实现的
新增红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
TREEIFY_THRESHOLD static final int TREEIFY_THRESHOLD = 8
一个桶的树化阈值，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
UNTREEIFY_THRESHOLD static final int UNTREEIFY_THRESHOLD = 6
一个树的链表还原阈值，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
MIN_TREEIFY_CAPACITY
static final int MIN_TREEIFY_CAPACITY = 64
当哈希表中的容量大于这个值时，表中的桶才能进行树形化
否则桶内元素太多时会扩容，而不是树形化
为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
HashMap 在 JDK 1.8 中新增的操作：桶的树形化 treeifyBin()
在 Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8)，就使用红黑树来替换链表，从而提高速度。
这个替换的方法叫 treeifyBin() 即树形化。// 将桶内所有的 链表节点 替换成 红黑树节点
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值 (默认为 64)，就去新建 / 扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n – 1) & hash]) != null) {
// 如果哈希表中的元素个数超过了 树形化阈值，进行树形化
// e 是哈希表中指定位置桶里的链表节点，从第一个开始
TreeNode<K,V> hd = null, tl = null; // 红黑树的头、尾节点
do {
// 新建一个树形节点，内容和当前链表节点 e 一致
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) // 确定树头节点
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
}while ((e = e.next) != null);
// 让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
if ((tab[index] = hd) != null){
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
1. 根据哈希表中元素个数确定是扩容还是树形化
2. 如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
3. 然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容
1. 判断键值对数组 table[i] 是否为空或为 null，否则执行 resize() 进行扩容；
2. 根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，转向⑥，如果 table[i] 不为空，转向③；
3. 判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向④，这里的相同指的是 hashCode 以及 equals；
4. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
5. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；
6. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。
