对HashMap的思考及手写实现
HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设计思想,并手写一个迷你版的HashMap!
对HashMap的思考
HashMap底层数据结构
第一,如图所示,HashMap有3个要素:hash函数+数组+单链表
通过写一个迷你版的HashMap来深刻理解
定义接口
接口
定义一个接口,对外暴露快速存取的方法。
注意MyMap接口内部定义了一个内部接口Entry。
接口实现
MyHashMap定义
HashMap的要素之一,就是数组,自然在这里,我们要定义数组,数组的初始化大小,还要考虑扩容的阀值。
看MyHashMap的构造
构造方法
构造方法有什么好说的呢?
仔细观察下,你会发现,其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个,但是对外却暴露了2个“门面”!
Entry
Entry
HashMap的要素之一,单链表的体现就在这里!
看put如何实现
put
第一,要考虑是否扩容?
HashMap中的Entry的数量(数组以及单链表中的所有Entry)是否达到阀值?
第二,如果扩容,意味着新生成一个Entry[],不仅如此还得重新散列。
第三,要根据Key计算出在Entry[]中的位置,定位后,如果Entry[]中的元素为null,那么可以放入其中,如果不为空,那么得遍历单链表,要么更新value,要么形成一个新的Entry“挤压”单链表!
hash函数
MyHashMap提供的hash函数
DK的HashMap提供的hash函数
我这里参考了JDK的HashMap的hash函数的实现,这里也再次说明了:要想散列均匀,就得进行二进制的位运算!
resize和rehash
resize/rehash
这里可以看出,对于HashMap而言,如果频繁进行resize/rehash操作,是会影响性能的。
resize/rehash的过程,就是数组变大,原来数组中的entry元素一个个的put到新数组的过程,需要注意的是一些状态变量的改变。
get实现
get
get很简单,只需要注意在遍历单链表的过程中使用== or equals来判断下即可。
Test测试
利用MyHashMap进行存取
运行结果
result
OK,一个迷你版的HashMap就写好了,你学到了么?

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
AI-多云互联,网络通信的“自动驾驶
数字时代需要可编程的灵活性,敏捷性和互连性 全球国际电信会议PTC称数字化转型将开启“‘连接’的新十年”。Equinix在发布的《全球互联指数》报告中指出,城市化、数据主权、网络安全和全球数字服务贸易等技术的使用,推动了全球数字化的发展趋势。正是在这样的背景下,数字媒体、人工智能/机器学习(AI/ML)、大数据和安全分析、增强/虚拟现实和物联网(IoT)等产业日益增长。 与传统骨干网络相比,这些技术应用的动态性和交互性特征需要更加的弹性、灵活、低延迟和高带宽的连接来处理数字洪流。事实上,全球互连指数预测,到2020年,数字业务将需要5,000 Tbps以上的互连带宽容量,才能满足企业之间数据交换,这一带宽容量需求已经超过了当前全球IP流量、互联网和MPLS网络的总体增长。 这就是为什么业界纷纷转向SDN和NFV技术,从而将其带入数字化时代的未来! 过去十年来,SDN和NFV的供应商和用户一直致力于充分利用这两种不断发展的技术,但仍有很大的增长空间。TBR报告称,近四分之三的领先一级运营商已经或计划采用SDN和NFV。报告预测从2016年到2022年,SDN/NFV总开支将增长94.3%...
- 下一篇
阿里云Redis助力新东方乐词业务快速稳定发展
背景介绍 乐词是新东方倾情打造权威英语单词背记APP,业务涵盖初中、高中、新概念、英语四六级、考研、雅思、托福、GRE、SAT、ACT 、GMAT、托业、商务英语等英语单词库,科学规划词根背记,离线背单词随时学,权威详尽单词解析,全新考试干货课程,群组背记英语单词,完整的视频教学体系为用户提供全方位的单词学习体验。乐词系统涵盖词书、背词、查词、视频课程、活动、用户、在线支付等10多个核心业务模块,用户使用日活10w+,为了给用户提供稳定可靠的服务,对我们系统的可用性提出了更高的要求。Redis作为业界目前流行的Key-Value型NoSQL存储组件,可以帮我们解决面临的技术挑战。因我们属于创业型项目,自建系统以及自行运维意味着前期较大的投入以及过高的运维成本,随着业务规模的扩张,资源水平扩展以及垂直扩展也是未来无法避免的痛点,所以我
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Mario游戏-低调大师作品
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS关闭SELinux安全模块