源码剖析:HashMap中插入节点put(k, v)和扩容resize()

HashMap在不同JDK版本的实现方式和源码有所区别,本文针对jdk1.8展开分析,从源码出发深入探讨HashMap插入元素及其中涉及的扩容的过程。

HashMap数据结构

HashMap本质由数组+链表/红黑树,其源码中定义了一个核心属性table(一个Node数组),Node可以理解为存储哈希表中键值对的容器。

HashMap会根据key哈希值找到当前键值对存放在table中的下标index,当多个key位于同一个下标时(称之为哈希冲突),会采用链表的方式,将当前Node插入到链表尾端;当链表的长度超过TREEIFY_THRESHOLD时,会将链表转换为二叉查找树进行存储(HashMap采用的是红黑树);当发现key相同时只替换value值即可。

上面提到发现”key相同“,进行key比较的时候会按照如下顺序进行比对:

  1. 先判断两个key的哈希值是否相同,如果不同则两个key不同,否则继续比较
  2. 判断是否指向同一个引用,即是否==,如果指向同一个引用则两个key相同,否则继续比较
  3. 判断equals是否相等,如果相等则两个key相同,否则不相同

从这里我们解释为什么说“重写equals方法就一定要重写hashCode方法”?

当我们需要使用到散列结构(HashMap, HashSet等)时,如果只重写equals方法而没有重写hashCode方法,在比较key是否相同时会先进行hashCode比较,没有重写hashCode方法会导致两个equals相等的对象的hashCode不同,因此在put操作时会当做两个不同的key来处理。

HashMap插入节点和扩容

put方法源码注释:

我们可以发现put方法实际是调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法,我们先来看计算哈希值的过程:

从源码我们可以发现,计算哈希值的时候,当keynull时指定了哈希值为0,说明HashMap是允许keynull的,并且只能有一个keynull。这里和其他的哈希表不同(如HashTable,ConcurrentHashMap),其他哈希结构都是不允许keynull的。

putVal()插入节点

插入节点的步骤:

  1. 根据哈希值找到当前key在table数组(哈希桶)中的位置
  2. table数组当前位置为空,则在此处创建新Node并放在table的当前位置即可,break
  3. 当前位置不为空,且发现当前位置的节点是一颗红黑树,执行红黑树插入节点的操作,break
  4. 当前位置不为空,也不是红黑树,则当前位置只有可能是链表,执行链表的插入操作
    1. 遍历链表,查找是否有相同key,如果发现了相同key,则进行值替换,break
    2. 遍历到链表尾部,仍未发现相同key,此处创建行Node,并将其插入到链表尾部;插入节点后若发现当前链表长度超过TREEIFY_THRESHOLD时,将链表变成红黑树,break
  5. 插入节点后,判断当前size是否超过threshold,如超过进行resize()
  6. Return

源码分析:(详细分析过程见注释)

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
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
// table为空时,初始化table
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 哈希桶当前位置为空,则直接把新的Node放到table数组的当前位置即可
tab[i] = newNode(hash, key, value, null);
else {
// 发生哈希冲突
Node<K,V> e; K k;
// p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))就是上面提到的「比较key」的源码
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 发现key相同,把当前Node赋给e,后面进行value替换操作
e = p;
else if (p instanceof TreeNode)
// 发现哈希桶当前位置已经是一颗树,进行红黑树插入节点操作,此处不进行详细阐述
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// table当前位置为链表,遍历链表,寻找是否有相同的key
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 遍历到链表尾部,仍未发现相同的key,创建新Node,并插入到链表尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 发现当前链表的长度达到了TREEIFY_THRESHOLD,链表变红黑树,提升查询效率
treeifyBin(tab, hash);
break;
}
// 此处同样是「比较key」的过程
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 发现有相同的key,把当前Node赋给e,后面进行value替换操作
p = e;
}
}
if (e != null) { // existing mapping for key
// 发现key相同,进行value替换操作
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 当前HashMap的节点数超过了门槛值,进行扩容
resize(); // 扩容操作
afterNodeInsertion(evict);
return null;
}

resize()扩容

源码注释:

从上面注释我们可以知道,当初始化或者哈希桶大小翻倍时会执行resize()方法。

resize()方法分为两个部分:

  1. 重新计算thresholdcapacity
  2. 重新放置所有Node

第一个过程较为简单,基本过程就是table大小翻倍,然后重新计算threshold = newCap * loadFactor,源码部分涉及到很多越界处理,看着有些复杂。

第二个过程遍历旧table,将节点放入到新table对应的位置,主要分为以下几步:

  1. table当前位置为空,直接跳过

  2. table当前位置只有一个节点,将该节点放到新tablee.hash & (newCap - 1)位置上即可

  3. table当前位置是一颗二叉树,执行红黑树的重新放置节点操作

  4. table当前位置是一个长度大于1的链表

    1. 在链表中存在位置不变和位置往后移动oldCap的节点,使用loHead,loTail来记录位置不变节点的头尾节点,使用hiHead, hiTail记录位置需要往后移动oldCap的头尾节点

    怎么判断哪些节点位置不变,哪些需要移动?为什么是向后移动oldCap个位置?
    e.hash & (newCap - 1) 代表新table的位置,且newCap = oldCap << 1,并且newCap和oldCap都是2的倍数
    举例说明:
    我们假定oldCap = 8(即0b1000),则newCap = 16(即0b10000)
    e.hash & 0b111 表示在旧table中的位置,& 操作是对e.hash进行截断,即e.hash的后三位即代表旧位置
    e.hash & 0b1111 表示在新table中的位置,同理,e.hash的后四位代表新位置
    因此我们只要判断e.hash在第四位是否为0即可,如果为0,则表示新位置和旧位置一致;如果不为0,则新位置比旧位置大0b1000
    结论:
    e.hash & oldCap == 0 : 新位置和旧位置一致
    e.hash & oldCap != 0 : 新位置比旧位置大oldCap

    1. 位置不动的节点通过newTab[j] = loHead来实现;位置往后移动通过newTab[j + oldCap] = hiHead来实现

源码分析:(详细分析过程见注释)

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
97
98
99
100
101
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;
}
// newCap = oldCap << 1,capacity翻倍,即table大小翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// threshold翻倍
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) {
// 重新计算threshold = newCap * loadFactor
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;
// 原来table当前位置为null的直接跳过
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 当前位置上的链表只有一个节点,重新计算在新table中的位置,并放置到新table对应位置即可
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 当前位置上是一颗红黑树,进行树的重新放置操作,此处不进行详细阐述
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 当前位置上是一颗节点数大于1的链表
// 不需要改变位置的头结点和尾节点
Node<K,V> loHead = null, loTail = null;
// 需要将位置往后移动oldCap个位置的头节点和尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/*
(e.hash & oldCap) == 0 是判断当前节点哈希值在新table中的位置是否需要改变
e.hash & (newCap - 1) 代表新table的位置,且newCap = oldCap << 1,并且newCap和oldCap都是2的倍数
举例说明:
我们假定oldCap = 8(即0b1000),则newCap = 16(即0b10000)
e.hash & 0b111 表示在旧table中的位置,& 操作是对e.hash进行截断,即e.hash的后三位即代表旧位置
e.hash & 0b1111 表示在新table中的位置,同理,e.hash的后四位代表新位置
因此我们只要判断e.hash在第四位是否为0即可,如果为0,则表示新位置和旧位置一致;如果不为0,则新位置比旧位置大0b1000
结论:
e.hash & oldCap == 0 : 新位置和旧位置一致
e.hash & oldCap != 0 : 新位置比旧位置大oldCap
*/
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;
// 将新旧位置不变的节点仍放到j位置上
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 将需要往后移的节点放到j+oldCap位置上
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}