Java集合类源码解析:HashMap (基于JDK1.8) (5)

下面看下转换红黑树的过程:

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 链表树化。这里用两张图来展示一下拆分前后的变化

红黑树拆分前:

Java集合类源码解析:HashMap (基于JDK1.8)

拆分后:

Java集合类源码解析:HashMap (基于JDK1.8)


至此,有关红黑树的一些转换操作就介绍完毕了,除此之外,hashMap还提供了很多操作红黑树的方法,原理都差不多,读者们可以自己去研究。

总结

HashMap的源码解析就告一段落了,最后,总结一下HashMap的一些特性:

1、HashMap 允许 key, value 为 null;

2、HashMap源码里没有做同步操作,多个线程操作可能会出现线程安全的问题,建议用Collections.synchronizedMap 来包装,变成线程安全的Map,例如:

Map map = Collections.synchronizedMap(new HashMap<String,String>());

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpxygs.html