HashMap 超详细源码解析

2019-07-04_112604.png

Java面试必考题

1. 介绍

HashMap.png

从上面的UML图中可以知道 HashMap 继承了 Map 的接口,是一个key-value 关联的哈希表,AbstractMap 提供了一些默认的实现。

它的底层是由数组 + 链表来实现,并且当链表长度大于 8 时会转换为红黑树:

640.png

2. 基本概念和属性

2.1 基本概念

在分析源码之前先了解一下在 HashMap 中的一些基本概念,如下:

  • size:当前哈希表中记录的key-value数量;
  • capacity:当前哈希表中可以容纳数量,即底层数组的长度。

以上两个概念相信大家都很熟悉,在其他的集合类中也经常出现。但是以下的概念与 HashMap 的扩容机制非常有关:

  • loadFactor(加载因子):用来衡量 HashMap 满的程度;
  • threshold(阈值):元素个数的临界值,当 size 大于该阈值时,哈希表容量将会扩容原来的两倍。

它们俩与容量之前满足 threshold = capacity * loadFactor 的关系。在 HashMap 中,默认的 capacity = 16, loadFactor = 0.75,计算得默认的阈值为12,也就是说默认情况下当哈希表中的元素大于12时,将会执行扩容。

2.2 基本变量和方法

在源码的首部定义了几个预设的常量:

1
2
3
4
5
6
7
8
// 初始化的默认容量,即16,用 1 << 4 表示是为了强调必须为2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大的哈希桶容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 将链表转换为红黑树的临界值
static final int TREEIFY_THRESHOLD = 8;

以及基本的变量:

1
2
3
4
5
6
7
8
9
10
11
12
// 底层存放结点数据的数组,长度始终是2的幂次
transient Node<K,V>[] table;
// keySet 方法返回的结果
transient Set<Map.Entry<K,V>> entrySet;
// 当前保存key-value的个数
transient int size;
// 修改的次数
transient int modCount;
// 阈值
int threshold;
// 加载因子
final float loadFactor;

从前面的结构图可以看出,数组中每个元素存放的是链表,其结点的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}
}

可以看到,结点中存放了键的哈希值,阅读源码发现,该值是通过静态方法 hash() 计算而来:其值不仅仅是key对象的hashCode()返回的值,还会经过扰动函数的扰动,使hash值更加地均衡,减少哈希碰撞的发生

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

那么什么是哈希碰撞呢?由于 HashMap 的哈希桶长度比hash取值范围小的多,因此需要将hash值对桶的长度取余,以找到存放该key的桶下标。这样会导致得到相同的索引发生,这种情况称为哈希碰撞(冲突)。发生碰撞的结点将会以链表的形式依次排列在相同索引的位置当中

2.3 构造方法

默认的构造函数初始化了默认的加载因子:

1
2
3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}

另外,可以指定初始化的容量与加载因子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public HashMap(int initialCapacity) { // 指定初始化容量的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

注意,初始化的容量必须为2次幂。即使你传入的不是符合的值,也会通过tableSizeFor方法计算出比传入值大且最近的2次幂的值。即7 -> 814 -> 16

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

另外还可以指定一个 Map 对象传入,将所有数据添加到哈希表当中:

1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) { 
this.loadFactor = DEFAULT_LOAD_FACTOR; // 默认加载因子
putMapEntries(m, false);
}

putMapEntries 会对阈值进行校验,判断新的阈值是否超过了初始化的阈值。并且当 Entries 结点个数超过阈值时会调用 resize() 触发扩容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
// 根据m的元素数量和当前表的加载因子,计算出阈值
float ft = ((float)s / loadFactor) + 1.0F;
// 修正边界,使其不大于最大容量并转换为int类型
int t = ((ft < (float) MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
// 如果新的阈值大于当前的阈值,则调用tableSizeFor返回一个新的满足2的n次方的阈值
threshold = tableSizeFor(t);
}
else if (s > threshold)
// 如果m的元素数量大于阈值,则要调用 resize 进行扩容
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

2.4 扩容机制

前面说到,当哈希表的容量大于阈值时则会触发扩容,举个例子,我们通过反射获取到 HashMap 中的sizecapacitythreshold参数值:

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
public class ThresholdDemo {

public static void printMapInfo(Map<?, ?> map) throws Exception {
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
Field threshold = mapType.getDeclaredField("threshold");
threshold.setAccessible(true);

System.out.println("size: " + size.get(map) + ", capacity : " + capacity.invoke(map) + ", threshold : " + threshold.get(map));
}

public static void main(String[] args) throws Exception {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i <= 12; i++) {
map.put(i, 1);
}
printMapInfo(map);

map.put(13, 1);
printMapInfo(map);
}
}

代码执行输入如下:

1
2
size: 12, capacity : 16, threshold : 12
size: 13, capacity : 32, threshold : 24 // 容量和阈值变为原来的两倍

HashMap 的扩容机制发生在哈希表key-value 个数大于阈值时, 即调用resize() 来触发。在前面的构造方法中可以看到,并未对容量和底层数组 table 初始化,这是因为推迟到了 resize() 进行执行。

根据不同的初始化情况,resize() 在第一个 if 分支中采取不同的初始化策略来更新阈值和容量。更新完成之后创建新的哈希表数组,如果原哈希桶中有元素,则将旧的哈希桶中所有结点转移到新的哈希桶当中。不过,在更新完容量之后随之而来存在一个问题。首先需要知道,获取key的哈希值对应的哈希索引下标方法如下:

1
2
3
int index = e.hash & (cap - 1)
// 等同于
int index = e.hash % cap

之所以要用”与”操作符替代取余数的方法是为了提高效率,这也是为什么容量要设置成2次幂的原因,因为2的n次幂转化为二进制为1后面n个0,减1之后为n个1,举个例子:

1
2
3
4
5
6
7
8
9
10
11
12
8 转换为十进制 = 1000
8 - 1 = 7 转换为十进制 = 111

假设某个键的哈希值为48690,让该值与cap-1=111做按位与运算,得:

// 当且仅当 1 & 1为1,其他均为0
1011111000110010 (48690)
0000000000000111 (7)
|||||||||||||||| &
0000000000000010 (2)

其结果与 48690 % 8 = 2 结果相同

前面说到增加容量之后存在的问题为:如果需要保持该计算索引的规则,当容量发生变化时其下标位置可能也会随之发生变化,即可能存在于原来的下标(称为低位),也有可能存在于扩容后的下标(称为高位),我们可以通过(e.hash & oldCap) == 0结果是否等于0来判断存放在低位还是高位,这一操作称之为reHash。举个例子:

1
2
3
4
5
6
7
假设有两个键的哈希值分别为:4869051669

reSize前,容量为4: indexA = 48690 & (4 - 1) = 2
indexB = 51669 & (4 - 1) = 1

reSize后,容量扩大为8: indexA = 48690 & (8 - 1) = 2 (低位)
indexB = 51669 & (8 - 1) = 5 (高位)

示意图如下,需要注意的是,在并发的环境下,reHash操作可能会形成链表环

UTOOLS1562231888312.png

具体的代码逻辑如下:

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
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 当前哈希桶容量
int oldThr = threshold; // 当前阈值
int newCap, newThr = 0; // 初始化新的哈希桶容量和阈值为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;
}
else if (oldThr > 0) // 哈希表为空但有阈值,为指定容量、阈值构造方法的情况
newCap = oldThr;
else { // 哈希表为空且没有阈值,为使用默认构造方法初始的情况
newCap = DEFAULT_INITIAL_CAPACITY;
// 计算默认阈值 = 默认容量 * 默认加载因子
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

if (newThr == 0) { // 当新的阈值为0时,通过新的容量与加载因子计算出新的阈值
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}

threshold = newThr; // 更新阈值
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] = null; // help GC
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 { // 发生了哈希碰撞,但是链表长度小于8

// 由于扩容之后容量翻倍,要确保 e.hash & (newCap - 1) 为哈希索引则可能需要调整原结点的位置
// 原结点可能存放在原来的下标,即低位;可能存放在扩容后的下标,即高位。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 用结点哈希值对旧容量“与”操作,如果结果为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;
}

3. 增删改查

增改

增改的逻辑都是由put方法来实现:

  • 当对应的哈希索引位置为空时执行增操作;
  • 否则判断是否与链表中的节点键值相同(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
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;

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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果hash值与已存在的hash相等,并且key值也相等,则准备更新对应结点的value
e = p;
else if (p instanceof TreeNode) // 转换成红黑树后的特殊操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当发生哈希碰撞时,将当前节点添加到链表的末尾
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 到达链表末尾
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 当链表的长度大于8时,将会转换成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 更新操作的情况,返回旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

可以看到,判断两个键是否相同的方法并不仅仅是比较两者的哈希值是否相等,而是先判断哈希值后(为了提高效率),在相等的情况下再比较equals是否相同。这也就是为什么要同时重写equals和hashCode方法的原因

查询的逻辑很简单,首先根据哈希值计算出索引值,检测第一个结点是否目标结点,如果不是则从链表或者红黑树中查找:

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
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 && // 检测第一个结点是否目标结点,如果是则直接返回
((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);
// 遍历直到找到目标结点为止,否则返回 null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

删除的逻辑与查询类似,查到对应结点之后再进行删除:

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
public 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) {
// table的引用、哈希索引对应的节点、talbe长度、哈希索引
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) // 如果node == p,说明是链表头是待删除节点
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}

4. 总结

  • HashMap 的底层结构为是数组 + 链表,当链表的长度大于8时将会转换为红黑树,当链表的长度小于6时会回转为链表;
  • HashMap 的容量必须为2次幂,这是因为为了增加取值的可能性;
  • HashMapsize 大于阈值时,容量和阈值会触发扩容增大为原来的两倍,扩容后的节点需要判断是否存在于低位还是高位。
  • HashMap 中判断是否为相同键的方法是先判断hash() 计算出值是否相同,再通过 equals 判断内容是否相同。
Pushy wechat
欢迎订阅我的微信公众号