深入理解HashMap

redis_logo

HashMap是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以key-value的形式存在。今天我们来深入了解一下这个集合的底层原理。


众所周知,HashMap是一个用于存储Key-Value键值对的集合,每一个键值对也叫做Entry。这些个键值对(Entry)分散存储在一个数组当中,这个数组就是HashMap的主干。

hashmap_logo

这个数组在首次使用时进行初始化,每一个元素的初始值都是Null。
为了了解它,我们从Put方法个Get方法来进行阐述。

一、Put方法的原理

HashMap在调用put方法时会先根据Key值来进行哈希运算来得到结果,即:

1
index =  Hash(“Key”)

假如计算出的index是2,那么就会将它放入index为2的位置,如图:

hashmap_2

但是再完美的Hash函数也难免会出现index冲突的情况。比如下面这样。
hashmap_3
这时候我们就可以使用链表来解决

HashMap数组的每一个元素不止是一个Entry对象,也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时,只需要插入到对应的链表即可:
hashmap_4
需要注意的是,新来的Entry节点插入链表时,使用的是“头插法”。
所以一个完整的HashMap样子应该是这样的
hashmap_5

二、Get方法的原理

使用Get方法根据Key来查找Value的时候,发生了什么呢?

首先会把输入的Key做一次Hash映射,得到对应的index:

index = Hash(“apple”)

由于刚才所说的Hash冲突,同一个位置有可能匹配到多个Entry,这时候就需要顺着对应链表的头节点,一个一个向下来查找。假设我们要查找的Key是“apple”:
hashmap_6
第一步,我们查看的是头节点Entry6,Entry6的Key是banana,显然不是我们要找的结果。

第二步,我们查看的是Next节点Entry1,Entry1的Key是apple,正是我们要找的结果。

之所以把Entry6放在头节点,是因为HashMap的发明者认为,后插入的Entry被查找的可能性更大

三、哈希方法

如何实现一个尽量均匀分布的Hash函数呢?我们通过利用Key的HashCode值来做某种运算。具体公式如下:

1
index =  HashCode(Key) &  (Length - 1)

从公式中我们可以看到运用了HashMap的长度。那么它的长度是多少呢?答案是16。因为这个数字可以尽量避免哈希碰撞,减少相同index的几率。如果你不相信的话,换个别的数字试试?

四、HashMap的扩容

HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。

这时候,HashMap需要扩展它的长度,也就是进行Resize。

影响发生Resize的因素有两个:

1.Capacity
HashMap的当前长度。上一期曾经说过,HashMap的长度是2的幂。
2.LoadFactor
HashMap负载因子,默认值为0.75f。

衡量HashMap是否进行Resize的条件如下:

1
HashMap.Size   >=  Capacity * LoadFactor

1.扩容
创建一个新的Entry空数组,长度是原数组的2倍。

2.ReHash
遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变。

让我们回顾一下Hash公式:
index = HashCode(Key) & (Length - 1)

当原数组长度为8时,Hash运算是和111B做与运算;新数组长度为16,Hash运算是和1111B做与运算。Hash结果显然不同。

参考文章

漫画:什么是HashMap?


本文作者: catalinaLi
本文链接: http://catalinali.top/2018/knowHashMap/
版权声明: 原创文章,有问题请评论中留言。非商业转载请注明作者及出处。

坚持原创技术分享,您的支持将鼓励我继续创作!