作者：张丰哲来源：jianshu.com/p/b638f19aeb64HashMap是Java中常用的集合，HashMap的一些思想对我们解决一些业务问题很有帮助。基于此，本博客将剖析HashMap的底层设计思想，手写一个迷你版的HashMap！首先想到HashMap，如图，HashMap有3个元素：哈希函数+数组+单向链表其次，哈希函数应该考虑什么？为了快速，对于给定的Key，需要能够快速计算出数组中的索引。那么什么操作足够快呢？明显是位运算！为了均匀分布，减少碰撞。说白了，我们希望数据通过hash函数均匀分布在数组中，不希望大量的数据发生碰撞，导致链表过长。又怎样？它还使用位操作，通过移动数据的二进制位，对哈希函数得到的数据进行哈希处理，从而降低碰撞的概率。如果发生碰撞怎么办？上图其实已经说明了JDK的HashMap是如何处理hash冲突的，通过单链表来解决。那么除了这种方法之外，还有没有其他的思路呢？比如有冲突，记下冲突的位置作为index，然后加上一个固定的步长，即index+step，找到这个位置，看是否还有冲突。如果冲突还在继续，就按照这个思路，继续加上一个固定的步长。其实这就是所谓的解决Hash冲突的线性检测法！通过写一个迷你版的HashMap来深入理解定义接口定义一个接口，对外暴露快速访问的方法。请注意，MyMap接口定义了一个内部接口Entry。实现HashMap的接口元素之一是数组。自然，在这里，我们需要定义数组，数组的初始大小，并考虑扩展阈值。MyHashMap的构造方法怎么说呢？仔细观察，你会发现这里其实用的是“门面模式”。这里的两个构造方法其实指向同一个，只不过对外暴露了两个“门面”！EntryHashMap的元素之一，单链表的体现就在这里！看put是怎么实现的，首先要考虑要不要扩容？HashMap（数组和单向链表中的所有条目）中的条目数是否达到阈值？第二，如果扩容了，意味着要生成一个新的Entry[]，不仅如此，还得重新哈希一次。三、根据Key计算Entry[]中的位置。定位后，如果Entry[]中的元素为null，就可以放入其中。如果不为空，就得遍历单向链表，或者更新值，要么组成一个新的Entry“挤”单向链表！关于hash函数，我这里参考了JDK的HashMap的hash函数的实现，这里也再次说明：要想均匀hash，就得进行二进制位运算！Resize和rehash这里可以看出，对于HashMap来说，如果频繁进行resize/rehash操作，会影响性能。resize/rehash的过程是指数组变大，将原数组中的入口元素一个一个放入新数组中。需要注意一些状态变量的变化。实现起来非常简单。遍历单链表的过程中只需要注意使用==或者equals进行判断即可。Test试运行结果OK，写了一个mini版的HashMap。你学会了吗？近期热点文章推荐：1.1,000+Java面试题及答案（2021最新版）2.别在满屏的if/else中，试试策略模式，真的很好吃！！3.操！Java中xx≠null的新语法是什么？4、SpringBoot2.5发布，深色模式太炸了！5.《Java开发手册（嵩山版）》最新发布，赶快下载吧！感觉不错，别忘了点赞+转发！
