推荐阅读：
47天时间，洒热血复习，我成功“挤进”了字节跳动（附Java面试题+学习笔记+算法刷题）zhuanlan.zhihu.com
图标
Java学习笔记、源码、面试题库、思维脑图领取，点击此文档shimo.im
图标
前言
提到HashMap，文章可谓是不计其数，“详解HashMap”啊，“HashMap源码解析”啊，“细说HashMap啊”，“胡说HashMap”啊....
image
再提到内部实现，稍有常识的同学估计张口就能说出个一二三来，哈希桶啊，链表加数组啊，1.8 之后链表过长会转为红黑树啊等等。但今天笔者想要带来的是，除了探究一下标题上的HashMap负载因子超过1会发生什么？ 还要看看我们耳熟能详的红黑树，它到底在多大数量级会出现？ 让我们一起测试一下！
回顾
测试之前，先回顾一下 Hashmap 都有哪些重要的元素？ 首当其冲重要的就是三个成员变量 capacity、loadFactor、threshold，其中 capacity 和 loadFactor 是可以从构造函数中传入的，通俗的来捋一波：
capacity : HashMap 中桶的数量, 总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。 关于这个属性，还让笔者想起昨天在脉脉上看的小段子，一个员工吐槽："在老板的代码里发现了new HashMap<> (3)这段代码"。刚刚笔者也说到初始容量必须是 2 的幂次方，但是写成 3，也不会报错，强大的 hashmap 都帮我们考虑好了，内部用了 tableSizeFor 这个方法，帮我们转换了一下：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
intput 3 | 4 | 5 | 8 ......
output 4 | 4 | 8 | 8
capacity 就是传入的 3，hashmap 拿到 3 并不会直接使用，经过 tableSizeFor 运算后会得到 2 的幂次方 4，所有你这里传 3 还是传 4，hashmap 都会优化为 4，脉脉上吐槽的员工估计是想嘲笑一下老板连基础知识都不扎实吧，我觉得老板是 Capacity 用不用减一记混了可能比较大吧，也不影响使用。言归正传..
loadFactor：负载因子，默认 0.75。也就是threshold是根据 capacity * loadfactor 算出来的，HashMap 会根据 threshold 的数值，来决定什么时候调整空间大小。 这个参数有点意思。首先默认 0.75，这个如果不深究倒是好解释，取了 0.5~1.0 的中间值嘛，但是如果我不按套路出牌设置为 2 ，HashMap会怎样呢？
image
动手看看效果
测试
上代码：
HashMap<String, String> testMap = new HashMap<>(2, 2);
testMap.put("test1", "val");
testMap.put("test2", "val");
testMap.put("test3", "val");
初始 capacity 给了 2，loadFactor 也给了 2，那么 threshold 即为 4，容量是 2 ，到 4 才扩容，但是我 put 了三个元素进去容量已经超了，并且还没有触发扩容，会发生什么？ 将断点打入 HashMap 的 putVal 方法，观察执行效果：
- 第一个元素 test1 进来，进入了两个分支：
if ((tab = table)i == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
首先桶是空的，进行初始化的 resize，根据构造函数的参数，初始化的容量只有 2，紧着这进入第二个分支，进行与运算计算出数组的索引，一看 “嗯这地方没人，我 new 一个放这”。
- 第二个元素进来，差不多同上，但是因为数组已经不是 null 了，所以没有进入第一个分支。
- 第三个元素进来，因为总长度只有 2，test3 根据 hash 方法计算后的值是 110250867，所以（2 - 1）& 110250867 的结果也只能是 1，key 为 test3 的元素就被追加到索引为 1 的元素后方。
也就是说，如果我们构造函数传入的 loadFactor 大于 1，HashMap 并不会报错而是像 hash 冲突一样，追加到计算出的索引后方，提前形成了链表，查找元素的时间复杂度也就高了起来。
关于转换为红黑树
紧接着来看看第二个疑问，到底多大数据量，会出现红黑树？ 首先 HashMap 有个重要的参数，就是TREEIFY_THRESHOLD 默认是 8，变量名很规范，一眼就能看出是干什么的，意如其名就是转为树的阈值，源码中的首次判断是否需要转为树，就是直接用的它：
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断是否转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
上面这段代码也是 putVal 中的一部分，通常负责为 hash 冲突的节点追加链表元素，-1 for 1st这句是源码里自带的，因为 binCount 是从 0 开始嘛，所以阈值减一，解释了一下。 就像代码表述的，到了阈值将会调用treeifyBin方法，那么 treeifyBin 就会直接进行红黑树转换吗？ NO! 我们看看方法实现的前三行：
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();
方法先校验了 hash 桶的数量，要是小于MIN_TREEIFY_CAPACITY的话，重新调整大小即可，默认值是 64，也就是说并不只是有TREEIFY_THRESHOLD一个参数的限制。 知道了从哪里转为红黑树，想要进行我们的测试，最简单暴力的方式就是将 treeifyBin 方法第二个分支打个断点。 我们将之前测试的构造函数删掉，采用默认的构造函数，写下测试代码：
HashMap<Integer, String> testMap = new HashMap<>();
int max = 1_000_00000;
for (int i = 0; i < max; i++) {
testMap.put(RandomUtil.randomInt(Integer.MAX_VALUE), "val");
}
简单暴力，随机一千万个 key，当第一次进入我们打的断点时，也就代表第一颗红黑树形成。点开 Idea 的 Evaluate 窗口，输入 this.size 就能看到当前 hashmap 的长度，我记录了十次第一个红黑树形成时的 size大小：
1\. 2696228
2\. 5685561
3\. 559996
4\. 2806127
5\. 没出现
6\. 6156770
7\. 768019
8\. 5577574
9\. 739868
10\. 8870967
十次下来大概平均三百万数量级左右，会出现第一颗红黑树，当然这不是一次非常严谨的测试，统计次数，测试数据的随机分布性，都有可能影响结果，但是这个结果也能体现两点：
- 红黑树没有想象中那么容易出现
- hashmap 很强大，将数值分布的很均匀。
结尾
两点测试就到这里，我们可以思考一下，既然数量级这么大才会出现红黑树，HashMap 还犯得着优化吗？笔者推测了一下，个人观点如下: HashMap 我们可以看到类 doc 的@since 注解是1.2，早在 jdk1.2 的时候 HashMap 就出现了，jdk1.2 是什么时间发布的呢，搜索可知是 1998 年！约 20 年前的电脑内存等配置和现在已经是今非昔比，现在的内存条件，已经可以操作比当年更大更长的对象了，当然也别忘了 JVM 也要进行调优。
image
所以，综合我的观点来看，HashMap 作为最常用的数据结构之一，进行优化的意义是非常大的！
作者：Vt
链接：https://juejin.im/post/5dcb53a8e51d45225371ad30
来源：掘金
网友评论