快来,我悄悄的给你说几个HashCode的破事。 (3)

简介: 快来,我悄悄的给你说几个HashCode的破事。 (3)

image.png


所以,在当前的案例中,数组下标为 32 的位置下挂的不应该是一个链表,而是一颗红黑树。


对不对?


image.png


这是不对的。链表转红黑树的阈值是节点大于 8 个,而不是等于 8 的时候。


也就是说需要再来一个经过 hash 计算后,下标为 32 的、且 value 和之前的 value 都不一样的 key 的时候,才会触发树化操作。


不信,我给你看看现在是一个什么节点:


image.png


没有骗你吧?从上面的图片可以清楚的看到,第 8 个节点还是一个普通的 node。


而如果是树化节点,它应该是长这样的:


image.png


不信,我们再多搞一个 hash 冲突进来,带你亲眼看一下,代码是不会骗人的。


那么怎么多搞一个冲突出来呢?


最简单的,这样写:


image.png


这样冲突不就多一个了吗?我真是一个天才,情不自禁的给自己鼓起掌来。


好了,我们看一下现在的节点状态是怎么样的:


怎么样,是不是变成了 TreeNode ,没有骗你吧?


image.png


另外,我还想多说一句,关于一个 HashMap 的面试题的一个坑。


面试官问:JDK 8 的 HashMap 链表转红黑树的条件是什么?


绝大部分背过面试八股文的朋友肯定能答上来:当链表长度大于 8 的时候。


这个回答正确吗?


是正确的,但是只正确了一半。



还有一个条件是数组长度大于 64 的时候才会转红黑树。


源码里面写的很清楚,数组长度小于 64,直接扩容,而不是转红黑树:


image.png


感觉很多人都忽略了“数组长度大于 64 ”这个条件。


背八股文,还是得背全了。


比如下面这种测试用例:


image.png


它们都会落到数组下标为 0 的位置上。


当第 9 个元素 BBBBAa 落进来的时候,会走到 treeifyBin 方法中去,但是不会触发树化操作,只会进行扩容操作。


因为当前长度为默认长度,即 16。不满足转红黑树条件。


所以,从下面的截图,我们可以看到,标号为 ① 的地方,数组长度变成了 32,链表长度变成了 9 ,但是节点还是普通 node:


image.png


怎么样,有点意思吧,我觉得这样学 HashMap 有趣多了。


image.png

目录
相关文章
|
9月前
|
存储 人工智能 JavaScript
编织魔法与修电脑:码农征途的奇妙起点
编织魔法与修电脑:码农征途的奇妙起点
94 0
|
存储 编译器 C++
【C++从0到王者】第三十五站:面试官让手撕红黑树,我直接向他秀一手手撕map与set
【C++从0到王者】第三十五站:面试官让手撕红黑树,我直接向他秀一手手撕map与set
97 0
|
9月前
|
机器人 程序员 C++
Scratch3.0——助力新进程序员理解程序(案例一十一、大象吃苹果)
Scratch3.0——助力新进程序员理解程序(案例一十一、大象吃苹果)
55 0
|
存储 人机交互 API
8个SwiftUI的小技巧让隔壁同事两眼放光,直呼太卷了
在日常的SwiftUI开发过程中,常常会出现一些“小BUG”让我们措手不及、头顶发凉。这些问题可能是由于我们自己不熟悉SwiftUI语法导致的,也有是SwiftUI本身自带的缺陷,毕竟是一个新兴语言。 那么本章就介绍一些SwiftUI开发的小技巧,帮助我们避避那些让我们头秃的坑。
1235 0
8个SwiftUI的小技巧让隔壁同事两眼放光,直呼太卷了
|
前端开发
#yyds干货盘点# 前端歌谣的刷题之路-第一百一十五题-根据包名 在指定空间中创建对象
#yyds干货盘点# 前端歌谣的刷题之路-第一百一十五题-根据包名 在指定空间中创建对象
58 0
#yyds干货盘点# 前端歌谣的刷题之路-第一百一十五题-根据包名 在指定空间中创建对象
|
安全 Java
快来,我悄悄的给你说几个HashCode的破事。 (2)
快来,我悄悄的给你说几个HashCode的破事。 (2)
151 1
快来,我悄悄的给你说几个HashCode的破事。 (2)
|
测试技术
快来,我悄悄的给你说几个HashCode的破事。 (4)
快来,我悄悄的给你说几个HashCode的破事。 (4)
108 0
快来,我悄悄的给你说几个HashCode的破事。 (4)
|
算法 Java
快来,我悄悄的给你说几个HashCode的破事。 (1)
快来,我悄悄的给你说几个HashCode的破事。 (1)
135 0
快来,我悄悄的给你说几个HashCode的破事。 (1)
|
Java
快来,我悄悄的给你说几个HashCode的破事。 (5)
快来,我悄悄的给你说几个HashCode的破事。 (5)
121 0
快来,我悄悄的给你说几个HashCode的破事。 (5)
|
SQL 安全 前端开发
来来来开小灶了,年后求职和跳槽的看过来,悄悄的看悄悄的收藏
面试官,您好我叫(XXX),今天来公司面试 JAVA开发工程师,之前在(XXX 公司)任职,从事这一行已经有(几)个年头了。这几年开发,主要接触的项目包括(你做过的项目!)等。在开发过程中,也用过好些框架,比如∶ springboot、springcloud、springmvc、spring、Mybatis等技术框架。熟练掌握框架之间的整合技术。有时候因为项目需求或是为了开发的高效性,自己我会研究一些技术,使用一些常用的主流 Java技术,例如∶(吹!用没用过不重要,主要是就是英文的!)。前端的技术也研究过一些。如(原生的、框架啊都往上整!)
219 0
来来来开小灶了,年后求职和跳槽的看过来,悄悄的看悄悄的收藏