所以,在当前的案例中,数组下标为 32 的位置下挂的不应该是一个链表,而是一颗红黑树。
对不对?
这是不对的。链表转红黑树的阈值是节点大于 8 个,而不是等于 8 的时候。
也就是说需要再来一个经过 hash 计算后,下标为 32 的、且 value 和之前的 value 都不一样的 key 的时候,才会触发树化操作。
不信,我给你看看现在是一个什么节点:
没有骗你吧?从上面的图片可以清楚的看到,第 8 个节点还是一个普通的 node。
而如果是树化节点,它应该是长这样的:
不信,我们再多搞一个 hash 冲突进来,带你亲眼看一下,代码是不会骗人的。
那么怎么多搞一个冲突出来呢?
最简单的,这样写:
这样冲突不就多一个了吗?我真是一个天才,情不自禁的给自己鼓起掌来。
好了,我们看一下现在的节点状态是怎么样的:
怎么样,是不是变成了 TreeNode ,没有骗你吧?
另外,我还想多说一句,关于一个 HashMap 的面试题的一个坑。
面试官问:JDK 8 的 HashMap 链表转红黑树的条件是什么?
绝大部分背过面试八股文的朋友肯定能答上来:当链表长度大于 8 的时候。
这个回答正确吗?
是正确的,但是只正确了一半。
还有一个条件是数组长度大于 64 的时候才会转红黑树。
源码里面写的很清楚,数组长度小于 64,直接扩容,而不是转红黑树:
感觉很多人都忽略了“数组长度大于 64 ”这个条件。
背八股文,还是得背全了。
比如下面这种测试用例:
它们都会落到数组下标为 0 的位置上。
当第 9 个元素 BBBBAa 落进来的时候,会走到 treeifyBin 方法中去,但是不会触发树化操作,只会进行扩容操作。
因为当前长度为默认长度,即 16。不满足转红黑树条件。
所以,从下面的截图,我们可以看到,标号为 ① 的地方,数组长度变成了 32,链表长度变成了 9 ,但是节点还是普通 node:
怎么样,有点意思吧,我觉得这样学 HashMap 有趣多了。