认识达内从这里开始

认真做教育专心促就业

Java集合类源码解析：HashMap（基于JDK1.8)2

发布：青岛IT培训
来源：青岛IT培训
时间：2019-04-17 11:32

青岛IT培训的小编总结，动态扩容：resize（）
在HashMap中，初始化数组或者添加元素个数超过阈值时都会触发 resize（）方法，它的作用是动态扩容，下面是方法的源码：
final Node<K,V>[] resize（） {
Node<K,V>[] oldTab = table;
int oldCap = （oldTab == null） ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//‘桶’数组的大小超过0,做扩容
if （oldCap > 0） {
//超过最大值不会扩容，把阈值设置为int的最大数
if （oldCap >= MAXIMUM_CAPACITY） {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//向左移动1位扩大为原来2倍
else if （（newCap = oldCap 《 1） < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY）
newThr = oldThr 《 1; // double threshold
}
//旧数组大小为0,旧阈值>0,说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
else if （oldThr > 0） // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧容量、旧阈值都是0,说明还没创建哈希表，容量为默认容量，阈值为容量*加载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = （int）（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）；
}
//新阈值还没有值，重新根据新的容量newCap计算大小
if （newThr == 0） {
float ft = （float）newCap * loadFactor;
newThr = （newCap < MAXIMUM_CAPACITY && ft < （float）MAXIMUM_CAPACITY ?
（int）ft : Integer.MAX_VALUE）；
}
threshold = newThr;
@SuppressWarnings（{“rawtypes”,“unchecked”}）
Node<K,V>[] newTab = （Node<K,V>[]）new Node[newCap];
table = newTab;
//不为空，代表是扩容操作
if （oldTab != null） {
//遍历旧数组的每一个‘桶',移动到新数组newTab
for （int j = 0; j < oldCap; ++j） {
Node<K,V> e;
if （（e = oldTab[j]） != null） {
oldTab[j] = null;
if （e.next == null）
newTab[e.hash & （newCap - 1）] = e;
//节点是树形节点，需要对红黑树进行拆分
else if （e instanceof TreeNode）
（（TreeNode<K,V>）e）。split（this, newTab, j, oldCap）；
else { // preserve order
//普通链表节点，遍历链表，并将链表节点按原顺序进行分组
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if （（e.hash & oldCap） == 0） {
if （loTail == null）
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if （hiTail == null）
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while （（e = next） != null）；
if （loTail != null） {
loTail.next = null;
newTab[j] = loHead;
}
if （hiTail != null） {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上面的源码有点长，但总体逻辑就三步：
计算新桶数组的容量大小 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，并初始化桶的数组table
将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树（调用split（）方法）。如果是普通节点，则节点按原顺序进行分组。
前面两步的逻辑比较简单，这里不多叙述。重点是第三点，涉及到了红黑树的拆分，这是因为扩容后，桶数组变多了，原有的数组上元素较多的红黑树就需要重新拆分，映射成链表，防止单个桶的元素过多。
红黑树的拆分是调用TreeNode.split（）来实现的，这里不单独讲。放到后面的红黑树一起分析。
节点树化、红黑树的拆分
红黑树的引进是HashMap 在 Jdk1.8之后最大的变化，在1.8以前，HashMap的数据结构就是数组加链表，某个桶的链表有可能因为数据过多而导致链表过长，遍历的效率低下，1.8之后，HashMap对链表的长度做了处理，当链表长度超过8时，自动转换为红黑树，有效的提升了HashMap的性能。
但红黑树的引进也使得代码的复杂度提高了不少，添加了有关红黑树的操作方法。本文只针对这些方法来做解析，不针对红黑树本身做展开，想了解红黑树的读者可以看我之前的文章
数据结构：红黑树的结构以及方法剖析（上）以及数据结构：红黑树的结构以及方法剖析（下）
节点树化
HashMap中的树节点的代码用 TreeNode 表示：
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;
TreeNode（int hash, K key, V val, Node<K,V> next） {
super（hash, key, val, next）；
}
可以看到就是个红黑树节点，有父亲、左右孩子、前一个元素的节点，还有个颜色值。知道节点的结构后，我们来看有关红黑树的一些操作方法。
先来分析下树化的代码：
//将普通的链表转化为树形节点链表
final void treeifyBin（Node<K,V>[] tab, int hash） {
int n, index; Node<K,V> e;
// 桶数组容量小于 MIN_TREEIFY_CAPACITY,优先进行扩容而不是树化
if （tab == null || （n = tab.length） < MIN_TREEIFY_CAPACITY）
resize（）；
else if （（e = tab[index = （n - 1） & hash]） != null） {
TreeNode<K,V> hd = null, tl = null;
do {
//把节点转换为树形节点
TreeNode<K,V> p = replacementTreeNode（e, null）；
if （tl == null）
//把转化后的头节点赋给hd
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）；
}
上面的代码并不太复杂，大致逻辑是根据hash表的元素个数判断是需要扩容还是树形化，然后依次调用不同的代码执行。
值得注意的是，在判断容器是否需要树形化的标准是链表长度需要大于或等于 MIN_TREEIFY_CAPACITY,前面也说了，它是HashMap的成员变量，初始值是64,那么为什么要满足这个条件才会树化呢？
当桶数组容量比较小时，键值对节点 hash
的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

所以，HashMap的树化过程也是尽量的考虑了容器性能，再看回上面的代码，链表树化之前是先把节点转为树形节点，然后再调用 treeify（）转换为红黑树，并且树形节点TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。

青岛IT培训

下面看下转换红黑树的过程：
final void treeify（Node<K,V>[] tab） {
TreeNode<K,V> root = null;
for （TreeNode<K,V> x = this, next; x != null; x = next） {
next = （TreeNode<K,V>）x.next;
x.left = x.right = null;
if （root == null） { //第一次进入循环，确定头节点，并且是黑色
x.parent = null;
x.red = false;
root = x;
}
else { //后面进入循环走的逻辑，x 指向树中的某个节点
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//从根节点开始，遍历所有节点跟当前节点 x 比较，调整位置，
for （TreeNode<K,V> p = root;;） {
int dir, ph;
K pk = p.key;
if （（ph = p.hash） > h） //当比较节点的哈希值比 x 大时， dir 为 -1
dir = -1;
else if （ph < h） //哈希值比 x 小时 dir 为 1
dir = 1;
else if （（kc == null &&
（kc = comparableClassFor（k）） == null） ||
（dir = compareComparables（kc, k, pk）） == 0）
// 比较节点和x的key
dir = tieBreakOrder（k, pk）；
TreeNode<K,V> xp = p;
//把当前节点变成 x 的父亲
//如果当前比较节点的哈希值比 x 大，x 就是左孩子，否则 x 是右孩子
if （（p = （dir <= 0） ? p.left : p.right） == null） {
x.parent = xp;
if （dir <= 0）
xp.left = x;
else
xp.right = x;
root = balanceInsertion（root, x）；
break;
}
}
}
}
moveRootToFront（tab, root）；
}
可以看到，代码的总体逻辑就是拿树中的节点与当前节点做比较，进而确定节点在树中的位置，具体实现的细节还是比较复杂的，这里不一一展开了。
红黑树拆分
介绍了节点的树化后，我们来学习下红黑树的拆分过程，HashMap扩容后，普通的节点需要重新映射，红黑树节点也不例外。
在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。
下面看一下拆分的方法源码：
//map 容器本身
//tab 表示保存桶头结点的哈希表
//index 表示从哪个位置开始修剪
//bit 要修剪的位数（哈希值）
final void split（HashMap<K,V> map, Node<K,V>[] tab, int index, int bit） {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
// 修剪后的两个链表，下面用lo树和hi树来替代
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for （TreeNode<K,V> e = b, next; e != null; e = next） {
next = （TreeNode<K,V>）e.next;
e.next = null;
//如果当前节点哈希值的最后一位等于要修剪的 bit 值，用于区分位于哪个桶
if （（e.hash & bit） == 0） {
//把节点放到lo树的结尾
if （（e.prev = loTail） == null）
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//把当前节点放到hi树
else {
if （（e.prev = hiTail） == null）
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if （loHead != null） {
// 如果 loHead 不为空，且链表长度小于等于 6,则将红黑树转成链表
if （lc <= UNTREEIFY_THRESHOLD）
tab[index] = loHead.untreeify（map）；
else {
tab[index] = loHead;
/*
* hiHead != null 时，表明扩容后，
* 有些节点不在原位置上了，需要重新树化
*/
if （hiHead != null） // （else is already treeified）
loHead.treeify（tab）；
}
}
//与上面类似
if （hiHead != null） {
if （hc <= UNTREEIFY_THRESHOLD）
tab[index + bit] = hiHead.untreeify（map）；
else {
tab[index + bit] = hiHead;
if （loHead != null）
hiHead.treeify（tab）；
}
}
}
源码的逻辑大概是这样：拆分后，将红黑树拆分成两条由 TreeNode 组成的链表（hi树和lo树）。如果链表长度小于 UNTREEIFY_THRESHOLD,则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。这里用两张图来展示一下拆分前后的变化
红黑树拆分前：
拆分后：
至此，有关红黑树的一些转换操作就介绍完毕了，除此之外，hashMap还提供了很多操作红黑树的方法，原理都差不多，读者们可以自己去研究。
总结
HashMap的源码解析就告一段落了，最后，总结一下HashMap的一些特性：
1、HashMap 允许 key, value 为 null;
2、HashMap源码里没有做同步操作，多个线程操作可能会出现线程安全的问题，建议用Collections.synchronizedMap 来包装，变成线程安全的Map,例如：
Map map = Collections.synchronizedMap（new HashMap<String,String>（））；
3、Jdk1.7以前，当HashMap中某个桶的结构为链表时，遍历的时间复杂度为O（n），1.8之后，桶中过多元素的话会转换成了红黑树，这时候的遍历时间复杂度就是O（logn）。
以上就是青岛IT培训给大家做的内容详解，更多关于UI的学习，请继续关注青岛IT培训

< 上一篇：Java集合类源码解析：HashMap（基于JDK1.8)1

下一篇：HashMap 源码详细分析(JDK1.8)1 >