Question

为什么面试要问hashmap 的原理

Answer 1

HashMap
的工作原理

HashMap
，都知道哪里要用
HashMap
，知道
Hashtable
和
HashMap
之间的区别
，那么
为何这道面试题如此特殊呢？是因为这道题考察的深度很深。
这题经常出现在高级或中高级
面试中。投资银行更喜欢问这个问题，甚至会要求你实现
HashMap
来考察你的编程能力。
ConcurrentHashMap
和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的
旅程吧！

先来些简单的问题

“你用过
HashMap
吗？”

“什么是
HashMap
？你为什么用到它？”

几乎每个人都会回答“是的”，然后回答
HashMap
的一些特性，譬如
HashMap
可以接
受
null
键值和值，而
Hashtable
则不能；
HashMap
是非
synchronized;HashMap
很快；
以及
HashMap
储存的是键值对等等。
这显示出你已经用过
HashMap
，
而且对它相当的熟
悉。但是面试官来个急转直下，从此刻开始问出一些刁钻的问题，关于
HashMap
的更多
基础的细节。面试官可能会问出下面的问题：

“你知道
HashMap
的工作原理吗？”

“你知道
HashMap
的
get()
方法的工作原理吗？”

你也许会回答“我没有详查标准的
Java API
，你可以看看
Java
源代码或者
Open JDK
。”
“我可以用
Google
找到答案。”

但一些面试者可能可以给出答案，
“
HashMap
是基于
hashing
的原理，
我们使用
put(key,
value)
存储对象到
HashMap
中，使用
get(key)
从
HashMap
中获取对象。当我们给
put()
方法传递键和值时，
我们先对键调用
hashCode()
方法，
返回的
hashCode
用于找到
bucket
位置来储存
Entry
对象。”这里关键点在于指出，
HashMap
是在
bucket
中储存键对象和

值对象，作为
Map.Entry
。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，
或者错误的认为仅仅只在
bucket
中存储值的话，
你将不会回答如何从
HashMap
中获取对
象的逻辑。这个答案相当的正确，也显示出面试者确实知道
hashing
以及
HashMap
的工
作原理。但是这仅仅是故事的开始，当面试官加入一些
Java
程序员每天要碰到的实际场景
的时候，错误的答案频现。下个问题可能是关于
HashMap
中的碰撞探测
(collision
detection)
以及碰撞的解决方法：

“当两个对象的
hashcode
相同会发生什么？”

从这里开始，真正的困惑开始了，一些面
试者会回答因为
hashcode
相同，
所以两个对象是相等的，
HashMap
将会抛出异常，
或者
不会存储它们。然后面试官可能会提醒他们有
equals()
和
hashCode()
两个方法，并告诉他
们两个对象就算
hashcode
相同，但是它们可能并不相等。一些面试者可能就此放弃，而
另外一些还能继续挺进，他们回答“因为
hashcode
相同，所以它们的
bucket
位置相同，
‘碰撞’会发生。因为
HashMap
使用
LinkedList
存储对象，这个
Entry(
包含有键值对的
Map.Entry
对象
)
会存储在
LinkedList
中。”这个答案非常的合理，虽然有很多种处理碰撞
的方法，这种方法是最简单的，也正是
HashMap
的处理方法。但故事还没有完结，面试
官会继续问：

“如果两个键的
hashcode
相同，
你如何获取值对象？”

面试者会回答：
当我们调用
get()
方法，
HashMap
会使用键对象的
hashcode
找到
bucket
位置，然后获取值对象。面试官
提醒他如果有两个值对象储存在同一个
bucket
，
他给出答案
:
将会遍历
LinkedList
直到找到
值对象。
面试官会问因为你并没有值对象去比较，
你是如何确定确定找到值对象的？除非面
试者直到
HashMap
在
LinkedList
中存储的是键值对，否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说，
找到
bucket
位置之后，
会调用
keys.equals()
方法去找到
LinkedList
中正确的节点，最终找到要找的值对象。完美的答案！