深入 Java 中的 HashMap (二)

文章目录
  1. 1. 扩容机制
  2. 2. 线程安全性
  3. 3. 参考文献

我们一定要过一段无怨无悔的人生,将来一定要出海,然后随心所欲的活着,比谁都要自由。

上一篇深入 Java 中的 HashMap (一)中,对 HashMap 作了简单的介绍,着重分析了其存储 put() 和读取 get()。这一篇主要谈谈 HashMap 的扩容机制和线程安全性。

扩容机制

扩容 (resize) 即重新计算并扩大容量。

当向 HashMap 对象里不断地添加元素,其中的元素会越来越多,hash 冲突的几率便越来越高。HashMap 内部的数组不再能装载更多的元素时,就须扩大数组的长度,以放下更多的元素。注意的是,Java 里的数组没法自动扩容,只能以一个新的容量大一点的数组,去代替需要扩充的容量小的数组。

由于 JDK 1.8 中囊括了红黑树,先以 JDK 1.7 的源码来作分析如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void resize(int newCapacity) {
// 扩容前的 Entry 数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 判断扩容前的数组大小是否达到 2^30
if (oldCapacity == MAXIMUM_CAPACITY) {
// 赋阈值为 int 的最大值 (2^31 - 1),则以后不再扩容
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
// 数据转移到新的 Entry 数组里
transfer(newTable);
// table 引用新的 Entry 数组
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}

可以看出,这里用一个容量更大的数组,来替代已有的容量小的数组。其中,transfer() 方法将老的 Entry 数组的元素,转移到新的 Entry 数组如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
// 遍历旧的 Entry 数组
for (int j = 0; j < src.length; j++) {
Entry<K, V> e = src[j];
if (e != null) {
// 清空旧 Entry 数组里的对象引用
src[j] = null;
do {
Entry<K, V> next = e.next;
// 重新计算每一元素在数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
// 访问后一个 Entry 链上的元素
e = next;
} while (e != null);
}
}
}

着重看 do{} 体内的代码,newTable[i] 的引用赋值给 e.next,以单链表的头插入方式,同一位置上,新元素总会被放在链表的头部;这样,若发生 hash 冲突,则先放在一个索引上的元素,最终会被放到 Entry 链的尾部,注意,JDK 1.8 与此不同;此外,旧数组中,同一条 Entry 链上的元素,重新计算索引位置后,有可能被放到新数组的不同位置上。

举例之前,先谈一谈由 key 获取哈希桶数组的索引位置

添加、删除或查找键值对时,首要的就是要定位到哈希桶数组的位置。我们知道,HashMap 的数据结构是数组加上链表。理想情况下,希望 HashMap 里的元素位置分布均匀,甚至使得每个位置上只有一个元素,以便于用 Hash 算法求位置时得到对应位置上要的元素。避免了遍历链表,优化其查询的效率。着重看下面两个方法:

1
2
3
4
5
6
static final int hash(Object key) {
int h;
// I. 取 key 的 hashCode 值,即 h = key.hashCode()
// II. 高位运算,即 h ^ (h >>> 16)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4
5
// 存在于 JDK 1.7 中,JDK 1.8 无
static int indexFor(int h, int length) {
// III. 取模运算
return h & (length - 1);
}

总结 Hash 算法即三部曲:取 key 的 hashCode 值高位运算取模运算

任意给定一个对象,若其 hashCode() 返回值相同,则调用以上 hash() 得到的 hash 值是相同的。hash 值对数组长度取模运算,如此,元素的分布相对来说较均匀,不过,模运算消耗较大。HashMap 中,调用 indexFor()以计算对象保存在 table 数组里的索引位置。扩展来说,其通过 h & (length - 1) 获取对象的保存位,由于 HashMap 底层数组的长度为 2^n,h & (length - 1) 运算等价于对 length 取模,即 h % length,注意的是,& 比 % 有更高的效率。

比较来看,JDK 1.8 中,(h = k.hashCode()) ^ (h >>> 16) 即 hashCode() 的高 16 位异或低 16 位实现,优化了高位运算的算法。如此,可以在数组 table 的 length 比较小的时候,同时保证考虑到高低位 bit 都参与进 hash 的计算中,且开销不会太大。

以上说明示意图如下:

好,举例说明下扩容过程。假定 hash 算法是简单地用 key mod 一下表的大小,即数组的长度。其中,哈希桶数组 table 的 size = 2,故 key 分别为 3、7、5,put 顺序依次为 5、7、3,mod 2 后都在 table[1] 里产生冲突。这里,假设负载因子 loadFactor 为 1,即当键值对的实际大小 size 大于 table 的实际大小时扩容。接着,哈希桶数组 resize 成 4,而后,所有的 Node 重新 rehash。示意图如下:

作为对比,看 JDK 1.8 中,使用的是 2 次幂的扩展,即长度扩为原来的 2 倍,故元素的位置是在原位置或在原位置再移动 2 次幂的位置。示例图如下,n 为 table 的长度,图一为扩容前 key1 和 key2 两种 key 确定索引位置的示例,图二为扩容后 key1 和 key2 两种 key 确定索引位置的示例。其中,hash1 是 key1 对应的哈希与高位运算的结果。示意图如下:

元素在重新计算 hash 后,由于 n 变为 2 倍,则 n -1 的 mask 范围在高位多 1 bit(为红色),index 发生的变化如下:

总结即,在扩充 HashMap 的时候,不需要像 JDK 1.7 的实现那样重新计算 hash,只需看原来的 hash 值新增的 bit 是 1 还是 0 就好,0 的话索引没变,1 的话索引为“原索引 + oldCap”。如此,省去了重新计算 hash 值的时间,同时,新增的 1 bit 是 0 还是 1,认为是随机的,故 resize 的过程,均匀地将之前冲突的节点分散到新的 bucket,即为 JDK 1.8 新增的优化点。另外注意的是,JDK 1.7 中 rehash 的时候,旧链表迁移新链表的时候,若在新表的数目索引位置相同,那么链表元素会倒置,但是 JDK 1.8 中,不会发生倒置。对照看 JDK 1.8 中 resize 的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
final HashMap.Node<K, V>[] resize() {
// 旧数组的引用
HashMap.Node<K, V>[] oldTab = table;
// 旧数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧数组的阀值
int oldThr = threshold;
// 新数组长度、新的阀值
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值不再扩充,任由其碰撞
if (oldCap >= MAXIMUM_CAPACITY) {
// 阀值改到最大,直接返回旧数组
threshold = Integer.MAX_VALUE;
return oldTab;
// 没超过最大值,则扩充为原来的 2 倍
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的 resize 上限
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
// 更新阀值
threshold = newThr;
@SuppressWarnings({"rawtypes", "unchecked"})
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
// 每个 bucket 移动到新的 buckets 中
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K, V> e;
if ((e = oldTab[j]) != null) {
// 原来的引用取消,方便垃圾回收
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
// 原来的 hash 值新增的 bit 为 0 的链,头部和尾部
HashMap.Node<K, V> loHead = null, loTail = null;
// 原来的 hash 值新增的 bit 为 1 的链,头部和尾部
HashMap.Node<K, V> hiHead = null, hiTail = null;
HashMap.Node<K, V> next;
do {
next = e.next;
// 原来的索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
// 原来的索引 + oldCap
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原来的索引放到 bucket 中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原来的索引 + oldCap 放到 bucket 中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

线程安全性

多线程中,避免使用线程不安全的 HashMap,而使用线程安全的 ConcurrentHashMap。扩展来说,即 HashMap 是只读的时候,加载一次,以后只有读取,不会发生结构上的改变;但是,若 HashMap 是可写的时候,则会发生结构上的修改,会引发诸多问题。下面举实例,在并发的多线程使用场景中,使用 HashMap 会造成死循环(基于 JDK 1.7):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class HashMapInfiniteLoop {

private static HashMap<Integer, String> map = new HashMap<>(2, 0.75F);

public static void main(String[] args) {
map.put(5, "C");

new Thread("Thread1") {
@Override
public void run() {
map.put(7, "B");
System.out.println(map);
}
}.start();

new Thread("Thread2") {
@Override
public void run() {
map.put(3, "A");
System.out.println(map);
}
}.start();
}

}

代码中看到,map 初始化为一个长度为 2 的数组,同时,loadFactor = 0.75,threshold = 2 * 0.75 = 1,则当往 map 中 put 第二个 key 时,map 就需要扩容(resize)。如此,运行便出现了死循环的问题。

至此,深入 Java 中的 HashMap (二) 分析到此完毕。

本人才疏学浅,如有疏漏错误之处,望读者中有识之士不吝赐教,谢谢。

1
Email: [email protected] / WeChat: Wolverine623

您也可以关注我个人的微信公众号码农六哥第一时间获得博客的更新通知,或后台留言与我交流

参考文献

1.https://tech.meituan.com/java-hashmap.html

2.https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html