认识达内从这里开始

认真做教育专心促就业

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

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

青岛IT培训的小编总结， 3.4.3 链表树化、红黑树链化与拆分
JDK 1.8 对 HashMap 实现进行了改进。最大的改进莫过于在引入了红黑树处理频繁的碰撞，代码复杂度也随之上升。比如，以前只需实现一套针对链表操作的方法即可。而引入红黑树后，需要另外实现红黑树相关的操作。红黑树是一种自平衡的二叉查找树，本身就比较复杂。本篇文章中并不打算对红黑树展开介绍，本文仅会介绍链表树化需要注意的地方。至于红黑树详细的介绍，如果大家有兴趣，可以参考我的另一篇文章 - 红黑树详细分析。
在展开说明之前，先把树化的相关代码贴出来，如下：
static final int TREEIFY_THRESHOLD = 8;
/**
* 当桶数组容量小于该值时，优先进行扩容，而不是树化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
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） {
// hd 为头节点（head），tl 为尾节点（tail）
TreeNode<K,V> hd = null, tl = null;
do {
// 将普通节点替换成树形节点
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）；
}
在扩容过程中，树化要满足两个条件：
链表长度大于等于 TREEIFY_THRESHOLD
桶数组容量大于等于 MIN_TREEIFY_CAPACITY
第一个条件比较好理解，这里就不说了。这里来说说加入第二个条件的原因，个人觉得原因如下：
当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。
回到上面的源码中，我们继续看一下 treeifyBin 方法。该方法主要的作用是将普通链表转成为由 TreeNode 型节点组成的链表，并在最后调用 treeify 是将该链表转为红黑树。TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。我们假设树化前，链表结构如下：
HashMap 在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下：
比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder（大家自己看源码吧）
tie break 是网球术语，可以理解为加时赛的意思，起这个名字还是挺有意思的。
通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：
橙色的箭头表示 TreeNode 的 next 引用。由于空间有限，prev 引用未画出。可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。这样的结构为后面红黑树的切分以及红黑树转成链表做好了铺垫，我们继续往下分析。
红黑树拆分
扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，HashMap 实现的思路则是上好佳（上好佳请把广告费打给我）。如上节所说，在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。
以上就是红黑树拆分的逻辑，下面看一下具体实现吧：
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
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
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
* 下面的循环是对红黑树节点进行分组，与上面类似
*/
for （TreeNode<K,V> e = b, next; e != null; e = next） {
next = （TreeNode<K,V>）e.next;
e.next = null;
if （（e.hash & bit） == 0） {
if （（e.prev = loTail） == null）
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
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）
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 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD,则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：
红黑树链化
前面说过，红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。相关代码如下：
final Node<K,V> untreeify（HashMap<K,V> map） {
Node<K,V> hd = null, tl = null;
// 遍历 TreeNode 链表，并用 Node 替换
for （Node<K,V> q = this; q != null; q = q.next） {
// 替换节点类型
Node<K,V> p = map.replacementNode（q, null）；
if （tl == null）
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode（Node<K,V> p, Node<K,V> next） {
return new Node<>（p.hash, p.key, p.value, next）；
}

上面的代码并不复杂，不难理解，这里就不多说了。到此扩容相关内容就说完了，不知道大家理解没。

青岛IT培训

3.5 删除
如果大家坚持看完了前面的内容，到本节就可以轻松一下。当然，前提是不去看红黑树的删除操作。不过红黑树并非本文讲解重点，本节中也不会介绍红黑树相关内容，所以大家不用担心。
HashMap 的删除操作并不复杂，仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：
public V remove（Object key） {
Node<K,V> e;
return （e = removeNode（hash（key）， key, null, false, true）） == null ?
null : e.value;
}
final Node<K,V> removeNode（int hash, Object key, Object value,
boolean matchValue, boolean movable） {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if （（tab = table） != null && （n = tab.length） > 0 &&
// 1. 定位桶位置
（p = tab[index = （n - 1） & hash]） != null） {
Node<K,V> node = null, e; K k; V v;
// 如果键的值与链表第一个节点相等，则将 node 指向该节点
if （p.hash == hash &&
（（k = p.key） == key || （key != null && key.equals（k））））
node = p;
else if （（e = p.next） != null） {
// 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
if （p instanceof TreeNode）
node = （（TreeNode<K,V>）p）。getTreeNode（hash, key）；
else {
// 2. 遍历链表，找到待删除节点
do {
if （e.hash == hash &&
（（k = e.key） == key ||
（key != null && key.equals（k）））） {
node = e;
break;
}
p = e;
} while （（e = e.next） != null）；
}
}
// 3. 删除节点，并修复链表或红黑树
if （node != null && （！matchValue || （v = node.value） == value ||
（value != null && value.equals（v）））） {
if （node instanceof TreeNode）
（（TreeNode<K,V>）node）。removeTreeNode（this, tab, movable）；
else if （node == p）
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval（node）；
return node;
}
}
return null;
}
删除操作本身并不复杂，有了前面的基础，理解起来也就不难了，这里就不多说了。
3.6 其他细节
前面的内容分析了 HashMap 的常用操作及相关的源码，本节内容再补充一点其他方面的东西。
被 transient 所修饰 table 变量
如果大家细心阅读 HashMap 的源码，会发现桶数组 table 被申明为 transient.transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，别人还怎么还原呢？
这里简单说明一下吧，HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap 中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建 HashMap.有的朋友可能会想，序列化 table 不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化 talbe 存在着两个问题：
table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。
以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash,此时再对在同一个 table 继续操作，就会出现问题。
综上所述，大家应该能明白 HashMap 不序列化 table 的原因了。
3.7 总结
本章对 HashMap 常见操作相关代码进行了详细分析，并在最后补充了一些其他细节。在本章中，插入操作一节的内容说的最多，主要是因为插入操作涉及的点特别多，一环扣一环。包含但不限于“table 初始化、扩容、树化”等，总体来说，插入操作分析起来难度还是很大的。好在，最后分析完了。
本章篇幅虽比较大，但仍未把 HashMap 所有的点都分析到。比如，红黑树的增删查等操作。当然，我个人看来，以上的分析已经够了。毕竟大家是类库的使用者而不是设计者，没必要去弄懂每个细节。所以如果某些细节实在看不懂的话就跳过吧，对我们开发来说，知道 HashMap 大致原理即可。
好了，本章到此结束。
4.写在最后
写到这里终于可以松一口气了，这篇文章前前后后花了我一周多的时间。在我写这篇文章之前，对 HashMap 认识仅限于原理层面，并未深入了解。一开始，我觉得关于 HashMap 没什么好写的，毕竟大家对 HashMap 多少都有一定的了解。但等我深入阅读 HashMap 源码后，发现之前的认知是错的。不是没什么可写的，而是可写的点太多了，不知道怎么写了。JDK 1.8 版本的 HashMap 实现上比之前版本要复杂的多，想弄懂众多的细节难度还是不小的。仅自己弄懂还不够，还要写出来，难度就更大了，本篇文章基本上是在边读源码边写的状态下完成的。由于时间和能力有限，加之文章篇幅比较大，很难保证不出错分析过程及配图不出错。
以上就是青岛IT培训给大家做的内容详解，更多关于UI的学习，请继续关注青岛IT培训

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

下一篇：IT行业现在还有前景么？一个10年行内人的6点看法 >