引：在Collection接口中用的最多的是ArrayList，在Map接口中用的最多的一定是HashMap，我们今天就来看看HashMap！
详细注释：源码分析地址
概览
它是基于哈希表实现的Map接口，允许null的值和null键。
HashMap的一个实例有两个影响其性能的参数： 初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表充满程度的度量。 当在散列表中的条目的数量超过了负载因数和容量的乘积，哈希表将被重新散列 （即内部数据结构被重建），使得哈希表具有桶的大约两倍。
作为一般规则，默认负载因子（0.75）提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括get和put ）。 在设置其初始容量时，应考虑Map中预期的条目数及其负载因子，以便最小化重新散列操作的数量。 如果初始容量大于最大条目数除以负载因子，则不会发生重新散列操作。
注意，HashMap不同步。 如果多个线程同时访问哈希映射，并且至少有一个线程在结构上修改了映射，那么它必须在外部进行同步。 （结构修改是添加或删除一个或多个映射的任何操作;仅改变与实例已经包含的Key相关联的值不是结构修改。）这通常通过对自然地封装映射的一些对象（ConcurrentMap等）进行同步来实现。 如果没有这样的对象存在，应该使用Collections.synchronizedMap方法“包装”。
所有这个类的方法返回的迭代器都是快速失败的 ：如果映射在迭代器创建之后的任何时间被结构地修改，除了通过迭代器自己的remove方法之外，迭代器将抛出一个ConcurrentModificationException 。
构造
在构造方法中主要就是设置初始容量和负载因子，如下面：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// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认初始容量，一定是2的n次方，这里是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认负载因子，这里是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 这里是Map存放条目的阈值
int threshold;
// 初始的节点数组，这里Node是个双向节点链表（下面注释中会直接说table）
transient Node<K,V>[] table;
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// ...
this.loadFactor = loadFactor;
// 可能大家觉得阈值应该需要乘以负载因子，先别急，往后看
this.threshold = tableSizeFor(initialCapacity);
}
// 根据所给的目标容量返回大于或等于2的幂次方
// 感觉这里吊炸天，看不懂的可以看后面参考的博客
static final int tableSizeFor(int cap) {
// 这里一定要减1，不然对于本来就是2的幂次方的数，会变成原来的两倍
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;
}
这里解答一下为什么要是2的幂次方？首先提一个东西就是散列到HashMap中是通过下面的公式：hash &(cap-1)
假设cap容量为15、16，那么他们减1之后的二进制表达为1110、1111，那么0001、0011、0101、0111, 1001、1011、1101这些桶将永远不会被用到。所以我们需要2的幂次方。
这里既然看到了hash我们就看一下HashMap的hash函数优化：1
2
3
4
5static final int hash(Object key) {
int h;
// 这里叫扰动函数(加入高位特征)，减少hash碰撞，具体的可以看后面参考里的文章
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
增
这里会有很多细节，需要耐心慢慢看。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// hash冲突的链表树化阈值（至少为8）
static final int TREEIFY_THRESHOLD = 8;
// 从树还原为链表阈值（小于6）
static final int UNTREEIFY_THRESHOLD = 6;
// 增加键值对，如果key已存在，则覆盖
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;
// 初始节点数组table为空或者长度为0
if ((tab = table) == null || (n = tab.length) == 0)
// 生成节点数组（这里会涉及到初始化table或扩容，下面会说），并返回长度
n = (tab = resize()).length;
// //如果新存放的hash值没有冲突，则放入tab
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 否则就是产生了hash冲突
Node<K,V> e; K k;
// 如果hash值相等且key值相等, 则令e指向冲突的头节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果头节点的key值与新插入的key值不等, 并且头结点是TreeNode类型,说明该hash值冲突是采用红黑树进行处理
else if (p instanceof TreeNode)
// 强转为TreeNode，插入黑红树(本篇文章不谈黑红树的操作，具体的黑红树操作看后续博文，下同)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 否则就是采用链表处理hash值冲突
else {
// 遍历冲突链表, binCount记录hash值冲突链表中节点个数
for (int binCount = 0; ; ++binCount) {
// //当遍历到冲突链表的尾部时
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 冲突链表节点大于8个
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 红黑树化
treeifyBin(tab, hash);
break;
}
//如果在冲突链表中找到相同key值的节点，直接用新的value覆盖原来的value值即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断onlyIfAbsent是否覆盖
// true表示仅当<key,value>不存在时进行插入, 为false表示强制覆盖
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 处理访问回调动作
afterNodeAccess(e);
return oldValue;
}
}
// 修改次数自增
++modCount;
// 当键值对数量size达到临界值threhold后, 需要进行扩容操作
if (++size > threshold)
resize();
// 处理插入回调动作
afterNodeInsertion(evict);
return null;
}
初始化table或者对table进行扩容(默认2倍)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
97final Node<K,V>[] resize() {
// //oldTab变量指向原来的数组
Node<K,V>[] oldTab = table;
// 用来判断是扩容还是初始化
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr变量保存原来数组的阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果原来就有东西，就进行扩容操作
if (oldCap > 0) {
// 当大于最大容量时，不扩容，只是改变阈值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// << 表示乘以2，变为原来的2倍（在操作默认大小的情况下）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新阈值也变为原来的2倍
newThr = oldThr << 1; // double threshold
}
// oldCap=0, 说明原来的table数组为null，开始初始化
// 新创建的容器容量为原来容器中设定的临界值（16）
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) {
// 这里对应的设置了阈值的情况下的初始化，设置阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 给threshold复制，这里应该也就解答了再构造那节提出的疑问了
threshold = newThr;
// 创建新数组
({"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<K,V> e;
if ((e = oldTab[j]) != null) {、
// 释放的对象及时置空，等待gc回收
oldTab[j] = null;
if (e.next == null)
// 重新hash进入新的数组
newTab[e.hash & (newCap - 1)] = e;
//如果原来这个节点已经转化为红黑树了，
//那么我们去将树上的节点rehash之后根据hash值放到新地方
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 这说明原来数组中保存的hash值存在冲突, 但是并没有采用红黑树对冲突的Hash值进行管理, 而是采用Node链表进行管理
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 如果为真，表明在扩容后(e.hash & (newCap - 1))还会和e.hash & (oldCap - 1)一样
// 如果为假，表名这些节点将hash在（当前下标 + oldCap）下
// 不懂的可以在思考🤔一下,使用这种操作，可以减少重新Hash计算
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;
}
删
1 | //删除key对应的键值对 |
改
改变对应key的值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
35public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
// 根据key找出节点
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
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 && // 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);
}
}
return null;
}
查
根据key查找值1
2
3
4
5public V get(Object key) {
Node<K,V> e;
// 这里的getNode和上面解析的一样
return (e = getNode(hash(key), key)) == null ? null : e.value;
}