留一半清醒、留一半醉!!!HashMap中treeifyBin源码解析

前言

点赞在看,养成习惯。

点赞收藏,人生辉煌。

点击关注【微信搜索公众号:编程背锅侠】,防止迷路。

HashMap系列文章

第一篇 HashMap源码中的成员变量你还不懂? 来来来!!!整理好的成员变量源码解析

第二篇 撸啊撸,再次撸HashMap源码,踩坑源码中构造方法!!!每次都有收获

第三篇 MoxiMoxi !!!你看过HashMap中的put方法的源码吗?

第四篇 HashMap源码中的resize扩容方法除了扩容还有一个用途你真的知道吗?

第五篇 留一半清醒、留一半醉!!!HashMap中treeifyBin、treeify源码解析


final void treeifyBin(HashMap.Node<K,V>[] tab, int hash)
将当前桶下的链表中的Node节点类型转化为TreeNode节点类型,并转换为红黑树

节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8,如果大于则将链表转换为红黑树,转换红黑树的方法 treeifyBin,整体代码如下:

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
  // 转换为红黑树 tab表示数组名 hash表示哈希值 
  treeifyBin(tab, hash);
复制代码

真的是只要TREEIFY_THRESHOLD大于临界值8就转化为红黑树吗?

(n = tab.length) < MIN_TREEIFY_CAPACITY
这句源码。MIN_TREEIFY_CAPACITY的值为64。其实转换为红黑色的条件是有两个。一个条件是大于临界值8,另一个条件就是容量要大于等于64。

为什么容量要大于64才允许树形化?

如果数组很⼩,转换为红黑树,遍历效率要低很多。如果又这个条件,会进行扩容,那么就会重新计算哈希值,链表长度有可能就变短了,数据会放到数组中,这样相对来说效率⾼一些。

源码阅读

// tab: 集合中的所有的Node节点,其实红黑树的第一个节点还是Node节点
final void treeify(Node<K,V>[] tab) {
 // 定义一个root节点
 TreeNode<K,V> root = null;
 // 遍历这个已经转换为树节点的链表,x指向当前节点、next指向下一个节点,首次遍历的时候这个节点就是根节点
 for (TreeNode<K,V> x = this, next; x != null; x = next) {
  // 将这个节点的下一个节点并强制转换为树节点
  next = (TreeNode<K,V>)x.next;
  // 初始化这个节点的左子树和右子树节点为null
  x.left = x.right = null;
  // 判断根节点是否为null,将当前的节点设置为根节点,也就是说有没有根节点
  // 第一次遍历,会进入这个判断,找出根节点
  if (root == null) {
   // 根节点的父节点设置为null
   x.parent = null;
   // 节点的颜色设置为黑
   x.red = false;
   // 将当前的这个节点赋值给根节点root,只有一个节点赋值成功,也就是说根节点指向当前节点
   root = x;
  }
  else {// 此时,已经存在根节点了
   // 获取当前节点的key赋值给k
   K k = x.key;
   // 获取当前节点的哈希值赋值给h
   int h = x.hash;
   // 定义key所属的Class
   Class<?> kc = null;
   // 真正的构建红黑树
   for (TreeNode<K,V> p = root;;) {
    // dir 标识方向,是在根节点的左侧还是右侧
    // ph标识当前树节点的hash值
    int dir, ph;
    // 当前根节点的key赋值给pk
    K pk = p.key;
    // 将根节点hash赋值给ph,如果当前根节点hash值大于当前链表节点的hash值
    if ((ph = p.hash) > h)
     // 标识当前链表节点会放到当前根节点的左侧
     dir = -1;
     // 将根节点hash赋值给ph,如果当前根节点hash值小于当前链表节点的hash值
    else if (ph < h)
     // 标识当前链表节点会放到当前根节点的右侧
     dir = 1;
     // 将根节点hash赋值给ph,如果当前根节点hash值等于当前链表节点的hash值
     // 如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实例
     // 那么通过comparable的方式再比较两者。
     // 如果还是相等,最后再通过tieBreakOrder比较一次
     // dir = compareComparables(kc, k, pk)) == 0等于0代表还是平衡
    else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
      (dir = compareComparables(kc, k, pk)) == 0)
     // 打破平衡
     dir = tieBreakOrder(k, pk);

    // 当前节点
    TreeNode<K,V> xp = p;
    // dir <= 0:当前链表节点放置在当前树节点的左侧,但不一定是该树节点的左子树,也可能是左子树的右子树或者更深层次的节点。
    // dir > 0:当前链表节点放置在当前树节点的右侧,但不一定是该树节点的右子树,也可能是右子树的左子树或者更深层次的节点。
    // 如果当前树节点不是叶子节点,那么最终会以当前树节点的左子树或者右子树为起始节点接着遍历,重新寻找自己(当前链表节点)的位置
    // 如果当前树节点就是叶子节点,那么根据dir的值,就可以把当前链表节点挂载到当前树节点的左或者右侧了。
    // 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
    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;
    }
   }
  }
 }
 // 链表节点都遍历完后,最终构造出来的树可能经历多次平衡操作,根节点目前到底是链表的哪一个节点是不确定的。
 // 要将红黑树的根节点移动至链表节点的第一个位置也就是 table[i]的位置。
 moveRootToFront(tab, root);
}
复制代码

源码总结

  • 1.根据哈希表中元素个数确定是扩容还是树形化 。必须满足以下两个条件

  • 2.如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建⽴起联系。

  • 3.然后让桶中的第⼀个元素指向新创建的树根节点,替换桶的链表内容为树形化内容。

转换为红黑树的源码分析

源码分析

// tab: 集合中的所有的Node节点,其实红黑树的第一个节点还是Node节点
final void treeify(Node<K,V>[] tab) {
  // 定义一个root节点
 TreeNode<K,V> root = null;
  // 遍历这个已经转换为树节点的链表,x指向当前节点、next指向下一个节点,首次遍历的时候这个节点就是根节点
 for (TreeNode<K,V> x = this, next; x != null; x = next) {
    // 将这个节点的下一个节点并强制转换为树节点
  next = (TreeNode<K,V>)x.next;
    // 初始化这个节点的左子树和右子树节点为null
  x.left = x.right = null;
    // 判断根节点是否为null,将当前的节点设置为根节点,也就是说有没有根节点
    // 第一次遍历,会进入这个判断,找出根节点
  if (root == null) {
      // 根节点的父节点设置为null
   x.parent = null;
      // 节点的颜色设置为黑
   x.red = false;
      // 将当前的这个节点赋值给根节点root,只有一个节点赋值成功,也就是说根节点指向当前节点
   root = x;
  }
  else {// 此时,已经存在根节点了
      // 获取当前节点的key赋值给k
   K k = x.key;
      // 获取当前节点的哈希值赋值给h
   int h = x.hash;
      // 定义key所属的Class
   Class<?> kc = null;
      // 真正的构建红黑树
   for (TreeNode<K,V> p = root;;) {
        // dir 标识方向,是在根节点的左侧还是右侧
        // ph标识当前树节点的hash值
    int dir, ph;
        // 当前根节点的key赋值给pk
    K pk = p.key;
        // 将根节点hash赋值给ph,如果当前根节点hash值大于当前链表节点的hash值
    if ((ph = p.hash) > h)
          // 标识当前链表节点会放到当前根节点的左侧
     dir = -1;
        // 将根节点hash赋值给ph,如果当前根节点hash值小于当前链表节点的hash值
    else if (ph < h)
          // 标识当前链表节点会放到当前根节点的右侧
     dir = 1;
        // 将根节点hash赋值给ph,如果当前根节点hash值等于当前链表节点的hash值
        // 如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实例
        // 那么通过comparable的方式再比较两者。
        // 如果还是相等,最后再通过tieBreakOrder比较一次
        // dir = compareComparables(kc, k, pk)) == 0等于0代表还是平衡
    else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
      (dir = compareComparables(kc, k, pk)) == 0)
          // 打破平衡
     dir = tieBreakOrder(k, pk);

        // 当前节点
    TreeNode<K,V> xp = p;
        // dir <= 0:当前链表节点放置在当前树节点的左侧,但不一定是该树节点的左子树,也可能是左子树的右子树或者更深层次的节点。
        // dir > 0:当前链表节点放置在当前树节点的右侧,但不一定是该树节点的右子树,也可能是右子树的左子树或者更深层次的节点。
        // 如果当前树节点不是叶子节点,那么最终会以当前树节点的左子树或者右子树为起始节点接着遍历,重新寻找自己(当前链表节点)的位置
        // 如果当前树节点就是叶子节点,那么根据dir的值,就可以把当前链表节点挂载到当前树节点的左或者右侧了。
    // 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
        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;
    }
   }
  }
 }
  // 链表节点都遍历完后,最终构造出来的树可能经历多次平衡操作,根节点目前到底是链表的哪一个节点是不确定的。
  // 要将红黑树的根节点移动至链表节点的第一个位置也就是 table[i]的位置。
 moveRootToFront(tab, root);
}
复制代码

记录9个hashCode相同的字符串

案例演示

@Test
public void test_hash_map_hash() {
 ArrayList<String> list = new ArrayList<>();
 list.add("3Qj");
 list.add("2pj");
 list.add("2qK");
 list.add("2r,");
 list.add("3RK");
 list.add("3S,");
 list.add("42j");
 list.add("43K");
 list.add("44,");
 list.forEach(s -> System.out.println(s + "  ====  " + s.hashCode()));
}
复制代码

打印结果

3Qj  ====  51628
2pj  ====  51628
2qK  ====  51628
2r,  ====  51628
3RK  ====  51628
3S,  ====  51628
42j  ====  51628
43K  ====  51628
44,  ====  51628
复制代码

谢谢点赞

  • 创作不易, 非常欢迎大家的点赞、评论和关注(^_−)☆

  • 你的点赞、评论以及关注是对我最大的支持和鼓励,而你的支持和鼓励

  • 我继续创作高质量博客的动力 !!!

原文 

https://juejin.im/post/5f0bf5ebe51d45349f7b2356

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 留一半清醒、留一半醉!!!HashMap中treeifyBin源码解析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址