面向面试编程:说一说 HashMap 的实现原理

面试官: 小伙子看你年纪轻轻敢来面我们公司很有勇气嘛,那么我们就来点开胃小菜, HashMap 平时应该用的很多吧,说一说它的实现原理吧。

候选者: (心里想 WTF 怎么一上来就问什么原理啊,我只是想来面试个初级开发而已,这二货是不拿错简历了。。。没办法了 事已至此硬着头皮上吧。。。)

什么是 hash？

候选人: 面试官你好首先我先谈谈什么是 hash 吧。hash 一般被翻译为 “散列”， 就是把任意长度的输入，通过散列算法，变换成固定长度的输出， 该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出， 所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。哈希表：哈希表是一种能实现关联数组的抽象数据结构，能把很多「键」映射到很多「值」上。哈希表使用哈希函数来计算索引，一个索引对应一个值。所以一个常见的使用场景就是，哈希表被广泛用于快速搜索数据,HashMap 也是该 应用场景的一种实现。

面试官: (心里想这小子有点东西啊,不过夜有可能是刷面试题背来的,我先沉住气看看他后面怎么答)。嗯好的你继续，还有其他么。

候选人: (MMP 我就知道没那么简单,只说这么一点糊弄不了老司机啊,不过还好我来之前看了 DevXTalk 的面向面试编程系列)。HashMap 中有两个关键参数, initialCapacity  初始化容量大小 和 loadFactor 负载因子 ， 这两个参数都影响着 HashMap 的性能。initialCapacity 决定了下一次 resize 后的容量（capacity <<1） ,
loadFactor  决定了 resize 发生的条件 （size> (capacity * loadFactor )） （一般情况下 ， 极端情况下是 size > Integer.MAX_VALUE） 。如果初始化时不指定这两个参数，会使用默认值 ， capacity  = 16 ， loadFactor  = 0.75 。对于 16 的容量空间，如果不能充分利用的话会造成空间资源的浪费。所以在 HashMap 初始化的时候 我们最好是根据当前的场景给一个初始化的容量大小。

// initialCapacity 初始化容量大小
// loadFactor 负载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
this.loadFactor = loadFactor;
// threshold 是HashMap是否要进行扩容的标记量
this.threshold = tableSizeFor(initialCapacity);
}

面试官: 小伙子答的还可以吧，但是这种程度可是胜任不了我们这个岗位的哦， 没事不要不好意思把你知道的全都说出来。（一脸猥琐的笑容）HashMap 的是如何散列的 有了解过么？

散列过程

候选人:别急嘛面试官，听我慢慢讲，你催我的话我会紧张的。

候选人:散列的过程就是将存入的元素均匀的分布到 HashMap 内部 Node 数据的过程。均匀分布指的是 ， 数组中的每个位置尽量都存储了一个 Node 节点，并且该位置上的链表只有一个元素。散列分布的越均匀进行碰撞检测的次数就越少， 查询性能就越高。这就是一个散列较为均匀的 ， 查询时最好情况下可以直接定位 ， 最坏情况下需要进行一次碰撞检测。

在散列时会经历碰撞检测,((capacity - 1) & hash) 会计算出 key 存储在 Node 数组中的那个位置上 （得到的值始终会落在 Node 数组的长度范围内 ， 等同于 hash % capacity  ， 不过位运算的效率更高）， 如果发现该位置上已经存在 Node 了，会将新存入的数据作为链表的尾节点。这样存储和查询时都会进行碰撞检测。碰撞检测其实就是比较传入的 key 的 hash 与同一 bucket 上所有的 key 的 hash 是否一致的过程。jdk8 在这方面做了优化，加入了树型结构来弥补链表线性结构性能较低的不足。

提高碰撞检测的性能 ， 从代码中也能看出来  ， 该运算的最理想情况（hash 相等情况下）是执行两步 ， 比较 hash ， 比较 key 。最坏情况是执行 4 步 ， 只要取最好情况就达到了提高性能的目的 。以此类推 key 就可以用一些 String ， Enum 这之类的数据类型。

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) {
// .......
}

面试官:(这小子果然有点东西啊，我得再问问他)。HashMap 的 resize 过程能否谈一谈呢？

reszie

候选人 : rezise 是一个较为消耗性能的过程 ， 在首次向 HashMap 中存入元素的时候会进行首次 resize ,
在之后每当产生新节点（这里的节点指的是 Node） ， 同时 size > threshold 的时候会进行 resize ， resize 的过程也是 rehash 的过程。所以我们在编程中应该尽可能的避免 reszie 的发生，比如初始化的时候 给定一个初始化大小。

面试官: 你说的不错，那么你有在并发场景下使用过 HashMap 么？

并发安全

候选人 : (哇！这老小子在给我挖坑，他想误导我，我可不会上当)。

候选人 : HashMap 是现场不安全的实现,并不适合在并发场景下使用， 在并发修改时它采用 fail-fast 的策略 ， 抛出 ConcurrentModificationException 。多线程环境下操作 HashMap 有可能会造成死循环 ， 在 resize 的过程当中。所以不要在多线程场景下使用 HashMap , 建议在并发场景下使用现场安全的 CurrentHashMap。(Fu*K 刚给自己挖了个坑，这老小子不会要开始问我 CurrentHashMap 了吧...)

面试官: 答的不错嘛年轻人,基础掌握的还是可以的,最快什么时间能到岗啊......我们团队最近很忙啊， 这帮兄弟都等着有新人加入能分担压力呢，加入我们一起做一件很牛×的事情吧。。。

欢迎加入 DevXTalk 的技术交流群,在这里你可以和大佬们一起交流分享技术,行业经验,提升自我。结识新的业内朋友，扩大自己的圈子，当你想换工作的时候也许就能拿到不错的 offer 。总之期待你的加入...

「看完本文有收获？转发给更多的朋友吧」

「DevXTalk 不止于技术」