浅析JDK1.8 HashMap源码。
写在开篇
HashMap是最常用的数据结构之一，是JDK中util包下的一个集合类，基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化。
类的继承关系
1 | public class HashMap<K,V> extends AbstractMap<K,V> |
继承于抽象的AbstractMap，实现了Map，Cloneable，Serializable这三个接口。
HashMap构造函数
我们看下不带参数的构造方法：1
2
3
4
5
6
7/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
我们可以看到HashMap的构造函数中只是简单地为负载因子（loadFactor）赋了一个默认的值0.75，其他的什么都没做。
HashMap的put函数
向HashMap中插入一个键值对主要涉及到下面的三个函数：1
2
3public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在进一步了解putVal之前，我们还需要知道后面我们会讲到的table究竟是何方神圣。1
2
3
4
5
6
7/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table; //实际上table就是HashMap中的数组。
putVal函数才是真正的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
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/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
/* //调用resize()初始化数组
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //0
int oldThr = threshold; //0
int newCap, newThr = 0;
if (oldCap > 0) {
//...
}
else if (oldThr > 0)
//...
else { //初始化数组容量和阈值
newCap = DEFAULT_INITIAL_CAPACITY; //16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12（也就是map的size达到12时，就会扩容）
}
if (newThr == 0) {
//...
}
threshold = newThr; //将新阈值赋给threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//...
}
return newTab; //返回初始化的新数组
}
*/
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)))) //key值相等
e = p;
else if (p instanceof TreeNode) //p为树结点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //p为链表结点
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 尾插法插入新结点
p.next = newNode(hash, key, value, null);
//static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD - 1) // 超过TREEIFY_THRESHOLD将把链表转化为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 存在key冲突（key值相同）
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//modCount是此HashMap经过结构修改的次数
++modCount;
if (++size > threshold)
resize(); //这里的resize()是扩容的含义了
afterNodeInsertion(evict);
return null;
}
接下来我们讲讲resize扩容操作（当map的size达到threshold时，就会扩容）。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
86final 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) {
//超过HashMap的容量上限就不再继续扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新容量为原容量的2倍，新的上线为原上线的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
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;
//初始化新容量数组
({"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]不为空
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 { //按照原顺序插入链表节点（不同于jdk1.7）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/*
*(e.hash & oldCap) == 0
* 如果这个判断为true则说明e这个节点在resize之后不需要挪位置，反之则需要换个位置。
* 虽然这个代码难理解，但是自己举几个例子也能判断出来
* 比如有1，17两个数，在HashMap大小是16的时候，他们的hash值都是1，
* 如果此时扩容为32，可以看出1的hash是不变的，
* 但是17是会变，也就是说 1 & 16 = 0， 17 & 16 != 0
*/
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如何降低冲突
主要从两个地方来说明：
为什么HashMap要采用2的n次方的数量级作为数组的长度
答案是因为HashMap需要用length-1的数量级和hash值做一个与操作1
p = tab[i = (n - 1) & hash]
如果长度是17,那么length-1就是16那么与下来的值要么是0要么是16,也就是说16个槽子只用了两个槽,效率是很低的,而如果采用16(2的四次方),就是15(01111)做与操作,均匀分不到0-15的槽子上
我们可以从下面的例子中说明问题：
1 | n = 17 -> 0001 0001 |
如果长度是17,那么length-1就是16，那么与下来的值要么是0要么是16,也就是说16个槽子只用了两个槽,效率是很低的。
1 | n = 16 -> 0001 0000 |
而如果长度是16,那么length-1就是15，做与操作可以均匀分配到0-15的槽子上。
hash函数
如果是自己实现hash算法的话，最简单的话就是直接用hasCode对(n-1)取余：1
index = key.hasCode() & (n-1)
这种方法是有缺陷的，就是取余的计算结果对高位是无效的，只是对低位有效，当计算出来的hasCode()只有高位有变化时，取余的结果还是一样的。
当key计算出来的hashCode()只有高位变化时，最终算出来的index索引就会引起hash冲突，如果冲突太多的话，HashMap的效率就会非常低下了。
我们看看JDK1.8中hash算法的实现。1
2
3
4
5
6static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
index = (n - 1) & hash(key) //n表示长度
首先，对hashCode进行16位的无符号右移，然后对自身进行异或运算，最后取余。通过上面的操作，hash能够把高位的变化影响到低位的变化。
至于为什么是使用异或（^）,因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念。
HashMap的get函数
get()比较简单，直接贴源码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap的remove函数
remove()和get()差不多，通过node将查找的结点记录下，再进行删除相关的操作。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
46public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
为什么HashMap是线程不安全的
JDK1.7 HashMap中出现的死循环、数据丢失已经得到了解决，可是它仍然存在数据覆盖的问题。
在putVal()如果不存在hash冲突：
1 | if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素 |
假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完if ((p = tab[i = (n - 1) & hash]) == null)后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
putval()最后size+1的时候：
1 | if (++size > threshold) |
++size，一个最常见的线程不安全问题，还是由于数据覆盖又导致了线程不安全。
被transient所修饰table变量
最后还想提一个容易被大家忽略的点，如果大家细心阅读HashMap的源码，会发现桶数组table被申明为transient。transient表示易变的意思，在Java中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组table是HashMap底层重要的数据结构，不序列化的话，别人还怎么还原呢？
这里简单说明一下吧，HashMap并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建HashMap。有的朋友可能会想，序列化table不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化talbe存在着两个问题：
- table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
- 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。
以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap的get/put/remove等方法第一步就是根据hash找到键所在的桶位置，但如果键没有覆写hashCode方法，计算hash时最终调用Object中的hashCode方法。但Object中的hashCode方法是native型的，不同的JVM下，可能会有不同的实现，产生的hash可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个table继续操作，就会出现问题。
参考：
transient所修饰table变量 https://segmentfault.com/a/1190000012926722?utm_source=tag-newest#item-3-6
