FreeCMS商业版

功能强大、开源、代码通俗易懂、注释详细、面向二次开发友好!

承接网站建设、软件开发、微信开发项目,价格从优,欢迎咨询合作!

FreeCMS商业版V2.8已发布!购买请联系客服QQ 124812878 查看更新日志



在线演示 立即购买 下载免费版 下载商业版用户手册
客服QQ: 124812878 联系电话: 18339991503 Email: freeteam@foxmail.com

对HashMap的思考及手写实现荐 - - ITeye博客

加入收藏夹】     【打印】     【关闭】 来源: 日期:2018-04-17 22:00:03 点击量: 收藏

前言

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

对HashMap的思考

对HashMap的思考及手写实现荐

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

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

要快,对于给定的Key,要能够快速计算出在数组中的index。那么什么运算够快呢?显然是位运算!

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

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

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

定义接口

对HashMap的思考及手写实现荐

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

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

接口实现

对HashMap的思考及手写实现荐

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

看MyHashMap的构造

对HashMap的思考及手写实现荐

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

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

Entry

对HashMap的思考及手写实现荐

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

看put如何实现

对HashMap的思考及手写实现荐

第一,要考虑是否扩容?

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

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

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

hash函数

对HashMap的思考及手写实现荐

对HashMap的思考及手写实现荐

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

resize和rehash

对HashMap的思考及手写实现荐

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

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

get实现

对HashMap的思考及手写实现荐

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

Test测试

对HashMap的思考及手写实现荐

运行结果

对HashMap的思考及手写实现荐

如果想学习Java性能优化,工程化、高性能及分布式、深入浅出。微服务、Spring,MyBatis,Netty源码分析的朋友可以加下454377428群里有阿里大牛直播讲解技术,以及Java大型互联网技术的视频免费分享给大家。

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




上一条

下一条

相关新闻
自定义表单
本例固定链接: 分享到:
更多