EUAdvancer

Java8-HashMap源码详解

bg
jdk1.8中HashMap源码的读后感

HashMap的数据结构

首先大致介绍HashMap的整体结构。HashMap = 数组 + 链表 + 红黑树

类的定义

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

这里出现一个很奇怪的现象,我们查看AbstractMap类的定义,可以发现它已经实现了Map接口

1
public abstract class AbstractMap<K,V> implements Map<K,V>

那么为什么HashMap还要再实现一遍呢?好吧,这显然是个设计错误

来源:https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete

Q: Why does LinkedHashSet extend HashSet and implement Set?

A: I’ve asked Josh Bloch, and he informs me that it was a mistake. He used to think, long ago, that there was some value in it, but he since “saw the light”. Clearly JDK maintainers haven’t considered this to be worth backing out later.

这里再贴出Map接口的类继承图

其中HashMap,TreeMap均继承自AbstractMap类,实现Map接口

节点类

链表的每个节点类的定义如下,它是个内部类(不是内部类也不能用static来修饰类),包含键值对

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
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 该节点的hash值,hash(key)的结果
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// 比较两个节点相等需要key和value均相等
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

put操作

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

计算哈希桶数组索引位置

首先通过key计算hash值,代码如下

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

该操作将key的hashcode值进行高16位和低16位异或,并且将其结果作为key的最终hash值。那么为什么要这么做呢,这要定位到确定索引的取模操作上

1
2
3
4
//jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
static int indexFor(int h, int length) {
return h & (length-1);
}

在这里采用了与操作代替了通过hash值对数组长度取模运算得到索引的方式,因为取模运算性能不高。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。问题出现在与运算将hash值的高位全部归零,只保留低位值用于数组下标访问。也就是说高位并不参与计算,这也导致即使hashCode映射再均匀,每次却只有低位能够参与计算,使得碰撞严重,因此将key的hashcode值进行高16位和低16位异或结果作为key的最终hash值

插入逻辑

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict)
{

// 定义了数组tab,p为当前key映射到的桶的头结点,n为数组大小,i为key映射的桶的索引
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;
// 如果头结点的key和当前key相同,则覆盖value
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) {
// 如果不存在相同key的节点,则新建节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果节点个数超过8个则将链表转为红黑树(如果tab的大小小于64则不转红黑树,而是resize扩容)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 构造红黑树
treeifyBin(tab, hash);
break;
}
// 如果存在相同key的节点,则覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改记录+1,用于迭代器快速失败
++modCount;
// 如果当前tab中含有的键值对大于阈值则对tab进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

总结put逻辑如下:

  1. 如果tab数组为空,则通过resize()扩容
  2. 计算该key映射的桶数组索引i,如果该桶(tab[i])没有节点,则直接插入节点
  3. 如果该桶(tab[i])有节点,则首先比较tab[i]的头结点的key和该key是否相同,相同则覆盖value
  4. 判断该桶的链是否为红黑树,如果是则直接向红黑树插入节点
  5. 如果是链表,则遍历链表,如果存在节点的key和该key相同则覆盖value,否则在链表尾插入新节点【然后判断链表长度是否大于8,如果大于则将链表转为红黑树】
  6. 如果当前tab中含有的键值对大于阈值,则扩容

扩容

resize操作在java1.8稍微有些复杂和难以理解,所以需要先从java1.7源码的resize说起

1
2
3
4
5
6
7
8
9
10
11
12
13
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { // 扩容前的数组大小如果已经达到最大则不再扩容
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity]; // 初始化一个新的Entry数组
transfer(newTable); // 将数据转移到新的Entry数组里
table = newTable; // 引用新数组
threshold = (int) (newCapacity * loadFactor);// 修改阈值
}

所以其实在java1.7中扩容操作很好理解,创建一个新容量的数组,然后将老数组的节点全部重新映射到新数组中,最后修改阈值。节点映射过程如下(遍历每个节点,重新计算节点在新数组的位置并插入):

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) {
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);
}
}
}

那么java1.8做了哪些改变呢?

  • 扩容为原来的两倍
  • 不需要重新计算每个节点在数组中的位置
  • 插入新节点不头痛头插入方式,而是直接插在链表尾上
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
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;
}
// 扩容为原来的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);
}
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) {
// 遍历旧的tab数组
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 { // preserve order
// 这里有两点改变
// 1. 新节点插在链表尾上
// 2. 不再计算节点映射的索引,而是判断节点在新数组映射的位置要么是在原位置,要么是在原位置再移动老数组长度的位置“
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;
}
// 旧链表中将会映射到原索引位置+oldCap的位置的节点组成一个链表
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;
}
// 将会映射到原索引位置+oldCap的位置的链表插入桶
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

关于不用再计算节点在新数组中映射位置的原理是:数组n长度扩为原来2倍,那么n-1的mask范围在高位多1bit(红色),因此结果只有两种,原位置或原位置+老数组长度(更多的证明就需要再去查看相应的解释了)

get操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public 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;
}

get操作思路非常清晰:

  1. 计算key的映射的桶数组索引i,如果该桶(tab[i])没有节点,则返回null
  2. 比较该桶的头结点和key和该key是否相同,如果相同则返回头结点的值
  3. 遍历该桶所有的节点,如果存在key相同的节点,则返回该节点的value,否则返回null

非线程安全

比如两个线程均向hashmap进行put操作,这时候刚好hashmap需要resize扩容,resize操作在节点从老数组映射到新数组的过程中有个单链表的头插法操作

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) {
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);
}
}
}

这个时候两个线程同时扩容就容易导致两个线程同时改变同个节点进行头插法就易导致出错,易形成环形链表

参考