源码速读：HashMap中的树会不会转成链表？

        /**
         * Returns a list of non-TreeNodes replacing those linked from
         * this node.
         * 返回一个非树节点链表，该链表替换从该节点链接的树节点。
         */
        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         * 移除在此调用之前必须存在的给定节点。
         * 这比典型的红黑树删除代码更混乱，
         * 因为我们不能将内部节点的内容与由“next”指针固定的叶继承节点交换，
         * 这些“next”指针在遍历期间可以独立访问。所以我们交换树的引用。
         * 如果当前树的节点似乎太少，则将bin转换回普通bin。(根据树的结构，测试触发2到6个节点)。
         */
        final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            //first 为当前桶的头结点,root为树的头结点  rl为根节点的左子树节点
            TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
            // succ 为当前节点的下一节点  pred为当前节点的上一个节点(用来关联双链表的上下节点)
            TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;
            // 如果当前节点无前一节点,则当前节点为头结点,则直接将当前节点的下一节点设置为头结点,
            // 否则的话将当上一节点(pred)的下一节点指针指向下一节点(next)
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            // 如果下一节点不为空 说明当前节点不是尾节点,
            // 则将下一节点(next)的前一节点指针指向前一节点(pred),这样,当前节点在双链表中就脱离出来了
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            // 这个是判断当前红黑树的结构是否太小,
            // 当然这种情况下是不存在,如果太小的话,
            // 当前桶结构就是单链表了,而不是红黑树了.
            if (root == null || root.right == null ||
                    (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            // 上面解析并使当前链表节点脱离双链表,下面就是使当前树节点脱离红黑树
            // p为当前树节点,
            // pl为当前树节点的左子树节点,
            // pr为右子树节点,
            // replacement为要替代当前树节点的节点(下面简称为当前树节点，左子树节点,右子树节点和替换节点)
            TreeNode<K, V> p = this, pl = left, pr = right, replacement;
            // 如果左右子树节点都不为空 进入判断
            if (pl != null && pr != null) {
                TreeNode<K, V> s = pr, sl;
                // 通过while循环遍历有右子树节点的最左侧的左子树节点,并赋值给s(下面简称为右子树最小树节点)
                while ((sl = s.left) != null) // find successor
                    s = sl;
                // 将当前节点的与s节点的颜色进行互换
                boolean c = s.red;
                s.red = p.red;
                p.red = c; // swap colors
                TreeNode<K, V> sr = s.right;
                TreeNode<K, V> pp = p.parent;
                // 下面这个判断是当前节点的右子树节点是否无子树节点，
                // 如果没有则将当前节点的父子树节点指针指向右子树节点,右子树节点的右子树指针指向当前节点,
                // 从而完成子树节点的替换
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                } else {
                    // 如果右子树节点有子树节点,
                    // 则将右子树最小节点与当前节点进行替换,
                    // 分别将当前节点的父子树节点的子树节点指针指向右子树最小节点,
                    // 原先右子树最小节点的父子树节点的子树节点指针指向当前节点,
                    // 右子树最小节点的右子树节点指针指向右子树,(到这里是完成了当前节点的右子树的替换，下面就是左子树替换)
                    TreeNode<K, V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                // 将当前节点左子树节点指针指向空
                p.left = null;
                // 将右子树最小树节点的右子树节点指针指向当前节点的右子树节点,
                // 右子树最小树节点的右子树节点的父子树节点指向当前节点
                if ((p.right = sr) != null)
                    sr.parent = p;
                // 将右子树最小节点的左子树指针指向左子树节点,并将左子树节点的父子树节点指针指向右子树最小节点
                if ((s.left = pl) != null)
                    pl.parent = s;
                // 如果此时的右子树最小子树节点的父子树节点为空,则其为根节点,将其赋值给root,
                // 否则的话,将父子树节点的的左/右子树节点的指针指向s
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                // 此时的sr是当前节点p的右子树节点，如果不为空则将replacement指向sr,否则指向p
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            } else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            // 上面的三个else 如果当前节点有子树节点则将relpacement指向此子树节点，否则指向p
            // 下面就开始使p脱离树了
            //下面的判断 如果p有子树节点(无论是替换前还是替换后)即replacement != p
            if (replacement != p) {
                TreeNode<K, V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
            // 如果此时的p为红色,则返回root,
            // 否则进入balanceDeletion,balanceDeletion是重新调整树结构并返回调整后的树的根节点.这里就不在多说了
            TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);

            // 如果p无子树节点(无论是替换前还是替换后)，
            // 使此时的p的父子树节点的左/右子树节点指向null,
            // 此时的p也算是脱离出来了
            if (replacement == p) {  // detach
                TreeNode<K, V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            // 最后通过moveRootToFront重新定义双链表的头部节点使之与树的根节点相同
            if (movable)
                moveRootToFront(tab, r);
        }