集合类 HashMap 最早出现在 JDK 1.2 中,底层基于散列算法(也称哈希算法)实现。HashMap 中允许 null 键和 null 值,且 null 键的哈希值为 0。HashMap 并不保证键值对的顺序,即随着对集合的操作,键值对的顺序可能会发生变化。并且 HashMap 是非线程安全类,在多线程环境中可能会存在问题。

此篇文章分析一下 JDK 1.8 中的 HashMap。

一、底层数据结构

HashMap 底层是基于散列算法实现,为解决哈希冲突,散列算法又分为散列再探测和拉链式。HashMap 中使用了拉链式的散列算法,并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下:

hashmap_data_structure

对于拉链式的散列算法,其数据结构是由「数组 + 链表(或树形结构)」组成。在进行增删改查等操作时,首先要定位到元素的所在桶的位置,之后再从链表中定位该元素。

在 HashMap 的实现中,用一个 Node 类型的数组,即成员变量 Node<K,V>[] table 表示这个底层存储的桶数组。桶数组中的每个元素(桶)都是一个 Node 节点。Node<K,V> 是 HashMap 的一个内部类,其定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
static class Node<K,V> implements Map.Entry<K,V> {
/** 哈希值,用来定位数组索引位置 */
final int hash;
/** key 键 */
final K key;
/** value 值 */
V value;
/** 下一个节点 */
Node<K,V> next;

// ...
}

可以看出,桶数组中的每个元素 Node 要么为空,要么是一个链表的头节点或者红黑树的根节点,根据节点中的 next 指针可以找到后面的节点元素,且后面节点元素的 hash 值均是相同的,即 HashMap 中的每个元素最终都存储为一个 Node 对象。

上面就是 HashMap 底层数据结构的原理,HashMap 的基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树解决长链表效率低的问题,底层数据结构变为了 「数组 + 链表 / 红黑树」,实现的复杂度多了一些。

二、构造方法和成员变量

HashMap 中有四个构造方法,构造方法中仅仅是初始化了一些重要的成员变量,比如 loadFactor 和 threshold,而底层的数据结构则是延迟到插入 key-value 键值对时再进行初始化。相关构造方法如下:

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
/** 构造方法 1,创建一个初始容量为默认容量 16 的 HashMap 对象 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/** 构造方法 2,创建初始容量为指定 initialCapacity 的 HashMap 对象 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/** 构造方法 3,创建初始容量为 initialCapacity、指定负载因子为 loadFactor 的 HashMap 对象 */
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 设置 loadFactor 变量值
this.loadFactor = loadFactor;
// 计算并设置 threshold 阈值
this.threshold = tableSizeFor(initialCapacity);
}

/** 构造方法 4,根据其它 Map 创建 HashMap 对象 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

上面的四个构造方法中,除了创建 HashMap 对象外,还涉及到初始容量 initialCapacity、负载因子 loadFactor 和阈值 threshold 这三个变量的初始化设置。

1. 初始容量、容量capacity和大小size

我们已经知道,HashMap 底层的数据结构是「数组 + 链表/红黑树」,这里数组的实现就是桶数组 Node<K,V>[] table 。所以,这里的容量 capacity 实际上就是这个桶数组 table 的大小,即 table.length ,表示这个桶数组最多可以装多少个「桶」。

这个容量的默认值为 16,或者根据用户指定的初始容量 initialCapacity,找到大于或等于 initialCapacity 的最小的 2 的幂(参见 tableSizeFor() 方法),将这个值作为 HashMap 的容量,也就是 table 数组的大小,且这个值一定会是 2 的整数次幂

而大小 size 则表示这个 HashMap 中已经装了多少个元素(key-value 键值对)。HashMap 的底层桶数组 table 中的每个桶可以是一个链表的头节点或者红黑树的根节点,每个链表或者红黑树中也可能会有多个 key-value 键值对,所以容量 capacity 和大小 size 是两个意义不同的概念。如下图所示:

hmap_capacity_size

2. 负载因子和阈值

在 HashMap 中查找元素能够有 O(1) 的时间复杂度,是因为根据下标访问 table 数组中的桶元素是 O(1) 的。但是由于哈希冲突,当每个桶中的元素较多,形成链表或者红黑树时,查找的时间复杂度就退化成了 O(n) 或 O(logn),所以应减小哈希碰撞的概率,尽量让元素(键值对)存储在桶数组上,避免落在延伸的链表或红黑树上。

如果 HashMap 中已存放的元素数量与桶数组 table 的容量(table.length)相比,显得比较大的话,那么即使再好的 Hash 算法,也容易出现哈希碰撞。所以 HashMap 容器不能装的太满,如果桶数组容量较大,而实际存储的元素较少,这样发生哈希碰撞的概率就会变小,Map 的存取效率就会更高。所以就需要在空间成本和时间成本之间进行权衡。

于是便引入了负载因子(loadFactor)用来衡量 HashMap 容器满的程度,用阈值(threshold)表示 HashMap 中最多能存储的元素(键值对)的个数,且 threshold = capacity * loadFactor

负载因子 loadFactor 的默认值为 0.75,这个值在时间和空间成本之间提供了很好的权衡。也就是说默认情况下,HashMap 中的元素个数最多为容量的 3/4,超过了这个值就会触发扩容机制

三、查找

HashMap 中的 get() 方法通过 key 来查找元素,源代码如下:

显示代码块

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;
// 1. 定位键值对所在桶的索引位置
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) {
// 2. 如果 first 是 TreeNode 类型,则调用黑红树查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);

// 2. 对链表进行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

由上可知,调用 get() 方法时,需要先计算出 key 对象在 HashMap 中的 hash 值,然后调用 getNode() 方法查找元素。在 getNode() 方法中,用前面计算的 hash 值进行模运算取余,得到 key 对应元素在桶数组中的索引位置,然后通过桶节点中的 next 指针遍历链表或者红黑树进行查找,直到找到目标元素。

可以看出,HashMap 查找元素的时间复杂度为 O(1),是因为它是基于下标访问数组的;但是在极端情况下,遍历链表或者红黑树时,可能会退化为 O(n) 或 O(logn) 的时间复杂度。

1. 确定桶的索引位置

那么在桶数组中如何确定某一元素(桶)的索引位置呢?直接用 hashCode 不行吗?

通过代码 key.hashCode() 可以得到 key 对象本身的散列码,这是一个 int 型的整数,最大值为 231-1,约等于 21 亿。如果直接用这个散列值作为下标访问 HashMap 主数组的话,大概会有 21 亿的映射空间,一方面内存中放不下这么大的数组,另一方面基本也不会用到这么大的 HashMap。

所以这个原始的散列码是不能直接拿来用的,用之前还需要与数组的实际长度进行模运算,得到的余数才能用作访问数组的下标。源码中的模运算代码如下:

1
2
3
4
5
// 桶数组的长度
int n = table.length;

// 根据 hash 值计算桶的索引位置
int bucketIndex = (n - 1) & hash;

这里计算索引的代码很简单,就是把散列值与数组长度做一个「与运算」,这样更加高效。那么,通过与运算怎么实现的呢?

因为 HashMap 中桶数组的长度为 2 的整数次幂(参见前文对容量的介绍),即二进制表示中最高位为 1,其余低位均为 0。所以「数组长度 - 1」正好相当于一个「低位掩码」(低位全为 1,高位全为 0)。这样,通过与运算将散列值的高位全部归零,从而屏蔽掉高位,只保留低位值,将运算结果用作访问数组的下标,即桶的索引位置。

以默认长度 16 为例,16 - 1 = 15,二进制表示 00000000 00000000 00000000 00001111 只有低 4 位为 1。和某个散列值进行与运算(同 1 为 1,有 0 则为 0)如下:

1
2
3
4
	00110101 10110101 11010100 01001010
& 00000000 00000000 00000000 00001111
----------------------------------------
00000000 00000000 00000000 00001010 // 高位全部归零,只保留了末 4 位

结果就是只截取了最低 4 位的值,这个值就是桶数组中桶的索引(数组下标)。

但这时候问题就来了,这样就算散列值分布再松散,计算结果只与低位信息有关,哈希冲突也会很严重。而且如果散列值在分布上成等差数列,恰好使最后几个低位呈规律性重复,碰撞就会更加严重。此时一个好的哈希函数、一个好的 hash 值就显得格外重要,于是「扰动函数」的价值就体现出来了。

2. 计算哈希值

HashMap 中计算哈希值的 hash() 方法代码如下:

1
2
3
4
5
6
7
static final int hash(Object key) {
int h;

// 1. h = key.hashCode(),取 key 对象的 hashCode 值;
// 2. h ^ (h >>> 16),高 16 位与自身进行异或运算。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这段计算 hash 值的代码也称为「扰动函数」,既保证了运算的高效性,也保证了 hash 值的离散性,减小了哈希冲突的概率。

代码 h ^ (h >>> 16) 中,右移 16 位刚好是 int 型整数 32 位的一半,然后将自己的低位半区与高位半区进行异或运算(相同取 0,相异取 1),这样混合原始哈希码的高位与低位,加大了低位信息的随机性,也变相的保留了高位数据的一些信息。例如下图这个例子:

hashmap_hash_index

四、插入

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; // table 桶数组
Node<K,V> p; // 对应位置的 Node 节点
int n; // 数组大小
int i; // 对应桶在 table 数组中的索引位置

// <1> 如果 table 未初始化,或者容量为 0 ,则进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize() /*扩容*/ ).length;

// <2> 如果对应位置的桶节点为空,则直接在该索引位置创建 Node 节点。
if ((p = tab[i = (n - 1) & hash] /*获得对应位置的桶节点*/) == null)
tab[i] = newNode(hash, key, value, null);

// <3> 如果对应位置的桶节点非空,则可能存在哈希冲突,即该桶中可能有多个元素,
else {
Node<K,V> e; // key 在 HashMap 中对应的老节点
K k;

// <3.1> 如果找到的 p 节点,就是要找的,则直接使用即可
if (p.hash == hash && // 判断 hash 值相等
((k = p.key) == key || (key != null && key.equals(k)))) // 判断 key 真正相等
e = p;

// <3.2> 如果找到的 p 节点,是红黑树 TreeNode 节点,则直接添加到树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

// <3.3> 如果找到的 p 是 Node 节点,则说明是链表,需要遍历查找
else {
// 顺序遍历链表
for (int binCount = 0; ; ++binCount) {

// (e = p.next):e 指向下一个节点,因为上面我们已经判断了最开始的 p 节点。
// 如果 e == null,则表示已经遍历到链表的末尾,说明 key 在 HashMap 中不存在,需要创建
if ((e = p.next) == null) {
// 创建新的 Node 节点
p.next = newNode(hash, key, value, null);
// 创建新的节点后,链表的长度如果达到 TREEIFY_THRESHOLD(8)时,则进行树化。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break; // 结束
}
// 如果遍历的 e 节点就是要找的,则退出遍历,直接使用当前 e 节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; // 结束

// p 指向下一个节点,遍历下一个节点
p = e;
}
}

// <4.1> 如果找到了对应的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 修改节点的 value ,如果允许修改
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 节点被访问的回调
afterNodeAccess(e);
// 返回老的值
return oldValue;
}
}

// <4.2> 如果 HashMap 中不存在 key 对应的节点,则会创建新的节点,那么流程就会走到这里:

// 增加修改次数,modCount 字段主要用来记录 HashMap 内部结构发生变化的次数,用于迭代的快速失败;
// 例如 put 新键值对,但是某个 key 对应的 value 值被覆盖不属于结构变化。
++modCount;
// 如果超过阀值,则进行扩容
if (++size > threshold)
resize();
// 添加节点后的回调
afterNodeInsertion(evict);
// 没有旧节点,返回的旧值为 null
return null;
}

对应流程图如下:

hashmap_put_process

五、扩容机制 resize()

当向 HashMap 中添加第一个元素或者元素数量超过阈值时,就会触发扩容机制。

扩容机制的 resize() 方法代码如下:

显示代码块及流程注释

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
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;

// 1.计算新的容量 newCap 和阈值 newThr:
// 如果 table 不为空,表明已经初始化过了
if (oldCap > 0) {
// 当 table 容量超过容量最大值,则不再扩容
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;
} else if (oldThr > 0)
// 调用非默认构造方法时会设置阈值,但 table 数组未初始化过,则此时将 threshold 的值赋值给 newCap,
// 相当于 HashMap 使用 threshold 变量暂时保存了 initialCapacity 参数的值
newCap = oldThr;
else {
// 若调用无参构造方法创建的 HashMap 对象,
// 则设置桶数组容量为默认容量,阈值为默认容量与默认负载因子的乘积
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

// 若经过上面的逻辑,新阈值 newThr 仍然为 0,则按阈值公式进行计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

// 2.重建新的 HashMap:
// 创建新的桶数组,桶数组的初始化也是在这里完成的
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

// 3.如果旧的桶数组不为空,则遍历桶数组,并将键值对映射到新的桶数组中
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 { // preserve order
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;
}
}
}
}
}
// 4.将新的桶数组 newTab 作为 HashMap 的 table 数组返回
return newTab;
}

整个扩容机制的基本逻辑为:

  1. 先计算出新的容量 newCap 和新阈值 newThr;
  2. 根据新的容量 newCap 创建新的桶数组 newTab 并进行初始化;
  3. 将键值对节点重新映射到新的桶数组 newTab 里:如果节点是 TreeNode 类型,则需要拆分红黑树再映射;如果是普通节点,则遍历链表,并将链表节点按原顺序进行分组映射。
  4. 将新的桶数组 newTab 作为 HashMap 的 table 数组返回。

上面流程的详解如下。

1. 计算新的容量和阈值

计算新容量 newCap 和新阈值 newThr 的过程有多种不同的情况,其代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
// 第一个条件分支
if (oldCap > 0) {
// 嵌套条件分支
if (oldCap >= MAXIMUM_CAPACITY) {...}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
}
else if (oldThr > 0) {...}
else {...}

// 第二个条件分支
if (newThr == 0) {...}

这两个条件分支先对不同的情况进行判断,然后采用不同的方式计算得出新的容量和阈值。

(1) 对于第一个条件分支,它覆盖了三种情况:

条件 覆盖情况 备注

oldCap > 0

桶数组 table 已经被初始化过 此时在「嵌套条件分支」中还分有两种子情况

oldThr > 0

oldCap == 0,旧的阈值大于 0,桶数组未被初始化过 调用 HashMap(int)HashMap(int, float) 构造方法创建 HashMap 对象时会出现这种情况。
else oldCap == 0 并且 oldThr == 0 调用默认的 HashMap() 构造方法创建 HashMap 对象时会产生这种情况,此时设置 newCap 为默认值 16,newThr = 16 * 0.75f = 12

对于 oldThr > 0 的情况,会将 oldThr 赋值给 newCap,等价于 newCap = oldThr = threshold = tableSizeFor(initialCapacity),也就是说我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。这也就解答了一个疑问:「initialCapacity 参数没有被保存下来,那么它怎么参与桶数组的初始化过程的呢?」

对于 oldCap > 0 的情况,在嵌套条件分支中还分有两种子情况:

  1. oldCap >= MAXIMUM_CAPACITY,最大桶数组容量 MAXIMUM_CAPACITY = 230,当桶数组容量大于或等于这个值时,不再扩容。
  2. (newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY,先计算得到新容量 newCap 为旧容量的两倍,然后若新容量 newCap 小于最大容量并且旧容量 oldCap 大于等于默认容量,就计算得到新阈值 newThr 为旧阈值 oldThr 的两倍,否则就进入第二个条件分支 newThr == 0 中重新计算 newThr 的值。这里的条件有两个意思:1),若新容量大于等于了最大容量,则新阈值不能直接从旧阈值扩大 2 倍计算得出,因为这样可能导致新阈值过大,需要重新计算;2),若旧容量小于默认容量 16,为防止阈值过小,也需要重新计算。

(2) 对于第二个条件分支newThr == 0 时的计算代码:

1
2
3
4
5
6
7
if (newThr == 0) {
// 按阈值公示进行计算
float ft = (float)newCap * loadFactor;
// 若新容量或者新阈值大于了最大容量值,则赋值 newThr = Integer.MAX_VALUE 。
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}

它覆盖的情况就是第一个条件分支中未计算 newThr 的值,或者计算 newThr = oldThr << 1 时发生了整型溢出导致归零。

对于移位运算导致的溢出情况,当 loadFactor 的小数位为 0、整数位可被 2 整除且大于等于 8 时,若容量值较大,那么在某次计算中就可能会导致 newThr 整型溢出归零。见下图:

newThr_overflow_zero

2. 重建新的HashMap

计算出新的容量和阈值后,就会创建新的桶数组 table 对象:

1
2
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

然后将键值对节点重新映射到新的桶数组 newTab 里:如果节点是 TreeNode 树形节点,则需要拆分红黑树再映射;如果是普通节点,则遍历链表,并将链表节点按原顺序进行分组。

对于链表节点的分组,

对于红黑树的拆分,

3. 链表的树化、红黑树的拆分与链化

JDK 1.8 对 HashMap 实现进行了改进。最大的改进莫过于在引入了红黑树处理频繁的碰撞,代码复杂度也随之上升。

当链表长度大于等于 TREEIFY_THRESHOLD = 8 并且桶数组容量大于等于 MIN_TREEIFY_CAPACITY = 64 时,就需要对链表进行树化。

对与红黑树,在重新映射节点时,会先将红黑树拆分成两条由 TreeNode 节点组成的链表。如果链表长度小于UNTREEIFY_THRESHOLD = 6,则将链表转换成普通链表;否则根据条件重新将 TreeNode 链表树化。

参考阅读