HashMap是我们在开发中使用十分频繁的一个数据结构,官方文档中对其的定义如下

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

从中我们可以知道,HashMap实现了Map接口,它的keyvalue都允许是null值,它是非同步的,它不保证有序且不保证排序不随时间发生变化。

来看一下HashMap的UML图
hashmap-uml

下面开始HashMap进行源码分析,源码基于jdk1.8.0_66
首先,数据在HashMap中到底是如何存储的?

1
transient Node<K,V>[] table;

可以看到是一个Node数组,NodeHashMap的一个静态内部类

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
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/

/** 我的注释:
* 绝大部分情况下Node是该结构,在冲突较为严重时会以TreeNode存储,链表结构转化为红黑树结构
* 后面会分析这个场景
*/

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
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;
}

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

至此,我们就可以很清楚的知道,在绝大部分情况下HashMap的结构了:
它以数组的方式存储数据,数组的元素为Node类型,Node有一个next域指向下一个Node,因此数组的每个元素是一个单向链表。我把这个结构用示意图简单画出来,大概是这个样子
hashmap-structure
另外需要说明的是,我们注意到tabletransient关键字修饰,说明其不会被序列化,这样做的主要原因有2个:

  1. 理想情况下,HashMap是比较空的,会存在较多的桶位没有被使用的情况,因此序列化空的桶位意义不大。另外HashMap实现了writeObjectreadObject方法,可以自行调用这两个方法来进行序列化和反序列化。
  2. 最重要的是,由于hashCodenative方法,其依赖于JVM的实现,虽然现在基本都是使用默认的HotSpot虚拟机,但是还是有个别其他情况。因此如果hashCode方法的实现不同,那么生成的hash码就是不同的,那么经过序列化和反序列化之后,就会导致在不同的JVM中,虽然table中的Node分布是相同的,但是由于同一个keyhash码不同,其在table中的索引就不同,在进行putget时,必然会发生同一个key返回不同的value,这显然是不正确的。writeObject仅仅写入了一些HashMap的基本信息如sizecapacity,以及每个Nodekeyvalue,并不写入和hash有关的信息,readObject则是通过这些数据重新创建HashMap的实例对象。这样的设计很好的避免了上面所说的问题。具体可以去看这两个方法的源码实现。

再来看HashMap中几个较为重要的参数

参数名 含义
DEFAULT_INITIAL_CAPACITY table的默认初始化容量,即table数组的长度,值为16,
DEFAULT_LOAD_FACTOR 默认的负载因子,值为0.75,当Node的数量大于capacity * load factorHashMap会进行resizetable的长度调整为原来的2倍
TREEIFY_THRESHOLD 值为8,链表的长度大于8时会转换成红黑树
UNTREEIFY_THRESHOLD 值为6,当红黑树的节点个数小于6,则会退化成链表
MIN_TREEIFY_CAPACITY 值为64table数组的长度大于64时才有可能从链表转红黑树,否则只会进行resize

有了上面的概念,接下来我们可以开始来看HashMap的几个重要的方法了。

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
public V put(K key, V value) {
// 计算key的hash
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
// 将通过hashCode方法得到的hash码的高16位和低16位进异或操作,可以有效减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict)
{

Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table不存在或者长度为0,那么进行初始化,resize方法下文会分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// n为table长度,(n - 1) & hash相当于 hash % n,
// 确定数组的下标后,如果该位置为null,则创建Node并将其放置在该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 节点存在
else {
Node<K,V> e; K k;
// p = tab[(n - 1) & hash]的Node的key就是我们要找的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// p为红黑树节点,则在红黑树中进行插入,暂不去探究在红黑树中的节点插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// p为链表节点,遍历链表
else {
for (int binCount = 0; ; ++binCount) {
// 如果当前节点没有next节点,则创建一个Node作为其next节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果节点个数已经大于TREEIFY_THRESHOLD,则转为红黑树,链表转化成红黑树的代码实现暂不去探究
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到了key,则停止寻找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e不为空说明是key已经存在,只需更新value即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// HashMap的修改次数 + 1
// 其他线程在迭代HashMap时发现modCount变化,则会抛出ConcurrentModificationException,fail-fast机制
++modCount;
// HashMap中的Node个数超过了threshold = load factor * capacity,进行resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

put方法的代码到这里基本就分析完了。

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
24
25
26
27
28
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) {
// first = tab[(n - 1) & hash]的key就是要找的key,直接返回它
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// first有next节点
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;
}

resize方法

resize方法的设计十分巧妙,这要得益于HashMap的一切几乎都和2的幂有关。
来看JDK官方文档中对resize的说明

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold.Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

重点就是,因为我们使用2的幂,所以每个元素的位置要么是和原来的位置相同,要么就是移动2的幂的偏移量(这个偏移量其实就是原tablelength
为什么可以这样,分析一下就很容易理解。
我们用(n - 1) & hash计算元素所在table的索引
假设tablelength16

操作数名称 操作数值 &结果
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0010 0001 0001 0101 5
hash2 1111 1111 1111 1111 0010 0001 0000 0101 5

现在要扩容到32

操作数名称 操作数值 &结果
n - 1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0010 0001 0001 0101 21
hash2 1111 1111 1111 1111 0010 0001 0000 0101 5

容易看出,扩容为2length后,n - 1的高位多了一个1,从而进行&运算后,对hash也多取了一个高位,而hash的该位置要么为0,要么为1,所以&运算的结果要么不变,要么加上一个offset,这就有了上面的结论。而hash的高位是1还是0也是随机的,因此进行扩容后,原本hash冲突的节点就能够很均匀的分散开来。
hashmap-expand

下面来看源码的实现

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
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倍,threshold也变为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) {
// 遍历table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 没有next节点,直接进行&运算后得到索引,将其放到新的table
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果是红黑树节点
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 遍历该索引处的链表
else { // preserve order
// 高位为0时的链表头和链表尾
Node<K,V> loHead = null, loTail = null;
// 高位为1时的链表头和链表尾
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// hash&上原table的length,来校验hash的高位是否为1
// 高位为0,插入到对应的链表中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 高位为1,插入到对应的链表中
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 高位为0的链表,索引没有变化,将新的链表放置在新的table的原索引处
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位为1的链表,索引需要加上原table的length,再将新的链表放置到该处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

总结

这篇文章主要分析了HashMap的三个方法,分别是putgetresize,经过分析我们可以比较清楚的理解HashMap的工作原理。HashMap的基于2的幂的巧妙设计,使得HashMap的扩容时的效率很高。
本文对于红黑树部分的源码没有去深究,但我们知道通过将链表转成红黑树,可以将查找的效率由O(n)提升到O(log n),这也是Java 8对于HashMap重大的效率改进之一。
我们在使用HashMap时,如果能对元素个数有一个预估,并在初始化的时候进行指定,就能够避免HashMap扩容的不必要的开销。在多线程的场景下,我们应该使用ConcurrentHashMap来替代HashMap,对于ConcurrentHashMap以后也会专门写一篇文章来分析。

参考资料
Java HashMap工作原理及实现
Java 8系列之重新认识HashMap