对HashMap的思考及手写实现-创新互联

作者：张丰哲
原文：https://www.jianshu.com/p/b638f19aeb64

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

成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都网站制作、成都做网站、外贸营销网站建设、察哈尔右翼后网络推广、微信小程序定制开发、察哈尔右翼后网络营销、察哈尔右翼后企业策划、察哈尔右翼后品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；成都创新互联为所有大学生创业者提供察哈尔右翼后建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

对HashMap的思考及手写实现

对HashMap的思考

对HashMap的思考及手写实现

HashMap底层数据结构

第一，如图所示，HashMap有3个要素：hash函数+数组+单链表
第二，对于hash函数而言，需要考虑些什么？
要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！
要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。
如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！

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

定义接口

对HashMap的思考及手写实现

接口

定义一个接口，对外暴露快速存取的方法。
注意MyMap接口内部定义了一个内部接口Entry。

接口实现

对HashMap的思考及手写实现

MyHashMap定义

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

看MyHashMap的构造

对HashMap的思考及手写实现

构造方法

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

Entry

对HashMap的思考及手写实现

Entry

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

看put如何实现

对HashMap的思考及手写实现

put

第一，要考虑是否扩容？
HashMap中的Entry的数量（数组以及单链表中的所有Entry）是否达到阀值？
第二，如果扩容，意味着新生成一个Entry[]，不仅如此还得重新散列。
第三，要根据Key计算出在Entry[]中的位置，定位后，如果Entry[]中的元素为null，那么可以放入其中，如果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表！

hash函数

对HashMap的思考及手写实现