面向面试学习系列-HashMap源码

标签: Java  java  hashmap  链表  hash

正当你在会议室里坐立不安,不知道这次会遇到什么面试官。

一道光顺着门缝折射进来,亮瞎了你的钛合金狗眼。

面试官看着你浓郁的发量和正襟危坐的姿势,不禁唏嘘一声,怕又是一个水货。


面试官,你好,我是大帅比,你很客气的对着面试官打招呼,希望能有一个好印象

面试官淡淡看你一眼(默念浪费半小时),你好,请坐


那我们正式开始吧,你说说JDK1.8对HashMap有哪些比较大的改动吗,面试官平淡的说道。

  • JDB1.8采用数组+链表+红黑树结构,之前一直都是数组+链表的结构
  • 链表新节点采用尾插法,避免JDK1.7使用头插法出现的死循环,导致CPU用满
  • resize()扩容时优化不再需要重新hash计算

面试官轻轻的点了点头,那知道为什么要增加红黑树结构吗?

主要是为了防止极端情况下,hash冲突严重时的查询性能。

比如HashMap的容量为16,现在有10个数据且hash相同。

数组+链接结构 就会形成数组一个节点的单链表形式

链表查询的时间复杂度是o(n)

红黑树查询的时间复杂度为o(logn)

面试官偷偷撇了你一眼,那红黑树和链表是怎样互相转化的呢?
插入: 默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个(阈值8):

  • 如果此时数组长度大于等于 64,则会触发链表节点转红黑树节点(treeifyBin)。
  • 如果数组长度小于64,则不会触发链表转红黑树,而是会进行扩容,因为此时的数据量还比较小。

移除: 当同一个索引位置的节点在移除后达到 6 个,并且该索引位置的节点为红黑树节点,会触发红黑树节点转链表节点(untreeify)。

为什么阈值要设置为8呢?

因为这是一种时间和空间上的妥协:

  • 红黑树节点占用空间大小约为链表的两倍大小,当节点过小时,红黑树查询优势不大,用两倍的空间换取微小的查询速度并不划算,而且红黑树添加新的节点需要左旋和右旋,也浪费性能。
  • 根据HashMap源码注释,节点分布在 hash 桶中的频率遵循泊松分布,按照泊松分布的公式计算,链表中节点个数为8时的概率为 0.00000006,冲突概率很小,并且8节点时红黑树的优势比较明显。

面试官认真的看了你下,心想,小家伙懂得还挺多啊,加点料。

HashMap有哪些常用的属性和默认值吗?

重要属性

  1. size:HashMap 已经存储的节点个数;
  2. threshold:扩容阈值,当 HashMap 的个数达到该值,触发扩容。
  3. loadFactor:负载因子,扩容阈值 = 容量 * 负载因子

属性默认值:

  1. 默认初始容量为16
  2. 默认扩容因子是0.75
  3. 默认扩容倍数为2倍

按照你的说法扩容阈值是0.75,那么如果我设置初始容量为11,那11*0.75岂不是带有小数,这怎么计算,能详细说说吗?(看你怎么给自己填坑)

HashMap默认容量是16,并且容量必须为2的N次方。

当我们初始设置容量时,HashMap会通过tableSizeFor()方法将我们设置的值找一个最近的2的N次方作为容量。

例如我们设置初始容量为11,那经过计算就变成16了,阈值计算是threshold=16*0.75=12。

具体的代码计算就是下面的这个:

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;
}

面试官认真的看了下你,嘴角漏出欣慰的微笑,今天还有点惊喜啊。

为什么初始容量设置为0.75,有什么讲究吗?

这个也是在时间和空间上权衡的结果:

  • 如果值较高,数组得到充分的利用,但是hash 冲突的概率会增大,增加查找成本。

  • 如果值较低,hash 冲突会降低,但是有较多的数组空间会被浪费。当达到阈值就会扩容,导致较多的数组没有保存节点数据。

所以折衷考虑 0.75 似乎是一个合理的值。

说到扩容,JDK1.8HashMap扩容具体是怎么优化的,为什么不需要重新hash计算?

获取节点位置:

首先HashMap进行选取数组节点时使用(n-1)& hash获得节点位置

扩容前

例如 容量16 hash值为 0110

(n-1) & 10110

​    0  1 1 1 1
&   1  0 1 1 0
------
​    0 0 1 1 0

00110也就是第6位

扩容后:

此时我们扩容后容量是32位

(n-1) & 10110

​       1 1 1 1 1
&      1 0 1 1 0
------------------------------
​       1 0 1 1 0

10110 = 00110+10000 = 6+15=23

结果:

我们可以看出HashMap扩容后,位置是否改变取决于hash的高位是不是为1

判断方法:(e.hash & oldCap) == 0

  • 为真:高位是0
  • 为假:高位为1

计算位置:

  • 如果为1
    新位置 = 原位置+原容量
  • 如果为0
    新位置 = 原位置

今天就到这吧,小伙子,很高兴加入我们。

1、HashMap源码解读
u=3742199653,1935850630&fm=26&gp=0

版权声明:本文为happy_blockhead原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/happy_blockhead/article/details/109623149

智能推荐

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

猜你喜欢

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...

css:顶部按钮固定,上面内容滑动

这种需求我们平时见到很多的,实现方法也多的参差不齐,下面我说一种简单的。如图: 可以看到只有红线部分滚动,底下按钮是固定的。 代码...

环形公路堵车概率模型(含详细解析)

文章目录 基础理论 代码实现 图形分析 基础理论 路面上有n辆车,以不同的速度向前行驶, 模拟堵车问题。 有以下假设: 假设某辆车的当前速度是v。 若前方可见范围内没车,则它在下一秒的车速提高到v+1,直到达到规定的最高限速。 若前方有车,前车的距离为d,且d < v,则它下 一秒的车速降低到d-1 。 每辆车会以概率p随机减速v-1。、 代码实现 图形分析 图形中颜色越重的地方,说明很多车...