IOTXING

记录技术学习之路

0%

HashMap源码解读

Hashmap

1.hashmap的家族

1
2
public class HashMap<K, V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

能够看出,hashmap是map的一个实现类

2.基础知识

1
hashmap是有链表加数组或者红黑树构成的,对加入的key计算得到hash值,然后经过计算得到索引,如果原有的索引位置上已经有了元素,那么就会形成一个bucket,然后把新的元素加入到bucket中去,至于bucket是链表还是红黑树,由bucket里面的元素的个数决定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//默认的初始容量,如果初始化的时候没有设置容量,则使用默认容量,也就是2的四次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量,默认值为2的30次方,如果用户设置了,则必须为2的n次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的负载因子,负载因子定义了何时去进行扩容
//一般不建议修改,例如cap为100,负载因子为0.75,那么在size>=75的时候,就会调用resize去进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** bucket中的对象由链表转为红黑树的临界值。如果是默认情况,那么当相同hashcode,不同key的对象数量达到8的时候,bucket就会由链表转换为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;

/**
*由红黑树转换成链表的临界值(只在resize的时候会发生)
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
*只有当表中的键值对超过该数量的时候,才会转换成树,避免在前期表刚建立的时候,大量的元素刚好加入同一个链表导致,这种情况应该扩容,而不是转换成红黑树。为了避免在转换成树和扩容之间冲突,应该至少为TREEIFY_THRESHOLD的四倍
*/
static final int MIN_TREEIFY_CAPACITY = 64;
1
2
3
4
5
6
transient Node<K,V>[] table;      //实际存储的数组
transient Set<Map.Entry<K,V>> entrySet;
transient int size; //当前hashmap的键值对数量
transient int modCount; //当前hashmap的修改次数
int threshold; //扩容的阈值
final float loadFactor; //负载因子

每个位置上面存放的都是一个node,也就是所说的bucket,一般情况下node是一个链表。

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
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;
}

public final K getKey()
{
return key;
}

public final V getValue()
{
return value;
}

public final String toString()
{
return key + "=" + value;
}

public final int hashCode()
{
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue)
{
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o)
{
if (o == this)
{
return true;
}
if (o instanceof Map.Entry)
{
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
{
return true;
}
}
return false;
}
}

3.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
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); //这里用到了tableSizeFor,求最近的一个2的n次方
}


public HashMap( int initialCapacity){
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


public HashMap(Map < ? extends K, ? extends V > m){
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false); //直接使用一个map来初始化hashmap,会把所有的元素传入到新的hashmap中去
}

4.put

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

在put的时候,会先计算key的hash值

1
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

如果key为null,返回0,(h = key.hashCode()) ^ (h >>> 16)这是一个扰动函数,h右移16位之后,再与原来的进行异或计算,因为已经右移了,所以高16位的异或之后还是原来的高16位。也就是说相当于把原来的h的高16位与h的低16位进行异或计算,进而来降低碰撞的概率。该部分内容较多,建议参考 [hash计算原理][https://www.zhihu.com/question/20733617]

在得到hash值之后,就开始了实际的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
final V putVal ( int hash, K key, V value,boolean onlyIfAbsent,
boolean evict){
Node<K,V>[] tab; //初始化相关变量,一个新的数组tab,一个新的node p
Node<K,V> p;
int n, i; //定义节点数组,新节点p
if ((tab = table) == null || (n = tab.length) == 0) //检查当前tab是否为空,如果为空的话,就先进行表的初始化,调用resize函数进行扩容
{
n = (tab = resize()).length; //扩容后的大小
}
if ((p = tab[i = (n - 1) & hash]) == null) //i = (n-1)&hash,n-1表示的容量,(n-1)&hash计算得出的是应该插入的位置,如果table上该位置还没有元素,则把当前元素插进去
{
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)))) //如果经过计算之后,发现key一样,直接修改原先的值
{
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
{
break; //如果要加入的节点中有个key跟要插入的一样,退出循环
}
p = e; //返回插入前的上一个节点值
}
}
if (e != null)
{ // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //如果设置了onlyIfAbsent,就不会更改原来已经存在的元素
{
e.value = value;
}
afterNodeAccess(e); //返回添加之前的元素
return oldValue;
}
}
++modCount; //修改修改次数
if (++size > threshold) //如果添加后的size达到了扩容的阈值,开始扩容
{
resize();
}
afterNodeInsertion(evict);
return null;
}

上面在数组还没有初始化,或者达到了扩容的阈值的时候,会调用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
final Node<K,V>[] resize () {                       //初始化或者扩容table
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //如果是扩容的话,先拿到之前的旧的容量,如果是初始化,设定为0
int oldThr = threshold; //定义旧的阈值
int newCap, newThr = 0; //定义新的容量以及新的阈值
if (oldCap > 0) //oldCap > 0,是扩容的情况
{
if (oldCap >= MAXIMUM_CAPACITY) //如果旧的容量已经超过了最大的容量
{
threshold = Integer.MAX_VALUE; //修改扩容的阈值为int的最大值
return oldTab; //因为之前容量过大,所以已经无法扩容了,直接返回之前的table
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //设定新的容量为旧容量的二倍,并且旧的容量比默认的容量大
oldCap >= DEFAULT_INITIAL_CAPACITY)
{
newThr = oldThr << 1; // double threshold //将阈值翻倍
}
}
else if (oldThr > 0) // 初始化操作,如果之前设置了初始化的容量,则使用定于的阈值,如果没有则使用默认阈值
{
newCap = oldThr;
}
else
{ // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //设置初始化时默认的容量以及阈值
}
if (newThr == 0) //注意这里,上面对初始化的情况下,只对没有设定了初始容量的情况设定了扩容阈值,如果是指定了初始容量,则会重新计算阈值
{
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE); //计算新的阈值,如果大于最大容量,使用int的最大值
}
threshold = newThr; //修改对象中的阈值
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap]; //初始化节点数组
table = newTab; //赋值table
if (oldTab != null)
{ //如果旧的table不是空的,就通过循环,把之前的都一个个加入到新的table中去
for (int j = 0; j < oldCap; ++j)
{
Node<K,V> e;
if ((e = oldTab[j]) != null)
{ //取到数组中的第e个元素
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; //如果有bucket,则需要重新计算其中元素的新位置,使用两个链表来存储
do
{
next = e.next; //在计算索引位置的时候,使用的是(n - 1) & hash,例如n为4,100,n-1为3,也就是011。扩容之后的n为8 1000,n-1为0111。
if ((e.hash & oldCap) == 0)
{ //这里我们能够发现,在计算位置的时候,低位都是一样的11,只有高位是不同的,旧的为0,而新的为1,
if (loTail == null) //这里我们只需要计算这个高位就行,因为我们在计算的时候使用的n-1,也就是说我们只要与n进行与计算,如果得到的结果为0,说明不需要移动位置
{
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)
{ //如果lo链表不是空的,就把lo链表放在新的table中相同索引的位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null)
{ //通过计算能够发现,新老索引位置的差值一定是为旧容量的大小,因为我们在扩容的时候是按照旧容量的两倍来计算的
hiTail.next = null;
newTab[j + oldCap] = hiHead; //把需要移位的元素放入到新的索引位置上去
}
}
}
}
}
return newTab;
}

这里有个需要注意的地方,因为我们在计算元素的索引时候,使用的是(n - 1) & hash来计算元素应该被存储的位置。因为上面使用了tableSizeFor来计算了n,所以n一定是2的n次方,例如n = 4,那么n的二进制表示就是1000,n-1的二进制表示就是0111。

现在如果开始扩容,那么新的容量一定是n的2倍,也就是8,换成2进制就是10000,n-1就是01111

对于同一个元素而言,新旧的位置区别在于 n-1不同,或者是只是n-1的高位不同

  • 旧容量n-1 00111

  • 新容量n-1 01111

我们把上面两个进行或运算,得到1000,而这正是oldCap的值。因此如果 (e.hash & oldCap) == 0,说明即使扩容,得到的索引还是和之前一样,如果为1,则说明需要进行移位。

现在我们已经接近了跟索引的问题,但是因为hashmap中有bucket,也就是同一个索引上面还有很多元素,而之前的元素因为执行了(n - 1) & hash得到了一样的值,才被存到同一个位置的,现在由于n发生了变化,可能某些元素在重新计算之后,需要移到新的位置去。因此才会有后面的loHead和hiHead。

并且通过上面的计算,我们能够发现,新老位置的索引差值,刚好是旧容量的值,因此新的索引位置就等于就旧的索引位置加上旧的容量