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

本文涉及的产品
容器服务 Serverless 版 ACK Serverless,952元额度 多规格
容器镜像服务 ACR,镜像仓库100个 不限时长
容器服务 Serverless 版 ACK Serverless,317元额度 多规格
简介: 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 面试怎么答,以及需要注意的知识点,希望对你有所帮助。

目录
相关文章
|
20天前
|
缓存 Java 关系型数据库
【Java面试题汇总】ElasticSearch篇(2023版)
倒排索引、MySQL和ES一致性、ES近实时、ES集群的节点、分片、搭建、脑裂、调优。
【Java面试题汇总】ElasticSearch篇(2023版)
|
12天前
|
设计模式 Java
结合HashMap与Java 8的Function和Optional消除ifelse判断
`shigen`是一位致力于记录成长、分享认知和留住感动的博客作者。本文通过具体代码示例探讨了如何优化业务代码中的if-else结构。首先展示了一个典型的if-else处理方法,并指出其弊端;然后引入了策略模式和工厂方法等优化方案,最终利用Java 8的Function和Optional特性简化代码。此外,还提到了其他几种消除if-else的方法,如switch-case、枚举行、SpringBoot的IOC等。一起跟随shigen的脚步,让每一天都有所不同!
28 10
结合HashMap与Java 8的Function和Optional消除ifelse判断
|
20天前
|
设计模式 Java 关系型数据库
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
本文是“Java学习路线”专栏的导航文章,目标是为Java初学者和初中高级工程师提供一套完整的Java学习路线。
174 37
|
1天前
|
存储 安全 Java
Java HashMap详解
`HashSet` 是 Java 中基于哈希表实现的 `Set` 接口集合,主要用于存储不重复元素,提供快速查找、插入和删除操作。它不允许重复元素,不保证元素顺序,但允许一个 `null` 元素。常用操作包括创建、添加、删除、检查元素及清空集合。由于其哈希表结构,`HashSet` 在插入、删除和查找操作上具有常数时间复杂度 O(1),性能高效。适用于需要快速访问和操作的场景,但需注意其无序性和线程安全问题。
|
20天前
|
设计模式 安全 算法
【Java面试题汇总】设计模式篇(2023版)
谈谈你对设计模式的理解、七大原则、单例模式、工厂模式、代理模式、模板模式、观察者模式、JDK中用到的设计模式、Spring中用到的设计模式
【Java面试题汇总】设计模式篇(2023版)
|
20天前
|
存储 关系型数据库 MySQL
【Java面试题汇总】MySQL数据库篇(2023版)
聚簇索引和非聚簇索引、索引的底层数据结构、B树和B+树、MySQL为什么不用红黑树而用B+树、数据库引擎有哪些、InnoDB的MVCC、乐观锁和悲观锁、ACID、事务隔离级别、MySQL主从同步、MySQL调优
【Java面试题汇总】MySQL数据库篇(2023版)
|
20天前
|
存储 缓存 NoSQL
【Java面试题汇总】Redis篇(2023版)
Redis的数据类型、zset底层实现、持久化策略、分布式锁、缓存穿透、击穿、雪崩的区别、双写一致性、主从同步机制、单线程架构、高可用、缓存淘汰策略、Redis事务是否满足ACID、如何排查Redis中的慢查询
【Java面试题汇总】Redis篇(2023版)
|
9天前
|
消息中间件 NoSQL Java
Java知识要点及面试题
该文档涵盖Java后端开发的关键知识点,包括Java基础、JVM、多线程、MySQL、Redis、Spring框架、Spring Cloud、Kafka及分布式系统设计。针对每个主题,文档列举了重要概念及面试常问问题,帮助读者全面掌握相关技术并准备面试。例如,Java基础部分涉及面向对象编程、数据类型、异常处理等;JVM部分则讲解内存结构、类加载机制及垃圾回收算法。此外,还介绍了多线程的生命周期、同步机制及线程池使用,数据库设计与优化,以及分布式系统中的微服务、RPC调用和负载均衡等。
|
3月前
|
SQL 安全 Java
Java面试题:什么是JDBC以及如何在Java中使用它进行数据库操作?
Java面试题:什么是JDBC以及如何在Java中使用它进行数据库操作?
40 0
|
3月前
|
druid Java 数据库连接
Java面试题:解释数据库连接池的概念及其作用,讨论常见的连接池实现。
Java面试题:解释数据库连接池的概念及其作用,讨论常见的连接池实现。
57 0
下一篇
无影云桌面