天下无难试之HashMap面试刁难大全

2023-11-28 02:32

本文主要是介绍天下无难试之HashMap面试刁难大全,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

0?wx_fmt=jpeg

HashMap的结构无疑是Java面试中出现频率最高的一道题,这个题是如此之常见,应该每个人都会信手拈来。可是就在我经历过的无数【允许我夸张一下】面试当中,能完整回答我提出的HashMap问题的人却是寥寥无几,如今这道题我已经问的有点厌烦了。

HashMap的结构是怎样的?

二维结构,第一维是数组,第二维是链表

Get方法的流程是怎样的?

先调用Key的hashcode方法拿到对象的hash值,然后用hash值对第一维数组的长度进行取模,得到数组的下标。这个数组下标所在的元素就是第二维链表的表头。然后遍历这个链表,使用Key的equals同链表元素进行比较,匹配成功即返回链表元素里存放的值。

Get方法的时间复杂度是多少?

小伙伴们在回答这道题是有很多人会开始怀疑人生,他们的脑细胞这个时候会出现短路现象。明明是O(1)啊,平时都记得牢牢的,可是刚才Get方法的流程里需要遍历链表,遍历的时间复杂度难道不是O(n)么?此刻观察这些孩子们的表情是非常卡哇伊呢的。当然还有些甚至是科班的小伙伴居然没听过时间复杂度,想到这里我也开始怀疑人生了。当他们卡壳的时候,我会稍微提醒一下,问下面的这一道题。

假如HashMap里的元素有100w个,请问第二维链表的长度大概是多少?

嗦嘎!链表的长度很短,相比总元素的个数可以忽略不计。这个时候小伙伴们的眼睛通常会开始发光,很童贞。作为面试官是很喜欢看到这种眼神的。我使用反射统计过HashMap里面链表的长度,在HashMap里放了100w个随机字符串键值对,发现链表的长度几乎从来没有超过7这个数字,当我增大loadFactor的时候,才会偶尔冒出几个长度为8的链表来。于是问题又来了。

既然链表如此短,为啥Java8要对HashMap的链表进行改造,使用红黑树来代替链表呢?

有很多同学都没具体去深入关注Java8的新特性,如果他们回答不上来,我也不会感到失望。因为到这个问题的时候,已经只剩下15%的同学不到了,如果再打击他们,看着他们落寞的身影走出了大门,我都要对自己感到失望了,怎么招个人就如此困难?

这道题的关键在于如果Key的hashcode不是随机的,而是人为特殊构造的话,那么第二维链表可能会无比的长,而且分布极为不均匀,这个时候就会出现性能问题。比如我们把对象的hashcode都统一返回一个常量,最终的结果就是hashmap会退化为一维链表,Get方法的性能巨降为O(n),使用红黑树可以将性能提升到O(log(n))。

0?wx_fmt=jpeg

请解释一下HashMap的参数loadFactor,它的作用是什么?

loadFactor表示HashMap的拥挤程度,影响hash操作到同一个数组位置的概率。默认loadFactor等于0.75,当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,在HashMap的构造器中可以定制loadFactor。

请说明一下HashMap扩容的过程

扩容需要重新分配一个新数组,新数组是老数组的2倍长,然后遍历整个老结构,把所有的元素挨个重新hash分配到新结构中去。这个rehash的过程是很耗时的,特别是HashMap很大的时候,会导致程序卡顿,而2倍内存的关系还会导致内存瞬间溢出,实际上是3倍内存,因为老结构的内存在rehash结束之前还不能立即回收。那为什么不能在HashMap比较大的时候扩容扩少一点呢,关于这个问题我也没有非常满意的答案,我只知道hash的取模操作使用的是按位操作,按位操作需要限制数组的长度必须是2的指数。另外就是Java堆内存底层用的是tcmalloc这类library,它们在内存管理的分配单位就是以2的指数的单位,2倍内存的递增有助于减少内存碎片,减少内存管理的负担。

HashMap是线程安全的么?

当然不是,线程安全的HashMap是ConcurrentHashMap。关于ConcurrentHashMap还可以问很多问题,这就需要另一篇文章来具体讲解了。

你了解Redis么,你知道Redis里面的字典是如何扩容的么?

好,如果这道题你也回答正确了,恭喜你,毫无无疑,你是一位很有钱途的高级程序员。

你了解Python么,你知道Python里面字典的结构是怎样的么?

这个就属于附加题了,如果这道题你也回答对了,那我的眼睛就要发射紫外线了。

0?wx_fmt=jpeg

这篇关于天下无难试之HashMap面试刁难大全的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/428920

相关文章

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

数据库面试必备之MySQL中的乐观锁与悲观锁

《数据库面试必备之MySQL中的乐观锁与悲观锁》:本文主要介绍数据库面试必备之MySQL中乐观锁与悲观锁的相关资料,乐观锁适用于读多写少的场景,通过版本号检查避免冲突,而悲观锁适用于写多读少且对数... 目录一、引言二、乐观锁(一)原理(二)应用场景(三)示例代码三、悲观锁(一)原理(二)应用场景(三)示例

Oracle数据库常见字段类型大全以及超详细解析

《Oracle数据库常见字段类型大全以及超详细解析》在Oracle数据库中查询特定表的字段个数通常需要使用SQL语句来完成,:本文主要介绍Oracle数据库常见字段类型大全以及超详细解析,文中通过... 目录前言一、字符类型(Character)1、CHAR:定长字符数据类型2、VARCHAR2:变长字符数

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Linux文件名修改方法大全

《Linux文件名修改方法大全》在Linux系统中,文件名修改是一个常见且重要的操作,文件名修改可以更好地管理文件和文件夹,使其更具可读性和有序性,本文将介绍三种在Linux系统下常用的文件名修改方法... 目录一、引言二、使用mv命令修改文件名三、使用rename命令修改文件名四、mv命令和rename命

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes(有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes?Kubernetes常用命令总

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象。) Ø  OID检索(按照对象的OID来检索对象。) Ø  HQL检索(使用面向对象的HQL查询语言。) Ø  QBC检索(使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线) Ø  本地SQL检索(使用本地数据库的SQL查询语句。) 包括Hibern