JDK1.8 HashMap源码解析 树形结构修剪

• JDK1.8 HashMap源码解析 目录
  • JDK1.8 HashMap源码解析(一) 数据结构&初始化
  • JDK1.8 HashMap源码解析(二) 数据赋值 put
  • JDK1.8 HashMap源码解析(三) 扩容机制和resize源码详解
  • JDK1.8 HashMap源码解析(四) 为什么HashMap桶中链表长度个数超过8才转为红黑树
  • JDK1.8 HashMap源码解析(五) 红黑树的具体实现方式？
  • JDK1.8 HashMap源码解析 树形结构修剪
  • HashMap 测试「链表转红黑树以及扩容」
  • JDK1.8 HashMap 总结

树形结构修剪 split()

HashMap 中， 当扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表结构，调用的就是 split()。

/**
     * Splits nodes in a tree bin into lower and upper tree bins, or untreeifies if now too small.
     * Called only from resize; see above discussion about split bits and indices.
     *
     * @param map the map
     * @param tab the table for recording bin heads 表示保存桶头结点的哈希表
     * @param index the index of the table being split 示从哪个位置开始修剪
     * @param bit the bit of hash to split on 要修剪的位数（哈希值）
     */
    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;
      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) {
          // 就把当前节点放到 lXXX 树中
          if ((e.prev = loTail) == null) {
            loHead = e;
          } else {
            loTail.next = e;
          }

          // 然后 loTail 记录 e
          loTail = e;
          // 记录 lXXX 树的节点数量
          ++lc;
        } else { // 如果当前节点哈希值最后一位不是要修剪的，就把当前节点放到 hXXX 树中
          if ((e.prev = hiTail) == null) {
            hiHead = e;
          } else {
            hiTail.next = e;
          }
          hiTail = e;
          // 记录 hXXX 树的节点数量
          ++hc;
        }
      }

      if (loHead != null) {
        // 如果 lXXX 树的数量小于 6，就把 lXXX 树的枝枝叶叶都置为空，变成一个单节点。
        // 然后让这个桶中，要还原索引位置开始往后的结点都变成还原成链表的 lXXX 节点。
        // 这一段元素以后就是一个链表结构
        if (lc <= UNTREEIFY_THRESHOLD) {
          tab[index] = loHead.untreeify(map);
        } else {
          // 否则让索引位置的结点指向 lXXX 树，这个树被修剪过，元素少了
          tab[index] = loHead;
          if (hiHead != null) // (else is already treeified)
          {
            loHead.treeify(tab);
          }
        }
      }
      if (hiHead != null) {
        // 同理，让 指定位置 index + bit 之后的元素
        // 指向 hXXX 还原成链表或者修剪过的树
        if (hc <= UNTREEIFY_THRESHOLD) {
          tab[index + bit] = hiHead.untreeify(map);
        } else {
          tab[index + bit] = hiHead;
          if (loHead != null) {
            hiHead.treeify(tab);
          }
        }
      }
    }

从上述代码可以看到，HashMap 扩容时对红黑树节点的修剪主要分两部分，先分类、再根据元素个数决定是还原成链表还是精简一下元素仍保留红黑树结构。

• 1、分类。
  
  指定位置、指定范围，让指定位置中的元素 （hash & bit) == 0 的，放到 lXXX 树中，不相等的放到 hXXX 树中。
• 2、根据元素个数决定处理情况。
  
  符合要求的元素（即 lXXX 树），在元素个数小于 6 时还原成链表，最后让哈希表中修剪的痛 tab[index] 指向 lXXX 树；在元素个数大于 6 时，还是用红黑树，只不过是修剪了下枝叶；不符合要的元素（即 hXXX 树）也是一样的操作，只不过最后它是放在了修剪范围外 tab[index + bit]。