关于java:手写一个迷你版-HashMap面试随便问

作者：张丰哲

起源：jianshu.com/p/b638f19aeb64

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

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

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

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

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

如果产生了碰撞怎么办？下面的图其实曾经阐明了 JDK 的 HashMap 是如何解决 hash 抵触的，就是通过单链表解决的。那么除了这个办法，还有其余思路么？

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

定义一个接口，对外裸露疾速存取的办法。

留神 MyMap 接口外部定义了一个外部接口 Entry。

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

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

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

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

第一，要思考是否扩容？

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

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

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

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

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

resize/rehash 的过程，就是数组变大，原来数组中的 entry 元素一个个的 put 到新数组的过程，须要留神的是一些状态变量的扭转。

get 很简略，只须要留神在遍历单链表的过程中应用 == or equals 来判断下即可。

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

近期热文举荐：

1.1,000+ 道 Java 面试题及答案整顿 (2021 最新版)

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

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

4.Spring Boot 2.5 重磅公布，光明模式太炸了！

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

感觉不错，别忘了顺手点赞 + 转发哦！

对 HashMap 的思考