-
HashMap
是在JDK1.2中引入的一种K/V对
形式的集合类. - 在底层,
HashMap
通过 数组和单链表 组合的结构形式来存储数据,数组在这作为一个外部结构,数组中的每个节点被称做Bucket(桶)
,而 桶是由在单链表构成 ,JDK1.8
之后 为了解决长链表下,查询和插入效率低下的情况,又引入了红黑树的作为桶的实现方式 , - 桶中的各节点是由
HashMap
定义的Node
内部类生成的,是普通的链表节点类.
- 注意:
HashMap
是线程不安全的,多线程情况下可能会出现环路(后面会讲) ,多线程状态下还是使用ConcurrentHashMap
比较合适.
重点参数
-
HashMap
的参数不多,除去当做默认属性的静态常量和底层数组对象,就只有以下五个
transient Node<K,V>[] table; transient int size transient int modCount; int threshold; final float loadFactor; 复制代码
-
table
就是整个HashMap
的底层数组,table
的初始化并不在构造函数中完成,而是在resize()
方法中完成.-
table
的初始化可能有点绕,构造函数中最多指定了阈值threshold
和负载因子loadFactor
并没有容量相关,但是在resize()
方法中 会根据旧容量和旧阈值判断新容量是等于默认容量,旧阈值或者两倍旧容量 ,最后根据新容量创建新数组
-
-
loadFactor
就是所谓的负载因子,默认为0.75,是控制扩容时机的关键属性,因为扩容发生在当前元素个数超过阈值时,而阈值等于当前容量乘以负载因子. -
modCount
为修改计数,是fast-fail
机制的关键参数.在对Map
中的元素做新增/删除操作时会自增,但修改不会(putVal()方法中覆盖原值)
新增逻辑
-
HashMap
的新增过程重点主要还是定位, 如何确定元素在数组中的位置 ,HashMap
采用的就是 Hash算法- 首先
HashMap
会根据Key
的hash值,按照表达式(n - 1) & hash
计算出桶的下标 - 如果此时桶为空,会创建一个新的
Node
,作为链表的第一个元素,直接存放在数组中.(以前还听说过什么链表首节点为空的情况,是假的.) - 如果节点存在又会区分树节点(TreeNode)和普通节点(Node)两种情况.
TreeNode
- 首先
- 另外 新增前会判断底层数组
table
是否初始化,新增后会判断该桶大小是否超过的8,超过则转化为红黑树,再判断整个数组是否需要扩容. -
Hash
同时也叫散列,可以把任意长度的输入通过算法,换算成固定长度的输出,不同元素通过Hash
算法获得的下标一致可以被称之为冲突或者碰撞
,Hash
算法的要求就是使元素尽量少的发生碰撞,从而均匀的散布在数组中
.而发生碰撞时,像HashMap
这种以一个列表下挂的方式可以被称为拉链法
.
查找逻辑
- 此处的查找逻辑是指调用
get()
方法,通过key
值查找的情况,如果自己遍历的另说.- 同样是根据表达式
(n - 1) & hash
计算出桶的下标(可以说是相当重要了),若得到的桶为空,直接返回null - 不为空时则会遍历整个桶,并根据
key.equals(k)
判断是否相等 - 遍历的方法也会根据节点类型的不同而不同,但是区分节点前直接存放在数组中的头结点是要先进行判断的.感觉上性能影响不大吧
- 同样是根据表达式
- 从查找的过程可以看出,确定桶下标的计算不存在随机性,时间复杂度就为O(1),具体的性能体现在遍历这一块,链表查询的时间复杂度为O(n),所以链表越长遍历时间也就越长,插入和查找的效率也就越低.所以在
JDK1.8
之后引入的红黑树作为桶的另一种实现方法.当链表长度大于8
时,桶的实现会转化为红黑树
. -
HashMap
的性能很大一部分取决于Hash
算法.
RESIZE逻辑
-
通过插入和查找我们可以知道,在数组大小不变的情况下,**链表越长或者说树的高度越高性能都会降低,**所以此时很有必要通过扩容数组的方式,重新排列桶中元素,降低链表长度,减少树的高度.
-
首先,触发扩容的情况是
size > threshold
即元素个数大于阈值.整个扩容过程可以简单的拆分为以下几步:- 对数组进行扩充,一般情况下是 数组容量和阈值都变为原来的两倍 .
- 此间会有上限判断,容量最大为
1 << 30
也就是1的30次方.
- 此间会有上限判断,容量最大为
- 遍历旧数组,重新判断元素的位置并散布到新数组.
- 对数组进行扩充,一般情况下是 数组容量和阈值都变为原来的两倍 .
-
resize()
方法中重新散布元素的方法还是很有意思的除去单元素链表和红黑树(桶的容量在1~7之间)- 首先将新数组分为两部分
lo
和hi
(源码是loHead和hiHead,我猜时low和high,怎么这么缩写随意),lo
表示0到旧容量部分,hi
表示余下算是新加入的部分,并以此创建两个链表 - 根据表达式
e.hash & oldCap
判断元素是否分布在lo
部分,是就挂到lo
链表下面,否就挂到hi
链表下面. -
lo
链表挂到和旧数组相同位置的桶,而hi
则挂到下标为原下标 + 旧数组容量
的桶.- 此处的依据就是
e.hash & (oldCap - 1) + oldCap == e.hash & (oldCap << 1) -1
- 此处的依据就是
- 首先将新数组分为两部分
-
可以看出
resize()
方法会调整全部的元素散列情况,因此过于频繁的resize
会降低HashMap
的性能, 因此如果一开始可以大概知道所需要存放的元素个数时,尽量直接指定容量大小. -
JDK1.7
之前的resize()
方法在并发条件下可能会发生闭环问题,但在JDK1.8
之后不会在出现,但并不代表HashMap
可以在并发条件下使用了,小部分情况还是会出现数据丢失等问题. -
介绍
JDK1.8
之前的闭环问题详情的文章
以上所述就是小编给大家介绍的《HashMap实现原理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Docker实现原理之 - OverlayFS实现原理
- 微热山丘,探索 IoC、AOP 实现原理(二) AOP 实现原理
- 带你了解vue计算属性的实现原理以及vuex的实现原理
- Docker原理之 - CGroup实现原理
- AOP如何实现及实现原理
- webpack 实现 HMR 及其实现原理
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据结构与算法分析
[美]Mark Allen Weiss / 张怀勇 / 人民邮电出版社 / 2007年 / 49.00元
《数据结构与算法分析:C++描述(第3版)》是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科生的数据结构课程和研究生算法分析课程的教材。本科生的数据结构课......一起来看看 《数据结构与算法分析》 这本书的介绍吧!