manbetx体育播客旗下品牌:|||||

全国咨询/投诉热线:400-618-4000

了解HashMap底层设计思想,教你手写一个迷你版的HashMap!【】

更新时间:2020年04月09日14时58分 来源:manbetx体育播客 浏览次数:

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

对HashMap的思考

HashMap的思考01


HashMap底层数据结构第一,如图所示,HashMap有3个要素:hash函数+数组+单链表。

第二,对于hash函数而言,需要考虑些什么?

要快,对于给定的Key,要能够快速计算出在数组中的index。那么什么运算够快呢?显然是位运算!要均匀分布,要较少碰撞。说白了,我们希望通过hash函数,让数据均匀分布在数组中,不希望大量数据发生碰撞,导致链表过长。那么怎么办到呢?也是利用位运算,通过对数据的二进制的位进行移动,让hash函数得到的数据散列开来,从而减低了碰撞的概率。

如果发生了碰撞怎么办?上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的,就是通过单链表解决的。那么除了这个方法,还有其他思路么?比如说,如果发生冲突,那么记下这个冲突的位置为 index,然后在加上固定步长,即index+step,找到这个位置,看一下是否仍然冲突,如果继续冲突,那么按照这个思路,继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法!

通过写一个迷你版的HashMap来深刻理解定义接口

定义接口

HashMap的思考02

接口

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

接口实现

HashMap的思考03

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

看MyHashMap的构造

HashMap的思考04


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

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

Entry

HashMap的思考05

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

看put如何实现

HashMap的思考06

第一,要考虑是否扩容?

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

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

第三,要根据Key计算出在Entry[]中的位置,定位后,如果Entry[]中的元素为null,那么可以放入其中,如

果不为空,那么得遍历单链表,要么更新value,要么形成一个新的Entry“挤压”单链表!

hash函数

HashMap的思考07

MyHashMap提供的hash函数

HashMap的思考08


JDK的HashMap提供的hash函数

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

resize和rehash

HashMap的思考09

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

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

get实现

HashMap的思考10.png

get

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

Test测试

HashMap的思考11

利用MyHashMap进行存取

运行结果

HashMap的思考12

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

猜你喜欢:

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额