天下无难试之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里面的字典是如何扩容的么?

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

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

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

原文发布于微信公众号 - 码洞(codehole)

原文发表时间:2018-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据分析

[数据清洗]-看上去一样的数字

数据不正确(格式不正确,数据不准确,数据缺失)我们做什么都是徒劳。数据清洗时数据分析的第一步,也是最耗时的一步。 数据清洗很枯燥,但是随着数据清理技巧越来越熟练...

29930
来自专栏令仔很忙

设计模式六大原则——合成/聚合复用原则(CARP)

简而言之,对于合成/聚合复用原则的定义就是:要尽量使用合成和聚合,尽量不要使用继承。

31110
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 6 章:值的不可变性

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 6 章:值的不可变性 在第 ...

22450
来自专栏斑斓

深入探索Scala的Option

程序员最深恶痛绝并力求避免的异常是NullPointerException,很不幸,我们往往又会忽略这个错误。不知是谁设计了Null这样的对象。我在文章《并非N...

34370
来自专栏技术墨客

Java函数式开发——优雅的Optional空指针处理

    在Java江湖流传着这样一个传说:直到真正了解了空指针异常,才能算一名合格的Java开发人员。在我们逼格闪闪的java码字符生涯中,每天都会遇到各种nu...

14220
来自专栏数据结构与算法

Debug

复杂度证明 普通莫队时间复杂度为 证明: 当我们第i个询问转移的第i+1个询问时 如果第i个询问区间和第i+1个询问区间的左端点所在块的编号相同,那么左端...

361110
来自专栏编程

Python利器之迭代器

各位小伙伴们 大家周四愉快 今天要和大家探讨一个 Python的特色功能 也是Python有别于其他变成语言的 强大利器 迭代器 迭代这一个词可能有的小伙伴不理...

19870
来自专栏阿杜的世界

《Scala程序设计》阅读书摘

JVM上的语言越来越多了,从前几年的groovy、Scala和Clojure,现在又听说一门Kotlin。对于前三种语言,groovy算是JVM平台上的动态脚本...

9820
来自专栏程序员互动联盟

【专业技术】如何写出优美的C 代码?

面向对象的语言更接近人的思维方式,而且在很大程度上降低了代码的复杂性,同时提高了代码的可读性和可维护性,传统的 C 代码同样可以设计出比较易读,易维护,复杂度较...

35490
来自专栏互联网技术栈

设计模式- 合成/组合原则

上面的问题都来源于对方法的改写动作。如果你在扩展一个类的时候,仅仅是增加新的方法,而不改写已有的方法,你可能会认为这样做是安全的,但是也并不是完全没有风险。

13040

扫码关注云+社区

领取腾讯云代金券