66.Java容器面试题:谈谈你对 HashMap 的理解

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 66.Java容器面试题:谈谈你对 HashMap 的理解

66.Java容器面试题:谈谈你对 HashMap 的理解


为了能够在面试回答中优雅而不失体面回答面试考点,该文章借鉴了不同平台对知识点的描述。

回答

HashMap 是一种存取高效但不保证有序的常用容器。它的数据结构为“数组+链表”,是解决哈希冲突的产物,也就是我们常说的链地址法。它实现了Map 接口采用K-V 键值对存储数据,并实现了浅拷贝和序列化。

HashMap 的默认初始大小为16,初始化大小必须为2的幂,最大大小为2的30次方。数组中存储的链表节点Entry 类实现于Map.Entry 接口,它实现了对节点的通用操作。

HashMap 的阈值默认为“容量*0.75f”,当存储节点数量超过该值,则对map 进行扩容处理。

HashMap 提供了4种构造方法,分别是默认构造方法;可以指定初始容量的构造方法;可以指定初始容量和阈值的构造方法以及基于一个Map 的构造方法。虽然是构造函数,但是真正的初始化都是在第一次添加操作里面实现的。

在第一次添加操作中,HashMap 会先判断存储数组有没有初始化,如果没有先进行初始化操作,初始化过程中会取比用户指定的容量大的最近的2 的幂次方数作为数组的初始容量,并更新扩容的阈值。

接着添加操作讲解。添加操作的执行流程为:

先判断有没有初始化

再判断传入的key 是否为空,为空保存在table[o] 位置

key 不为空就对key 进hash,hash 的结果再& 数组的长度就得到存储的位置

如果存储位置为空则创建节点,不为空就说明存在冲突

解决冲突HashMap 会先遍历链表,如果有相同的value 就更新旧值,否则构建节点添加到链表头

添加还要先判断存储的节点数量是否达到阈值,到达阈值要进行扩容

扩容扩2倍,是新建数组所以要先转移节点,转移时都重新计算存储位置,可能保持不变可能为旧容量+位置。

扩容结束后新插入的元素也得再hash 一遍才能插入。

获取节点的操作和添加差不多,也是

先判断是否为空,为空就在table[0] 去找值

不为空也是先hash,&数组长度计算下标位置

再遍历找相同的key 返回值

HashMap 的其他操作大同小异,再讲讲HashMap1.7 的问题还有1.7 和1.8 的差别。

HashMap 是一个并发不安全的容器,在迭代操作是采用的是fast-fail 机制;在并发添加操作中会出现丢失更新的问题;因为采用头插法在并发扩容时会产生环形链表的问题,导致CPU 到达100%,甚至宕机。

解决并发问题可以采用

Java 类库提供的Collections 工具包下的Collections.synchronizedMap()方法,返回一个线程安全的Map

或者使用并发包下的 ConcurrentHashMap,ConcurrentHashMap采用分段锁机制实现线程安全

使用HashTable (不推荐)

Hash1.7 和1.8 最大的不同在于1.8 采用了“数组+链表+红黑树”的数据结构,在链表长度超过8 时,把链表转化成红黑树来解决HashMap 因链表变长而查询变慢的问题;其次

在hash 取下标时将1.7 的9次扰动(5次按位与和4次位运算)改为2次(一次按位与和一次位运算)

1.7 的底层节点为Entry,1.8 为node ,但是本质一样,都是Map.Entry 的实现

还有就是在存取数据时添加了关于树结构的遍历更新与添加操作,并采用了尾插法来避免环形链表的产生

但是并发丢失更新的问题依然存在。

回答顺序:数据结构+继承结构+基本字段+构造方法+添加操作+扩容操作+获取操作+并发问题+与1.8的区别

考点分析

HashMap 作为最基本的容器,它本身的设计与1.7 1.8的差异性导致HashMap 成为面试中最最高频的考点。所以掌握HashMap 势在必行,但是想要在各种宽泛的回答中脱颖而出,就必须对hashMap 前因后果了然于胸。

考点一:为什么初始容量必须为2 的幂?为什么负载因子为0.75f?为什么要做那么多扰动处理?

这些问题都要围绕一个点来回答:减少哈希冲突。

(1)容量必须为2 的幂是为了增加取值的可能性。

2 的n次幂转化为二进制为1后面n个0,在计算下标的时候是hash&(length - 1),也就是&(n-1)个1:初始容量为4->100,length-1 -> 11。所有的二进制为都为1有什么好处?

0/1 & 1 都为它本身

0/1 & 0 都为 0

可以看出&1保证了取值的平均。如果某一位为0 ,比如最后一位,那么它&出来下标就一定是个偶数,减少了HashMap 数组一半的取值,大大增加了冲突的可能。

(2)负载因子为0.75f 是空间与时间的均衡

如果负载因子小,意味着阈值变小。比如容量为10 的HashMap,负载因子为0.5f,那么存储5个就会扩容到20,出现哈希冲突的可能性变小,但是空间利用率不高。适用于有足够内存并要求查询效率的场景。

相反如果阈值为1 ,那么容量为10,就必须存储10个元素才进行扩容,出现冲突的概率变大,极端情况下可能会从O(1)退化到O(n)。适用于内存敏感但不要求要求查询效率的场景

(3)hash() 的意义在于使hash 结果不同

hash 算法的好坏直接影响hash 结构的效率,坏的hash 算法极端情况下可能会使hash 结构的存取效率从O(1)退化到O(n)。1.8 之所以把9 次扰动降到2 次,是出于计算效率的考虑。

考点二:& 字符虽然和 % 效果一样,但是操作效率更高

考点三:为什么int,String 适合最为key?

int 和 String 的好处在于hash 出来的值不会改变。如果是一个对象,那么他们可能会因为内部引用的改变而hashCode 值的改变,会导致存储重复的数据或找不到数据的情况。

考点四:并发操作导致的添加丢失和环形链表的产生过程

知识点拓展

不仅仅是HashMap 的东西,根据你的回答,面试官会引出很多其他的问题,所以你在自己设计回答的过程中可以有意识引导面试官问出你熟悉的内容,安排的明明白白。

拓展一:解决Hash 冲突的不同方案

链地址法

开发地址:线性探测法、平方探测法

完全散列:布谷鸟散列

拓展二:HashMap 是浅拷贝,说一说浅拷贝和深拷贝的区别

拓展三:说一说Collections.synchronizedMap()和HashTable 的区别

拓展四:说一说HashMap 如何实现有序(LinkHashMap 和TreeMap)以及他们的差别

拓展五:说一说ConcurrentHashMap 如何实现线程安全

结尾

这篇文章更多的是HashMap 面试怎么答,以及需要注意的知识点,希望对你有所帮助。

目录
相关文章
|
1月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
83 2
|
30天前
|
Java 程序员
Java社招面试题:& 和 && 的区别,HR的套路险些让我翻车!
小米,29岁程序员,分享了一次面试经历,详细解析了Java中&和&&的区别及应用场景,展示了扎实的基础知识和良好的应变能力,最终成功获得Offer。
70 14
|
1月前
|
存储 缓存 算法
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
|
1月前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
1月前
|
Java 编译器 程序员
Java面试高频题:用最优解法算出2乘以8!
本文探讨了面试中一个看似简单的数学问题——如何高效计算2×8。从直接使用乘法、位运算优化、编译器优化、加法实现到大整数场景下的处理,全面解析了不同方法的原理和适用场景,帮助读者深入理解计算效率优化的重要性。
36 6
|
1月前
|
存储 安全 Java
Java多线程编程中的并发容器:深入解析与实战应用####
在本文中,我们将探讨Java多线程编程中的一个核心话题——并发容器。不同于传统单一线程环境下的数据结构,并发容器专为多线程场景设计,确保数据访问的线程安全性和高效性。我们将从基础概念出发,逐步深入到`java.util.concurrent`包下的核心并发容器实现,如`ConcurrentHashMap`、`CopyOnWriteArrayList`以及`BlockingQueue`等,通过实例代码演示其使用方法,并分析它们背后的设计原理与适用场景。无论你是Java并发编程的初学者还是希望深化理解的开发者,本文都将为你提供有价值的见解与实践指导。 --- ####
|
1月前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
74 4
|
1月前
|
存储 Java 程序员
Java基础的灵魂——Object类方法详解(社招面试不踩坑)
本文介绍了Java中`Object`类的几个重要方法,包括`toString`、`equals`、`hashCode`、`finalize`、`clone`、`getClass`、`notify`和`wait`。这些方法是面试中的常考点,掌握它们有助于理解Java对象的行为和实现多线程编程。作者通过具体示例和应用场景,详细解析了每个方法的作用和重写技巧,帮助读者更好地应对面试和技术开发。
135 4
|
2月前
|
Java
让星星⭐月亮告诉你,HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时,通过调整指针的方式将其移动至链表头部。具体步骤包括:从链表中移除根节点,更新根节点及其前后节点的指针,确保根节点成为新的头节点,并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现,确保了高效的数据访问与管理。
32 2
|
2月前
|
Java 索引
让星星⭐月亮告诉你,HashMap之往红黑树添加元素-putTreeVal方法源码解读
本文详细解析了Java `HashMap` 中 `putTreeVal` 方法的源码,该方法用于在红黑树中添加元素。当数组索引位置已存在红黑树类型的元素时,会调用此方法。具体步骤包括:从根节点开始遍历红黑树,找到合适位置插入新元素,调整节点指针,保持红黑树平衡,并确保根节点是链表头节点。通过源码解析,帮助读者深入理解 `HashMap` 的内部实现机制。
43 2