面试高频问题：HashMap实现原理

我会带着你远行 2022-01-13 02:23 259阅读 0赞

今天给同学们讲讲一个面试经常遇到的高频问题，HashMap实现原理，希望在金三银四的季节对同学们有帮助。

![面试高频问题：HashMap实现原理][HashMap]

### HashMap结构图目录 ###

###  一、唠叨 ###

###  二、解析思路 ###

###  三、get方法 ###

###  四、put方法 ###

###  五、resize方法 ###

###  一、唠叨 ###

认真阅读了下HashMap的实现方式，也参考了网上别人的一些解析，个人觉得还是有些东西想说。网上有的文章名字为HashMap源码解析，实际上就是给它里面的一些方法加上一些注释而已，有不少都是这样的。  
我自己看源码的时候，发现不是别人不想解析，而是它的实现真的需要亲自研读，多理顺几遍才知道怎么回事。  
我在这里解析的文字描述也较多，不管谁的解析，自己也都要看一下JDK源码的具体实现，我们仅提供参考而已。

### 二、解析思路 ###

源码不太方便看，先说明一下我的阅读思路。  
1.把常用的几个方法拷贝到文本编辑器里面。  
2.HashMap中不同的时候会有不同的流程，梳理方法中的逻辑流程。就像采用极端法，采用特殊的数据，然后查看方法执行语句。未执行的语句暂时不考虑。  
3.注释源码...我觉得HashMap的实现方式不够好，关键的几个方法里面包含的情况太多了，阅读起来是有难度的，而写程序的目的之一不就是让其他开发者阅读吗？一个方法内部做了太多的事情，违反了代码整洁的规则，一个函数做要尽量少的事情。  
解析  
之前稍微介绍了一些HashMap的特性，HashMap初探。  
（[https://www.jianshu.com/p/be9ffb76db30）这里接着深入][https_www.jianshu.com_p_be9ffb76db30]。

### 三、get方法 ###

先挑最简单的说

![面试高频问题：HashMap实现原理][HashMap 1]

1 先从数组下标，找到对应的Node2.   
2 如果Node里的第一个节点命中，直接返回  
3 如果有冲突，则通过key.equals(k)去查找对应的entry  
4 若为树，则在树中通过key.equals(k)查找，O(logn)；  
5 若为链表，则在链表中通过key.equals(k)查找，O(n)。put方法这个中间涉及的逻辑多一些，方法需要分不同的步骤看。

![面试高频问题：HashMap实现原理][HashMap 2]

### 四、put方法 ###

这个中间涉及的逻辑多一些，方法需要分不同的步骤看。  
思路：  
1对key的hashCode()做hash，然后再计算index;  
2如果没碰撞直接放到bucket里；  
3如果碰撞了，以链表的形式存在buckets后；  
4如果节点已经存在就替换old 5value(保证key的唯一性)  
6如果碰撞导致链表过长(大于等于TREEIFY\_THRESHOLD)，就把链表转换成红黑树；  
7如果Node的容量满了(超过load factor\*current capacity)，就要resize。

![面试高频问题：HashMap实现原理][HashMap 3]

![面试高频问题：HashMap实现原理][HashMap 4]

一般不发生碰撞的时候，相对简单，数据量较小的情况下。

![面试高频问题：HashMap实现原理][HashMap 5]

我解释下关于碰撞冲的循环。  
1.查看是否存在相同的key，存在相同的key跳出循环，覆盖key的value。  
2.如果不存在相同的key，在链表末尾插入新的Node如果链表节点过长，转换为树。  
3.如果链表节点过长，转换为树。

![面试高频问题：HashMap实现原理][HashMap 6]

红黑树的部分，我们下次单独解析

###  五、resize方法 ###

这个涉及的内容，有不少线需要捋一捋。首先看申明时候会resize()。它们都在调用put的时候执行的。

1.table == 的时候

![面试高频问题：HashMap实现原理][HashMap 7]

2.键值映射的的数目大于临界值的时候。

![面试高频问题：HashMap实现原理][HashMap 8]

六、resize具体方法

![面试高频问题：HashMap实现原理][HashMap 9]

![面试高频问题：HashMap实现原理][HashMap 10]

如果是第一次resize，我们抽出来会执行到的语句。  
1.初始化容量  
2.初始化threshold，也就是初始化临界值，决定了table的键值对数目到什么时候会再次resize()

![面试高频问题：HashMap实现原理][HashMap 11]

第二次及后续的resize执行流程

![面试高频问题：HashMap实现原理][HashMap 12]

resize中对有碰撞的链表的操作写的很有意思，再叙述一下。在重新分配索引的时候，有重新组建链表的操作。

![面试高频问题：HashMap实现原理][HashMap 13]

举个比较夸张的例子，读者就明白了。  
1.e.hash < 2，那么e.hash&oldCap就等于0，索引为小于之前hash表大小以内的索引。也就是当初的索引不变。  
2.e.hash > 2的时候，e.hash&old不等于0，那么它的索引就为当前表的索引再加上新扩容的大小。

![面试高频问题：HashMap实现原理][HashMap 14]  
                案例图

这个图说的是，当hashmap的表大小为2扩充到4的时候，原本挂载在1位置的链表，重新分配之后的样子。

![面试高频问题：HashMap实现原理][HashMap 15]

最后  
篇幅有限，我这里仅仅介绍了get方法，put方法，resize方法的具体原理，文章就已经非常长了，不利于阅读。  
下次再补充一下HashMap的hash方法原理，其余的相关注意事项。

转载于:https://blog.51cto.com/14295469/2401102

[HashMap]: https://s1.51cto.com/images/blog/201905/27/2b3913f0dd7bd32e43d80623035023f7.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[https_www.jianshu.com_p_be9ffb76db30]: https://www.jianshu.com/p/be9ffb76db30%EF%BC%89%E8%BF%99%E9%87%8C%E6%8E%A5%E7%9D%80%E6%B7%B1%E5%85%A5
[HashMap 1]: https://s1.51cto.com/images/blog/201905/27/8766c325709231ea638589853c16edc6.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 2]: https://s1.51cto.com/images/blog/201905/27/94069275d06d9978afe88946493ef68a.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 3]: https://s1.51cto.com/images/blog/201905/27/a62a9da2acc261aa8c51af5db2386590.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 4]: https://s1.51cto.com/images/blog/201905/27/c7ee2157b9e6908bd0b3381b4b309d45.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 5]: https://s1.51cto.com/images/blog/201905/27/273bff4200442d9d55c5f3d6ecd531d0.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 6]: https://s1.51cto.com/images/blog/201905/27/b9a40b406d6ea4d5a19b78b9d92ba8a8.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 7]: https://s1.51cto.com/images/blog/201905/27/b4480c0f7e286e5a7d090db19f962528.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 8]: https://s1.51cto.com/images/blog/201905/27/a1b96269fcb50a91de82bb704ef6a4d3.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 9]: https://s1.51cto.com/images/blog/201905/27/6b077408149bbbf53721034069bbe1b3.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 10]: https://s1.51cto.com/images/blog/201905/27/d9b449bdab082b8076c2e07b8777291b.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 11]: https://s1.51cto.com/images/blog/201905/27/09809edc437be2200aa7482f5fa8c863.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 12]: https://s1.51cto.com/images/blog/201905/27/840b68f99c3693d4805eb1cf5c4db9e5.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 13]: https://s1.51cto.com/images/blog/201905/27/bdb2f417591f3dc6ebc49742518ef0eb.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 14]: https://s1.51cto.com/images/blog/201905/27/59cfee145788ff9e4a6fc21f63633695.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=
[HashMap 15]: https://s1.51cto.com/images/blog/201905/27/35e4cb4b4354ebc542e74abe5f846d4a.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=