HashMap链表转红黑树源码解析

HashMap链表转红黑树需要同时满足两个条件：

1.table数组长度>=64

2.链表长度>8

当调用put方法添加元素到map时，链表转红黑树的入口是treeifyBin(tab, hash)方法。为了让元素集中添加到某个桶bucket中，简单粗暴的做法是写一个类，重写hashCode和equals方法

/**
 * 想要HasMap都分配到同一个桶上，就要保证hashCode一样，所以本类重写了hashCode方法，并且都返回1111
 * HashMap判断key是否相等，是用==号，比较的是内存地址。所以new两个User对象，用==号比较肯定是false
 * 重写equals方法，永远返回false，这样HashMap就不会认为key是一样的了。就会往同一个桶插入user对象，
 * 直到链表长度超过8，就可以演示链表转红黑树的现象。
 *
 * HashMap是这样判断key相等的，相等就把旧值替换为新值
 * 这里key不等(都是new出来的，所以==号结果是false)
 * equals也不等，因为重写了返回为false
 * if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))    // p是链表表头
 *     e = p;
 *
 * @author: lbj
 * @create: 2020-07-31 23:56
 */
public class User {
    @Override
    public boolean equals(Object o) {
        return false;   // 故意
    }

    @Override
    public int hashCode() {
        return 1111;    // 故意
    }
}
           

写个demo，for循环100次往map里添加元素，当添加到第9个元素的时候，才进入到treeifyBin方法

public class HashMapTest {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();
        for (Integer i=0;i<100;i++) {
            System.out.println("i==="+i);
            map.put(new User(),1);
        }
    }
}
           

运行效果如下图：

在treeifyBin方法会首先判断table数组的长度，如果小于64的话，就扩容，容量为原来的2倍。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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 {// while循环，把Node节点转成TreeNode节点
            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);
    }
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
           

变成红黑树之后，再往map添加元素，就走putVal方法的这个分支

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           

附上TreeNode的结构

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}