Java基础教程: 手写HashMap

价       格: 9.90
讲座评分: 暂无评分
视频时长:1小时22分钟
等 87 人参与
可以用微信小程序直接看哦
及时获取更多直播动态
鼠标移动放大
14 收藏

讲师信息

方老司
1.5k 声望
0412

同济大学计算机系,先后担任过 500 强 CISCO 开发、中金所开发、有渔学堂技术合伙人,程序员职业发展论坛earnfish.com联合创始人,现专职云原生服务的研究。

内容简介

请务必加入微信群,讲座时间会更新,讲座内容会更改,而且优惠信息,讲座资料会在群里发放

一 讲座简介

HashMap 几乎是每一场面试必考知识点,与其费尽心思的看各种博客,还不如自己撸一个,一劳永逸的解决问题。

二 内容大纲

  1. HashMap的数据结构
    数据结构是什么?这种数据结构在内存中是怎么样,是如何实现O(1)的?
  2. put,get 等方法的实现
    Java中的泛型
  3. Hash算法,以及冲突的解决方法
    对象hashcode是如何来的,为何需要hashcode,在hashmap里的“扰动函数”,”==“以及”equal“的区别
  4. 二叉树、红黑树简介
    Java7和Java8中对冲突的解决方式是不一样的
  5. HashMap 可能导致的死循环
    为何说HashMap不是线程安全的,哪些地方可能导致问题?

三 面向人群

初、中级后端Java开发

四 目标

明白HashMap的底层机制,实现原理

五 参考资料

转载 http://blog.51cto.com/zhangfe...

5.1 HashMap原理图

clipboard.png

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

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

一是考虑什么数据结构能直接根据下标在O(1)内取到值,当然是数组了

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

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

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

5.2 定义接口

clipboard.png

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

5.3 实现接口

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

5.4 MyHashMap的构造

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

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

5.5 Entry

clipboard.png

HashMap的要素之一

5.6 实现put方法

clipboard.png

第一,要考虑是否扩容?
HashMap中的Entry的数量(数组以及单链表中的所有Entry)是否达到阀值?

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

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

5.7 hash函数

clipboard.png

clipboard.png

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

5.8 resize和rehash

clipboard.png

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

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

5.9 get实现

clipboard.png

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

5.10 测试

clipboard.png


0 条评价

暂无评价

SegmentFault 讲堂是什么?

SegmentFault 讲堂是以开发者为中心的视频演讲平台。 旨在和开发者一起分享和创造有价值的技术内容。 目前讲堂主要有视频观看,下载相关文档以及和主讲人聊天互动的功能。

关注 SegmentFault 服务号

  • 订阅讲堂开播提醒
  • 及时获取更多直播动态

添加 SF.GG 讲堂粉丝 QQ 群

  • 群号码:642336612(备注 SF 用户名)
  • 不定期获取讲座优惠信息,随时和开发者交流互动