⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 jianshu.com/p/b638f19aeb64 「张丰哲」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

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

对HashMap的思考

HashMap底层数据结构

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

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

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

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

如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！

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

定义接口

i接口

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

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

接口实现

MyHashMap定义

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

看MyHashMap的构造

构造方法

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

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

Entry

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

看put如何实现

put

第一，要考虑是否扩容？

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

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

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

hash函数

MyHashMap提供的hash函数

JDK的HashMap提供的hash函数

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

resize和rehash

resize/rehash

这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。

resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。

get实现

get

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

Test测试

利用MyHashMap进行存取

运行结果

result

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

周末愉快！

See u next blog!

芋道源码 —— 纯源码解析博客

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