对HashMap的思考及手写实现

前言

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

对HashMap的思考

HashMap底层数据结构

第一,如图所示,HashMap有3个要素:hash函数+数组+单链表 第二,对于hash函数而言,需要考虑些什么? 要快,对于给定的Key,要能够快速计算出在数组中的index。那么什么运算够快呢?显然是位运算! 要均匀分布,要较少碰撞。说白了,我们希望通过hash函数,让数据均匀分布在数组中,不希望大量数据发生碰撞,导致链表过长。那么怎么办到呢?也是利用位运算,通过对数据的二进制的位进行移动,让hash函数得到的数据散列开来,从而减低了碰撞的概率。 如果发生了碰撞怎么办?上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的,就是通过单链表解决的。那么除了这个方法,还有其他思路么?比如说,如果发生冲突,那么记下这个冲突的位置为index,然后在加上固定步长,即index+step,找到这个位置,看一下是否仍然冲突,如果继续冲突,那么按照这个思路,继续加上固定步长。其实这就是所谓的线性探测来解决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函数

JDK的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就写好了,你学到了么?

周末愉快!

原文:jianshu.com/p/b638f19aeb64

原文发布于微信公众号 - Java团长(javatuanzhang)

原文发表时间:2018-06-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

Bessie的好牌(队列)- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

1193
来自专栏WindCoder

Java漫谈-容器

除并发应用,Queue在Java SE5中仅有两个实现 LinkedList和PriorityQueue,差异在于排序行为,而不是性能。

791
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十九】Iterator&fail-fast机制

【Java提高十九】Iterator&fail-fast机制 Iterator详解 迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行...

40211
来自专栏大数据架构

Java进阶(六)从ConcurrentHashMap的演进看Java多线程核心技术

2295
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

2198
来自专栏青玉伏案

算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

2147
来自专栏Spark学习技巧

JAVA集合框架中的常用集合及其特点、适用场景、实现原理简介

1513
来自专栏Java进阶架构师

对HashMap的思考及手写实现

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

982
来自专栏大史住在大前端

野生前端的数据结构基础练习(6)——集合

3.为Set类增加一个higher(element)方法,该方法返回比传入元素大的元素中最小的一个,并写一段代码来测试该功能。

1023
来自专栏我是业余自学C/C++的

队列

队列和栈一样,是一种特殊的线性表。跟栈不同的是,队列的插入和删除分别在线性表的两端进行,因此,队列是一个先进先出(FIFO)的线性表。插入元素的一端叫队尾(ba...

801

扫码关注云+社区

领取腾讯云代金券