我们都知道Java中的HashMap是使用数组，结合链表来实现的，其结构如下：
如果加入的元素数量达到了设定的阈值，那么必然会涉及到扩容重新分配空间，将元素重新插入到新的空间中，也就是发生了rehash。这个过程其实是很耗时的，这也是为什么我们写代码时，最好指定的HashMap的初始空间大小的原因，就是为了避免或者减少发生rehash的次数。下面我们来看看这个过程的具体实现。
JDK是一直在升级的，其中的代码也在不断优化调整，我们这次主要就看下JDK1.7和 JDK1.8中的实现
JDK1.7
了解实现就免不了看源码，我们先来看下put方法的主要源码（为了方便阅读，省略了部分代码）
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
| public V put(K key, V value) {
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
|
如果大家对上面的大段代码比较头疼，我就用文字来简单概括一下：
当map中的元素数量达到阈值时，会重新创建一个新的数组，长度为旧数组的两倍(如果长度没有达到上限的话)，这时会依次对旧数组(包括其中的链表)按顺序重新计算索引插入，之后重新赋值引用即可
而我们通常说的HashMap线程不安全，其实主要原因就在上面transfer方法中的链表处理逻辑里
简单描述一下，就是当一个线程1持有链表中的一个元素e和下一个元素的引用next时，如果此时当前线程时间片用完
这时另一个线程2启动，它将整个链表重新rehash完毕，碰巧这几个链表元素还在同一个索引位置，因为链表插入使用头插入，这时的链表顺序和之前就是相反的
此时如果线程1启动，很明显的它持有的e和next位置被调换了，next竟然会持有e的引用，这时继续处理的结果就是在这两个元素之前成环状，一旦调用get方法处理到这个地方，就会发生死循环
主要的思路就这些，大家如果有兴趣可以继续查看一下其它的资料
下面我们接着来看JDK1.8的rehash
JDK1.8
JDK1.8的HashMap相比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
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
| public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
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 TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
我们具体看下其中的链表处理部分，把这部分代码拿出来分析一下
在这之前，我们需要先证明一个结论：
HashMap rehash重新计算索引后，新索引要么等于原索引位置，要么等于原索引值+原数组大小
说一下HashMap的几个相关知识点
- HashMap的数组大小一定是2的N次幂（这是由HashMap自己保证）
- HashMap的索引计算方式为 hash(key) & (size - 1)，由1可知，size-1的二进制低位都为1
- HashMap扩容时一般为增大一倍，即size = size * 2，相当于 size = size << 1
其实hash(key) & (size -1)，由于size-1在范围内的值二进制都是1，所以结果就是hash值在数组范围内的值，size值影响的只是取hash值的低位二进制的位数而已，它本身相当于不参与计算。如果不太好理解，再举个例子
如果size=16，size-1的二进制就是1111，与hash结果进行按位与运算，就是取hash结果自己的低4位值
而如果扩容后size=32，size-1的二进制就是11111，与hash结果进行按位与运算，就是取hash结果自己的低5位值
这样其实我们就可以得到之前的结论了，对于上面的例子，如果hash结果的倒数第5位是0，那么重新hash后他还在原位置，否则就会在原基础上增加的二进制值是10000（oldSize），即 oldIndex + oldSize
准备工作已经结束，下面我们来分析这部分代码
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
|
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
|
总结一下1.8的链表处理部分，因为rehash后新索引只有两种情况
- newIndex = oldIndex
- newIndex = oldIndex + oldSize
这个可以通过(e.hash & oldCap) == 0判断，在遍历链表的过程中，使用尾插法(保证前后顺序)将链表分组插入到临时链表中，最后再将链表引用赋值到对应的数组空间中
这种方法其实就解决了1.7中的链表rehash成环的问题
好了，基本内容就是这些，如有错误之处，欢迎指正～