HashMap 数据结构
在 Java 中，HashMap 的数据结构被称为“链表散列”，这是一种基于数组和链表的数据结构。它通过将哈希函数的结果映射到数组的索引来存储键值对，同时使用链表来解决哈希冲突。其中：
- 数组具有较快的查询速度，但插入和删除操作的性能相对较差；
- 链表的查询性能较差，但插入和删除操作的性能相对较高。
这种方式使得 HashMap 结合了数组和链表（或红黑树）的优点，从而提供高效的键值对存储和查找功能。
JDK 1.8 对 HashMap 数据结构又做了优化，当链表长度超过阈值时，会将链表转换为红黑树进行处理，红黑树相对于链表具有更快的查询性能，特别适用于高冲突场景下的大容量哈希表。示意图如下：
哈希表数组与哈希桶
在 HashMap 中，哈希表是以数组形式存在的。具体来说，HashMap 内部声明了一个 transient Node<K,V>[] table 数组，每个数组元素即一个哈希桶 (Bucket)。
哈希表数组的容量 $n$ 始终是 2 的幂次方 ($n = 2^k$)，以便支持位运算，$k$ 是一个非负整数。
哈希桶 Node 节点
在哈希冲突不严重时，键值对的存储和查找是通过内部类 Node 来实现的。每个 Node 对象都包含了一个键 (Key)、一个值 (Value)，以及指向下一个 Node 对象的指针。当哈希冲突发生时，HashMap 会将键值对存储在相应的 Node 对象中，并通过链表来组织这些 Node 对象。以下是 Node 类的部分源码：
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;
//...
}
|
哈希桶 TreeNode
当某个桶内哈希冲突比较严重时，桶内的 Node 链表会被转化为以内部类 TreeNode 为节点的红黑树，TreeNode 部分源码如下：
1
2
3
4
5
6
7
8
| static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 根节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 用于删除时断开下一个连接
boolean red;
//...
}
|
Java HashMap 特点
散列存储：HashMap 使用散列存储方式，通过哈希函数计算键 (Key) 的哈希值，将其映射到一个桶，然后将键值对存储在这个桶中。这样可以实现快速的键值对查找，时间复杂度为 $O(1)$。
键和值都可以为 null：HashMap 中的键和值都可以为 null。
需要注意的是，如果键为 null，它的哈希值为 0。因此所有的 null 键都会被存储在同一个桶中，从而降低 HashMap 的性能。在使用时最好避免使用 null 作为键。
非线程安全：HashMap 不是线程安全的，因此在多线程环境中使用时需要进行外部同步，或者使用 ConcurrentHashMap。
不保证键值对的顺序：HashMap 不保证键值对的顺序，即使键值对按照一定的顺序插入，也不一定会按照相同的顺序遍历它们。
初始容量和负载因子：HashMap 可以指定初始容量和负载因子来优化性能。初始容量指的是哈希表的容量，负载因子指的是哈希表在达到多少填充程度时会自动扩容。
HashMap#get 原理
HashMap#get 源码如下：
1
2
3
4
| public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
|
其中的核心实现为 HashMap#getNode：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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 && // [2] 判断桶内第一个元素是否是要查询的元素
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 下一个节点非空判断
if ((e = first.next) != null) {
// 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { // 非树结构，循环遍历链表节点
if (e.hash == hash && // hash 相等并且 key 相同，则返回此节点
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// [3] 找不到匹配项，返回空
return null;
}
|
[1]：该方法首先判断 table 是否为空，如果 table 不为空，那么方法会通过计算 tab[(n - 1) & hash] 找到相应的桶，并取出桶中的第一个节点 first。[2]：接着，方法会先检查 first 是否就是要查找的节点。- 如果是，直接返回
first。 - 如果不是，那么方法会遍历链表或红黑树上的所有节点，查找与
key 相等的节点，直到找到或遍历完所有节点。
[3]：如果找到了与 key 相等的节点，则返回该节点；否则，返回 null。
哈希表的底层实现是一个大小为 2 的次幂的数组。因此在调用 get 方法时，将 Key 的哈希码值转换为数组的下标是非常关键的一步。通过查看 HashMap#getNode 方法的源码，我们可以发现，该方法计算数组下标的算法为 (n - 1) & hash，这个位运算等价于取模运算 hash % n，但性能却远超取模运算。
为什么 (n - 1) & hash 等价于 hash % n
(n - 1) & hash 和 hash % n 等价的原因在于哈希表的长度 $n$ 是 2 的幂次方，即 $n = 2^k$，因此 n - 1 的二进制表示中所有位都是 1，例如当 n = 16 时，n - 1 的二进制表示为 1111。
在这种情况下，(n - 1) & hash 实际上相当于将哈希值的二进制表示的低 k 位与 n - 1 进行按位与操作。由于 n - 1 的二进制表示中所有位都是 1，因此该操作的结果等价于将哈希值的低 k 位保留下来，其余位都变成了 0。最终，(n - 1) & hash 的结果就是 hash % n 的值，也就是 hash 值对应的在哈希表中的下标。
HashMap#hash 特性
Java 中的每个对象都有一个哈希码 (Hash Code)，可以通过调用 java.lang.Object#hashCode 方法或者键类型重写的 hashCode() 方法来获取。其中，Object 类中的 hashCode() 方法会根据对象的内存地址计算出一个整数值作为该对象的哈希码。HashMap 中的键的哈希码就是在键对象的 hashCode() 方法的基础上计算的：
1
2
3
4
5
| static final int hash(Object key) {
int h;
// key 等于 null，返回 0，否则实际计算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
HashMap 对键的哈希码做了再处理，具体算法为 (h = key.hashCode()) ^ (h >>> 16)，即将键的哈希码 h 与其右移 16 位后的结果进行异或运算，这样可以有效地提高哈希码的随机性和分布性，从而提升查询性能。
我们知道：
- 16 位有符号数的最大值为 32767，而
HashMap 的表的容量在大多数情况下不会超过这个值； HashMap 中哈希表的容量始终是 2 的次幂，因此哈希值对哈希表容量取余，等价于这两个值按位与。
如果直接使用 32 位哈希码，当不同键的哈希码的低位相同、高位不同时，它们对哈希表取模就有可能映射到同一个位置（高位在低容量场景下会被截断），进而拖慢 HashMap 的性能。这种处理方式提升了哈希码的高 16 位对映射过程的影响，降低了哈希冲突的概率。
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
| 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; Node<K,V> p; int n, i;
// [1] 哈希表为空则创建表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// [2] 根据 key 的哈希值计算出要插入的数组索引 i，
// 如果 table[i] 等于 null，则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // [3] 如果存在 Hash 冲突
Node<K,V> e; K k;
if (p.hash == hash && // [3.1] 判断 Key 是否与桶内第一个元素的 Key 相等
((k = p.key) == key || (key != null && key.equals(k))))
// [3.1.1] 如果相等，直接覆盖 value
e = p;
else if (p instanceof TreeNode) // [3.2] 否则判断第一个元素是否为红黑树
// [3.2.1] 是红黑树则调用 tree api 插入键值对
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // [3.3] 是链表，则手动插入
for (int binCount = 0; ; ++binCount) {
// [3.3.3] 找到了链表末尾
if ((e = p.next) == null) {
// 先将新节点插到链表结尾
p.next = newNode(hash, key, value, null);
// 发现链表长度到达阈值
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 方法中判断表容量是否超过 64，是则转为红黑树，否则只扩容
treeifyBin(tab, hash);
break;
}
// [3.3.2] key 已经存在，跳出循环，执行 onlyIfAbsent 策略
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// [3.3.1] 否则向下遍历
p = e;
}
}
// [4] onlyIfAbsent 策略：默认为相同的 key 覆盖 value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 给 LinkedHashMap 设定的模板方法
return oldValue;
}
}
++modCount;
// [5] 超过最大容量，扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 给 LinkedHashMap 设定的模板方法
return null;
}
|
当执行 put(K, V) 方法来插入数据时，如果发生了哈希碰撞并且当前键 (key) 是一个全新的键，首先会将新的数据节点插入到链表的末尾。然后，会检查链表的长度，如果长度大于等于 8 且数组的容量大于 64，则会将该链表转换成红黑树。
HashMap 扩容原理
HashMap 刚被申请时会有一个初始容量（桶数量），随着数据的插入，占用的容量会逐渐增加。当 HashMap 中的已用桶数量达到一定阈值时，就会触发扩容操作，将当前数组的容量扩大一倍，并将所有元素重新分配到新的桶中。在这种情况下，每个元素都需要确定其在新数组中的位置。源码如下：
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
| 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) { // [1] 如果哈希表中已有数据
// [1.1] 如果当前数组容量大于等于阈值，则不扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// [1.2] 否则扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITY
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // [2] 如果哈希表为 null，且设定了 threshold
// 则使用旧的 threshold 作为初始化容量
newCap = oldThr;
else { // [3] 如果哈希表为 null，且 threshold 为 0
// 则使用默认的初始化容量 16
newCap = DEFAULT_INITIAL_CAPACITY;
// 扩容阈值设为 newCap * 扩容因子后的值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// [4] 如果新的阈值等于 0，也就是上述场景 [1.1]、[2]
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// 安全设置阈值，防止溢出
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// [5] 更新阈值
threshold = newThr;
// [6] 创建扩容后的容器
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// [7] 将新的数组赋值给 table
table = newTab;
// [8] 如果哈希表中有数据，则移动数据
if (oldTab != null) {
// [9] 根据容量循环数组，复制非空元素到新 table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 旧引用释放
if (e.next == null)
// [9.1] 如果链表只有一个元素，则直接放入新桶
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// [9.2] 如果是红黑树，则执行红黑树相关的操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // [9.3] 如果是链表，则进行链表复制（JDK 1.8 扩容优化部分）
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) {
// 如果不需要移动，插入 low 队列
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 如果需要移动，插入 high 队列
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// 将 low 链表放到新数组的原索引位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 将新链表放到新数组原索引 + oldCap 处的位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
在扩容过程中，HashMap 会将旧数组中的每个桶内的元素依次迭代，并将每个元素根据其哈希值计算出在新数组中的位置。而由于新数组的容量是旧数组的两倍，因此旧数组中的每个桶位都对应着新数组中的两个桶位。具体地说，旧数组中的第 i 个桶位对应了新数组中的两个桶位：下标分别是 i 和 i + oldCap。然后 HashMap 通过高位运算来确定元素是否需要移动。假设元素 e 存储在旧数组的桶位 i 中：
- 如果
(e.hash & oldCap) == 0，那么它在新数组中的位置仍然是 i； - 否则，它在新数组中的位置是
i + oldCap。
HashMap 通过这种设计，避免了 Rehash 操作，极大地提高了性能。
e.hash & oldCap 数学原理
首先，我们知道 Key 在旧数组中的索引位置，即 e.hash % oldCap 等价于 e.hash & (oldCap - 1)。假设有如下场景：
1
2
3
4
5
6
| ---------------
e.hash -> 1 0 1 1 1 1 1 0
oldCap -> 1 0 0 0 0
oldCap-1 -> 0 1 1 1 1
---------------
index -> 1 1 1 0
|
当哈希表容量扩大一倍后，新数组的长度由 1 0000 变为 10 0000，此时元素 e 在新数组中的索引位置如下：
1
2
3
4
5
6
7
8
| ---------------
e.hash -> 1 0 1 1 1 1 1 0
newCap -> 1 0 0 0 0 0
newCap-1 -> 0 1 1 1 1 1
---------------
index -> 1 1 1 1 0
*
重点关注最高位
|
在这个示例中，元素 e 的二进制哈希值的第五位为 1，那么在哈希表容量扩大后，e 在新数组中的索引位置就是 1 1110，即 1110 + 1 0000。想要得到哈希值第五位是否为 1，只需做以下计算，再判断结果是否为 0 即可：
1
2
3
4
5
6
7
| ---------------
e.hash -> 1 0 1 1 1 1 1 0
markword -> 1 0 0 0 0
---------------
index -> 1 0 0 0 0
*
重点关注最高位
|
而这里的 1 0000 恰好是旧容量 (oldCap) 的二进制值。因此，我们可以通过对 e.hash 和 oldCap 进行按位与操作来判断第五位是否为 1，从而决定是否需要将 e 移动到新数组的相应位置。
注释
虽然 JDK 1.8 HashMap 并未对桶内元素进行 Rehash 操作，但是通过高位与运算，将原链表（红黑树）分散在了新数组的两个桶内，依旧起到了缩短链表长度（红黑树深度）的作用，同时性能也较 Rehash 更高。
HashMap 扩容因子为何为 0.75
当哈希表中出现多次冲突导致链表长度过长时，HashMap 会将链表转换为红黑树，以提高查询性能。但是，由于红黑树节点 (TreeNode) 的大小大约是常规链表节点大小的两倍，所以在选择是否进行转换时，应该优先考虑扩容而不是转换（具体表现为源码中只有当哈希表容量超过 64 时才进行链表转树，否则只进行 resize 扩容）。
当设置的扩容因子较大时，扩容的门槛也会相应提高，从而减少扩容的频率，并且占用的空间也会更少。然而，这样做也会增加哈希冲突的概率，从而增加链表转树的可能性。相反地，当扩容因子值较小时，扩容的门槛会降低，哈希冲突的可能性也会比较小，因此操作性能会比较高，但会占用更多的空间。
为了在容量和性能之间达到平衡，HashMap 将扩容因子定为了 0.75。
HashMap 链表转红黑树阈值为何为 8
在分析之前，我们先来了解下为什么 HashMap 需要将链表转换为红黑树。如上文所述，相对于红黑树，链表具有更小的空间占用优势，但在查询时的时间复杂度较高；而红黑树则恰好相反。在设计算法时，通常需要平衡时间复杂度和空间复杂度这两个指标，在 HashMap 这里具体表现为：
- 一方面，我们不希望链表过长，以免影响查询性能；
- 另一方面，我们也不希望链表太容易转换为红黑树，以避免占用过多的内存空间。
幸运的是，HashMap 在哈希碰撞发生的次数方面符合泊松分布，我们可以利用泊松分布来同时满足这两个要求。
泊松分布指出：在单位时间（或面积、体积）内，某个随机事件平均发生 $\lambda$ 次（期望为 $\lambda$）的情况下，该事件实际发生 $k$ 次的概率遵循泊松分布，其概率方程如下：
$P(X = k) = \frac {(\lambda)^k} {k!} e^{-\lambda}$, $k = 0,1,2,…$
- $k$：发生的次数
- $X$：一种关系，含义为“实际发生 $k$ 次”
- $P$：$X$ 关系发生的概率
- $\lambda$：数学期望，表示单位时间（或面积、体积）内随机事件的平均发生次数
在哈希表中，我们以哈希桶为单位体积，并将插入操作看做一系列的随机事件，其中每个事件表示将一个 Key 映射到某个哈希桶内。因此：
- $\lambda$ 表示每个桶内平均存储元素的数量；
- $P(X = k)$ 表示现实中有 $k$ 个 Key 被映射到同一个哈希桶内（即哈希碰撞了 $k$ 次）的概率。
根据 HashMap 源码注释，当 $\lambda = 0.5$ 时，$k$ 从 0 到 8 得到的概率 $P$ 如下：
1
2
3
4
5
6
7
8
9
| * 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
|
由上可知，在 $\lambda = 0.5$ 的情况下，某个哈希桶内发生 8 次碰撞的概率非常小。因此，HashMap 设定只有当链表长度超过 8 时，才会考虑将其转换为红黑树来处理，以平衡链表的低效查询与红黑树的高空间占用。
为什么 HashMap 泊松分布的期望为 0.5
到这里还剩一个最重要的问题没有解决，上文我们直接从源码中知晓了 $\lambda$ 被设定为 0.5，而且泊松分布概率方程准确与否，与频率 $\lambda$ 的选定息息相关，所以 Java 是怎么选定 $\lambda = 0.5$ 的呢？答案与前文提到的扩容因子 0.75 有关。
首先，我们假定一种理想情况：哈希算法能够完美地散列，因此在向 HashMap 中插入数据时，不会发生任何哈希冲突。然后，随着数据的不断插入，HashMap 会触发多次扩容操作。由于扩容因子为 0.75，每次扩容前哈希表内数据量占容器的比值为 0.75，每次扩容后哈希表内数据量占容器的比值为 0.375，所以在数据不断添加的过程中，哈希表内数据量的占比以锯齿状在 0.375 ~ 0.75 间变化：
1
2
3
4
5
6
7
| ^
|
| . . . _______ 0.75
| /| /| /| _____________0.5625
| / |/ |/ |/ _______0.375
|/
+--------------------------------->
|
在忽略方差的情况下，哈希表容量占比的期望值约为 0.5625，也就是说，平均每个桶内大约有 0.5625 个元素，Java 的设计师们将其向下取整，选择了 $\lambda = 0.5$，这便是源码中 $\lambda$ 值的由来。
至此，与 HashMap 相关的内容就介绍完了。
