Hashmap源码解析-putVal方法(3)

HashMap源码解读系列教程:

本节将会分析令人激动人心的put方法。该方法是hashmap的核心,只有了解了这个方法,我们才能够知道Hashmap为什么这么牛逼。

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

put方法的其实内部调用的就是putVal,因此真如本节的标题一样,将会把讲解重点放到putVal方法上。

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

该函数一共有5个参数,分别的作用是:

  • hash,key对应的hash值
  • key,key的值
  • value,value的值
  • onlyIfAbsent,只有key不存在的时候,才会将键值对添加到map中。
  • evict,用来区分是不是被构造器调用,当使用HashMap(Map<? extends K, ? extends V> m)这个构造器时,会标记下。
    在深入putVal方法之前,我们还得详细讲一下hash函数

1、hash函数

put方法里面计算key时,使用了这个函数,这个函数是将key值转化为hash值(int类型,4个字节,32位)。

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  1. 如果key为null,那么hash值直接为0;
  2. 否则先求出key的hashcode,再求出hashcode右移16位的值,最后将两个值进行异或,得到最终的hash。

这里给key.hashCode()做右移和异或就是对hashCode增加扰动。如计算方法下图所示:

hash函数

至于为什么要增加扰动,这又要谈到寻址算法。当我们得到一个hash值后,要讲这个值映射到散列表数组中的某一个位置。下面这段代码实现这个功能。

1
2
//n就是数组的长度
int index = (n - 1) & hash

默认情况下,数组的长度是16,从二进制的角度来看,他占的位数并不多。于是参与计算的部分只有低位那个数(下图中的红色部分)。

hashmap寻址算法

所以最开始上面获取hash值的时候,我们就必须让key.hashCode的高16位也参与到计算。也就是高16位与低16位混合(异或)。这样做“与”操作时增大了随机性。

异或(^):两位相同返回0,不同返回1

与(&):两位同时为1,则值为1。否则为0

或(|):两位只要有一个值为1 那么值为1

为什么寻址算法需要数组长度减一呢?

这就要先回去谈到之前创建散列表数组长度的tableSizeFor函数了。他规定了数组长度必须大于等于给定值且最近的2的整数次幂的数。比如说2、4、8、16、32、64等。那么length-1得到的二进制数在低位都是连续k个的1。比如15的二进制是1111。那么 hash & (k 个连续的 1) 返回的就是 hash 的低 k 个位,该计算结果范围刚好就是 0 到 2^k-1,即 0 到 length - 1,跟取模结果一样。

那为什么不直接取模呢?
因为与运算的效率比取模的效率更高!

2、putVal

putVal是HashMap存对象最核心的方法。代码其实也不多,就40多行,但是没有讲解看起来还是比较艰难的,下面我们看下这段代码,我们会以注释的形式对每行代码进行讲解。

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//散列表
Node<K,V>[] tab;
//键值对
Node<K,V> p;
//n:散列表的长度
//i:当前键值对存放在散列表的桶位
int n, i;
//table:类的成员变量,散列表。
//将当前的散列表对象赋值给tab,散列表的长度赋值给n。
if ((tab = table) == null || (n = tab.length) == 0)
//如果散列表是null或者散列表的长度位0,那么会触发resize方法(resize方法后面还会具体讲到),来初始化散列表。因为使用构造方法new出来的hashmap并不会马上初始化散列表,而是在第一次put的时候才初始化。
n = (tab = resize()).length;
//(n - 1) & hash是一个寻址算法,定位要存放的键值对放到哪个桶位
if ((p = tab[i = (n - 1) & hash]) == null)
//如果散列表的当前桶位是null,那么直接创建一个链表头部节点即可。
tab[i] = newNode(hash, key, value, null);
else {
//当前桶位已经有值了,并且这个桶位的值已经赋值给变量p。
//e:桶位中要存放的键值对
//k:临时变量key
Node<K,V> e; K k;

if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果当前桶位节点的key的hash值和要存的key的hash值一致
//且key也相等,那么要存放的键值对以老的为准(具体看后面对onlyIfAbsent的判断)
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//循环比较链表中每一个元素,看是否能找到key相等的。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//建立循环条件
p = e;
}
}
//发现有key相同的键值对
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;
}

jdk源码的写法大量使用了代码简写,阅读起来成本会高一点点。比如:

1
2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

可以把他写成下面这样,可读性会更高。

1
2
3
4
Node<K,V> p = tab[i = (n - 1) & hash]
if (p == null){
tab[i] = newNode(hash, key, value, null);
}

3、resize

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
final Node<K,V>[] resize() {
//散列表引用备份
Node<K,V>[] oldTab = table;
//扩容前的散列表容量(桶位数)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//扩容前的散列表扩容阈值,触发本次扩容的阈值
int oldThr = threshold;
//newCap:新的散列表容量(桶位数)
//newThr:新的扩容阈值
int newCap, newThr = 0;
//散列表已经初始化过了,表示一次正常的扩容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//当扩容到一定程度,就不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 左移运算符,num << 1,相当于乘以2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果老容量*2小于最大容量且老容量大于默认容量,那么扩容阈值就扩大1倍。
newThr = oldThr << 1; // double threshold
}
// 【暗含oldCap=0】散列表还未初始化,构造方法初始化的容量放到了oldThr里面,所以这里直接赋值即可
// 1.new HashMap(initCap,loadFactor)
// 2.new HashMap(initCap)
// 3.new HashMap(map)
else if (oldThr > 0)
newCap = oldThr;
//【暗含oldCap=0且oldThr=0】
else {
//使用了默认的构造方法 new 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;
@SuppressWarnings({"rawtypes","unchecked"})
//扩容后的散列表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//将所有的数据搬移到扩容后的散列表中去
//遍历扩容前散列表中所有的桶位
for (int j = 0; j < oldCap; ++j) {
//当前node节点
Node<K,V> e;
//判断桶位是否有数据
if ((e = oldTab[j]) != null) {
//方便垃圾回收
oldTab[j] = null;
//长度为一的链表
if (e.next == null)
//该对象未发生过hash碰撞,直接将这个元素搬到新的散列表的某个位置中。
newTab[e.hash & (newCap - 1)] = e;
//该桶位已经树华
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//散列表的情况
else {
//低位链表:存放扩容之后的数组的下标位置和扩容前下标位置一致的键值对
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;
}
}
}
}
}
return newTab;
}