您现在的位置是:首页 > 文章详情

对HashMap的思考及手写实现

日期:2018-09-06点击:506

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

113f07deff4ef2c4bbdc88d82517610971bca46b

对HashMap的思考

9fa71e3820033292d7dc50e4096b8d08e6c05979

HashMap底层数据结构

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

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

定义接口

3049e2388c68198a5cabc58c4bb8150eafed5d65

接口

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

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

接口实现

3df1edd11dbd6abc1120ca7099f98b05b5aa2420

MyHashMap定义

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

看MyHashMap的构造

073615f0c1e6eb6db4cbabfa909e726c7918657d

构造方法

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

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

Entry

cf4a1cbf925b9a3502e7fa392b91ae70b8961f25

Entry

HashMap的要素之一,单链表的体现就在这里!

看put如何实现

9018909d621dacd850ed7826b8ee520bf5daa89c

put

第一,要考虑是否扩容?

HashMap中的Entry的数量(数组以及单链表中的所有Entry)是否达到阀值?

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

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

hash函数

5b702abd16b2c97380c903e16862e7b27a795ca9

MyHashMap提供的hash函数

050cd3f13a8cb259d4a07c63bfd5136939c3d616

DK的HashMap提供的hash函数

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

resize和rehash

0a51b8ecae52893439a8acd50c9384c6c3454e42

resize/rehash

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

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

get实现

06726a1ae41900026be30a970dbcc6ad2a63a367

get

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

Test测试

b1af512e9f14138f699c364723144e4fc8f65e8d

利用MyHashMap进行存取

运行结果

972a2bfec24dab953f41f23d8be5a2ce5dd06178

result

OK,一个迷你版的HashMap就写好了,你学到了么?


原文发布时间为:2018-09-6
本文作者:张丰哲
本文来自云栖社区合作伙伴“ java进阶架构师”,了解相关信息可以关注“ java进阶架构师”。
原文链接:https://yq.aliyun.com/articles/636918
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章