转载

留一半清醒、留一半醉！！！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
复制代码