天下无难试之HashMap面试刁难大全
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))。
请解释一下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里面的字典是如何扩容的么?
好,如果这道题你也回答正确了,恭喜你,毫无无疑,你是一位很有钱途的高级程序员。
原文地址:https://www.jianshu.com/p/42135dbb943c
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
程序员刚写完代码,就被开除了,网友:你TM真是个天才
前几天在逛贴吧的时候,看到这样一个帖。一程序员说自己刚写完代码,就别公司老板给开除了。为什么会这样的呢? 原来是这位程序员写了一段这样的代码: public static Date getNextDay() { try { Thread.sleep(24*60*60*1000); } catch (InterruptrdException e) { e.printStackTrace(); } return new Date(); } 这段代码本意是想要获取下一天的日期的。结果这位程序员老哥写了个sleep函数,SLEEP的作用是延时,程序暂停若干时间,在执行时要抛出一个中断异常,必须对其进行捕获并处理才可以使用这个函数。 然后一群吧友纷纷进来吐槽。“你他娘的真实个天才,哈哈哈,你是怎么进的公司啊?” 也有人表示佩服,觉得很有想法“没毛病啊,睡一天不就是第二天了嘛”[捂脸] 看完这段代码,你们工作中有没有用过这样的思维做事呢? 欢迎在讨论交流。 程序员学习交流学习群:878249276,群里有分享的视频,面试指导,架构资料,还有思维导图、群里有视频,都是干货的,你可以下载来看。主要分享...
- 下一篇
如何开发自己的Spring Boot Starter
我们在使用 Spring Boot 的过程中,往往都是在pom.xml里加了一系列的依赖,然后启支一个包含main方法的Application,一切就OK啦。给你我的感觉,就像是自己要动手做个菜,自己不再需要准备每一部分的原材料,直接购买包装好的一份菜的原料,下锅即可。 那我们详细看下,这份「包装好」的原料中,到底做了些什么。 添加Starter依赖 这里添加的依赖,除了我们之前在Maven中熟悉的之外,还有一些都是长这个样子: 名为xxx-starter,比如 具体这些starter是怎么起作用的呢,他们什么时候开始工作的? 一切都要从入口处说起。我们以上面的starter为例,看到这个mybatis的starter,其对应的pom中,包含这些依赖 我们看到,相当于我们添加了一个Starter的依赖,其背后会引入许多其定义的其他依赖,通过 Maven 的传递依赖,这些都会被自动添加了进来。 自动配置 相比传统的依赖,我们看到其中包含这样一个:mybatis-spring-boot-autoconfigure,这也是每个Starter的秘密所在:「AutoConfigure」 它会在实...
相关文章
文章评论
共有0条评论来说两句吧...