HashMap在不同JDK版本的实现方式和源码有所区别，本文针对jdk1.8展开分析，从源码出发深入探讨HashMap插入元素及其中涉及的扩容的过程。
HashMap数据结构
HashMap本质由数组+链表/红黑树，其源码中定义了一个核心属性table（一个Node数组），Node可以理解为存储哈希表中键值对的容器。
HashMap会根据key的哈希值找到当前键值对存放在table中的下标index，当多个key位于同一个下标时（称之为哈希冲突），会采用链表的方式，将当前Node插入到链表尾端；当链表的长度超过TREEIFY_THRESHOLD时，会将链表转换为二叉查找树进行存储（HashMap采用的是红黑树）；当发现key相同时只替换value值即可。
上面提到发现”key相同“，进行key比较的时候会按照如下顺序进行比对：
- 先判断两个
key的哈希值是否相同，如果不同则两个key不同，否则继续比较
- 判断是否指向同一个引用，即是否
==，如果指向同一个引用则两个key相同，否则继续比较
- 判断
equals是否相等，如果相等则两个key相同，否则不相同
从这里我们解释为什么说“重写equals方法就一定要重写hashCode方法”？
当我们需要使用到散列结构（HashMap, HashSet等）时，如果只重写equals方法而没有重写hashCode方法，在比较key是否相同时会先进行hashCode比较，没有重写hashCode方法会导致两个equals相等的对象的hashCode不同，因此在put操作时会当做两个不同的key来处理。
HashMap插入节点和扩容
put方法源码注释：
我们可以发现put方法实际是调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法，我们先来看计算哈希值的过程：
从源码我们可以发现，计算哈希值的时候，当key为null时指定了哈希值为0，说明HashMap是允许key为null的，并且只能有一个key为null。这里和其他的哈希表不同（如HashTable,ConcurrentHashMap），其他哈希结构都是不允许key为null的。
putVal()插入节点
插入节点的步骤：
- 根据哈希值找到当前key在table数组（哈希桶）中的位置
- table数组当前位置为空，则在此处创建新Node并放在table的当前位置即可，break
- 当前位置不为空，且发现当前位置的节点是一颗红黑树，执行红黑树插入节点的操作，break
- 当前位置不为空，也不是红黑树，则当前位置只有可能是链表，执行链表的插入操作
- 遍历链表，查找是否有相同key，如果发现了相同key，则进行值替换，break
- 遍历到链表尾部，仍未发现相同key，此处创建行Node，并将其插入到链表尾部；插入节点后若发现当前链表长度超过
TREEIFY_THRESHOLD时，将链表变成红黑树，break
- 插入节点后，判断当前
size是否超过threshold，如超过进行resize()
- Return
源码分析：（详细分析过程见注释）
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
|
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 {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
resize()扩容
源码注释：
从上面注释我们可以知道，当初始化或者哈希桶大小翻倍时会执行resize()方法。
resize()方法分为两个部分：
- 重新计算
threshold及capacity
- 重新放置所有Node
第一个过程较为简单，基本过程就是table大小翻倍，然后重新计算threshold = newCap * loadFactor，源码部分涉及到很多越界处理，看着有些复杂。
第二个过程遍历旧table，将节点放入到新table对应的位置，主要分为以下几步：
旧table当前位置为空，直接跳过
旧table当前位置只有一个节点，将该节点放到新table的e.hash & (newCap - 1)位置上即可
旧table当前位置是一颗二叉树，执行红黑树的重新放置节点操作
旧table当前位置是一个长度大于1的链表
- 在链表中存在位置不变和位置往后移动
oldCap的节点，使用loHead,loTail来记录位置不变节点的头尾节点，使用hiHead, hiTail记录位置需要往后移动oldCap的头尾节点
怎么判断哪些节点位置不变，哪些需要移动？为什么是向后移动oldCap个位置？
e.hash & (newCap - 1) 代表新table的位置，且newCap = oldCap << 1，并且newCap和oldCap都是2的倍数
举例说明：
我们假定oldCap = 8（即0b1000），则newCap = 16（即0b10000）
e.hash & 0b111 表示在旧table中的位置，& 操作是对e.hash进行截断，即e.hash的后三位即代表旧位置
e.hash & 0b1111 表示在新table中的位置，同理，e.hash的后四位代表新位置
因此我们只要判断e.hash在第四位是否为0即可，如果为0，则表示新位置和旧位置一致；如果不为0，则新位置比旧位置大0b1000
结论：
e.hash & oldCap == 0 : 新位置和旧位置一致
e.hash & oldCap != 0 : 新位置比旧位置大oldCap
- 位置不动的节点通过
newTab[j] = loHead来实现；位置往后移动通过newTab[j + oldCap] = hiHead来实现
源码分析：（详细分析过程见注释）
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| 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;
}
|