手写一个迷你版 HashMap，面试随便问！

约定不等于承诺〃 2022-09-10 13:20 286阅读 0赞

作者：张丰哲  
来源： jianshu.com/p/b638f19aeb64

HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本篇博客将分析HashMap底层设计思想，并手写一个迷你版的HashMap！

# 对HashMap的思考 #

![HashMap底层数据结构][HashMap]

第一，如图所示，HashMap有3个要素：hash函数+数组+单链表

第二，对于hash函数而言，需要考虑些什么？

要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！

要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。

如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？

比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！

## 通过写一个迷你版的HashMap来深刻理解 ##

#### 定义接口 ####

![20210908174013727.png][]

**定义一个接口，对外暴露快速存取的方法。**

**注意MyMap接口内部定义了一个内部接口Entry。**

## 接口实现 ##

![20210908174013887.png][]

> **HashMap的要素之一，就是数组，自然在这里，我们要定义数组，数组的初始化大小，还要考虑扩容的阀值。**

## 看MyHashMap的构造 ##

![2021090817401464.png][]

构造方法有什么好说的呢**？**

仔细观察下，你会发现，其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个，但是对外却暴露了2个“门面”！

## Entry ##

![20210908174014213.png][]

> **HashMap的要素之一，单链表的体现就在这里！**

## 看put如何实现 ##

![20210908174014362.png][]

第一，要考虑是否扩容？

HashMap中的Entry的数量（数组以及单链表中的所有Entry）是否达到阀值？

第二，如果扩容，意味着新生成一个Entry\[\]，不仅如此还得重新散列。

第三，要根据Key计算出在Entry\[\]中的位置，定位后，如果Entry\[\]中的元素为null，那么可以放入其中，如果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表！

## hash函数 ##

![20210908174014509.png][]

![JDK的HashMap提供的hash函数][JDK_HashMap_hash]

> **我这里参考了JDK的HashMap的hash函数的实现，这里也再次说明了：要想散列均匀，就得进行二进制的位运算！**

## resize和rehash ##

![20210908174014814.png][]

> **这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。**
> 
> **resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。**

## get实现 ##

![20210908174014814.png][]

> **get很简单，只需要注意在遍历单链表的过程中使用== or equals来判断下即可。**

## Test测试 ##

![20210908174014814.png][]

## 运行结果 ##

![20210908174015229.png][]

**OK，一个迷你版的HashMap就写好了，你学到了么？**

**近期热文推荐：**

1.[1,000+ 道 Java面试题及答案整理(2021最新版)][1_000_ _ Java_2021]

2.[别在再满屏的 if/ else 了，试试策略模式，真香！！][if_ else]

3.[卧槽！Java 中的 xx ≠ null 是什么新语法？][Java _ xx _ null]

4.[Spring Boot 2.5 重磅发布，黑暗模式太炸了！][Spring Boot 2.5]

5.[《Java开发手册（嵩山版）》最新发布，速速下载！][Java]

觉得不错，别忘了随手点赞+转发哦！

[HashMap]: /images/20220829/d9fe27588c5b4c63bb3adf3422607e08.png
[20210908174013727.png]: /images/20220829/ac0c11bdd86b4d3da9e72e7c14fca622.png
[20210908174013887.png]: /images/20220829/c431ca5f415342e08558a0e6dd6f9a1b.png
[2021090817401464.png]: /images/20220829/7324d8cc17634b4586865734d9c04b48.png
[20210908174014213.png]: /images/20220829/53b3a094476241ee92ae225cead07c00.png
[20210908174014362.png]: /images/20220829/fe5416fc04d545b499cbdc8e569a7de5.png
[20210908174014509.png]: /images/20220829/ac4c8367fdc344eea2218fc0924526bf.png
[JDK_HashMap_hash]: /images/20220829/defbb58935f744f6a82f635493d22404.png
[20210908174014814.png]: /images/20220829/42c6c1488d2943c9a980455b5b4de5c4.png
[20210908174015229.png]: /images/20220829/43ca7f218f854ccfabb386c464136a22.png
[1_000_ _ Java_2021]: https://www.javastack.cn/mst/
[if_ else]: https://www.javastack.cn/article/2021/strategy-pattern-instead-of-if-else/
[Java _ xx _ null]: https://www.javastack.cn/article/2021/intellij-idea-ligatures-settings/
[Spring Boot 2.5]: https://www.javastack.cn/article/2021/spring-boot-2.5-released/
[Java]: http://www.javastack.cn/article/2020/alibaba-release-java-develop-rules-songshan/