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

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

HashMap结构图目录

一、唠叨

二、解析思路

三、get方法

四、put方法

##五、resize方法

一、唠叨

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

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

##三、get方法 先挑最简单的说

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

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

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

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

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

五、resize方法

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

1.table == 的时候

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

六、resize具体方法

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

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

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

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

案例图

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

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