hashmap链表转化成红黑树的过程以及红黑树转化成链表的过程

1.链表转红黑树的实现代码

// 该方法主要是将单向链表转化成双向链表（为了后面操作，比如在后面将红黑树放到数组上时，以及红黑树转成链表时简化操作）
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果数组为空或者数组大小小于最小数化的大小(64),则直接进行数据扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    	// 数组扩容的方法
        resize();
     // 获取要树化的链表的头结点，并判断是否为空
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 遍历要树化的整个链表，转化单向链表为双向链表
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 将数组中该位置的头指向转化成双向链表的头并判断是否非空
        if ((tab[index] = hd) != null)
        	// 树化该链表
            hd.treeify(tab);
    }
}

// 该方法是将链表转化成树，插入左右节点的依据是key的hash值去进行判断，如果插入元素的hash值大于节点的hash值，则插入到叶子节点的左边，如果小于则插入到右边，如果相等，则进行特殊处理（详情看后面）再去比较大小
final void treeify(Node<K,V>[] tab) {
   TreeNode<K,V> root = null;
   // 遍历转化的双向链表，此处this即为上面方法的hd(表头)
   for (TreeNode<K,V> x = this, next; x != null; x = next) {
       next = (TreeNode<K,V>)x.next;
       x.left = x.right = null;
       // 如果treeNode是空的（即第一个元素）,则将元素置为根元素，且设置为黑节点
       if (root == null) {
           x.parent = null;
           x.red = false;
           root = x;
       }
       else {
       	   // 获取节点的key以及key的hash值
           K k = x.key;
           int h = x.hash;
           Class<?> kc = null;
           // 从红黑树根节点去从头遍历
           for (TreeNode<K,V> p = root;;) {
           		// 获取红黑树p节点的key以及key的hash值
               int dir, ph;
               K pk = p.key;
               // 比较要插入元素的hash值与红黑树节点p的大小，用dir去记录值
               if ((ph = p.hash) > h)
                   dir = -1;
               else if (ph < h)
                   dir = 1;
               // 当插入元素的hash值与红黑树节点p的hash值相等时，
               // kc == null &&  (kc = comparableClassFor(k)) == null  如果插入的元素x没有实现Comparable接口则通过tieBreakOrder去比较
               // (dir = compareComparables(kc, k, pk)) == 0 如果实现了Comparable接口,p节点为空或x元素不是同一个类，也是通过tieBreakOrder去比较，否则通过compareComparables里面的compareTo方法去比较，如果也为0,则也是通过tieBreakOrder去比较，否则直接返回该结果
               else if ((kc == null &&
                         (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0)
                   dir = tieBreakOrder(k, pk);
				// 用xp来指向当前遍历红黑树的节点p
               TreeNode<K,V> xp = p;
               // p根据dir的值去选择指向其左右节点,并判断其是否为空,如果不为空循环下一次
               // 换句话说就是你要插入的位置是否有值了，有值就继续循环
               if ((p = (dir <= 0) ? p.left : p.right) == null) {
               		// 设置要插入元素x在红黑树中的父节点是xp(就是红黑树遍历的当前元素) 
                   x.parent = xp;
                   // 指定插入到左边还是右边。
                   if (dir <= 0)
                       xp.left = x;
                   else
                       xp.right = x;
                   // 到此为止元素已经插入到对应的树中,最后就是将数转换成红黑树了
                   root = balanceInsertion(root, x);
                   break;
               }
           }
       }
   }
   // 确保转化后的红黑树在数组上
   moveRootToFront(tab, root);
}

// 将数转化成为红黑树，主要是红黑树的实现规则，可以大概了解下
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 将插入的元素x置为红色
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
    	// 如果x的父节点是空的，将x颜色置为黑色，返回(其实就是红黑树的特点，根节点为黑色)
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 如果x的父节点是黑色或者爷爷节点是空的，则就是红黑树直接返回了
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 如果父节点是爷爷节点的左节点
        if (xp == (xppl = xpp.left)) {
        	// 如果爷爷节点的右节点不为空且是红色，则爷爷节点的右置为黑色，父节点也置为黑色，爷爷节点置为红色，
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                // 再次循环调整数，此时起点不再是插入的元素x,而是从xpp开始调整了
                x = xpp;
            }
            else {
            	// 如果爷爷节点的右节点为空或是黑节点
            	// 如果当前插入元素是父节点的右节点
                if (x == xp.right) {
                	// 针对父节点进行左旋，想了解怎么实现可以自己跟下代码
                    root = rotateLeft(root, x = xp);
                    // 获取爷爷节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 如果父节点不为空
                if (xp != null) {
                	// 父节点设为黑色
                    xp.red = false;
                    //如果爷爷节点不为空
                    if (xpp != null) {
                    	// 则爷爷节点置为红色
                        xpp.red = true;
                        // 针对爷爷节点进行右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // 如果父节点是爷爷节点的右节点
        else {
        	// 如果爷爷节点的左节点不为空且为红色，则爷爷节点的左节点置为黑色，父节点也置为黑色，爷爷节点置为红色，
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                // 再次循环调整数，此时起点不再是插入的元素x,而是从xpp开始调整了
                x = xpp;
            }
            else {
                // 如果爷爷节点的左节点为空或是黑节点
            	// 如果当前插入元素是父节点的左节点
                if (x == xp.left) {
                	// 针对父节点进行右旋
                    root = rotateRight(root, x = xp);
                    // 获取爷爷节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 如果父节点不为空
                if (xp != null) {
                	// 父节点置为黑色
                    xp.red = false;
                    // 如果爷爷节点不为空
                    if (xpp != null) {
                    	// 爷爷节点置为红色
                        xpp.red = true;
                        // 针对爷爷几点进行左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

// 主要是确保转化的红黑树还在数组正确位置上
// 结合上面方法我们知道了数组上的链表既是红黑树，也是双向链表
 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
    	// 获取根元素的下标在数组里面的位置
        int index = (n - 1) & root.hash;
        // 获取该数组位置上的元素first
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        // 如果该first不是根元素，则需要处理了
        if (root != first) {
            Node<K,V> rn;
            // 将数组该位置设置成root
            tab[index] = root;
            // 获取根节点的前一个节点
            TreeNode<K,V> rp = root.prev;
            // root的后一个节点不为空
            if ((rn = root.next) != null)
            	// 则摘除双向链表的root节点
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null)
        		// 如果first不为空，则first作为root的下一个元素
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        // 校验是否满足红黑树和双向链表的特性
        assert checkInvariants(root);
    }
}

// 对接前面，如果插入元素的key的hash值与树节点的key的hash值相同时获取dir的条件，该方法就是判断插入元素是否有实现Comparable接口
static Class<?> comparableClassFor(Object x) {
	// 如果插入元素的key是Comparable的实例(实现了Comparable接口，范围有点大，后面继续作限制)
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // 如果对象是String,直接返回该对象的类对象
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
         // getGenericInterfaces():返回的是该对象的运行时类型直接实现的接口数组,不能是继承的
        if ((ts = c.getGenericInterfaces()) != null) {

           /*
            * 五个条件同时满足时，才获取到正确的类型
            * 1、((t = ts[i]) instanceof ParameterizedType)：实现了泛型参数的类型
            * 2、((p = (ParameterizedType) t).getRawType() == Comparable.class)：获取接口不带参数部分的类型对象且该类型是Comparable
            * 3、(as = p.getActualTypeArguments())：获取泛型参数数组
            * 4、as.length == 1：只有一个泛型参数，
            * 5、as[0] == c：该实现类型是该类型本身
            * 总结：就是key要实现jdk提供的public interface Comparable<T>接口，用这些条件去限制，放在实现自己写的
            */
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

// 如果节点p是null,或者p和x不是一个类对象，则返回0,否则返回实现的compareTo方法的值
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

// 当插入元素x与树结点p的键的hash值相同时进行比较a代表插入元素的key,b代表树结点的key
// 如果a为空或b为空或者通过String的compareTo方法比较的类名相等，则比较的a和b默认hashcode的值
// 否则就是用String的compareTo方法比较的类名结果
 static int tieBreakOrder(Object a, Object b) {
     int d;
     if (a == null || b == null ||
         (d = a.getClass().getName().
          compareTo(b.getClass().getName())) == 0)
          // System.identityHashCode(a): 该方法是无论类是否有覆盖hashCode方法，都会调用默认的hashCode方法去返回值
         d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
              -1 : 1);
     return d;
 }

2.链表转红黑树步骤总结

链表转化成红黑树的实现步骤分为以下几步

1. 当链表结点达到8时调用此方法进行转换
2. 判断数组长度是否达到64，有则转化，没有则扩容
3. 将原单向链表转化成双向链表，再将双向链表放到数组原来位置上
4. 遍历链表去进行转换，每次转换都会从根节点遍历红黑树，确定元素放在红黑树的位置，插入上去后调整树为红黑树
5. 当所有元素转换完成后将转换的红黑树放在数组原位置上

确定元素放在红黑树的位置

1. 确定树是否为空，为空则放到根目录上
2. 比较存放元素与当前遍历树的结点的的hash值，当前数结点的hash值大于存放元素的hash值，会将元素存放在左结点，前数结点的hash值小于存放元素的hash值，会将元素存放到右结点；当两则相等时比较其他大小确定
3. 判断左节点或右结点是否为空，为则放置到该位置，否则继续遍历树

插入元素和树结点的值一样时的比较方式（画的有点丑）

3.红黑树转链表的代码实现

// 实现方式非常简单，转化成红黑树后，遍历链表，转化成单向链表，返回表头
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;
}

4.其他关于hashmap的分析

hashmap的常见静态属性和方法
hashmap的扩容机制
hashmap的存放元素的实现过程