目的

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

说明

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

HashMap结构示意图

思路

通过以往的两次分析，我们得知了元素在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调试键的说明

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

第0个元素落在1位置

第1个元素落在1位置

第2个元素也是必然落在1位置

其实除了看源码的赋值情况，我们看Debug控制台也能看出端倪，先对map选择view as object
再对key=1选择view as object
展开，就能看见结构了，1是指位置1，位置1处有两个元素，0的next是1
我们再对1的next进行view as object
会发现此时1的next为null
仔细看看，还能发现不少东西，我们就不用一步一步调试了

继续把底阶段的7个元素放进去，会发现确实是一个串着一个都在1号位

比较麻烦的是每一个 next你都需要手动选择一下 view as object
然后我们进入第二阶段，我们预计插入10个元素，因为树化的临界值是 TREEIFY_THRESHOLD=8

当然，根据我们昨天的调试结果可以预知前7个元素会被此次循环的前7次的新值代替，对比一下

value全部由 A变成了 B，然后继续一路 Force Step Into，碰到次要的地方就 Step out然后再 Force Step Into，不多说，不会的请参考 IDEA调试键的说明。

这里我们要重点看一下putVal里的643行，当将8连接到7的时候，binCount = TREEIFY_THRESHOLD - 1，触发了treeifyBin
关键时刻来了，我们进去treeifyBin看看之前，记一下现在的状态值

在进treeifyBin前，size=8、table的长度为16，就是map的容量，扩容阈值等于12，进去

告诉我们此时还不能树化，因为tab.length < MIN_TREEIFY_CAPACITY，这个

这个常量的意思是，如果你的table总容量小于64就不给你树化了，哪怕你一个单链的元素个数超过了8个，不树化，而是进行扩容。
所以又多了一种扩容的场景，之前我们分析过两种扩容的场景

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

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

由于我们的特殊hash值，即使map容量从16扩成了32，元素还是在原来的位置，当再次插入元素时，上面的条件还将满足，还会再次扩容至64

继续插入元素，来到地三阶段，我们先将前面10个元素的value替换成C，当插到10号元素时，经过两轮扩容，终于来到了能深入的treeifyBin
此刻tab[1]不为null，将执行do……while，下面这行代码的作用就是将平普通Node转换成TreeNode

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

待续……