认识达内从这里开始

认真做教育专心促就业

HashMap 源码详细分析(JDK1.8)2

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

青岛IT培训的小编总结，HashIterator 在初始化时，会先遍历桶数组，找到包含链表节点引用的桶，对应图中就是3号桶。随后由 nextNode 方法遍历该桶所指向的链表。遍历完3号桶后，nextNode 方法继续寻找下一个不为空的桶，对应图中的7号桶。之后流程和上面类似，直至遍历完最后一个桶。以上就是 HashIterator 的核心逻辑的流程，
在本小节的最后，抛两个问题给大家。在 JDK 1.8 版本中，为了避免过长的链表对 HashMap 性能的影响，特地引入了红黑树优化性能。但在上面的源码中并没有发现红黑树遍历的相关逻辑，这是为什么呢？对于被转换成红黑树的链表该如何遍历呢？大家可以先想想，然后可以去源码或本文后续章节中找答案。
3.4 插入
3.4.1 插入逻辑分析
通过前两节的分析，大家对 HashMap 低层的数据结构应该了然于心了。即使我不说，大家也应该能知道 HashMap 的插入流程是什么样的了。首先肯定是先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对接在链表最后一个位置，或者更新键值对。这就是 HashMap 的插入流程，是不是觉得很简单。当然，大家先别高兴。这只是一个简化版的插入流程，真正的插入流程要复杂不少。首先 HashMap 是变长集合，所以需要考虑扩容的问题。其次，在 JDK 1.8 中，HashMap 引入了红黑树优化过长链表，这里还要考虑多长的链表需要进行优化，优化过程又是怎样的问题。引入这里两个问题后，大家会发现原本简单的操作，现在略显复杂了。在本节中，我将先分析插入操作的源码，扩容、树化（链表转为红黑树，下同）以及其他和树结构相关的操作，随后将在独立的两小结中进行分析。接下来，先来看一下插入操作的源码：
public V put（K key, V value） {
return putVal（hash（key）， key, value, false, true）；
}
final V putVal（int hash, K key, V value, boolean onlyIfAbsent,
boolean evict） {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶数组 table,table 被延迟到插入新数据时再进行初始化
if （（tab = table） == null || （n = tab.length） == 0）
n = （tab = resize（））。length;
// 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可
if （（p = tab[i = （n - 1） & hash]） == null）
tab[i] = newNode（hash, key, value, null）；
else {
Node<K,V> e; K k;
// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
if （p.hash == hash &&
（（k = p.key） == key || （key != null && key.equals（k））））
e = p;
// 如果桶中的引用类型为 TreeNode,则调用红黑树的插入方法
else if （p instanceof TreeNode）
e = （（TreeNode<K,V>）p）。putTreeVal（this, tab, hash, key, value）；
else {
// 对链表进行遍历，并统计链表长度
for （int binCount = 0; ; ++binCount） {
// 链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
if （（e = p.next） == null） {
p.next = newNode（hash, key, value, null）；
// 如果链表长度大于或等于树化阈值，则进行树化操作
if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st
treeifyBin（tab, hash）；
break;
}
// 条件为 true,表示当前链表包含要插入的键值对，终止遍历
if （e.hash == hash &&
（（k = e.key） == key || （key != null && key.equals（k））））
break;
p = e;
}
}
// 判断要插入的键值对是否存在 HashMap 中
if （e != null） { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if （！onlyIfAbsent || oldValue == null）
e.value = value;
afterNodeAccess（e）；
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值时，则进行扩容
if （++size > threshold）
resize（）；
afterNodeInsertion（evict）；
return null;
}
插入操作的入口方法是 put（K,V），但核心逻辑在V putVal（int, K, V, boolean, boolean）方法中。putVal 方法主要做了这么几件事情：
当桶数组 table 为空时，通过扩容的方式初始化 table
查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
判断键值对数量是否大于阈值，大于的话则进行扩容操作
以上就是 HashMap 插入的逻辑，并不是很复杂，这里就不多说了。接下来来分析一下扩容机制。
3.4.2 扩容机制
在 Java 中，数组的长度是固定的，这意味着数组只能存储固定量的数据。但在开发的过程中，很多时候我们无法知道该建多大的数组合适。建小了不够用，建大了用不完，造成浪费。如果我们能实现一种变长的数组，并按需分配空间就好了。好在，我们不用自己实现变长数组，Java 集合框架已经实现了变长的数据结构。比如 ArrayList 和 HashMap.对于这类基于数组的变长数据结构，扩容是一个非常重要的操作。下面就来聊聊 HashMap 的扩容机制。
在详细分析之前，先来说一下扩容相关的背景知识：
在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。
HashMap 的扩容机制与其他变长集合的套路不太一样，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。以上就是 HashMap 的扩容大致过程，接下来我们来看看具体的实现：
final Node<K,V>[] resize（） {
Node<K,V>[] oldTab = table;
int oldCap = （oldTab == null） ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 table 不为空，表明已经初始化过了
if （oldCap > 0） {
// 当 table 容量超过容量最大值，则不再扩容
if （oldCap >= MAXIMUM_CAPACITY） {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按旧容量和阈值的2倍计算新容量和阈值的大小
else if （（newCap = oldCap 《 1） < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY）
newThr = oldThr 《 1; // double threshold
} else if （oldThr > 0） // initial capacity was placed in threshold
/*
* 初始化时，将 threshold 的值赋值给 newCap,
* HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
* 调用无参构造方法时，桶数组容量为默认容量，
* 阈值为默认容量与默认负载因子乘积
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = （int）（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）；
}
// newThr 为 0 时，按阈值计算公式进行计算
if （newThr == 0） {
float ft = （float）newCap * loadFactor;
newThr = （newCap < MAXIMUM_CAPACITY && ft < （float）MAXIMUM_CAPACITY ?
（int）ft : Integer.MAX_VALUE）；
}
threshold = newThr;
// 创建新的桶数组，桶数组的初始化也是在这里完成的
Node<K,V>[] newTab = （Node<K,V>[]）new Node[newCap];
table = newTab;
if （oldTab != null） {
// 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
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;
}
上面的源码有点长，希望大家耐心看懂它的逻辑。上面的源码总共做了3件事，分别是：
计算新桶数组的容量 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的

将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

青岛IT培训

上面列的三点中，创建新的桶数组就一行代码，不用说了。接下来，来说说第一点和第三点，先说说 newCap 和 newThr 计算过程。该计算过程对应 resize 源码的第一和第二个条件分支，如下：
// 第一个条件分支
if （ oldCap > 0） {
// 嵌套条件分支
if （oldCap >= MAXIMUM_CAPACITY） {…}
else if （（newCap = oldCap 《 1） < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY） {…}
}
else if （oldThr > 0） {…}
else {…}
// 第二个条件分支
if （newThr == 0） {…}
通过这两个条件分支对不同情况进行判断，进而算出不同的容量值和阈值。它们所覆盖的情况如下：
分支一：
这里把oldThr > 0情况单独拿出来说一下。在这种情况下，会将 oldThr 赋值给 newCap,等价于newCap = threshold = tableSizeFor（initialCapacity）。我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap.这也就解答了前面提的一个疑问：initialCapacity 参数没有被保存下来，那么它怎么参与桶数组的初始化过程的呢？
嵌套分支：
这里简单说明一下移位导致的溢出情况，当 loadFactor小数位为 0,整数位可被2整除且大于等于8时，在某次计算中就可能会导致 newThr 溢出归零。
分支二：
说完 newCap 和 newThr 的计算过程，接下来再来分析一下键值对节点重新映射的过程。
在 JDK 1.8 中，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。关于红黑树拆分的逻辑将会放在下一小节说明，先来看看链表是怎样进行分组映射的。
我们都知道往底层数据结构中插入节点时，一般都是先通过模运算计算桶位置，接着把节点放入桶中即可。事实上，我们可以把重新映射看做插入操作。在 JDK 1.7 中，也确实是这样做的。但在 JDK 1.8 中，则对这个过程进行了一定的优化，逻辑上要稍微复杂一些。在详细分析前，我们先来回顾一下 hash 求余的过程：
桶数组大小 n = 16,hash1 与 hash2 不相等。但因为只有后4位参与求余，所以结果相等。当桶数组扩容后，n 由16变成了32,对上面的 hash 值重新进行映射：
扩容后，参与模运算的位数由4位变为了5位。由于两个 hash 第5位的值是不一样，所以两个 hash 算出的结果也不一样。上面的计算过程并不难理解，继续往下分析。
假设我们上图的桶数组进行扩容，扩容后容量 n = 16,重新映射过程如下：
依次遍历链表，并计算节点 hash & oldCap 的值。
如果值为0,将 loHead 和 loTail 指向这个节点。如果后面还有节点 hash & oldCap 为0的话，则将节点链入 loHead 指向的链表中，并将 loTail 指向该节点。如果值为非0的话，则让 hiHead 和 hiTail 指向该节点。完成遍历后，可能会得到两条链表，此时就完成了链表分组：
最后再将这两条链接存放到相应的桶中，完成扩容。
重新映射后，两条链表中的节点顺序并未发生变化，还是保持了扩容前的顺序。以上就是 JDK 1.8 中 HashMap 扩容的代码讲解。另外再补充一下，JDK 1.8 版本下 HashMap 扩容效率要高于之前版本。如果大家看过 JDK 1.7 的源码会发现，JDK 1.7 为了防止因 hash 碰撞引发的拒绝服务攻击，在计算 hash 过程中引入随机种子。以增强 hash 的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方法会根据容量判断是否需要生成新的随机种子，并重新计算所有节点的 hash.而在 JDK 1.8 中，则通过引入红黑树替代了该种方式。从而避免了多次计算 hash 的操作，提高了扩容效率。
本小节的内容讲就先讲到这，接下来，来讲讲链表与红黑树相互转换的过程。
以上就是青岛IT培训给大家做的内容详解，更多关于UI的学习，请继续关注青岛IT培训

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

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