面试官，求你不要再问我HashMap的实现原理了（一）

ゝ一世哀愁。 2023-07-19 10:47 4阅读 0赞

面试官 : 平常开发过程中使用过的HashMap吧。

面试者：使用过。

面试官：那你可以给我简单介绍一下HashMap的实现原理吗？

。。。。。。。。。。

这种场景Java开发的小伙伴在面试过程中肯定遇到过，当然，每个人的回答的程度都不一样，作者总结了一些常常会被问到的问题。一方面，帮助方便大家面试，另一方面，可以让大家对HashMap可以有一个比较深的认识。

面试开始！！！

面试官：你可以给我简单说说HashMap的数据结构和底层原理吗？

面试者：当然，HashMap是数组和链表组合而成，每一个数组中都存储这一个 key-value实例，Jdk7之前叫做Entry，jd8之后叫做Node（节点），每一个Node里面记录了hash、key、value下一个节点Node，在我们往Map中put值得时候，会首先计算该值得hash，然后在数据中找到对应得位置，当然，不排除会put得值得hash是相同得情况，那么这个时候链表得作用就体现了出来，当计算hash得出相同得Node时，会在相同得位置形成了链表。

面试官：说到使用链表，那么链表得插入方式？

面试者：在Jdk1.8之前采用得时头插法，也就是每次插入得新值，会在链表得最前面，但是jdk1.8及之后采用得是尾插法，也就是每次新值都会在链表得后面。

面试官：那么为什么更改头插法变为尾插法了呢？扩容？如何扩容？

面试者：改为尾插法得原因，首先要考虑到Map得扩容机制，也就是resize，那么，什么时候会扩容呢，这主要由Map得两个元素决定，一是容量，二是负载因子，容量如果我们没有设置的话，默认容量是16，他的负载因子是0,75，意思就是当数组占比已经达到 容量\*0.75的时候，就要扩容。那么库容是怎样的，Map得扩容机制是将容量复制为原来得二倍，然后完全遍历集合得数据，进行重新Hash操作，再放入新的数据中。那么为什么要重新获取hash然后扩容呢，为什么不直接取出然后放到新的数组中呢？这就牵扯到一个index计算公式得问题，Map中计算index得公式是 index = hashCode(key) & （length-1）,公式可以看出，当集合狂容得时候，length发生变化时，index本身就发生了变化，所以原来是长度是16得计算得出是2得元素，在扩容成32得时候index肯定是不一样得，所以，肯定要重新计算。 回到最初得问题，为什么不使用头插法而使用尾插法了呢？这个是多线程情况下，在触发扩容得时候，数据元素需要重新计算hash位置，容易造成闭环。 如下图，假设数组长度是4，插入A,B,C三个数据，当插入第C得时候开始扩容，但是如果两个线程一，线程二，线程一是没有扩容之前执行 key(3)->key(7) ，但是线程二触发了扩容，数组数据开始重新排序，这时候触发key(7)->key(3)的情况，这时候，线程一在执行之后，就会出现下图闭环得情况，然后如果我们执行get方法得时候，就会出现问题，那也就是，为什么多线程情况下，不能使用。当然，尾插法的时候，原有顺序是A->B 再插入得时候还是 A->B，不存在问题。

![2020042817203187.png][]

面试官：那么为什么Map得容量一定要是2得幂次方。

简单来说就是方便，均匀分布，计算index得公式为 index = hashCode(key) & （length-1） 位运算，二进制得运算不需要转化成十进制，所以效率很高。当然，如果lengh为2得幂次方时， h & (length - 1) == h % length，而index就是h得取余，而位运算得效率也远远高于位运算，那么为什么是16，而不是 4 8 32 等等，有可能跟执行效率或者什么有关。

*  HashMap的底层数据结构？
 *  HashMap的存取原理？
 *  Java7和Java8的区别？
 *  为啥会线程不安全？
 *  有什么线程安全的类代替么?
 *  默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
 *  HashMap的扩容方式？负载因子是多少？为什是这么多？
 *  HashMap的主要参数都有哪些？
 *  HashMap是怎么处理hash碰撞的？
 *  hash的计算规则？

[2020042817203187.png]: /images/20230528/a0c7d97755954b97b181e85565fdd022.png