走读源码探究HashMap的树化时机以及红黑树的操作机制

系统管理员 2022-12-06 01:11 148阅读 0赞

通过两篇文章：[深入源码分析HashMap到底是怎样将元素put进去的][HashMap_put] 和 [HashMap扩容后，元素是如何重新分布的][HashMap]，我们逐一分析了HashMap的初始化和扩容机制，在末尾还留下了一个悬念，就是HashMap的树化，即什么时候转化成红黑树，以及怎么转成红黑树的没有深入探究，今天我们就来通过走读代码，一步一步走进HashMap的红黑树。

## 目的 ##

探究`Node`转化成`TreeNode`的时机以及`TreeNode`的操作机制

## 说明 ##

本次探究使用的jdk版本：1.8

## HashMap结构示意图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]

## 思路 ##

通过以往的两次分析，我们得知了元素在map中的位置主要取决于**元素本身的hash值**，只要多个元素同时落在同一个位置上，当它满足一定条件时，就会触发链表转化成红黑树的操作

那问题就变成了如何使众多的key的hash值相同呢，答案是重写`hashCode()`方法，有意让不同的key的hash值相同

为了让代码出现极端情况，我们将所有的数字类型的key的hash值都设为`1`，核心代码

@Override
            public int hashCode() { 
                if (key == null) { 
                    return 0;
                }
    
                Pattern pattern = Pattern.compile(REG);
                // 所有数字，hashCode全部给1，为了复现碰撞极高， 且更容易树化(超过8)
                if (pattern.matcher(key).matches()) { 
                    return 1;
                } else { 
                    // 非数字
                    return 2;
                }
            }

## 开始 ##

完整案例代码

package cn.com.suntree.utils.myself;
    
    import java.util.HashMap;
    import java.util.regex.Pattern;
    
    public class Demo { 
        public static void main(String[] args) { 
            HashMap<MapKey, String> map = new HashMap<MapKey, String>();
            //第一阶段， hashCode的值全为 1
            for (int i = 0; i < 7; i++) { 
                map.put(new MapKey(String.valueOf(i)), "A");
            }
    
            //第二阶段， hashCode的值全为 1
            for (int i = 0; i < 10; i++) { 
                map.put(new MapKey(String.valueOf(i)), "B");
            }
    
            //第三阶段， hashCode的值全为 1
            for (int i = 0; i < 50; i++) { 
                map.put(new MapKey(String.valueOf(i)), "C");
            }
    
            //第四阶段， hashCode的值全为 2
            map.put(new MapKey("Z"), "D");
            map.put(new MapKey("J"), "D");
            map.put(new MapKey("F"), "D");
    
            System.out.println(map);
        }
    
        /** * 重写了hashCode使得hashCode碰撞极高 */
        static class MapKey { 
            private static final String REG = "[0-9]+";
    
            private String key;
    
            public MapKey(String key) { 
                this.key = key;
            }
    
            @Override
            public boolean equals(Object o) { 
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
    
                MapKey mapKey = (MapKey) o;
    
                return !(key != null ? !key.equals(mapKey.key) : mapKey.key != null);
    
            }
    
            /* * 确保每次key的hashCode都相同 */
            @Override
            public int hashCode() { 
                if (key == null) { 
                    return 0;
                }
    
                Pattern pattern = Pattern.compile(REG);
                // 所有数字，hashCode全部给1，为了复现碰撞极高， 且更容易树化(超过8)
                if (pattern.matcher(key).matches()) { 
                    return 1;
                } else { 
                    // 非数字
                    return 2;
                }
            }
    
            @Override
            public String toString() { 
                return key;
            }
        }
    }

有了前两次的调试经验，有些过程这次我会跳过，即碰到次要的地方就`Step out`然后再`Force Step Into`，不多说，不会的请参考 [IDEA调试键的说明][IDEA]

先插入几条数据，看看是不是实现了hash值重复，即元素是不是落在同一个位置上

第0个元素落在`1`位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]  
第1个元素落在`1`位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 2]  
第2个元素也是必然落在`1`位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 3]  
其实除了看源码的赋值情况，我们看`Debug`控制台也能看出端倪，先对map选择`view as object`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 4]  
再对`key=1`选择`view as object`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 5]  
展开，就能看见结构了，`1`是指位置`1`，位置`1`处有两个元素，`0`的`next`是`1`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 6]  
我们再对`1`的`next`进行`view as object`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 7]  
会发现此时`1`的`next`为`null`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 8]  
仔细看看，还能发现不少东西，我们就不用一步一步调试了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 9]  
继续把底阶段的7个元素放进去，会发现确实是一个串着一个都在`1`号位

比较麻烦的是每一个`next`你都需要手动选择一下`view as object`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 10]  
然后我们进入第二阶段，我们预计插入10个元素，因为树化的临界值是`TREEIFY_THRESHOLD`=8  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 11]  
当然，根据我们昨天的调试结果可以预知前7个元素会被此次循环的前7次的新值代替，对比一下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 12]  
value全部由`A`变成了`B`，然后继续一路`Force Step Into`，碰到次要的地方就`Step out`然后再`Force Step Into`，不多说，不会的请参考 [IDEA调试键的说明][IDEA]

这里我们要重点看一下`putVal`里的`643`行，当将`8`连接到`7`的时候，`binCount = TREEIFY_THRESHOLD - 1`，触发了`treeifyBin`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 13]  
关键时刻来了，我们进去`treeifyBin`看看之前，记一下现在的状态值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 14]  
在进`treeifyBin`前，`size=8`、`table`的长度为16，就是map的容量，扩容阈值等于12，进去  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 15]  
告诉我们此时还不能树化，因为`tab.length < MIN_TREEIFY_CAPACITY`，这个  
![在这里插入图片描述][20200911165312385.png_pic_center]  
这个常量的意思是，如果你的table总容量小于64就不给你树化了，哪怕你一个单链的元素个数超过了8个，不树化，而是进行扩容。  
所以又多了一种扩容的场景，之前我们分析过两种扩容的场景

*  插入第一个元素时，初始扩容；
 *  当插入元素个数到达`threshold`扩容阈值时，扩容
 *  还有就是这，当某个位置元素**≥8**个时，即单链长度**≥8，且map容量小于64**，扩容

那就扩呗，昨天已经分析了扩容，不在赘述。

由于我们的特殊hash值，即使map容量从16扩成了32，元素还是在原来的位置，当再次插入元素时，上面的条件还将满足，还会再次扩容至64  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 16]  
继续插入元素，来到地三阶段，我们先将前面10个元素的`value`替换成`C`，当插到`10`号元素时，经过两轮扩容，终于来到了能深入的`treeifyBin`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 17]  
此刻`tab[1]`不为`null`，将执行`do……while`，下面这行代码的作用就是将平普通`Node`转换成`TreeNode`

TreeNode<K,V> p = replacementTreeNode(e, null);

## 待续…… ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70]

[HashMap_put]: https://blog.csdn.net/leisure_life/article/details/108482840
[HashMap]: https://blog.csdn.net/leisure_life/article/details/108489393
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/90e71e60287d429eba30504270520e4c.png
[IDEA]: https://blog.csdn.net/leisure_life/article/details/108483754
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d8f2bd9fd48f43cca64db0c2fd97d89c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f4bfb9cf3f98483498e02a9d79de9b29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/c944249e18d4487a947b969108edc45f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/c9c0c3dd07d846cb8cd99613f3822cbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/06ce1586e96e46ccabf9d0fbcea735c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/465b86ee564d4ced8abd9a4cc3181f63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/2fa4c0ae6aba4de4878d696ea44429a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/c29a3902b3d1445386379ee06b921118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/5559b51ad07d4c5ba845169a301deb6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/f884209602a143e99db752da0fe4c2f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/21f747cc3cea4456a1ecbfef0ef6b06a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/155a13260a6049b8ae7c2f6d05b2e1be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221123/12d18dad873146dab5b8c0922cbabb50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221123/d49c0ce1a0824230b0f5b56d530a74ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221123/bd99cef2ed4245c7a6d59c4221cc42e9.png
[20200911165312385.png_pic_center]: /images/20221123/def3159e7dd44397bf10cabc6a1865cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221123/740eb90c927d4116821a6861735b58fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221123/4bc898ed1e1a49659b0c2c8c3be401bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70]: /images/20221123/134615f2e1e844f69aee910640a81ebc.png