问题描述
我们知道，当 HashMap 中的元素达到一定值（这个值称作 threshold）后，会进行扩容，扩容后，数组的长度会变成原始数组的两倍，需要把原始数组中的元素重新散列到新数组中（这个过程称作 rehash）。
例如，原始 Node 数组的长度为 16 时，哈希值为 2, 18, 34, 50, 66 的元素都会被放在数组下标为 2 的位置。扩容后，新 Node 数组的长度变为 32，这些元素将会被分别放到不同的位置：
- 哈希值 2, 34, 66 还应该放在原来下标为 2 的位置（oldCap 的偶数倍）
- 哈希值 18, 50 就应该放到下标为 18 的位置了（oldCap 的奇数倍）
所以可以把这些元素分成两部分，一部分是留在原始下标位置的，另一部分是要挪到新的下标位置的。
oldIdx = hash & (oldCap - 1)newIdx = hash & (newCap - 1) = oldIdx + oldCap
那么，如何拆分成这两部分呢？
源码分析
JDK8 源码如下，我们重点关注下半部分移动元素的部分。
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
| final Node<K,V>[] resize() {
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
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;
}
|
拆分依据
可以看到，判断一个元素是应该放在原始下标位置 oldIdx 还是应该挪到新的下标位置 newIdx=oldIdx+oldCap 的依据是：
1
| if ((e.hash & oldCap) == 0)
|
其实，用个例子演示下就明白了，还用文章开头的例子，原始数组下标为 2 的位置会有哈希值为 2, 18, 34, 50, 66 的元素，它们的二进制分别为：
1
2
3
4
5
| 16: 0001 0000
2: 0000 0010 18: 0001 0010
34: 0010 0010 50: 0011 0010
66: 0100 0010
|
左边是需要放到原始下标位置 oldIdx 的，右边是需要放到新的下标位置 newIdx=oldIdx+oldCap 的。
新链表建法
两个新链表的创建方法也比较有意思，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Node<K,V> loHead = null, loTail = null;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
|
初始是，链表头指针和尾指针都为 null，放入第一个元素后，头指针和尾指针都指向第一个元素，然后不断往尾指针后添加元素。最后，判断如果尾指针不为 null，说明链表不为空，把头指针放在数组相应位置，尾指针的 next 设为 null 表示结束。