面试必问: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的时间了。


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



相关文章
|
27天前
|
消息中间件 存储 缓存
大厂面试高频:Kafka 工作原理 ( 详细图解 )
本文详细解析了 Kafka 的核心架构和实现原理,消息中间件是亿级互联网架构的基石,大厂面试高频,非常重要,建议收藏。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:Kafka 工作原理 ( 详细图解 )
|
20天前
HashMap原理
1.HashMap在Jdk1.8以后是基于数组+链表+红黑树来实现的,特点是,key不能重复,可以为null,线程不安全 2.HashMap的扩容机制: HashMap的默认容量为16,默认的负载因子为0.75,当HashMap中元素个数超过容量乘以负载因子的个数时,就创建一个大小为前一次两倍的新数组,再将原来数组中的数据复制到新数组中。当数组长度到达64且链表长度大于8时,链表转为红黑树
27 2
|
22天前
|
架构师 数据库
大厂面试高频:数据库乐观锁的实现原理、以及应用场景
数据库乐观锁是必知必会的技术栈,也是大厂面试高频,十分重要,本文解析数据库乐观锁。关注【mikechen的互联网架构】,10年+BAT架构经验分享。
大厂面试高频:数据库乐观锁的实现原理、以及应用场景
|
27天前
|
存储 缓存 安全
大厂面试高频:ConcurrentHashMap 的实现原理( 超详细 )
本文详细解析ConcurrentHashMap的实现原理,大厂高频面试,必知必备。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:ConcurrentHashMap 的实现原理( 超详细 )
|
29天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
29天前
|
存储 安全 Java
面试高频:Synchronized 原理,建议收藏备用 !
本文详解Synchronized原理,包括其作用、使用方式、底层实现及锁升级机制。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
面试高频:Synchronized 原理,建议收藏备用 !
|
2月前
|
存储 算法 安全
HashMap的实现原理,看这篇就够了
关注【mikechen的互联网架构】,10年+BAT架构经验分享。深入解析HashMap,涵盖数据结构、核心成员、哈希函数、冲突处理及性能优化等9大要点。欢迎交流探讨。
HashMap的实现原理,看这篇就够了
|
25天前
|
SQL 存储 Oracle
大厂面试高频:聊下分库分表与读写分离的实现原理
本文详解了分库分表和读写分离的原理与实现,帮助解决大数据量下的性能瓶颈问题,大厂面试高频,建议收藏。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:聊下分库分表与读写分离的实现原理
|
28天前
|
存储 缓存 Java
大厂面试高频:Volatile 的实现原理 ( 图文详解 )
本文详解Volatile的实现原理(大厂面试高频,建议收藏),涵盖Java内存模型、可见性和有序性,以及Volatile的工作机制和源码案例。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:Volatile 的实现原理 ( 图文详解 )
|
2月前
|
存储 监控 算法
美团面试:说说 G1垃圾回收 底层原理?说说你 JVM 调优的过程 ?
尼恩提示: G1垃圾回收 原理非常重要, 是面试的重点, 大家一定要好好掌握
美团面试:说说 G1垃圾回收 底层原理?说说你 JVM 调优的过程  ?