面试必问:HashMap 底层实现原理(二)

简介: HashMap是在面试中经常会问的一点,很多时候我们仅仅只是知道HashMap他是允许键值对都是Null,并且是非线程安全的,如果在多线程的环境下使用,是很容易出现问题的。 这是我们通常在面试中会说的,但是有时候问到底层的源码分析的时候,为什么允许为Null,为什么不安全,这些问题的时候,如果没有分析过源码的话,好像很难回答, 这样的话我们来研究一下这个源码。看看原因吧。

我们再看看构造方法

构造方法

29.png30.png31.png

在这源码中,loadFactor负载因子是一个非常重要的参数,因为他能够反映HashMap桶数组的使用情况, 这样的话,HashMap的时间复杂度就会出现不同的改变。


当这个负载因子属于低负载因子的时候,HashMap所能够容纳的键值对数量就是偏少的,扩容后,重新将键值对 存储在桶数组中,键与键之间产生的碰撞会下降,链表的长度也会随之变短。


但是如果增加负载因子当这个负载因子大于1的时候,HashMap所能够容纳的键值对就会变多,这样碰撞就会增加, 这样的话链表的长度也会增加,一般情况下负载因子我们都不会去修改。都是默认的0.75。

扩容机制

resize()这个方法就是重新计算容量的一个方法,我们看看源码:

32.png33.png34.png35.png

所以说在经过resize这个方法之后,元素的位置要么就是在原来的位置,要么就是在原来的位置移动2次幂的位置上。 源码上的注释也是可以翻译出来的


36.png所以说他的扩容其实很有意思,就有了三种不同的扩容方式了,


在HashMap刚初始化的时候,使用默认的构造初始化,会返回一个空的table,并且 thershold为0,因此第一次扩容的时候默认值就会是16. 同时再去计算thershold = DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY = 16*0.75 = 12.


如果说指定初始容量的初始HashMap的时候,那么这时候计算这个threshold的时候就变成了 threshold = DEFAULT_LOAD_FACTOR * threshold(当前的容量)


如果HashMap不是第一次扩容,已经扩容过了,那么每次table的容量

threshold也会变成原来的2倍。


之前看1.7的源码的时候,是没有这个红黑树的,而是在1.8 之后做了相应的优化。 使用的是2次幂的扩展(指长度扩为原来2倍)。 而且在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,这样子他就剩下了计算hash的时间了。


看完这个源码,翻译了一节节的英文,算是大致明白了一点源码内容了,有什么讨论的问题咱们可以一起讨论一下,感谢观看。



相关文章
|
15天前
|
存储 算法 安全
HashMap的实现原理,看这篇就够了
关注【mikechen的互联网架构】,10年+BAT架构经验分享。深入解析HashMap,涵盖数据结构、核心成员、哈希函数、冲突处理及性能优化等9大要点。欢迎交流探讨。
HashMap的实现原理,看这篇就够了
|
1天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
1天前
|
存储 安全 Java
面试高频:Synchronized 原理,建议收藏备用 !
本文详解Synchronized原理,包括其作用、使用方式、底层实现及锁升级机制。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
面试高频:Synchronized 原理,建议收藏备用 !
|
24天前
|
存储 监控 算法
美团面试:说说 G1垃圾回收 底层原理?说说你 JVM 调优的过程 ?
尼恩提示: G1垃圾回收 原理非常重要, 是面试的重点, 大家一定要好好掌握
美团面试:说说 G1垃圾回收 底层原理?说说你 JVM 调优的过程  ?
|
24天前
|
SQL 存储 关系型数据库
美团面试:binlog、redo log、undo log的底层原理是什么?它们分别实现ACID的哪个特性?
老架构师尼恩在其读者交流群中分享了关于 MySQL 中 redo log、undo log 和 binlog 的面试题及其答案。这些问题涵盖了事务的 ACID 特性、日志的一致性问题、SQL 语句的执行流程等。尼恩详细解释了这些日志的作用、所在架构层级、日志形式、缓存机制以及写文件方式等内容。他还提供了多个面试题的详细解答,帮助读者系统化地掌握这些知识点,提升面试表现。此外,尼恩还推荐了《尼恩Java面试宝典PDF》和其他技术圣经系列PDF,帮助读者进一步巩固知识,实现“offer自由”。
美团面试:binlog、redo log、undo log的底层原理是什么?它们分别实现ACID的哪个特性?
|
15天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
37 5
|
23天前
|
负载均衡 算法 Java
蚂蚁面试:Nacos、Sentinel了解吗?Springcloud 核心底层原理,你知道多少?
40岁老架构师尼恩分享了关于SpringCloud核心组件的底层原理,特别是针对蚂蚁集团面试中常见的面试题进行了详细解析。内容涵盖了Nacos注册中心的AP/CP模式、Distro和Raft分布式协议、Sentinel的高可用组件、负载均衡组件的实现原理等。尼恩强调了系统化学习的重要性,推荐了《尼恩Java面试宝典PDF》等资料,帮助读者更好地准备面试,提高技术实力,最终实现“offer自由”。更多技术资料和指导,可关注公众号【技术自由圈】获取。
蚂蚁面试:Nacos、Sentinel了解吗?Springcloud 核心底层原理,你知道多少?
|
23天前
|
SQL 关系型数据库 MySQL
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
尼恩,一位40岁的资深架构师,通过其丰富的经验和深厚的技術功底,为众多读者提供了宝贵的面试指导和技术分享。在他的读者交流群中,许多小伙伴获得了来自一线互联网企业的面试机会,并成功应对了诸如事务ACID特性实现、MVCC等相关面试题。尼恩特别整理了这些常见面试题的系统化解答,形成了《MVCC 学习圣经:一次穿透MYSQL MVCC》PDF文档,旨在帮助大家在面试中展示出扎实的技术功底,提高面试成功率。此外,他还编写了《尼恩Java面试宝典》等资料,涵盖了大量面试题和答案,帮助读者全面提升技术面试的表现。这些资料不仅内容详实,而且持续更新,是求职者备战技术面试的宝贵资源。
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
|
23天前
|
消息中间件 Java Linux
得物面试:什么是零复制?说说 零复制 底层原理?(吊打面试官)
尼恩,40岁老架构师,专注于技术分享与面试辅导。近期,尼恩的读者群中有小伙伴在面试一线互联网企业如得物、阿里、滴滴等时,遇到了关于零复制技术的重要问题。为此,尼恩系统化地整理了零复制的底层原理,包括RocketMQ和Kafka的零复制实现,以及DMA、mmap、sendfile等技术的应用。尼恩还计划推出一系列文章,深入探讨Netty、Kafka、RocketMQ等框架的零复制技术,帮助大家在面试中脱颖而出,顺利拿到高薪Offer。此外,尼恩还提供了《尼恩Java面试宝典》PDF等资源,助力大家提升技术水平。更多内容请关注尼恩的公众号【技术自由圈】。
得物面试:什么是零复制?说说 零复制 底层原理?(吊打面试官)
|
26天前
|
机器学习/深度学习 算法
让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)
`HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括: 1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。 2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。 3. 最终加 1,确保返回值为 2 的幂次方。 该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。
32 1