java 对HashMap扩容的简单分析

HashMap如何进行扩容?HashMap的容量为什么是2的幂次?

参考:http://tech.meituan.com/java-hashmap.html

http://blog.csdn.net/t894690230/article/details/51329017

一、为什么需要扩容

java 对java8中HashMap的简单分析

在上篇文章中提到了这个问题:

“如果HashMap中的数组很大,即使较差的hash算法也会比较分散。如果数组很小,即使好的hash算法也会出现较多碰撞。”

“所以,应该具体情况具体分析,通过优秀的hash算法和扩容算法配合,保证数据均匀分布,尽量减少hash碰撞(hash碰撞直接导致链表变长)。”

扩容有两个目的,一是保证HashMap中有足够的容量装载元素,二是保证HashMap中的元素均匀分散,减少碰撞。

二、历代HashMap的扩容方法

(1)参数理解

首先应该了解HashMap中的重要参数(扩容依据):

首先,Node<k,v>[] table的初始化长度length(默认值是16),loadFactor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。

threshold = length * loadFactor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

结合负载因子的定义公式可知,threshold就是在此loadFactor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。

默认的负载因子0.75是对空间和时间效率的一个平衡选择,除非在时间和空间比较特殊的情况下,否则建议不要修改。如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

(2)何为快速失败?何为安全失败?

来自:https://www.cnblogs.com/ygj0930/p/6543350.html

1、快速失败

在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

1.原理

迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

2.注意

这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时,修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。

因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的bug。

3.场景

java.util包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)。

2.安全失败

采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。

1.原理

由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。

2.缺点

基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

举个例子,如果我开始遍历一个ConcurrentHashMap,在遍历过程中我对这个ConcurrentHashMap做的所有修改,都不会在ConcurrentHashMap中体现。

3.场景

java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

(3)Jdk1.6

在jdk1.6中,HashMap的构造函数中有如下代码:

这是阈值的计算公式,其中capacity(容量)默认值为16,loadFactor(负载因子)默认值为0.75,可以计算阈值为:

使用addEntry方法插入元素时,如果数量超过12,就会发生扩容:

把阈值和元素数量进行比对。如果有需要,直接把数组容量*2。

在看jdk1.6的源码的时候,我有种“简单粗暴”的感觉。当时的插入还是“头插法”,先插入再扩容。对比如今的源码,感觉Jdk的进步难以想象。

(4)Jdk1.7

在jdk1.7中,HashMap的构造函数中有如下代码:

对比jdk1.6中的方法,可以发现这里把第一次计算阈值的操作省了下来,直接给threshold进行赋值(initialCapacity的数值与之前第一次计算阈值的大小一样)。

计算阈值的方法也有变化:

通过比较计算得来的阈值和最大允许值,防止扩容出现问题。

addEntry方法也发生了变化:

这里有个明显的优化:在插入元素前先判断当前bucket是否为空,如果为空,则直接插入元素,暂时不进行扩容。

扩容的初衷之一是“保证HashMap中有足够的容量装载元素”,如果当前bucket为空,当然要尽量利用空间。

(5)Jdk1.8

在jdk1.8中,HashMap发生了很大的变化,构造函数中有如下代码:

查看tableSizeFor方法:

写个程序来验证位运算的结果:

TestBitwise.java

结果为:

无论输入值为多少,阈值一定为2的n次方。这个设计是有目的的,在下面会提到。

查看putVal方法,发现扩容操作变为了resize方法(重排序方法?):

可以看到,putVal方法中判断是否达到阈值与jdk1.6是相同的,没有像jdk1.7中那样判断当前bucket是否不为空(这是因为resize方法做了改变)。

调用的resize方法非常复杂,不再是简单的阈值 * 2(jdk1.8的HashMap中引入了红黑树优化,扩容复杂了很多),这里不做详细解读:

三、HashMap的容量为什么是2的幂次?

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。

相对来说素数导致冲突的概率要小于合数,具体证明可以参考:

http://blog.csdn.net/liuqiyao_01/article/details/14475159

Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。

HashMap采用这种非常规设计,主要是为了在取模(计算bucket)和扩容(resize)时做优化。

(1)位运算的优化

HashMap中的数据结构是数组+单链表的组合,我们希望的是元素存放的更均匀,最理想的效果是,数组中每个位置都只有一个元素。这样查询的时候效率最高,不需要遍历单链表,也不需要通过equals去比较K,而且空间利用率最大。

那如何计算才会分布最均匀呢?我们首先想到的就是%运算,哈希值 % 容量 = bucketIndex,看一下jdk1.8中的源码:

可以发现,使用了位运算的“&”代替了取模。

当容量一定是2的幂次时,h & (length – 1) == h % length,这两种做法是等价不等效的,位运算效率更高。

举个例子,假设当前HashMap中容量为32(2的5次方),length为32,hash值为100,那么100 & (32 – 1) 肯定等于 100 % 32 等于 4。但是,如果容量不为32(举个例子:3的3次方27),就无法通过“&”进行取模运算,效率将变低。

(2)resize的优化

看一下resize方法的部分代码:

可以发现,在resize中需要计算bucket位置的代码全都是位运算。理由同上。

(3)查找bucket的位置(寻址)

参考:https://www.zhihu.com/question/20733617

我们查看这个方法:

这里的n为当前数组大小。如果数组大小正好为2的n次幂,那么n-1正好相当于一个“低位掩码”,和hash值进行了“&”操作之后,就能得到bucket的位置。

这说明了,HashMap的容量之所以是2的幂次,是由寻址算法决定的。

四、总结

简单分析,有机会将详细分析resize方法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注