logo头像
Snippet 博客主题

深入分析HashMap源码

1. HashMap简述

1.1 大致介绍

Map作为存放Key-Value数据容器在日常开发过程中是非常常见的,大部分的高级编程语言都具备Map类型的内存数据结构。在这里我们研究Java语言Map体系中最常用的HashMap(基于JDK1.8的实现)。

首先,我们打开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
/**
* HashMap是基于Map接口哈希表(Hash Table)的一种实现。
* 此实现提供所有可选的映射(map)操作,并允许存放null值和null键。
* (HashMap与Hashtable大致等效,但HashMap是不同步的,并且允许为null。)
* 此类无法保证map的顺序。特别是,它不能保证顺序会随着时间的推移保持恒定(即存元素的顺序和取元素的顺序是不一致的)。
* 假设哈希函数将元素恰好分散在存储桶中,则此实现为基本操作(get和put)提供恒定时间的性能。
* 集合视图上的迭代所需的时间与HashMap实例的“容量(capacity)”(存储桶数)及其大小(键-值映射数)成正比。
* 因此,如果迭代性能很重要,则不要将初始容量设置得过高(或负载因子过低),这一点非常重要。
*
* HashMap的实例具有两个影响其性能的参数: 初始容量和负载因子
* 容量是哈希表中的存储桶数,初始容量只是哈希表创建时的容量。
* 负载因子是衡量散列表的容量在自动增加之前允许达到的满量。
* 当哈希表中的entry(元素)数量超过负载因子和当前容量的乘积时,
* 哈希表会rehashed(即内部数据结构被重建),以便哈希表的存储桶数量大约是其两倍。
*
* 一般说来,默认的负载系数(.75)在时间和空间成本之间提供了一个很好的权衡。
* 较高的值会减少空间开销,但会增加查找成本(体现在HashMap类的大多数操作中,包括get和put)。
* 当设置map的初始容量时,应考虑map中预期的entry数量和负载因子,以便最大程度地减少重新哈希(rehash)操作的次数。
* 如果初始容量大于最大entry数除以负载因子,则将不会进行任何哈希操作(反过来说,就是初始容量16*负载因子0.75 < entry数量就需要扩容)。
*
* 如果要在HashMap实例中存储许多映射,则创建具有足够大容量的映射将比让其根据需要增长表的自动重新哈希处理更有效地存储映射
* (简言之,就是存许多映射时,指定足够大的容量可以避免反复自动rehash以提高程序性能)。
* 请注意,使用许多具有相同hashCode()的键是降低任何哈希表性能的肯定方法。
* 为了改善碰撞,当键为Comparable的实现类时,该类可以使用键之间的比较顺序来帮助打破关系。
*
* 请注意,此实现不同步。如果多个线程同时并发访问一个hashmap,并且至少有一个线程在结构上修改了map,那么它必须在外部进行同步。
* (结构修改是添加或删除一个或多个映射的任何操作。仅更改与实例已经包含的键相关联的值并不是结构上的修改。)
* 这通常通过对自然地封装映射的一些对象(同步的map)进行同步来实现。这最好在创建时完成,以防止偶发的线程不同步访问map:
* Map m = Collections.synchronizedMap(new HashMap(...));
*
* 所有这个类的“集合视图方法”返回的迭代器都是fail-fast的:如果映射在迭代器创建之后的任何时间被结构地修改,
* 除了通过迭代器自己的remove方法之外,迭代器将抛出一个ConcurrentModificationException。
* 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。
*
* 请注意,迭代器的fail-fast行为无法保证,因为一般来说,在不同步并发修改的情况下,无法做出任何硬性保证。
* fail-fast迭代器尽力最大努力抛出ConcurrentModificationException。
* 因此,编写依赖于此异常的程序的正确性将是错误的:迭代器的fail-fast行为应仅用于检测错误。
*
* 该类是Java Collections Framework的一员。
*
* @param <K> 存放Key键的类型
* @param <V> 存放Value值的类型
*
* @author Doug Lea
* @author Josh Bloch
* @author Arthur van Hoff
* @author Neal Gafter
* @see Object#hashCode()
* @see Collection
* @see Map
* @see TreeMap
* @see Hashtable
* @since 1.2
*/

最后,我们通过对类注释的大致理解,就可以对HashMap有个初步的认识。

1.2 底层数据结构

  • 哈希表
  • 链表
  • 红黑树

1.3 继承体系

image-20200618154544604

1.3.1 Map顶层接口

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
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
package java.util;

import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;

/**
* Map的顶层接口
* @param <K>
* @param <V>
*/
public interface Map<K,V> {

// 查询操作

/**
* 返回map中键值映射的数量。
* 如果map包含超过Integer.MAX_VALUE个元素,则返回Integer.MAX_VALUE。
* @return 此映射中的键值映射数
*/
int size();


/**
* 如果map不包含键值映射,则返回true。
* @return 如果此映射不包含键值映射返回true.
*/
boolean isEmpty();


/**
* 如果此映射包含指定key的映射,则返回true。
* @param key 是否包含的key
* @return 如果包含指定的key返回true
*/
boolean containsKey(Object key);


/**
* 如果此映射包含指定value的映射,则返回true。
* @param value 是否包含的value
* @return 如果包含指定的value返回true
*/
boolean containsValue(Object value);


/**
* 返回到指定key所映射的value
* @param key
* @return
*/
V get(Object key);

// 修改操作

/**
* 将key和value存放到mao映射里
* @param key
* @param value
* @return
*/
V put(K key, V value);


/**
* 根据指定的key移除映射元素
* @param key
* @return
*/
V remove(Object key);


// 批量操作

/**
* 将另一个map添加到当前map
* @param m
*/
void putAll(Map<? extends K, ? extends V> m);


/**
* 从map中清空所有的映射
*/
void clear();


// 视图

/**
* 返回map中所有的key的Set集合(key不重复)
* @return
*/
Set<K> keySet();


/**
* 返回map中所有的value的Collection集合
* @return
*/
Collection<V> values();


/**
* 返回此map中包含的映射的Set集合
* 集合元素的Entry对象是K-V映射关系
* @return
*/
Set<Entry<K, V>> entrySet();


/**
* 映射对象的抽象接口
* @param <K>
* @param <V>
*/
interface Entry<K,V> {

/**
* 返回当前entry对象的key
* @return
*/
K getKey();

/**
* 返回当前entry对象的value
* @return
*/
V getValue();


/**
* 修改当前entry对象的value
* @param value
* @return
*/
V setValue(V value);


/**
* 比较两个entry是否相等
* @param o
* @return
*/
boolean equals(Object o);

/**
* 返回当前entry的哈希码值(hashcode)
* @return
*/
int hashCode();

/**
* 返回一个Comparable比较器,根据Key的自然顺序来比较
* @param <K>
* @param <V>
* @return
*/
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}

/**
* 返回一个Comparable比较器,根据Value的自然顺序来比较
* @param <K>
* @param <V>
* @return
*/
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}


/**
* 返回一个Comparator比较器,根据Value的自然顺序来比较
* @param cmp
* @param <K>
* @param <V>
* @return
*/
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}

/**
* 返回一个Comparable比较器,根据Value来的自然顺序来比较
* @param <K>
* @param <V>
* @return
*/
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}


// 比较和哈希


/**
* 比较指定对象与当前map是否相等
* @param o
* @return
*/
boolean equals(Object o);


/**
* 返回当前map的hashCode
* @return
*/
int hashCode();



// 默认方法实现

/**
* 返回到指定Key所在映射的Value。
* 如果找到了返回对应的value,若无此包含该键的映射则返回传参过来的默认值。
* 默认实现不会保证此方法的同步或原子属性。 提供原子性保证的任何实现都必须覆盖此方法并记录其并发属性。
* @param key
* @param defaultValue
* @return
*/
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}


/**
* 内部迭代执行指定的操作
* @param action
*/
default void forEach(BiConsumer<? super K, ? super V> action) {
// 校验是否为空
Objects.requireNonNull(action);
// 遍历
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
// 获取key
k = entry.getKey();
// 获取value
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// 执行操作
action.accept(k, v);
}
}


/**
* 循环遍历所有entry并将映射的value重新设置为function操作后的结果
* @param function
*/
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
// 校验操作是否为空对象
Objects.requireNonNull(function);
// 循环遍历
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
// 获取key
k = entry.getKey();
// 获取value
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}

// 对key和vaue进行操作,这里可能抛出(IllegalStateException)而不是ConcurrentModificationException
// ise thrown from function is not a cme.
v = function.apply(k, v);

try {
// 重新set entry的value
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}


/**
* 典型的CAS操作。
* 若存在key,则替换key对应的value。
* 若不存在key,则将key和value添加到此map中。
* @param key
* @param value
* @return
*/
default V putIfAbsent(K key, V value) {
// 根据指定的key获取value
V v = get(key);
// 如果返回的value为null,将key和value添加到map中
if (v == null) {
v = put(key, value);
}
// 返回value
return v;
}


/**
* 根据key和value校验后删除指定的映射关系
* @param key
* @param value
* @return
*/
default boolean remove(Object key, Object value) {
// 根据key获取当前的value
Object curValue = get(key);
// 如果当前的value和传入的value不同或者当前value为空且对应的key不在map映射中,直接返回false
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
// 删除指定的映射
remove(key);
// 删除后返true
return true;
}


/**
* key、oldValue校验成功后替换key的最新value为newValue
* @param key
* @param oldValue
* @param newValue
* @return
*/
default boolean replace(K key, V oldValue, V newValue) {
// 获取当前key对应的value
Object curValue = get(key);
// 如果当前的value和传入的value不同或者当前value为空且对应的key不在map映射中,直接返回false
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
// 将key对应的value覆盖为最新的newValue
put(key, newValue);
// 返回true
return true;
}


/**
* 替换key对应的oldValue为最新value,并返回oldValue
* @param key
* @param value
* @return
*/
default V replace(K key, V value) {
// 存放当前map中key对应的value
V curValue;
// 如果key对应的value存在
if (((curValue = get(key)) != null) || containsKey(key)) {
// 重新替换key的curValue为value
curValue = put(key, value);
}
// 返回替换之前的value
return curValue;
}


/**
* 对于存在的指定key的value映射,不做任何操作,直接返回value。
* 对于不存在的指定key的value映射,通过mappingFunction操作后,将操作结果作为key的value存入map中。
* @param key
* @param mappingFunction
* @return
*/
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
// 校验mappingFunction操作对象是否为null
Objects.requireNonNull(mappingFunction);
// 存放value
V v;
// 判断value等于null
if ((v = get(key)) == null) {
// 存放新的value
V newValue;
// 对于key进行mappingFunction操作,并把操作结果赋值给newValue
if ((newValue = mappingFunction.apply(key)) != null) {
// 如果newValue不是null,替换key之前的value
put(key, newValue);
// 返回newValue
return newValue;
}
}

// 如果value不等于不做任何操作
return v;
}


/**
* 对于存在的指定key的value映射,通过remappingFunction操作后,将操作结果作为key的newValue存入map中并返回newValue。
* 对于不存在的指定key的value映射,不做任何操作,直接返回null。
* @param key
* @param remappingFunction
* @return
*/
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
// 校验remappingFunction操作对象是否为null
Objects.requireNonNull(remappingFunction);
// 存放旧值value
V oldValue;
// 如果旧值oldValue不等于null,做remappingFunction操作返回newValue
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
// 如果newValue不为null,替换oldValue为newValue
put(key, newValue);
// 返回newValue
return newValue;
} else {
// 如果newValue为null,移除key的映射
remove(key);
// 返回null
return null;
}
} else {
// 如果旧值oldValue等于null,返回null
return null;
}
}

/**
*
* 做一些remappingFunction后的结果作为key的value
* @param key
* @param remappingFunction
* @return
*/
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
// 校验remappingFunction操作对象是否为null
Objects.requireNonNull(remappingFunction);
// 获取key的旧值oldValue
V oldValue = get(key);

// 做一些remappingFunction操作,获取newValue
V newValue = remappingFunction.apply(key, oldValue);
// 如果操作后的newValue为null
if (newValue == null) {
// 删除映射关系
if (oldValue != null || containsKey(key)) {
// 如果oldValue不为null或包含此key的映射关系,删除这个key的映射
remove(key);
// 删除成功后,返回null
return null;
} else {
// 如果newValue不为null,什么也不做,直接返回null
return null;
}
} else {
// 添加或替换旧的映射
put(key, newValue);
// 返回新的newValue
return newValue;
}
}


/**
* 做一些remappingFunction后的结果作为key的value
* @param key
* @param value
* @param remappingFunction
* @return
*/
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
// 校验remappingFunction操作对象是否为null
Objects.requireNonNull(remappingFunction);
// 校验value操作对象是否为null
Objects.requireNonNull(value);
// 获取key的旧值oldValue
V oldValue = get(key);
// 根据oldValue判断获取新的newValue
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
// 如果newValue为空,remove掉
remove(key);
} else {
// 重新将key的value set为newValue
put(key, newValue);
}
// 返回newValue
return newValue;
}

}

1.3.2 AbstractMap抽象类

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
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
package java.util;
import java.util.Map.Entry;

/**
* 抽象的Map,实现的map的基本功能
* @param <K>
* @param <V>
*/
public abstract class AbstractMap<K,V> implements Map<K,V> {

/**
* 唯一的构造器,通常是子类隐式调用
*/
protected AbstractMap() {
}

// 查询操作

/**
* 此实现返回entrySet().size()。
*/
public int size() {
return entrySet().size();
}

/**
* 此实现返回size() == 0比较的结果。
*/
public boolean isEmpty() {
return size() == 0;
}

/**
* 如果此映射包含指定value的映射,则返回true,否则返回false
* @param value 是否包含的value
* @return
*/
public boolean containsValue(Object value) {
// 获取entrySet()的迭代器对象
Iterator<Entry<K,V>> i = entrySet().iterator();
// 判断value是否null
if (value==null) {
// 如何value为null,迭代遍历获取元素
// i.hasNext()判断迭代器是否还有下一个元素
while (i.hasNext()) {
// 获取当前迭代的元素
Entry<K,V> e = i.next();
// 如果真的有null值的value,直接返回true
if (e.getValue()==null)
return true;
}
} else {
// 如果value不为null,也循环遍历
while (i.hasNext()) {
// 获取当前迭代的元素
Entry<K,V> e = i.next();
// 这里也是比对,只不过两个对象(value)比对用equals,相同则返回true
if (value.equals(e.getValue()))
return true;
}
}
// 上述情况都不存在,即在找不到这个value,直接返回false
return false;
}


/**
* 如果此映射包含指定key的映射,则返回true,否则返回false
* @param key 是否包含的key
* @return
*/
public boolean containsKey(Object key) {
// 获取entrySet()的迭代器对象
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
// 判断key是否null
if (key==null) {
// 如何key为null,迭代遍历获取元素
while (i.hasNext()) {
// 获取当前迭代的元素
Entry<K,V> e = i.next();
// 如果真的有null值的键,直接返回true
if (e.getKey()==null)
return true;
}
} else {
// 如何key不为null,迭代遍历获取元素
while (i.hasNext()) {
// 获取当前迭代的元素
Entry<K,V> e = i.next();
// 这里也是比对,只不过两个对象(value)比对用equals,相同则返回true
if (key.equals(e.getKey()))
return true;
}
}
// 上述情况都不存在,即在找不到这个key,直接返回false
return false;
}


/**
* 根据key获取value
* @param key
* @return
*/
public V get(Object key) {
// 获取entrySet()的迭代器对象
Iterator<Entry<K,V>> i = entrySet().iterator();
// 处理空键: 如果key为null值,迭代遍历取出映射entry对象,直接返回entry的value
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
// 处理非空键: 如果key不为null值,迭代遍历取出映射entry对象,直接返回entry的value
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
// 上述两种情况都未找到key的映射,直接返回null
return null;
}


// 修改操作

/**
* 这个抽象类的put方法不允许外部调用,一旦外部调用抛出UnsupportedOperationException
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
throw new UnsupportedOperationException();
}


/**
* 根据key移除对应的映射元素
* @param key
* @return
*/
public V remove(Object key) {
// 获取entrySet()的迭代器对象
Iterator<Entry<K,V>> i = entrySet().iterator();
// 声明一个Entry对象,用于存放key对应的映射entry
Entry<K,V> correctEntry = null;
// 判断key是否为null
if (key==null) {
// 空键处理: 迭代遍历,知道找到key对应的Entry对应,若找到赋值给correctEntry变量
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
// 非空键处理: 迭代遍历,直到找到key对应的Entry对应,若找到赋值给correctEntry变量
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
// 声明一个变量,存放key对应的旧值oldValue
V oldValue = null;
// 判断上述的查找操作correctEntry是否找到,即判断是否为null
if (correctEntry !=null) {
// 如果correctEntry找到了,获取value并赋值给oldValue
oldValue = correctEntry.getValue();
// 删除当前指针所指向的元素,找到correctEntry,光标指针会停留在correctEntry,所以不用传参删除
i.remove();
}
// 返回旧值oldValue
return oldValue;
}


// 批量操作

/**
* 将一个map映射m添加到当前map映射中
* @param m
*/
public void putAll(Map<? extends K, ? extends V> m) {
// 迭代遍历,将m所有的映射存放在当前映射里
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}

/**
* 清空map中所有的映射
*/
public void clear() {
// 其实就是调用Set集合的clear()
entrySet().clear();
}


// 视图

/**
* map映射中所有(不重复)键视图(Set)集合
* transient修饰的字段将不会序列化
* 此字段可能是线程不安全的
*/
transient Set<K> keySet;

/**
* map映射中所有值视图(Collection)集合
* transient修饰的字段将不会序列化
* 此字段可能是线程不安全的
*/
transient Collection<V> values;


/**
* 获取map映射中所有(不重复)键视图(Set)集合
* @return
*/
public Set<K> keySet() {
// 将keySet赋值给ks
Set<K> ks = keySet;
// 判断ks是否为null
if (ks == null) {
// 若ks为null,实现一个AbstractSet的匿名内部类,并new出来赋值给ks
ks = new AbstractSet<K>() {
@Override
public Iterator<K> iterator() {
// 这里默认也实现一个AbstractSet.Iterator的匿名内部类
return new Iterator<K>() {
// 获取entrySet()的迭代器对象
private Iterator<Map.Entry<K,V>> i = entrySet().iterator();

/**
* 光标后移,判断是否有元素,即使判断是否有下一个元素
* @return
*/
@Override
public boolean hasNext() {
return i.hasNext();
}

/**
* 获取当前光标的元素(这里返回的是entry的key)
* @return
*/
@Override
public K next() {
return i.next().getKey();
}

/**
* 移除当前光标的元素
*/
@Override
public void remove() {
i.remove();
}
};
}

/**
* 返回迭代器的大小
* 迭代器的size()实现应当与AbstractMap.this.size()一致
* @return
*/
@Override
public int size() {
return AbstractMap.this.size();
}

/**
* 判断迭代器是否有元素,无元素返回false。
* 迭代器的isEmpty()实现应当与AbstractMap.this.isEmpty()一致
* @return
*/
@Override
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}

/**
* 清空迭代器的元素
* 迭代器的clear()实现应当与AbstractMap.this.clear()一致
* @return
*/
@Override
public void clear() {
AbstractMap.this.clear();
}

/**
* 判断迭代器是否包含元素k。
* 迭代器的contains()实现应当与AbstractMap.this.contains()一致
* @return
*/
@Override
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
// 然后将一个实现的匿名类赋值给全局的keySet视图,第一次初始化视图
keySet = ks;
}
// 直接返回ks
return ks;
}


/**
* 获取map映射中所有值视图(Collection)集合
* @return
*/
public Collection<V> values() {
// 将values赋值给ks
Collection<V> vals = values;
// 判断vals是否为null
if (vals == null) {
// 若vals为null,实现一个AbstractCollection的匿名内部类,并new出来赋值给vals
vals = new AbstractCollection<V>() {
// 这里默认也实现一个AbstractCollection.Iterator的匿名内部类
public Iterator<V> iterator() {

return new Iterator<V>() {
// 获取entrySet()的迭代器对象
private Iterator<Entry<K,V>> i = entrySet().iterator();

/**
* 光标后移,判断是否有元素,即使判断是否有下一个元素
* @return
*/
public boolean hasNext() {
return i.hasNext();
}

/**
* 获取当前光标的元素对应的元素(这里返回的是entry的key)
* @return
*/
public V next() {
return i.next().getValue();
}

/**
* 移除当前光标的元素
*/
public void remove() {
i.remove();
}
};
}

/**
* 返回迭代器的大小
* 迭代器的size()实现应当与AbstractMap.this.size()一致
* @return
*/
public int size() {
return AbstractMap.this.size();
}

/**
* 判断迭代器是否有元素,无元素返回false。
* 迭代器的isEmpty()实现应当与AbstractMap.this.isEmpty()一致
* @return
*/
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}

/**
* 清空迭代器的元素
* 迭代器的clear()实现应当与AbstractMap.this.clear()一致
* @return
*/
public void clear() {
AbstractMap.this.clear();
}

/**
* 判断迭代器是否包含元素v。
* 迭代器的contains()实现应当与AbstractMap.this.containsValue()一致
* @return
*/
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
// 然后将一个实现的匿名类赋值给全局的values视图,第一次初始化视图
values = vals;
}
// 直接返回vals
return vals;
}


/**
* entrySet继续抽象,交给子类去实现
* @return
*/
public abstract Set<Entry<K,V>> entrySet();


// 比较与哈希操作


/**
* 重写的equals()
* @param o
* @return
*/
public boolean equals(Object o) {
// 先比较引用
if (o == this)
// 若传进来的对象o就是当前this指向的对象,返回true
return true;

// 判断是否属于Map的实现类
if (!(o instanceof Map))
// 若不是Map的子类,说明肯定不是同类对象,直接返回false
return false;
// 强转为Map类型的对象
Map<?,?> m = (Map<?,?>) o;
// 长度比较,若m的size和当前的size不一致,返回false
if (m.size() != size())
return false;

try {
// 获取entrySet集合的迭代器
Iterator<Entry<K,V>> i = entrySet().iterator();
// 迭代遍历
while (i.hasNext()) {
// 获取当前迭代的entry对象
Entry<K,V> e = i.next();
// 获取key
K key = e.getKey();
// 获取value
V value = e.getValue();
// 判断value是否为null
if (value == null) {
// 若value为空,继续判断,根据当前的key去拿m映射中的value,判断m不存在该key或拿出来的不是null,则返回false
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
// 若value非空,比对value和m取出来的value是否相同,不相同返回false
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
// 出现异常返回false
return false;
} catch (NullPointerException unused) {
// 出现异常返回false
return false;
}

// 其他情况返回true
return true;
}


/**
* 返回当前map的hashCode
* @return
*/
public int hashCode() {
// 定义变量h,存放当前对象的hashCode
int h = 0;
// 获取entry集合的迭代器对象
Iterator<Entry<K,V>> i = entrySet().iterator();
// 迭代遍历
while (i.hasNext())
// 将每个entry对象的hashCode累加到变量h
h += i.next().hashCode();
// 返回最终的hashCode
return h;
}


/**
* 重写的toString()
* 思考,这个是不是多次一举:
* sb.append(value == this ? "(this Map)" : value);
* sb.append(key == this ? "(this Map)" : key);
* 答案:并不是多次一举, 请看下面代码:
* Map<Object, Object> map = new HashMap<>();
* map.put("k", "v");
* map.put(map, map);
* 如果不那样写,直接append(key)或append(value),如果没有判断this的话,toString方法会一直执行,直到抛出StackOverflowError
* @return
*/
public String toString() {
// 获取entry集合的迭代器对象
Iterator<Entry<K,V>> i = entrySet().iterator();
// 如果没有迭代元素, 直接返回“{}”字符
if (! i.hasNext())
return "{}";

// 创建一个StringBuilder字符串缓冲对象
StringBuilder sb = new StringBuilder();
// 先添加一个前缀符号“{”
sb.append('{');
// 循环遍历, 死循环遍历法
for (;;) {
// 获取entry对象
Entry<K,V> e = i.next();
// 获取key
K key = e.getKey();
// 获取value
V value = e.getValue();
// 将key添加到字符串缓冲区中,思考: key == this ? "(this Map)" : key)多次一举
sb.append(key == this ? "(this Map)" : key);
// 添加key和value的连接符“=”
sb.append('=');
// 将value添加到字符串缓冲区中,思考: value == this ? "(this Map)" : value)多次一举
sb.append(value == this ? "(this Map)" : value);
// 如果没有下一个元素,添加后缀"}",然后返回
if (! i.hasNext())
return sb.append('}').toString();
// 连接符拼接
sb.append(',').append(' ');
}
}


/**
* 浅拷贝,不拷贝keySet和values
* 重写的clone()
* @return
* @throws CloneNotSupportedException
*/
protected Object clone() throws CloneNotSupportedException {
// 浅拷贝,Object.clone()
AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
// 不拷贝keySet
result.keySet = null;
// 不拷贝values
result.values = null;
// 返回浅拷贝的map副本对象result
return result;
}


/**
* 静态的eq()比较方法,只比较两个对象的引用地址是否相同
* @param o1
* @param o2
* @return
*/
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}


/**
* 维护键和值的简单的Entry实现类。
* 可以使用setValue方法来更改值。
* 此类有助于构建自定义map实现的过程。
* 例如,返回SimpleEntry实例的数组通过Map.entrySet().toArray()可能很方便。
* @param <K> Entry的key
* @param <V> Entry的value
*/
public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
/**
* 序列化的UID
*/
private static final long serialVersionUID = -8499721149061103585L;

// 私有的key,并且定义为final不能修改
private final K key;
// 私有的value
private V value;

/**
* 键值构造器
* @param key
* @param value
*/
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}

/**
* Entry构造器
* @param entry
*/
public SimpleEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}

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

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

/**
* 重新设置value,并返回旧的值oldValue
* @param value
* @return
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}

/**
* 重写的equals()
* @param o
* @return
*/
public boolean equals(Object o) {
// 如果不是Map.Entry的子类实现,直接返回false
if (!(o instanceof Map.Entry))
return false;
// 强转为Map.Entry对象
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// 对比key是否相同并value是否相同
return eq(key, e.getKey()) && eq(value, e.getValue());
}

/**
* 返回hashCode,取key和value的异或值
* @return
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}

/**
* 重写toString()
* 用“=”连接符连接key和value
* @return
*/
public String toString() {
return key + "=" + value;
}

}

/**
* 实现不可修改的Entry类。
* 该类不支持setValue操作。
* 该类在返回键-值映射的线程安全快照的方法中可能很方便。
*/
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
// 序列化UID
private static final long serialVersionUID = 7138329143949025153L;

// 私有不可修改的key
private final K key;
// 私有不可修改的value
private final V value;

/**
* 键值构造器
* @param key
* @param value
*/
public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
}

/**
* Entry构造器
* @param entry the entry to copy
*/
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}

/**
* 返回key
* @return
*/
public K getKey() {
return key;
}

/**
* 返回value
* @return
*/
public V getValue() {
return value;
}

/**
* 不支持setValue操作
* @param value
* @return
*/
public V setValue(V value) {
throw new UnsupportedOperationException();
}

/**
*
* @param o
* @return
*/
public boolean equals(Object o) {
// 如果不是Map.Entry的子类实现,直接返回false
if (!(o instanceof Map.Entry))
return false;
// 强转为Map.Entry类型
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// 对比key是否相同并value是否相同
return eq(key, e.getKey()) && eq(value, e.getValue());
}

/**
* 返回hashCode,取key和value的异或值
* @return
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}

/**
* 重写toString()
* 用“=”连接符连接key和value
* @return
*/
public String toString() {
return key + "=" + value;
}

}

}

2. HashMap源码分析

2.1 成员变量

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
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

/** 序列化UID */
private static final long serialVersionUID = 362498820763181265L;

/**
* 默认位桶数组初始容量,必须是2的幂,这里默认是16
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;


/**
* 位桶数组大小的最大值。构造参数的大小必须是2的几次幂并且小于等于1<<30
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;


/**
* 默认负载因子是0.75,可以在构造参数里设置
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;


/**
* 树化阈值
* 一个桶中的bin的存储方式由链表转换为红黑树的阈值,当链表大小超过TREEIFY_THRESHOLD的时候转换为红黑树
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 树退化阈值
* 红黑数转换为链表(收缩机制),当执行resize操作(此时HashMap的数据存储位置会重新计算)时,桶中bin的数量少于6时,此时收
* 缩为普通链表,提高查询效率
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;


/**
* 最小树形化容量阈值,即当哈希表中的容量 > 该值时,才允许树形化链表(即将链表转换成红黑树),否则,若桶内元素太多时,则直接扩容,而不是树形化
* 当桶中bin被树化时最小的hash表容量.(若没有达到这个阈值,即hash表容量小于MIN_TREEIFY_CAPACITY
* 当桶中bin数量太多时会执行resize扩容操作).这个MIN_TREEIFY_CAPACITY的值至少TREEIFY_THRESHOLD
* 的4倍。
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 位桶数组,即Hash表,其大小总是2的几次幂,JDK1.7类型是Entry<K,V>[],JDK8优化成Node<K,V>[]
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;

/**
* 缓存的entrySet,即键值对映射对象,这里使用了AbstractMap的keyset()和values()
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* 当前map中包含的key-value数,即map的大小
* The number of key-value mappings contained in this map.
*/
transient int size;

/**
*
* HashMap的修改次数,在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,
* 比如迭代器迭代时候我们手动删除元素时,modCount会增加这个值。在迭代过程中,判断modCount和
* expectedModCount是否相等,不相等则抛出ConcurrentModificationException异常,这就是所谓的
* Fail-Fast机制。同样,ArrayList,LinkedList也有这个字段。
* 具体详情请参照HashMap源码下的抽象迭代类HashIterator,
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;

/**
* 要根据threshold的阈值来判断map是否要扩容,即threshold = capacity * load factor,
* 第一次扩容为16 * 0.75 = 12 , 当map的位桶数组容量为12的时,此时需要继续扩容。
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
* hash table的负载因子,默认负载因子是DEFAULT_LOAD_FACTOR,即0.75
* The load factor for the hash table.
* @serial
*/
final float loadFactor;
}

2.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
/**
* 多参构造器:
* 构造一个具有指定初始容量和负载因子的空HashMap。
*
* @param initialCapacity the initial capacity 初始化容量
* @param loadFactor the load factor 负载因子
* @throws IllegalArgumentException if the initial capacity is negative or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
// 若初始化容量小于0.则抛出IllegalArgumentException异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 若初始化容量大于最大容量,则最大容量就是初始化容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 若负载因子小于等于0,或是NaN(非数字),则抛出IllegalArgumentException异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 赋值负载因子
this.loadFactor = loadFactor;
// 计算threshold,后续和负载因子判断是否扩容
this.threshold = tableSizeFor(initialCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 单构造器
* 构造一个空的HashMap,它具有指定的初始容量和默认的负载系数(0.75)
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
// 调用另一个构造,只不过负载因子默认指定0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
1
2
3
4
5
6
7
8
9
/**
* 空参构造:
* 构造一个空的HashMap,其默认初始容量*(16)和默认加载因子(0.75)
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 单参构造:
* 使用与指定的Map相同的映射构造一个新的HashMap。
* 创建的HashMap具有默认的负载因子(0.75)和足以将映射保存在指定的Map中的初始容量。
* 其实就是将其他Map接口的实现类转化为HashMap。
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将传入Map对象m的Entries映射放入HashMap中
putMapEntries(m, false);
}

2.3 红黑树实现

2.3.1 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
/**
* 基本的hash桶节点,即数组存放的元素类型,实现了Map.Entry<K,V>接口。
* JDK1.7的结构是Map.Entry<K, V>的子类HashEntry<K, V>
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
// key的哈希值,用来定位数组索引位置
final int hash;
// map的key,不可不变对象,一旦设置新Key,不可更改key的值,HashMap中可存null值
final K key;
// map的value,也可以存放null值。key相同则覆盖value,
V value;
// 链表的下一个node
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,node的hashCode为key的hashCode与value的hashCode的异或结果
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

// 设置新的value,返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// 一般重写了hashCode方法,equals也会重写。
public final boolean equals(Object o) {
// 引用都是一个,则判断是同一个对象,直接返回true
if (o == this)
return true;
// 判断是否是Map.Entry同一类型,若类型不同,则返回false
if (o instanceof Map.Entry) {
// 若是 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;
}
}

2.3.2 TreeNode红黑树

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
/**
* 红黑树节点,继承LinkedHashMap.Entry<K,V>
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}

/**
* 把红黑树的根节点设为 其所在的数组槽 的第一个元素
* 首先明确:TreeNode既是一个红黑树结构,也是一个双链表结构
* 这个方法里做的事情,就是保证树的根节点一定也要成为链表的首节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) { // 根节点不为空 并且 HashMap的元素数组不为空
int index = (n - 1) & root.hash; // 根据根节点的Hash值 和 HashMap的元素数组长度 取得根节点在数组中的位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 首先取得该位置上的第一个节点对象
if (root != first) { // 如果该节点对象 与 根节点对象 不同
Node<K,V> rn; // 定义根节点的后一个节点
tab[index] = root; // 把元素数组index位置的元素替换为根节点对象
TreeNode<K,V> rp = root.prev; // 获取根节点对象的前一个节点
if ((rn = root.next) != null) // 如果后节点不为空
((TreeNode<K,V>)rn).prev = rp; // root后节点的前节点 指向到 root的前节点,相当于把root从链表中摘除
if (rp != null) // 如果root的前节点不为空
rp.next = rn; // root前节点的后节点 指向到 root的后节点
if (first != null) // 如果数组该位置上原来的元素不为空
first.prev = root; // 这个原有的元素的 前节点 指向到 root,相当于root目前位于链表首位
root.next = first; // 原来的第一个节点现在作为root的下一个节点,变成了第二个节点
root.prev = null; // 首节点没有前节点
}

/*
* 这一步是防御性的编程
* 校验TreeNode对象是否满足红黑树和双链表的特性
* 如果这个方法校验不通过:可能是因为用户编程失误,破坏了结构(例如:并发场景下);也可能是TreeNode
* 的实现有问题(这个是理论上的以防万一);
*/
assert checkInvariants(root);
}
}

/**
* 参数为HashMap的元素数组
*/
final void treeify(Node<K,V>[] tab) {
// 定义树的根节点
TreeNode<K,V> root = null;
// 遍历链表,x指向当前节点、next指向下一个节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // 下一个节点
x.left = x.right = null; // 设置当前节点的左右节点为空
if (root == null) { // 如果还没有根节点
x.parent = null; // 当前节点的父节点设为空
x.red = false; // 当前节点的红色属性设为false(把当前节点设为黑色)
root = x; // 根节点指向到当前节点
}
else { // 如果已经存在根节点了
K k = x.key; // 取得当前链表节点的key
int h = x.hash; // 取得当前链表节点的hash值
Class<?> kc = null; // 定义key所属的Class
for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历,此遍历没有设置边界,只能从内部跳出
// GOTO1
int dir, ph; // dir 标识方向(左右)、ph标识当前树节点的hash值
K pk = p.key; // 当前树节点的key
if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
dir = -1; // 标识当前链表节点会放到当前树节点的左侧
else if (ph < h)
dir = 1; // 右侧

/*
* 如果两个节点的key的hash值相等,那么还要通过其他方式再进行比较
* 如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实
* 例,那么通过comparable的方式再比较两者。
* 如果还是相等,最后再通过tieBreakOrder比较一次
*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);

TreeNode<K,V> xp = p; // 保存当前树节点

/*
* 如果dir 小于等于0 : 当前链表节点一定放置在当前树节点的左侧,但不一定是该树节点的左孩
* 子,也可能是左孩子的右孩子 或者 更深层次的节点。如果dir 大于0 : 当前链表节点一定放置在
* 当前树节点的右侧,但不一定是该树节点的右孩子,也可能是右孩子的左孩子 或者 更深层次的节
* 点。
*
* 如果当前树节点不是叶子节点,那么最终会以当前树节点的左孩子或者右孩子为起始节点 再从
* GOTO1 处开始 重新寻找自己(当前链表节点)的位置。
* 如果当前树节点就是叶子节点,那么根据dir的值,就可以把当前链表节点挂载到当前树节点的左或
* 者右侧了。
* 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp; // 当前链表节点 作为 当前树节点的子节点
if (dir <= 0)
xp.left = x; // 作为左孩子
else
xp.right = x; // 作为右孩子
root = balanceInsertion(root, x); // 重新平衡
break;
}
}
}
}

// 把所有的链表节点都遍历完之后,最终构造出来的树可能经历多个平衡操作,根节点目前到底是链表的哪一个节点是不确定的
// 因为我们要基于树来做查找,所以就应该把 tab[N] 得到的对象一定根节点对象,而目前只是链表的第一个节点对象,所以要做相应的处理。
moveRootToFront(tab, root);
}

}

2.4 重要方法

2.4.1 hash方法

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
/**
* 计算key的hash值.
* 采用key作为基数进行高位运算,减少hash碰撞。
* 低16位与高16位做异或运算,是在speed、 utility、quality三个方面进行权衡。
* key为null则hashCode为0;不为null则将key的hashCode赋值给h,最终的hashCode = h ^ (h >>> 16);
* 这里我们要讲讲数组索引的计算方式:(n- 1) & hash,n表示table.length
* 这里通过key.hashCode()计算出key的哈希值,然后将哈希值h右移16位,再与原来的h做异或^运算,这一步是高位运
* 算。设想一下,如果没有高位运算,那么hash值将是一个int型的32位数。而从2的-31次幂到2的31次幂之间,有将近几
* 十亿的空间,如果我们的HashMap的table有这么长,内存早就爆了。所以这个散列值不能直接用来最终的取模运算,而
* 需要先加入高位运算,将高16位和低16位的信息"融合"到一起,也称为"扰动函数"。这样才能保证hash值所有位的数值
* 特征都保存下来而没有遗漏,从而使映射结果尽可能的松散。最后,根据 n-1 做与操作的取模运算。这里也能看出为什么
* HashMap要限制table的长度为2的n次幂,因为这样,n-1可以保证二进制展示形式是(以16为例)0000 0000 0000
* 0000 0000 0000 0000 1111。在做"与"操作时,就等同于截取hash二进制值得后四位数据作为下标。这里也可以看
* 出"扰动函数"的重要性了,如果高位不参与运算,那么高16位的hash特征几乎永远得不到展现,发生hash碰撞的几率就
* 会增大,从而影响性能。
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
// 存储key的hashCode值
int h;
// 若key为null,则hash值为0。若不为null,先将h右移16位进行高位运算,然后将得到的结果与h再次进行异或运算返回
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2.4.2 tableSizeFor方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 对于给定的目标容量,返回两倍大小的幂。位运算快
* 简单来说:cap=5返回8,cap=12返回16,离2的n次幂(2^n>cap)最近的值
* 返回大于输入参数且最近的2的整数次幂的数,例如输入14,则返回2的4次幂,即16。
* 如果算出来的n大于等于最大的容量,则取最大的容量。
* Returns a power of two size for the given target capacity.
*/
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;
}

2.4.3 size方法

1
2
3
4
5
6
7
8
9
/**
* 返回此map中的键值数
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() {
return size;
}

2.4.4 isEmpty方法

1
2
3
4
5
6
7
8
9
/** isEmpty方法
* 若此map不包含键值映射关系,返回true
* Returns <tt>true</tt> if this map contains no key-value mappings.
*
* @return <tt>true</tt> if this map contains no key-value mappings
*/
public boolean isEmpty() {
return size == 0;
}

2.4.5 get方法

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
/**
* 我们实际用的get方法,底层调用的是getNode方法
* 返回指定key映射的value;如果此映射不包含键的映射,则返回null.
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
// 定义一个Node节点,用于存放查找结果
Node<K,V> e;
// 执行查找操作,将查找后的节点并返回
// 根据key及其hash值查询node节点,如果存在,则返回该节点的value值;如果不存在,则返回null。
return (e = getNode(hash(key), key)) == null ? null : e.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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 实现Map.get相关的方法
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none 。
* 如果找到node返回node,没有找到node则返回null
* 根据key搜索节点的方法。记住判断key相等的条件:hash值相同 并且 符合equals方法。
*/
final Node<K,V> getNode(int hash, Object key) {
// 定义变量tab是将要遍历查找的Node数组引用,first和e表示tab上的找到的Node节点,n为tab的长度,k为Key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 根据输入的hash值,可以直接计算出对应的下标(n - 1) & hash,缩小查询范围,如果存在结果,则必定在table的这个位置上。
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))))
// 判断第一个存在的节点的key是否和查询的key相等。如果相等,直接返回该节点。
return first;
// 如果第一个不匹配,则判断它的下一个是红黑树还是链表。遍历该链表/红黑树直到next为null。
if ((e = first.next) != null) {
// 红黑树就按照树的查找方式返回值。
if (first instanceof TreeNode)
// 当这个table节点上存储的是红黑树结构时,在根节点first上调用getTreeNode方法,在内部遍历红黑树节点,查看是否有匹配的TreeNode。
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 链表的方式遍历匹配返回值。
do {
// 当这个table节点上存储的是链表结构时,若两者hash相同且key是否完全相同则直接返回。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 如果key不同,一直遍历下去直到链表尽头,直到e.next == null才终止循环。
} while ((e = e.next) != null);
}
}
// 没有找到则返回null。
return null;
}

2.4.6 put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 将K-V添加到map中,如果存在K,覆盖V.
* 实际调用的是putVal方法.
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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
/**
* 实现Map.get相关的方法.
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* (onlyIfAbsent为true时,如果key存在,就不会进行put操作,原有的对应的value不会被覆盖)
* @param evict if false, the table is in creation mode.
* (evict参数用于LinkedHashMap中的尾部操作,这里没有实际意义。)
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义变量tab是将要操作的Node数组引用,p表示tab上的某Node节点,n为tab的长度,i为tab的下标。
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断当table为null或者tab的长度为0时,即table尚未初始化,此时通过resize()方法得到初始化的table。
if ((tab = table) == null || (n = tab.length) == 0)
// 这种情况是可能发生的,HashMap的table字段注释中提到:The table, initialized on first use, and resized as necessary。
n = (tab = resize()).length;
// 此处通过(n - 1)& hash计算出的值作为tab的下标i,并另p表示tab[i],也就是该链表第一个节点的位置。并判断p是否为null。
if ((p = tab[i = (n - 1) & hash]) == null)
// 当p为null时,表明tab[i]上没有任何元素,即不存在Hash冲突,那么接下来就new第一个Node节点,调用newNode方法返回新节点赋值给tab[i]。这里值得注意的是i = (n - 1) & hash相当于对hash对n的取模
tab[i] = newNode(hash, key, value, null);
// 下面进入p不为null的情况,有三种情况:p为链表节点;p为红黑树节点;p是链表节点但长度为临界长度TREEIFY_THRESHOLD,再插入任何元素就要变成红黑树了。
else {
// 定义e引用,表示即将插入的Node节点,并且下文可以看出 k = p.key。
Node<K,V> e; K k;
if (p.hash == hash &&
// HashMap中判断key相同的条件是key的hash相同(Hash是否冲突),并且符合equals方法。这里判断了p.key是否和插入的key相等,如果相等,则将p的引用赋给e。e会在最后统一进行赋值及返回。
((k = p.key) == key || (key != null && key.equals(k))))
// 这一步的判断其实是属于一种特殊情况,上述三个条件都满足,即两者hash值相同且key完全相同,于是插入操作就不需要了,只要把原来的value覆盖就可以了。e会在最后统一进行赋值及返回,这里先不进行覆盖操作。
e = p;
else if (p instanceof TreeNode)
// 现在开始了第一种情况,当前桶p是红黑树节点,那么肯定插入后仍然是红黑树节点,就要按照红黑树的方式写入数据。所以我们直接强制转型p后调用TreeNode.putTreeVal方法,返回的引用赋给e。
// 你可能好奇,这里怎么不遍历tree看看有没有key相同的节点呢?其实,putTreeVal内部进行了遍历,存在相同hash时返回被覆盖的TreeNode,否则返回null。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 接下里就是p为链表节点的情形,也就是上述说的另外两类情况:插入后还是链表/插入后转红黑树。另外,上行转型代码也说明了TreeNode是Node的一个子类。
else {
// 我们需要一个计数器来计算当前链表的元素个数,并遍历链表,binCount就是这个计数器。
for (int binCount = 0; ; ++binCount) {
// 遍历过程中当发现p.next为null时,说明链表到头了,就需要将当前的key、value封装成一个新节点,将新的链表节点直接在p的后面插入即可,即把新节点的引用赋给p.next,插入操作就完成了。注意此时e赋给p。
if ((e = p.next) == null) {
// 最后一个参数为新节点的next,这里传入null,保证了新节点继续为该链表的末端。
p.next = newNode(hash, key, value, null);
// 插入成功后,要判断是否需要转换为红黑树,因为插入后链表长度加1,而binCount并不包含新节点,所以判断时要将临界阈值减1。binCount大于等于7(其实实际上链表此时的大小为8)时转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 当满足上述转换条件时,调用treeifyBin方法,将该链表转换为红黑树。
treeifyBin(tab, hash);
// 当然如果不满足转换条件,那么插入数据后结构也无需变动,所有插入操作也到此结束了,break退出即可。
break;
}
// 在遍历链表的过程中,有可能遍历到与插入的key相同的节点,此时只要将这个节点引用赋值给e,最后通过e去把新的value覆盖掉就可以了。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到了相同key的节点,那么插入操作也不需要了,直接break退出循环进行最后的value覆盖操作。
break;
// e是当前遍历的节点p的下一个节点,p = e 就是依次遍历链表的核心语句。每次循环时p都是下一个node节点。
p = e;
}
}
// 下面JDK注释已经很清晰了,针对已经存在key的情况做处理。即我们对e进行处理。
if (e != null) { // existing mapping for key
//定义oldValue,即原存在的节点e的value值。
V oldValue = e.value;
// 方法注释提到,onlyIfAbsent为true时,若存在key相同时不做覆盖处理,这里作为判断条件,可以看出当onlyIfAbsent为默认值false或者oldValue为null时,进行覆盖操作。
if (!onlyIfAbsent || oldValue == null)
// 覆盖操作,将原节点e上的value设置为插入的新value。
e.value = value;
// 这个函数在hashmap中没有任何操作,是个空函数,它存在主要是为了linkedHashMap的一些后续处理工作。
afterNodeAccess(e);
// 返回的是被覆盖的oldValue。我们在使用put方法时很少用他的返回值,甚至忘了它的存在,这里我们知道,他返回的是被覆盖的oldValue。
return oldValue;
}
}
// 收尾工作,值得一提的是,对key相同而覆盖oldValue的情况,在前面已经return,不会执行这里,所以那一类情况不算数据结构变化,并不改变modCount值。如果走到这里,说明已经新增一个Key-Value的Node节点,modCount要自增
++modCount;
// 同理,覆盖oldValue时显然没有新元素添加,除此之外都新增了一个元素,这里++size并与threshold判断是否达到了扩容标准。
if (++size > threshold)
// 当HashMap中存在的node节点大于threshold时,hashmap进行扩容。
resize();
// 这里与前面的afterNodeAccess同理,是用于linkedHashMap的尾部操作,HashMap中并无实际意义。
afterNodeInsertion(evict);
// 最终,对于真正进行插入元素(不是覆盖的操作)的情况,put函数一律返回null。
return null;
}

2.4.7 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
/**
* map扩容机制
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 当前所有元素所在的数组,称为老的元素数组
Node<K,V>[] oldTab = table;
// 老的元素数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 老的扩容阀值设置
int oldThr = threshold;
// 新数组的容量,新数组的扩容阀值都初始化为0
int newCap, newThr = 0;
// 如果老数组长度大于0,说明已经存在元素
if (oldCap > 0) {
// 超过最大值就不再扩充了,即2的30次方时,就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
// 扩容阀值设置为int最大值(2的31次方 -1 ),因为oldCap再乘2就溢出了。
threshold = Integer.MAX_VALUE;
// 超过了最大的容量,不能扩容,直接返回老的元素数组
return oldTab;
}
/* 没超过最大值,就扩充为原来的2倍
* 如果数组元素个数在正常范围内,那么新的数组容量为老的数组容量的2倍(左移1位相当于乘以2)
* 如果扩容之后的新容量小于最大容量并且老的数组容量大于等于默认初始化容量(16),那么新数组的扩
* 容阀值设置为老阀值的2倍。(老的数组容量大于16意味着:要么构造函数指定了一个大于16的初始化容量值,
* 要么已经经历过了至少一次扩容)
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 运行到这个else if,说明老数组没有任何元素
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果老数组的扩容阀值大于0,那么设置新数组的容量为该阀值,这一步也就意味着构造该map的时候,指定了初始化容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 能运行到这里的话,说明是调用无参构造函数创建的该map,并且第一次添加元素
// 设置新数组容量为16
newCap = DEFAULT_INITIAL_CAPACITY;
// 设置新数组扩容阀值为 16 * 0.75 = 12。0.75为负载因子(当元素个数达到容量了4分之3,那么扩容)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果扩容阀值为0
if (newThr == 0) {
// 计算新的resize上限
float ft = (float)newCap * loadFactor;
// 计算扩容阀值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 设置新数组的扩容阀值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组(对于第一次添加元素,那么这个数组就是第一个数组;对于存在oldTab的时候,那么这个数组就是要需要扩容到的新数组)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将该map的table属性指向到该新数组newTab
table = newTab;
// 如果老数组不为空,说明是扩容操作,那么涉及到元素的转移操作
if (oldTab != null) {
// 遍历老数组把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
// 数组中的某个元素
Node<K,V> e;
// 如果当前位置元素不为空,那么需要转移该元素到新数组
if ((e = oldTab[j]) != null) {
// 释放掉老数组对于要转移走的元素的引用(主要为了使得数组可被回收)
oldTab[j] = null;
// 如果元素没有有下一个节点,说明该元素不存在hash冲突
if (e.next == null)
// 把元素存储到新的数组中,存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & (数组长度-1)】
// 这种与运算求模的方式要求 数组长度必须是2的N次方,但是可以通过构造函数随意指定初始化容量呀,如果指定了17,15这种,岂不是出问题了就?没关系,最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。 15 -> 16、17-> 32
newTab[e.hash & (newCap - 1)] = e;
/*
* 如果该元素有下一个节点,那么说明该位置上存在一个链表了(hash相同的多个元素以链表的方式存
* 储到了老数组的这个位置上了)。例如:数组长度为16,那么hash值为1(1%16=1)的和hash值为
* 17(17%16=1)的两个元素都是会存储在数组的第2个位置上(对应数组下标为1),当数组扩容为
* 32(1%32=1)时,hash值为1的还应该存储在新数组的第二个位置上,但是hash值为17(17%32=1
* 7)的就应该存储在新数组的第18个位置上了。所以,数组扩容后,所有元素都需要重新计算在新数组
* 中的位置。
*/
else if (e instanceof TreeNode)
// 如果该节点为TreeNode类型
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 链表优化重hash的代码块
// 按命名来翻译的话,应该叫低位首尾节点
Node<K,V> loHead = null, loTail = null;
// 按命名来翻译的话,应该叫高位首尾节点
Node<K,V> hiHead = null, hiTail = null;
// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
// 遍历链表
do {
// next表示下一个node节点
next = e.next;
// 原索引
// 这一步判断好狠,拿元素的hash值和老数组的长度做与运算
// 数组的长度一定是2的N次方(例如16),如果hash值和该长度做与运算,结果为0,就说明该hash值和数组长度取模后的值一定小于数组长度(例如mod值为1)。
// 那么该hash值再和新数组的长度取摸的话mod值也不会放生变化,所以该元素的在新数组的位置和在老数组的位置是相同的,所以该元素可以放置在低位链表中。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 如果没有尾,说明链表为空,链表为空时,头节点指向该元素。
loHead = e;
else
// 如果有尾,那么链表不为空,把该元素挂到链表的最后。
loTail.next = e;
// 把尾节点设置为当前元素。
loTail = e;
}
// 原索引+oldCap
// 如果与运算结果不为0,说明hash值大于老数组长度(例如hash值为17)。
// 此时该元素应该放置到新数组的高位位置上。
// 例:老数组长度16,那么新数组长度为32,hash为17的应该放置在数组的第17个位置上,也就是下标为16,那么下标为16已经属于高位了,低位是[0-15],高位是[16-31]。
else {
if (hiTail == null)
// 如果没有尾,说明链表为空,链表为空时,头节点指向该元素。
hiHead = e;
else
// 如果有尾,那么链表不为空,把该元素挂到链表的最后。
hiTail.next = e;
// 把尾节点设置为当前元素。
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里,即低位的元素组成的链表还是放置在原来的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里,即高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置。
if (hiTail != null) {
hiTail.next = null;
// 例1:hash为17在老数组放置在0下标,在新数组放置在16下标;
// 例2:hash为18在老数组放置在1下标,在新数组放置在17下标。
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的位桶数组
return newTab;
}

2.4.8 treeifyBin方法

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
/**
* 转换为红黑树的操作
* 参数tab: 元素数组
* 参数hash: key的hashCode
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/*
* 如果元素数组为空或者数组长度小于 树结构化的最小限制
* MIN_TREEIFY_CAPACITY 默认值64,对于这个值可以理解为:
* 如果元素数组长度小于这个值,没有必要去进行结构转换;
* 当一个数组位置上集中了多个键值对,那是因为这些key的hash值和数组长度取模之后结果相同.(并不是因为这些
* key的hash值相同).因为hash值相同的概率不高,所以可以通过扩容的方式,来使得最终这些key的hash值在和新
* 的数组长度取模之后,拆分到多个数组位置上。
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果数组为null或者小于MIN_TREEIFY_CAPACITY=64则进行扩容操作
resize();
// 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY,那么就有必要进行结构转换了。
// 根据hash值和数组长度进行取模运算后,得到链表的首节点。
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 定义首、尾节点。
TreeNode<K,V> hd = null, tl = null;
do {
// 将该节点转换为树节点。
TreeNode<K,V> p = replacementTreeNode(e, null);
// 如果尾节点为空,说明还没有根节点。
if (tl == null)
// 首节点(根节点)指向当前节点
hd = p;
else {
// 尾节点不为空,以下两行代码是一个双向链表结构
// 当前树节点的 前一个节点指向尾节点
p.prev = tl;
// 尾节点的 后一个节点指向当前节点
tl.next = p;
}
// 把当前节点设为尾节
tl = p;
// 当遍历尾节点为null时候,则结束,否则有节点继续遍历链表
} while ((e = e.next) != null);

// 到目前为止 也只是把Node对象转换成了TreeNode对象,把单向链表转换成了双向链表
// 把转换后的双向链表,替换原来位置上的单向链表
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

3. 面试连环炮

  1. HashMap的基本介绍?

    HashMap类是线程不安全且无序的K-V的Map集合容器,底层采用数组+链表+红黑树(JDK8以后)实现。

    默认初始化容量为16,默认负载因子是0.75f,当存放在元素时候,计算的hash有冲突(膨胀)时候,进行hash拉链法处理成链表.

    在效率权衡之下, 当链表长度大于8时,转化红黑树。当红黑树的节点数小于6时候,又转化为链表。

    当容量超过旧容量*负载因子的阈值时,会resize扩容。

  2. 为什么是16?为什么必须是2的幂?如果输入值不是2的幂比如10会怎么样?

  3. HashMap的什么时候扩容?扩容机制是什么样的?

  4. HashMap中get和put实现是怎么样的?

  5. 为什么不直接将key作为哈希值而是与高16位做异或运算?

  6. 为什么引入红黑树?

4. 参考文档

支付宝打赏 微信打赏

请作者喝杯咖啡吧