Java源码阅读之HashMap - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方,欢迎指正~
转载请注明出处https://blog.lzoro.com

前言

基于JDK1.8

基本说明

常量

以下常量皆为HashMap类中定义

常量 默认值 说明
DEFAULT_INITIAL_CAPACITY 1<<4=(16) 默认初始容量
MAXIMUM_CAPACITY 1 << 30 最大容量
DEFAULT_LOAD_FACTOR 0.75 默认负载因子(当存储比例超过该参数时会触发hashmap扩容)
TREEIFY_THRESHOLD 8 链表 -> 树化阈值
UNTREEIFY_THRESHOLD 6 树 -> 链表化阈值
MIN_TREEIFY_CAPACITY 64 树化后表格最小容量(至少4倍于TREEIFY_THRESHOLD)

节点(静态内部类)

HashMap的实际负责K,V存储的是transient Node<K,V>[] table,而这里的Node<K,V>则是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
/**
* 基本Hash节点,用于大多数Entries
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //Hahs
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;
}

/**
* 获取Key
*/
public final K getKey() { return key; }

/**
* 获取Value
*/
public final V getValue() { return value; }

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

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

/**
* Value设置
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

/**
* Equal方法
*/
public final boolean equals(Object o) {
//地址比较
if (o == this)
return true;
//是否是Map.Entry实例
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
//只有当Key和value都相等时,才返回true
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

静态工具集

在正式了解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
/**
* 计算关键字key的hashCode()并将Hash高位和地位进行异或(XORs)
* 这个与HashMap中的Table下标计算有关
* 哈希桶(table)的长度都是2的n次幂,So,index仅和hash的低n位有关
* 将高16位和低16进行异或,让高16位参与运算,防止频繁碰撞。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
* 如果x的类是C且C实现了Comparable,则返回x的class,否则返回null
* 如:`class C implements Comparable<C>`的形式
*
*/
static Class<?> comparableClassFor(Object x) {
//判断x是否是Comparable实例
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}

/**
* 如果x不为null且x的Class为1`kc`,则返回k.compareTo(x)
* 否则返回0
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}

/**
* 返回大于等于cap的最小的2的n次幂
* 超过MAXIMUM_CAPACITY,则返回MAXIMUM_CAPACITY
*
* 有点抽象,举个例子,如这里的cap为11
* n = 11-1=10
* 10的二进制 -> 0000 1010
* n |= n >>> 1 -> 0000 1010
* 0000 0101
* 0000 1111
*
* n |= n >>> 2 -> 0000 1111
* 0000 0011
* 0000 1111
*
* n |= n >>> 4 -> 0000 1111
* 0000 0000
* 0000 1111
*
* n |= n >>> 8 -> 0000 1111
* 0000 0000
* 0000 1111
* n |= n >>> 16 0000 1111
* 0000 0000
* 0000 1111
*
* 此时n的二级制为0000 1111,即15
* 既不小于0,也不大于MAXIMUN_CAPACITY,所以返回n+1
*
* 结果是16,即大于11的且是最小的2的n次幂
*
* 具体的原理可以google哈~
*
* 膜拜Java大神,膝盖奉上。
*/
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;
}

初始化过程

了解了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
/**
* 负责存储的哈希桶(table), 首次使用的时候进行初始化,在必要的时候进行扩容.
* 分配时,长度总是2的n次幂
* (在某些操作中可以容忍长度为零,以允许当前不需要的引导机制)
*/
transient Node<K,V>[] table;

/**
* 缓存entrySet
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* map的size
*/
transient int size;

/**
* HashMap在结构上的修改次数
* 该字段用于fail-fast策略
* 就是当使用迭代器时,如果发现预期的modCount与实际不合时抛出ConcurrentModificationException
*/
transient int modCount;

/**
* 下次resize时的哈希桶大小(capacity * load factor).
*
* @serial
*/
int threshold;

/**
* hash table的负载因子
*
* @serial
*/
final float loadFactor;

接下来是HashMap提供的4个构造方法

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
/**
* 利用指定的容量和负载因子构造一个空的HashMap
*
* @param initialCapacity 初始化容量
* @param loadFactor 负载因子
* @throws 初始容量为负数/负载因子为<=0时会抛出IllegalArgumentException
*/
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;
//这里实际上并初始化数组,只是利用上面讲到的tableSizeFor计算了长度
this.threshold = tableSizeFor(initialCapacity);
}

/**
* 利用指定的容量和默认负载因子(0.75).构造一个空的HashMap
*
* @param initialCapacity 初始化容量
* @throws 初始容量为负数时会抛出IllegalArgumentException
*/
public HashMap(int initialCapacity) {
//实际调用的是上面的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 利用默认初始容量(16)和默认负载因子(0.75).构造一个空的HashMap
*/
public HashMap() {
//其他成员变量都是默认值
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
* 根据给定的Map和默认的初始容量以及默认负载因子构造一个HashMap
*
* @param m
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//这个方法放在后面说明
putMapEntries(m, false);
}

看了上面四个构造方面,除了利用给定的Map来进行构造(第四个),其他三个都只是进行成员变量的赋值,并未真正进行空间的分配。

第四个构造函数,内部其实是调用了putMapEntries进行初始化并且存放元素,方法内部调用了另外几个关键方法,如tableSizeFor(前面已提到),resize初始化/扩容和putVal存放元素(后续会分析)。

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
/**
* 实现 Map.putAll 和 构造函数
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//如果给定的map是空的话,则不进行其他操作
if (s > 0) {
//map不为空
//如果哈希桶还未初始化
if (table == null) { // pre-size
//计算相关阈值
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
//这里的计算后,不立即进行初始化/扩容
threshold = tableSizeFor(t);
}
else if (s > threshold)
//初始化/扩容
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);
}
}
}

关键方法

put

用过HashMap的小伙伴肯定都知道这个方法,哈?没用过的话。那还是先去用用吧。

可以看到put方法,先是对key进行hash(上面的静态工具集有提到),然后调用putVal进行实际存储,另外还有putIfAbsent方法,该方法只在map不存在相应的键值对时进行放入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 将给定的key和value存储到map当中
* 若容器中已存在该key的话,旧的value会被新的value替代
*/
public V put(K key, V value) {
//可以看到这里
return putVal(hash(key), key, value, false, true);
}

/**
* 如果存在,就不覆盖旧值
*/
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}

putVal具体实现

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
/**
* 实现Map.put和相关方法
*
* @param hash key的hash
* @param key key
* @param value value
* @param onlyIfAbsent 如果为true,不改变旧值
* @param evict 如果为false,则表将采取creation模式.
* @return 前一个值,如果没有则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义相关变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table未被初始化的话,则调用resize进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//哈希桶下标计算i=(n-1)&hash,并判断桶中该位置有没有元素
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和key跟桶上找到的节点相等,则将旧的p节点赋值给e
e = p;
else if (p instanceof TreeNode)
//如果p节点是树节点(红黑树)
//插入一个树节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果以上两者皆不是,则证明当前链表还未树化
//根据定位的p节点,进行操作
for (int binCount = 0; ; ++binCount) {
//判断p节点的后续节点是否存在
if ((e = p.next) == null) {
//不存在则创建一个新节点进行插入
p.next = newNode(hash, key, value, null);
//链表长度超过树化阈值,则执行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//树化
treeifyBin(tab, hash);
break;
}
//如果p的下一个节点e跟给定节点一致,则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//把e赋值给p,进行链表遍历
p = e;
}
}
//如果e不为null
if (e != null) { // existing mapping for key
//获取旧值
V oldValue = e.value;
//判断入参条件onlyIfAbsent/旧值是否为null
if (!onlyIfAbsent || oldValue == null)
//将新值赋值给e节点
e.value = value;
//空实现 - 主要是为了linkedHashMap的一些后续处理工作
afterNodeAccess(e);
return oldValue;
}
}
//增加modCount - 在上面有给出这个变量的含义
++modCount;
//若达到扩容阈值,则进行扩容
if (++size > threshold)
//扩容
resize();
//空实现 与 afterNodeAccess同理
afterNodeInsertion(evict);
return null;
}

再跟踪下上面的几个方法newNodeputTreeValtreeifyBinresize

newNode是创建一个新节点,其实就是内部类Node的一个实例,比较简单

1
2
3
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}

putTreeVal是树化后插入节点的实现,treeifyBin是对链表进行树化。
这里的操作涉及到红黑树的操作,如果对红黑树不了解的话,建议可以先了解下相关概念和算法,由于篇幅关系,关于红黑树后面另开章节分析。

这里简单介绍一下基础概念。

红黑树(Red Black Tree) 是一种自平衡二叉查找树,性质如下:

  • 1.节点非黑即红
  • 2.根节点是黑色
  • 3.每个叶节点(NIL节点,空节点)是黑色的
  • 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/**
* 初始化或者是将哈希桶(table)大小加倍。
* 如果为空,则按threshold分配空间
* 否则,由于采取2的n次幂扩展,容器中的元素在新table中要么呆在原索引处, 要么有一个2的n次幂的位移
*
* @return the table
*/
final Node<K,V>[] resize() {
//旧的哈希桶
Node<K,V>[] oldTab = table;
//旧的容量/长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的threshold
int oldThr = threshold;
//新的相关变量
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//旧的容量大于等于MAXIMUM_CAPACITY
//则将threshod赋值为Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
//此时不再进行扩容,返回旧的哈希桶
return oldTab;
}
//新的容量为旧容量的的2倍
//判断新容量是否小于最大值且旧容量大于默认值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//对新的threshold赋值(2倍于旧的)
newThr = oldThr << 1; // double threshold
}
//判断旧的threshold
//这种情况下,初始容量为threshold的
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//threshold初始化为0,则表明是使用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//判断新的threshold是否为0
if (newThr == 0) {
//计算新的threshold,为新的容量*负载因子
float ft = (float)newCap * loadFactor;
//进行最大值判断
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将计算出来的threshold赋值到成员变量threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//根据计算的容量新建一个哈希桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//成员变量table指向新的哈希桶
table = newTab;
//判断旧的哈希桶是否为null
if (oldTab != null) {
//下面通过循环来移动将旧哈希桶移动到新的哈希桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//没有后续节点
if (e.next == null)
//将该节点存放到新的哈希桶
//使用的是2的n次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。

//eg.1
//扩容前
//e.hash = 8 -> 0000 1000
//oldCap-1 = 15 -> 0000 1111
& -> 0000 1000
// 结果 = 8
//扩容后
//e.hash = 8 -> 0000 1000
//newCap-1 = 31 -> 0001 1111
// & -> 0000 1000
// 结果 = 8 所以位置不变

//eg.2
//扩容前
//e.hash = 16 -> 0001 0000
//oldCap-1 = 15 -> 0000 1111
& -> 0000 0000
// 结果 = 0
//扩容后
//e.hash = 16 -> 0001 0000
//newCap-1 = 31 -> 0001 1111
// & -> 0001 1000
// 结果 = 16
//位置移动了0 + 16(2的4次幂,也是原来的容量oldCap)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是树化后的节点,则进行split
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//如果还未树化/没有后续节点
//维护顺序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//旧链表迁移新链表
do {
//取出后续节点
next = e.next;
//这里的e.hash & oldCap 目的是取出高位的1bit来判断是否为0,跟上面的 & (oldCap - 1)不同,这里是取出高位1bit来判断是否需要移动
//eg.1
// e.hash = 8 -> 0000 1000
// oldCap = 16 -> 0001 0000
& -> 0000 0000
结果 = 0
//如果为0,不需要移动

// e.hash = 16 -> 0001 0000
// oldCap = 16 -> 0001 0000
& -> 0001 0000
结果 = 16
//如果不为0

//不需要移动
if ((e.hash & oldCap) == 0) {
//不需要移动时,以loHead为首节点,维护链表顺序
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//需要移动时,以hiHead为首节点,维护链表顺序
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;//最后一个节点的next指向的是自己,所以置为null
newTab[j] = loHead;//在新的哈希桶中存放链表
}
if (hiTail != null) {
hiTail.next = null;//同上面
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的哈希桶
return newTab;
}

这里先抛开红黑树,单看哈希桶和链表,大致可以将扩容总结如下:

1
2
3
4
5
6
7
1、计算新的容量和阈值  
2、根据新的容量创建新的哈希桶
3、将旧桶中的元素节点存放到新的哈希桶
3.1、判断桶中的节点是否有后续节点,没有的话,确认下标后存放元素
3.2、判断是否树化,如果是,则进行红黑树操作(后续分析)
3.3、桶中节点存在后续节点(链表),则进行链表的顺序维护后,存放到新的哈希桶
4、返回扩容后的哈希桶

get

现在出门都是成双成对了(单身狗出门随时一嘴狗粮),所以HashMap里面既然有put来存放元素,肯定也有获取元素的方法,就是现在要分析的get,另外还有jdk1.8新增的getOrDefault

内部主要还是调用了hash方法对key进行哈希运算,然后调用getNode取得节点。

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
/**
* 如果存在对应的键值对,则根据对应的key,返回value,否则返回null
*
* 更精确点说,如果在该map中,存在一个key跟给定的key相同
* (同为null,或者调用equal为true),则返回该key对应的value,否则返回null
*
* null返回值不一定表示map没有包含此key的映射
* 也有可能是映射的value的确是null
* 可以使用containsKey操作来区分这两种情况(指定的key不存在/key存在但value为null)
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
* 给定key如果不存在的话,就返回默认值
*/
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

/**
* 实现 Map.get 和其他相关方法
*
* @param hash key的哈希
* @param key key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
//相关变量
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//检查哈希桶是否为null,长度是否大于0,计算下标取出元素判断是否为null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//对应的下标存在元素,则证明该key存在映射
//每次都对元素(链表首节点)进行检查判断
//如果是要找的节点,则返回
if (first.hash == hash && // always check first node
((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);
//未进行树化,则从链表中搜索对应节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果未搜索到节点,则返回null
return null;
}

remove

成双成对,不存在的。这里还有一个remove方法,用来移除键值对。

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
/**
* 根据给定的key从map中移除指定键值对
*/
public V remove(Object key) {
Node<K,V> e;
//调用下方的removeNode来实现移除
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}

/**
* 根据给定的key和value从map中移除指定键值对
*/
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}

/**
* 实现 Map.remove 和相关方法
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//前置判断,包括哈希桶是否为null,长度是否为0以及是否存在元素等
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;
//以下开始查找节点,跟getNode的类似,不再赘述
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)
//如果是首节点,就将后续节点存放到哈希桶对应下标上
tab[index] = node.next;
else
//后续节点前移
p.next = node.next;
//修改操作计数
++modCount;
//size - 1
--size;
//空实现
afterNodeRemoval(node);
return node;
}
}
return null;
}

clear

清空hashmap的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 清空所有键值对映射
* 调用结束后map将会被置空
*/
public void clear() {
Node<K,V>[] tab;
//操作计数 + 1
modCount++;
//判断哈希桶是否已经初始化
if ((tab = table) != null && size > 0) {
size = 0;
//循环清空
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}

containsValue

调用该方法判断map中是否存在对应的value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 如果map中存在指定value,则返回true
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
//判断哈希桶是否被初始化过
if ((tab = table) != null && size > 0) {
//哈希桶循环查询
for (int i = 0; i < tab.length; ++i) {
//哈希桶上每个元素,进行循环查询
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//存在值则返回
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}

其他方法

除了上面罗列的一些关键方法外,Hashmap还提供了以下方法,不再具体分析源码。

  • keySet—————– 获取所有的key(Set)
  • values—————– 获取所有的值(Collection)
  • entrySet————— 获取键值对集合(Set)
  • computeIfAbsent– 值不存在则放入
  • merge—————— 给定的key没有绑定,则进行绑定,否则替换原key的值
  • forEach—————- 循环
  • replace/replaceAll- 替换

注意

HashMap非线程安全,如果在并发场景下,使用HashMap要小心。

另外,如果需要线程安全的Map,可以移步ConcurrentHashMap

当然,不care效率的话,HashTable也是OK的。

总结

1、关键常量,如树化阈值等,见文章头部。

1、关键成员变量

  • table 哈希桶
  • loadFactor 负载因子
  • threshold 阈值

2、构造时,除了指定map进行构造外,其他构造函数均未初始化哈希桶。

3、通过hash来确认元素在桶中的位置,所以hash要足够分散,否则容易造成碰撞导致性能问题。

4、其他的诸如put、get、remove等关键操作的流程已在上诉源码中分析,之后抽空看能不能画个图更直观。

5、其他的待补充。

篇幅有点长,溜了溜了,如果对你有帮助无妨给个赞呗~~3Q

分享到