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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
|
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/* ------------------------------------------------------------------------------ */
// 默认容量 16，必须是 2 的幂，aka：also known as
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2^30，因为 Java int 的最大值为 2^31 - 1，同时最大容量必须是 2 的幂，因此为 2^30
// 1 << 30 : 01000000 00000000 00000000 00000000 最高位是符号位
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子 = 存储的 key-value 节点数 / 容量
// 负载因子过大会减少空间开销，但会增加查找成本（get 和 put 方法）
// 负载因子过小会导致大量空间浪费
// 0.75 是权衡时间和空间开销的较好折衷
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 哈希桶树化的阈值，当一个哈希桶中的节点数大于等于 8 的时候，要把链表转化成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 哈希桶红黑树转链表的阈值，当红黑树中小于等于 6 个节点时，要把红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希桶可以树化的最小表大小，当表的容量小于 64 时，如果桶中有过多的节点，应该扩容而不是树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 底层存储用的哈希表，实质上是一个 Node 的数组
transient Node<K,V>[] table;
/* ------------------------------------------------------------------------------ */
// 哈希表中存储的基本节点类型，本质上就是一个 Map
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值，定位节点在哈希表中的索引位置
final K key; // 节点键
V value; // 节点值
Node<K,V> next; // 在桶中的链表中，链接下一个节点
...
}
// 红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left; // 左子树
TreeNode<K,V> right; // 右子树
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 节点颜色
...
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) // p 的 hash 值大于目标 hash，转到左子树
p = pl;
else if (ph < h) // p 的 hash 值小于目标 hash，转到右子树
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // hash 值相等，并且 key 一样，返回
return p;
// hash 值一样但是 key 不同，需要继续寻找
else if (pl == null) // 左子树为空，转到右子树
p = pr;
else if (pr == null) // 右子树为空，转到左子树
p = pl;
else if ((kc != null || // 指定了比较器或者 k 实现了可比较接口，进行比较选择左子树还是右子树
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
...
// 仅在 resize 函数中调用，扩容时把原红黑树分割成两棵树，称为 lower tree 和 higher tree
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
// lc 表示 lower count，代表 lower tree 中的节点数；hc 同理
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 分割逻辑，节点 key 的 hash 值与 bit 与运算为 0 则分到 lower tree中
// 在 resize 函数中调用时，bit 传入的是旧表的容量
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc; // lower count 加 1
}
// 节点 key 的 hash 值与 bit 与运算不为 0 则分到 higher tree中
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 lower tree 的节点树小于等于 UNTREEIFY_THRESHOLD（6）
// 就转红黑树为链表，这是唯一通过 UNTREEIFY_THRESHOLD 判断解除树化的地方
// 也就是说，只有在 resize 的时候，才会有当节点数小于等于 6 转化成链表的说法
// 通过 removeTreeNode 方法移除树的元素时，不是根据 UNTREEIFY_THRESHOLD，而是判断
// root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null)) 来解除树化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
// lower tree 放在原索引处
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
// higher tree 放在原索引 + 原容量处，因为是 2 倍扩容，相当于是对称位置
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
...
final void treeify(Node<K,V>[] tab) {...}
final Node<K,V> untreeify(HashMap<K,V> map) {...}
// 树版本的 putVal
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {...}
// 与红黑树有关的插入删除算法
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {...}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {...}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {...}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {...}
}
/* ------------------------------------------------------------------------------ */
// 构造函数
public HashMap() { // 默认容量 16，负载因子 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) { // 调用 HashMap(int, float) 的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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;
// threshold 是下一次要扩容的阈值，threshold = capacity * load_factor
// 在数组还没初始化的时候，值为初始的容量
// tableSizeFor(int) 函数是找到离给定数字最近的 2 的整幂数
// 比如，指定初始容量为 20，那么 HashMap 的初始容量为 32，而不是 20
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 找到给定数字的下一个 2 的整幂数
* 转化成二进制来看，给定一个数字（不是 2 的幂）的下一个 2 的整幂就是最高位前一位为 1，其余位为 0 的数；
* 对于本身就是 2 的幂的数就是本身
* 所以找给定数字的下一个 2 的整幂数可以通过 3 个步骤来完成：
* 1. 原数字减 1
* 2. 把低于最高位的所有位“变成” 1
* 3. 把 1 加回来
* 举例，对数字 01010001 来说，减 1 变成 01010000，然后使用无符号右移取或进行“涂抹”低位
* n 01010000
* n >>> 1 00101000
* n | n >>> 1 01111000
* 重复进行上述步骤，可以把所有的低位都变成 1
* 对于有符号 int，最差情况下需要右移 30 次才能把所有低位变成 1（每次右移涂抹下一位为 1，x 表示 1 或 0）
* 01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
* => 011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
* => 0111xxxxxxxxxxxxxxxxxxxxxxxxxxxx
* => 01111xxxxxxxxxxxxxxxxxxxxxxxxxxx
* => 011111xxxxxxxxxxxxxxxxxxxxxxxxxx
* ...
* => 01111111111111111111111111111111
* 但其实，第一次涂抹一位之后有两位是确定的；可以右移两位进行或运算，这样得到四位确定的；再右移四位进行或运算，得到八位；...
* 最后把减去的 1 加回来，得到 2 的整数幂
* 就是下面代码中的实现！
*/
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;
}
/**
* 在 putAll() 方法和构造方法 HashMap(Map<? extends K, ? extends V>) 中调用
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size(); // 要添加的元素个数
if (s > 0) {
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();
// 把 m 中所有元素添加到 HashMap 中
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);
}
}
}
/* ------------------------------------------------------------------------------ */
// hash 方法
static final int hash(Object key) {
int h;
// key 为 null，hash 值为 0。在 HashMap 中，允许有一个键为 null 的条目，可以有多个值为 null 的条目
// key 不为 null 的话，通过调用 key 的 hashCode方法得到 32 位的整型数，然后高 16 位和低 16 位做异或运算
// 右移 16 位异或，就在低位中掺杂了高位的信息，从而把高位的信息也参与到计算下标的运算中，可以使 hash 值更分散
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 从下面的 put 方法可以看到，HashMap 使用 n - 1 & hash(key) 计算数组下标
// n - 1 是因为与 HashMap 的容量都是 2 的幂相配合，可以使得有更多的 1 参与运算，从而使计算结果更分散
// 举例来说，如果 n = 16，即 0001 0000，如果不减 1，hash(key) 只有 1 位能够区分不同的 key，数组下标只有 0 和 16
// 减 1 之后变成 15，即 0000 1111，这样可以有更多的 1 参与运算，得到的结果可以更加分散，并且不会数组越界
// 当 n 都是 2^x 时，hash(key) & n - 1 等价于 hash(key) % n，使用 & 是因为位运算效率更高（比如 % 8 和 & 7是等价的）
// 注意：
// => key 的值不同，hash(key) 的值也有可能是相同的，在于 hash 函数的设计！
// => hash(key) 的值不同，数组下标也有可能是相同的，在于求下标的方法的设计！
/* ------------------------------------------------------------------------------ */
// put 方法
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;
// 如果是第一次使用，需要初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用 n - 1 & hash 计算元素要放入的数组索引，如果该位置还没有元素，则直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
// 从此处可以看出，Node 中的 hash 字段是使用 hash() 函数计算的 key 的哈希值
tab[i] = newNode(hash, key, value, null);
else { // 如果该位置已经有其他的元素了
Node<K,V> e; K k;
// 桶中的第一个元素 hash 值和 key 都相同，说明已经存在这个键值对了，使用 e 来记录，后面更新
// 在 Java 里，equals() 判断对象相同，则 hash 也一定要相同，那么为什么还要比较 hash 呢？
// 看代码，二者是 && 逻辑，存在短路规则，当两个 hash 不同时，可以认定两个 key 不同，就不用执行后续判断了
// 只有当 hash 不同时，才会执行后续判断，这样就提高了查找的效率
// 在后续的判断中，== 判断的是对象的内存地址，如果地址一样，无疑是同一个 key，|| 逻辑短路不用进行后续判断
// 如果没有重写 equals 方法的话，等价与 ==；但如果重写了 equals，那么属性相同的 key 也被认为是相同的
// 每一步的逻辑都是有其原因的！！！
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 否则，hash 不一样或者 key 不一样，说明不是同一个键值对
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);
// 如果链表长度大于树化的阈值（8）就链表转红黑树，binCount 从 0 开始，所以 >=7
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 在树化代码里，大于等于 MIN_TREEIFY_CAPACITY 时（64），才进行哈希桶（bin）链表转红黑树
// 当数组（table）的长度小于 MIN_TREEIFY_CAPACITY 时，不进行树化而是数组扩容（resize）
treeifyBin(tab, hash);
break;
}
// 链表中存在 hash 值和 key 值都相等的键值对，跳出循环，e 记录该条目，后面更新
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e 不为空，存在 key 相同的映射，更新该键对应的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 设置为 true 表示如果存在该键对应的映射，不改变映射的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 注意这里直接 return 掉了，不会判断 ++size > threshold
return oldValue;
}
}
++modCount;
// 如果加入元素后大于扩容阈值了，就要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// put 方法返回 put 前的旧值，如果以前有这个映射就返回旧值；没有就返回 null
return null;
}
/* ------------------------------------------------------------------------------ */
// get 方法
public V get(Object key) {
Node<K,V> e;
// 对 key 使用 hash 函数计算 hash 值然后进行查找
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 数组不空，长度不为 0，计算出来的数组下标处有节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查第一个节点是不是要找的，需要比较 key 的 hash 值和 equals 结果
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;
}
/* ------------------------------------------------------------------------------ */
// resize 方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 原来的表容量大于 0，说明已经初始化过了
if (oldCap > 0) {
// 如果原来的容量大于等于最大容量，就不再扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则，容量和扩容阈值都变成原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 表的容量小于等于 0，说明还未初始化
else if (oldThr > 0) // initial capacity was placed in threshold
// 未初始化的表阈值设置的是表容量，因此用阈值设置容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 原阈值为 0 的话就都使用默认值，表容量 16，负载因子 0.75，阈值 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr == 0 表示数组还未初始化且原阈值是大于 0 的情况
if (newThr == 0) {
// 计算阈值，阈值=容量*负载因子
float ft = (float)newCap * loadFactor;
// 阈值和容量都不能大于最大值，当负载因子大于 1 的时候，阈值是可以大于容量的
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<K,V> e;
// 如果 j 索引处不为 null，即有节点
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 原表中设置为 null，为了 gc？
// 如果 next 为空，说明就一个节点，直接计算新下标值放入
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;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 分割逻辑，e.hash & oldCap == 0 为 lower list
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // e.hash & oldCap != 0 为 higher list
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// lower list 放在原索引处
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// higher list 放在原索引 + 原容量处，因为是 2 倍扩容，相当于是对称位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
}
|