当前位置:首页 > Java技术 > java集合:HashMap的底层实现原理

java集合:HashMap的底层实现原理

2022年08月05日 22:28:16Java技术4

        HashMap的底层实现原理是面试中出现频率非常高的一道面试题,本文将对HashMap的底层实现原理做一个简要的概况和总结,便于复习。

一、对于Map集合存储结构的理解

首先介绍以HashMap为典型代表的Map集合的存储结构

① Map中的key:无序的、不可重复的,底层使用Set集合存储key;key所在的类要重写equals()和hashCode() 。

② Map中的value:无序的、可重复的,底层使用Collection集合存储value;value所在的类要重写equals() 。

③ Map中的entry:无序的、不可重复的,底层使用Set集合存储entry,每个entry都相当于一组

key-value 。

二、HashMap的常用方法

如果想要使用HashMap,我们需要对HashMap的常用方法有一个基本的了解:

* 添加:put(Object key,Object value)
* 删除:remove(Object key)
* 修改:put(Object key,Object value)
* 查询:get(Object key)
* 长度:size()
* 遍历:keySet() / values() / entrySet()

三、HashMap的内存结构说明

① HashMap在jdk7中的实现原理

HashMap对象在实例化后,底层创建了一个长度为16的一维数组 Entry[ ] table

当执行方法 put(key1,value1) 添加数据时,HashMap底层的实现原理如下(此前可能已经执行过多次put()方法):

首先,调用key1所在类的hashCode()计算key1的哈希值,此哈希值经过底层算法的计算以后,可以得到在Entry数组中的存放位置,接下来又分为三种情况。

情况1:如果此位置上的数据为空,此时的key1-value1添加成功。

情况2:如果此位置上数据不为空(意味着此位置上存在一个或多个数据(多个数据以链表的形式存在)),则比较key1和已经存在的数据的哈希值,如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功,即key1-value1和原来的数据会以链表的形式存储。

情况3:与情况二类似,在比较key1和已经存在的数据的哈希值时,如果key1的哈希值和某个已经存在的数据(如key2-value2)的哈希值相同,则调用key1所在类的equals()方法,返回key1和key2的比较结果,如果返回的是false,此时key1-value1添加成功,同样也是和原来的数据以链表的形式存储;如果返回的是true,则会使用value1替换value2。

在不断添加数据的过程中,会涉及到数组的扩容问题。当添加数据超出临界值(且数据要存放的位置非空)时,需要对数组扩容。默认的扩容方式:扩容为原来容量的2倍,并将原来的数据复制过来。

② HashMap在jdk8中相较于jdk7在底层实现方面的不同

(1). 使用空参构造器创建HashMap对象时,底层没有直接创建一个长度为16的数组。
(2). jdk8底层存储数据的数组使用的是Node[ ],而不是Entry[ ] 。
(3). jdk8在首次调用put()方法时,底层才会创建长度为16的数组。
(4). jdk7中底层存储数据的结构是:数组+链表。jdk8中底层存储数据的结构是:数组+链表+红黑树。
(5).当存储数据形成链表时,链表的结构不相同,jdk7的链表结构是:新的数据指向旧的数据。jdk8的链表结构是:旧的数据指向新的数据。
(6).当底层数组的某一个索引位置上的元素以链表形式存在的数据个数大于8 ,且当前数组的长度大于64时,此时这个索引位置上的数据改为使用红黑树存储。

四、HashMap底层重要属性的说明

DEFAULT_INITIAL_CAPACITY:HashMap的默认容量:16
DEFAULT_LOAD_FACTOR:HashMap的默认加载因子:0.75
threshold:扩容的临界值 = 容量 * 填充因子:16 * 0.75 = 12
TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树:8
MIN_TREEIFY_CAPACITY:Bucket中Node被转化为红黑树时最小的Hash表容量:64

作者:白白甜甜冰
来源链接:https://blog.csdn.net/weixin_48016395/article/details/123007398

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/17955.html

标签: Java集合Java
分享给朋友:

“java集合:HashMap的底层实现原理” 的相关文章

深入理解 Java 并发锁

深入理解 Java 并发锁

📦 本文以及示例源码已归档在 javacore 一、并发锁简介 确保线程安全最常见的做法是利用锁机制(Lock、sychronized)来对共享数据做互斥同步,这样在同一个时刻,只有一个线程可以执行某个方法或者某个代码块,那么操作必然是原子性的,线程安全的...

Java 并发核心机制

Java 并发核心机制

📦 本文以及示例源码已归档在 javacore 一、J.U.C 简介 Java 的 java.util.concurrent 包(简称 J.U.C)中提供了大量并发工具类,是 Java 并发能力的主要体现(注意,不是全部,有部分并发能力的支持在其他包中)。...

Java 内存模型

Java 内存模型

📦 本文以及示例源码已归档在 javacore Java 内存模型(Java Memory Model),简称 JMM。 JVM 中试图定义一种 JMM 来屏蔽各种硬件和操作系统的内存访问差异,以实现让 Java 程序在各种平台下都能达到一致的内存访问效果。...

Java 日志框架详解

Java 日志框架详解

1. JUL学习 JUL全称Java util Logging是java原生的日志框架,使用时不需要另外引用第三方类库,相对其他日志框 架使用方便,学习简单,能够在小型应用中灵活使用。 1.1 架构介绍 Loggers...

java之整数的分解可以理解为倒序输出

Scanner in=new Scanner(System.in); int number ; number=in.nextInt(); int result=0; do{ int diget=number%10;...

Java实现1到n的倒数的累加和

Java实现1到n的倒数的累加和

从键盘读入一个数,然后进行运算 实现代码: public static void main(String[] args) { Scanner in=new Scanner(System.in); int n ; n=in....

Java开发手册精华总结

Java开发手册精华总结

阿里 Java 开发手册的思考总结 一个优秀的工程师和一个普通的工程师的区别,不是满天飞的架构图,他的功底体现在所写的每一行代码上。 -- 毕玄 1. 命名风格 【书摘】类名用 UpperCamelCase 风格,比如 DO/BO/VO...

Java Web 工作技巧总结 16.8

Java Web 工作技巧总结 16.8

摘要: 原创出处:www.bysocket.com 泥瓦匠BYSocket 希望转载,保留摘要,谢谢! 四时不谢之兰,百节长青之竹,万古不败之石,千秋不变之人。 1. AOP – LOG 项目中,一个请求过来,一个响应回去。...

JAVA UUID 生成唯一标识

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket Reprint it anywhere u want 需求     项目在设计表的时候,要处理并发多...

初探设计:Java继承何时用?怎么用?

初探设计:Java继承何时用?怎么用?

Writer      :BYSocket(泥沙砖瓦浆木匠) 一、回顾继承 常见的如下: 1、依赖(”uses-a“) 2、聚合(”has-a“) 3、继承(”is-a“)类...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。