前言

　　本文从三个部分去探究HashMap的链表转红黑树的具体时机：

　　　　一、从HashMap中有关“链表转红黑树”阈值的声明；

　　　　二、【重点】解析HashMap.put(K key, V value)的源码；

　　　　三、测试；

 

一、从HashMap中有关“链表转红黑树”阈值的声明，简单了解HashMap的链表转红黑树的时机

　　在 的 “四、问题探究”中，我有稍微提到过散列表后面跟什么数据结构是怎么确定的：

　　HashMap中有关“链表转红黑树”阈值的声明：

/**    *  使用红黑树(而不是链表)来存放元素。当向至少具有这么多节点的链表再添加元素时，链表就将转换为红黑树。    * 该值必须大于2，并且应该至少为8，以便于删除红黑树时转回链表。    */    static final int TREEIFY_THRESHOLD = 8;    /**     *  当桶数组容量小于该值时，优先进行扩容，而不是树化：     */    static final int MIN_TREEIFY_CAPACITY = 64;

 

二、【重点】解析HashMap.put(K key, V value)的源码，去弄清楚链表转红黑树的具体时机

　　通过查看HashMap的源码可以发现，它的put(K key, V value)方法调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)来实现元素的新增。所以我们实际要看的是putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)的源码。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {        Node
     
      [] tab;        Node
      
        p;        int n, i;        if ((tab = table) == null || (n = tab.length) == 0)             n = (tab = resize()).length;         if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null); //直接放在散列表上的节点，并没有特意标识其为头节点，其实它就是"链表/红黑树.index(0)"        else {             Node
       
         e;            K k;            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                 e = ((TreeNode
        
         ) p).putTreeVal(this, tab, hash, key, value); 　　　　　　　else { //下面的代码是探究“链表转红黑树”的重点：                for (int binCount = 0;; ++binCount) {                    if ((e = p.next) == null) { //沿着p节点，找到该桶上的最后一个节点：                        p.next = newNode(hash, key, value, null); //直接生成新节点，链在最后一个节点的后面； //“binCount >= 7”：p从链表.index(0)开始，当binCount == 7时，p.index == 7,newNode.index == 8；                         //也就是说，当链表已经有8个节点了，此时再新链上第9个节点，在成功添加了这个新节点之后，立马做链表转红黑树。                        if (binCount >= TREEIFY_THRESHOLD - 1)
        
       
      
     

　　　　　　　　　　　　　　　　treeifyBin(tab, hash); //链表转红黑树 break; 　　　　　　　　　　　　} 　　　　　　　　　　　　…… 　　　　　　　　　　　　p = e; 　　　　　　　　　　} 　　　　　　 } 　　　　　　　…… 　　　　} 　　　　…… }

　　通过源码解析，我们已经很清楚HashMap是在“当链表已经有8个节点了，此时再新链上第9个节点，在成功添加了这个新节点之后，立马做链表转红黑树”。

 

三、通过debug，进一步理解链表转红黑树的具体时机

　　1. 自定义一个类：该类中去重写hashCode()，让一组数据能得到同样的哈希值，从而实现哈希碰撞。同时也重写equals()方法。

public class A03Bean {    protected int number;        public A03Bean(int number) {        this.number = number;    }        /**     * 重写hashCode()方法，只要是4的倍数，最后算出的哈希值都会是0.     */    @Override    public int hashCode() {        return number % 4;    }        /**     * 也必须重写equals()方法。当发生哈希冲突的时候，需要调用equals()方法比较两个对象的实际内容是否相同。     */    @Override    public boolean equals(Object obj) {        if (this == obj)            return true;        if (obj == null)            return false;        if (getClass() != obj.getClass())            return false;        A03Bean other = (A03Bean) obj;        if (number != other.number)            return false;        return true;    }}

　　2. 将自定义类A03Bean的实例放到HashMap中：

public class A03Method_TreeifyBin2 {    public static void main(String[] args) {        HashMap
     
       hashMap = new HashMap<>();        hashMap.put(new A03Bean(4), 0);        hashMap.put(new A03Bean(8), 1);        hashMap.put(new A03Bean(12), 2);        hashMap.put(new A03Bean(16), 3);        hashMap.put(new A03Bean(20), 4);        hashMap.put(new A03Bean(24), 5);        hashMap.put(new A03Bean(28), 6);        hashMap.put(new A03Bean(32), 7);        hashMap.put(new A03Bean(36), 8);        hashMap.put(new A03Bean(40), 9);        hashMap.put(new A03Bean(44), 10);                System.out.println("hashMap.size = " + hashMap.size());                //查看是否所有对象都放到HashMap中了：        for(A03Bean key : hashMap.keySet()) {            System.out.println(key.number);        }    }}
     

　　3.debug，断点查看当同一个桶上的链表的长度达到多长时会做“链表转红黑树”的操作。

　　　　断点打在HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法的“treeifyBin(tab, hash);”这里。

　　4.测试结果：

　　　　当put进第9个元素（hashMap.put(new A03Bean(36), 8);）时，HashMap做了链表转红黑树的操作。

　　　　也就是说：当链表已经有8个元素了，此时put进第9个元素，先完成第9个元素的put，然后立刻做链表转红黑树。这个结论和第2点中得到的结论一致。

　　　　最后的输出结果也证明了所有的元素都成功put进了集合中，hashMap.size等于11。

　　到这里，有关“HashMap的链表转红黑树的具体时机”算是解释清楚了，有时间再探究“HashMap的红黑树转回链表的具体时机”。