关于 treeify

treeify 方法其实是 TreeNode 类的一个实例方法，通过 TreeNode 对象调用，实现该对象打头的链表转换为树结构。

源码

1、treeify

  1. /**
  2.  * Forms tree of the nodes linked from this node.
  3.  */
  4. final void treeify(Node<K,V>[] tab) {
  5.     TreeNode<K,V> root = null;
  6.     for (TreeNode<K,V> x = this, next; x != null; x = next) {
  7.         next = (TreeNode<K,V>)x.next;
  8.         x.left = x.right = null;
  9.         if (root == null) {
  10.             x.parent = null;
  11.             x.red = false;
  12.             root = x;
  13.         }
  14.         else {
  15.             K k = x.key;
  16.             int h = x.hash;
  17.             Class<?> kc = null;
  18.             for (TreeNode<K,V> p = root;;) {
  19.                 int dir, ph;
  20.                 K pk = p.key;
  21.                 if ((ph = p.hash) > h)
  22.                     dir = -1;
  23.                 else if (ph < h)
  24.                     dir = 1;
  25.                 else if ((kc == null &&
  26.                           (kc = comparableClassFor(k)) == null) ||
  27.                          (dir = compareComparables(kc, k, pk)) == 0)
  28.                     dir = tieBreakOrder(k, pk);
  30.                 TreeNode<K,V> xp = p;
  31.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  32.                     x.parent = xp;
  33.                     if (dir <= 0)
  34.                         xp.left = x;
  35.                     else
  36.                         xp.right = x;
  37.                     root = balanceInsertion(root, x);
  38.                     break;
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     moveRootToFront(tab, root);
  44. }

2、treeify 源码注释

  1. /**
  2.  * 参数为HashMap的元素数组
  3.  */
  4. final void treeify(Node<K,V>[] tab) {
  5.     // 定义树的根节点
  6.     TreeNode<K,V> root = null;
  8.     // 遍历链表，x指向当前节点、next指向下一个节点
  9.     for (TreeNode<K,V> x = this, next; x != null; x = next) {
  10.         // 下一个节点
  11.         next = (TreeNode<K,V>)x.next;
  13.         // 设置当前节点的左右节点为空
  14.         x.left = x.right = null;
  16.         // 如果还没有根节点
  17.         if (root == null) {
  18.             // 当前节点的父节点设为空
  19.             x.parent = null;
  20.             // 当前节点的红色属性设为false（把当前节点设为黑色）
  21.             x.red = false;
  22.             // 根节点指向到当前节点
  23.             root = x;
  24.         }
  25.         // 如果已经存在根节点了
  26.         else {
  27.             // 取得当前链表节点的key
  28.             K k = x.key;
  29.             // 取得当前链表节点的hash值
  30.             int h = x.hash;
  31.             // 定义key所属的Class
  32.             Class<?> kc = null;
  33.             // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
  34.             for (TreeNode<K,V> p = root;;) {
  35.                 // dir 标识方向（左右）、ph标识当前树节点的hash值
  36.                 int dir, ph;
  37.                 // 当前树节点的key
  38.                 K pk = p.key;
  39.                 // 如果当前树节点 hash 值 大于 当前链表节点的 hash 值
  40.                 if ((ph = p.hash) > h)
  41.                     // 标识当前链表节点会放到当前树节点的左侧
  42.                     dir = -1;
  43.                 else if (ph < h)
  44.                     // 标识当前链表节点会放到当前树节点的右侧
  45.                     dir = 1;
  47.                 /*
  48.                  * 如果两个节点的 key 的 hash 值相等，那么还要通过其他方式再进行比较
  49.                  * 如果当前链表节点的 key 实现了 comparable 接口，并且当前树节点和链表节点是相同 Class 的实例，那么通过 comparable 的方式再比较两者。
  50.                  * 如果还是相等，最后再通过 tieBreakOrder 比较一次
  51.                  */
  52.                 else if ((kc == null &&
  53.                           (kc = comparableClassFor(k)) == null) ||
  54.                          (dir = compareComparables(kc, k, pk)) == 0)
  55.                     dir = tieBreakOrder(k, pk);
  56.                 // 保存当前树节点
  57.                 TreeNode<K,V> xp = p;
  58.                 /*
  59.                  * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
  60.                  * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
  61.                  * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
  62.                  * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
  63.                  * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
  64.                  */
  65.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  66.                     // 当前链表节点 作为 当前树节点的子节点
  67.                     x.parent = xp;
  68.                     if (dir <= 0)
  69.                         // 作为左孩子
  70.                         xp.left = x;
  71.                     else
  72.                         // 作为右孩子
  73.                         xp.right = x;
  74.                     // 重新平衡
  75.                     root = balanceInsertion(root, x);
  76.                     break;
  77.                 }
  78.             }
  79.         }
  80.     }
  82.     // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
  83.     // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
  84.     moveRootToFront(tab, root);
  85. }