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

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

对HashMap的思考

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

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

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

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

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

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

定义接口

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

接口

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

接口实现

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

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

看MyHashMap的构造

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

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

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

Entry

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

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

看put如何实现

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

第一,要考虑是否扩容?

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

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

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

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

hash函数

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

MyHashMap提供的hash函数

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

JDK的HashMap提供的hash函数

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

resize和rehash

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

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

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

get实现

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

get

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

Test测试

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

利用MyHashMap进行存取

运行结果

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

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

本文来自投稿,不代表重蔚自留地立场,如若转载,请注明出处https://www.cwhello.com/263299.html

如有侵犯您的合法权益请发邮件951076433@qq.com联系删除

(0)
黑马程序员黑马程序员订阅用户
上一篇 2023年5月15日 08:30
下一篇 2023年5月16日 07:26

相关推荐

  • 索引的底层实现原理是什么?

    索引存储在内存中,为服务器存储引擎为了快速找到记录的一种数据结构。索引的主要作用是加快数据查找速度,提高数据库的性能。索引的分类(1) 普通索引:最基本的索引,它没有任何限制。(2) 唯一索引:与普通索引类…

    2023年5月6日 编程分享
    01
  • 小编教你 淘宝黑搜原理及讲解分享,黑搜为什么有效。

    淘宝商家们需要好好的去运营自己的淘宝店铺,只要店铺有产品能够成为爆款一定能获得有效的推广,所以淘宝商家们需要采取一些方式去达到这个目的,下面分享淘宝黑搜方面的内容。首先,我们先了解一下淘宝黑搜是什么…

    2023年10月19日
    00
  • JSP运行原理及运行过程

    JSP的工作模式是请求/响应模式,客户端首先发出HTTP请求,JSP程序收到请求后将进行处理并返回处理结果。在一个JSP文件第一次被请求的时候,JSP引擎(容器)把该JSP文件转换成一个Servlet,而这个引擎本身也是一个Serv…

    2023年5月8日
    011
  • 小编教你什么是底层大都走不出底层。

    中高考结束后,村里又掀起了「老带新」的打工潮。 一周前,我接到电话,是姑姑打来的。 「听说你在广州混的还不错呀,你看能不能带我大崽去学徒?」 我没有丝毫惊讶。 因为这种事遇太多,但凡你在某地混熟了,能存…

    2023年7月29日 创业分享
    00
  • 教你seo优化的原理是什么。

    seo优化的原理就是利用百度、谷歌等搜索引擎的排名规则,通过对网站的内外部优化使网站的自然排名上升,以获取流量的技巧。seo分为白帽和黑帽,白帽就是符合规则,百度、谷歌等提倡的做法。下面小编小编就为大家介…

    2023年6月23日
    00
  • 我来教你SEO优化利用的是什么原理。

    seo网站优化对于今天的人们来说,已经不再是笼罩在神秘的面纱了,现在越来越多的人开始了解网站优化,这个行业是做什么的,并且在网站优化中网站关键字排名优化占据了的位置。因为如果你是这个网站的关键词,他有很…

    2023年6月26日
    00
  • 为什么大厂总爱问计算机基础知识和原理?

    黑马粉丝,你听过这个段子吗?如果你在简历中写了这句话,保证能拿到大厂面试机会:扎实的计算机基础,良好的数据结构与算法功底。然后,你就会被问到头皮发麻。虽然是段子,但也一定程度上说明了大厂非常注重计算…

    2023年5月8日 编程分享
    00
  • 小编分享SEO网站排名优化的原理是什么。

    随着互联网信息的增加,大大小小的网站也越来越多,网站的排名也显得至关重要,越是排名靠前的网站能获得的客户浏览数量也越多,说到这,大家肯定都想要问网站要怎样做才能提高排名,seo网站排名优化的原理是什么了…

    2023年6月19日
    00

联系我们

QQ:951076433

在线咨询:点击这里给我发消息邮件:951076433@qq.com工作时间:周一至周五,9:30-18:30,节假日休息