共计 1438 个字符,预计需要花费 4 分钟才能阅读完成。
作者:张丰哲
起源:jianshu.com/p/b638f19aeb64
HashMap 是 Java 中罕用的汇合,而且 HashMap 的一些思维,对于咱们平时解决业务上的一些问题,在思路上有帮忙,基于此,本篇博客将剖析 HashMap 底层设计思维,并手写一个迷你版的 HashMap!
对 HashMap 的思考
第一,如图所示,HashMap 有 3 个因素:hash 函数 + 数组 + 单链表
第二,对于 hash 函数而言,须要思考些什么?
要快,对于给定的 Key,要可能疾速计算出在数组中的 index。那么什么运算够快呢?显然是位运算!
要均匀分布,要较少碰撞。说白了,咱们心愿通过 hash 函数,让数据均匀分布在数组中,不心愿大量数据产生碰撞,导致链表过长。那么怎么办到呢?也是利用位运算,通过对数据的二进制的位进行挪动,让 hash 函数失去的数据散列开来,从而减低了碰撞的概率。
如果产生了碰撞怎么办?下面的图其实曾经阐明了 JDK 的 HashMap 是如何解决 hash 抵触的,就是通过单链表解决的。那么除了这个办法,还有其余思路么?
比如说,如果发生冲突,那么记下这个抵触的地位为 index,而后在加上固定步长,即 index+step,找到这个地位,看一下是否依然抵触,如果持续抵触,那么依照这个思路,持续加上固定步长。其实这就是所谓的线性探测来解决 Hash 抵触的办法!
通过写一个迷你版的 HashMap 来深刻理解
定义接口
定义一个接口,对外裸露疾速存取的办法。
留神 MyMap 接口外部定义了一个外部接口 Entry。
接口实现
HashMap 的因素之一,就是数组,天然在这里,咱们要定义数组,数组的初始化大小,还要思考扩容的阀值。
看 MyHashMap 的结构
构造方法有什么好说的呢 ?
仔细观察下,你会发现,其实这里应用到了“门面模式”。这里的 2 个构造方法其实指向的是同一个,然而对外却裸露了 2 个“门面”!
Entry
HashMap 的因素之一,单链表的体现就在这里!
看 put 如何实现
第一,要思考是否扩容?
HashMap 中的 Entry 的数量(数组以及单链表中的所有 Entry)是否达到阀值?
第二,如果扩容,意味着新生成一个 Entry[],不仅如此还得从新散列。
第三,要依据 Key 计算出在 Entry[] 中的地位,定位后,如果 Entry[] 中的元素为 null,那么能够放入其中,如果不为空,那么得遍历单链表,要么更新 value,要么造成一个新的 Entry“挤压”单链表!
hash 函数
我这里参考了 JDK 的 HashMap 的 hash 函数的实现,这里也再次阐明了:要想散列平均,就得进行二进制的位运算!
resize 和 rehash
这里能够看出,对于 HashMap 而言,如果频繁进行 resize/rehash 操作,是会影响性能的。
resize/rehash 的过程,就是数组变大,原来数组中的 entry 元素一个个的 put 到新数组的过程,须要留神的是一些状态变量的扭转。
get 实现
get 很简略,只须要留神在遍历单链表的过程中应用 == or equals 来判断下即可。
Test 测试
运行后果
OK,一个迷你版的 HashMap 就写好了,你学到了么?
近期热文举荐:
1.1,000+ 道 Java 面试题及答案整顿 (2021 最新版)
2. 别在再满屏的 if/ else 了,试试策略模式,真香!!
3. 卧槽!Java 中的 xx ≠ null 是什么新语法?
4.Spring Boot 2.5 重磅公布,光明模式太炸了!
5.《Java 开发手册(嵩山版)》最新公布,速速下载!
感觉不错,别忘了顺手点赞 + 转发哦!