以下内容基于jdk1.7.0_79源码；
什么是HashMap
基于哈希表的一个Map接口实现，存储的对象是一个键值对对象(Entry<K,V>)；
HashMap补充说明
基于数组和链表实现，内部维护着一个数组table，该数组保存着每个链表的表头结点；查找时，先通过hash函数计算hash值，再根据hash值计算数组索引，然后根据索引找到链表表头结点，然后遍历查找该链表；
HashMap数据结构
画了个示意图，如下，左边的数组索引是根据hash值计算得到，不同hash值有可能产生一样的索引，即哈希冲突，此时采用链地址法处理哈希冲突，即将所有索引一致的节点构成一个单链表；
HashMap继承的类与实现的接口
Map接口，方法的含义很简单，基本上看个方法名就知道了，后面会在HashMap源码分析里详细说明
AbstractMap抽象类中定义的方法
HashMap源码分析，大部分都加了注释
package java.util;
2 import java.io.*;
3
4 public class HashMap<K,V>
5 extends AbstractMap<K,V>
6 implements Map<K,V>, Cloneable, Serializable
7 {
8
9 /**
10 * 默认初始容量，默认为2的4次方 = 16
11 */
12 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
13
14 /**
15 * 最大容量，默认为1的30次方
16 */
17 static final int MAXIMUM_CAPACITY = 1 << 30;
18
19 /**
20 * 默认负载因子，默认为0.75
21 */
22 static final float DEFAULT_LOAD_FACTOR = 0.75f;
23
24 /**
25 *当表还没膨胀的时候，一个共享的空表对象
26 */
27 static final Entry<?,?>[] EMPTY_TABLE = {};
28
29 /**
30 * 表，大小可以改变，且大小必须为2的幂
31 */
32 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
33
34 /**
35 * 当前Map中key-value映射的个数
36 */
37 transient int size;
38
39 /**
40 * 下次扩容阈值，当size > capacity * load factor
41 */
42 int threshold;
43
44 /**
45 * 负载因子
46 */
47 final float loadFactor;
48
49 /**
50 * Hash表结构性修改次数，用于实现迭代器快速失败行为
51 */
52 transient int modCount;
53
54 /**
55 * 容量阈值，默认大小为Integer.MAX_VALUE
56 */
57 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
58
59 /**
60 * 静态内部类Holder，存放一些只能在虚拟机启动后才能初始化的值
61 */
62 private static class Holder {
63
64 /**
65 * 容量阈值
66 */
67 static final int ALTERNATIVE_HASHING_THRESHOLD;
68
69 static {
70 //获取系统变量jdk.map.althashing.threshold
71 String altThreshold = java.security.AccessController.doPrivileged(
72 new sun.security.action.GetPropertyAction(
73 "jdk.map.althashing.threshold"));
74
75 int threshold;
76 try {
77 threshold = (null != altThreshold)
78 ? Integer.parseInt(altThreshold)
79 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
80
81 // jdk.map.althashing.threshold系统变量默认为-1，如果为-1，则将阈值设为Integer.MAX_VALUE
82 if (threshold == -1) {
83 threshold = Integer.MAX_VALUE;
84 }
85 //阈值需要为正数
86 if (threshold < 0) {
87 throw new IllegalArgumentException("value must be positive integer.");
88 }
89 } catch(IllegalArgumentException failed) {
90 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
91 }
92
93 ALTERNATIVE_HASHING_THRESHOLD = threshold;
94 }
95 }
96
97 /**
98 * A randomizing value associated with this instance that is applied to
99 * hash code of keys to make hash collisions harder to find. If 0 then
100 * alternative hashing is disabled.
101 */
102 transient int hashSeed = 0;
103
104 /**
105 * 生成一个空的HashMap,并指定其容量大小和负载因子
106 *
107 * @param initialCapacity 初始容量大小
108 * @param loadFactor 负载因子
109 * @throws IllegalArgumentException 当参数为无效的时候
110 */
111 public HashMap(int initialCapacity, float loadFactor) {
112 //保证初始容量大于等于0
113 if (initialCapacity < 0)
114 throw new IllegalArgumentException("Illegal initial capacity: " +
115 initialCapacity);
116 //保证初始容量不大于最大容量MAXIMUM_CAPACITY
117 if (initialCapacity > MAXIMUM_CAPACITY)
118 initialCapacity = MAXIMUM_CAPACITY;
119
120 //loadFactor小于0或为无效数字
121 if (loadFactor <= 0 || Float.isNaN(loadFactor))
122 throw new IllegalArgumentException("Illegal load factor: " +
123 loadFactor);
124 //负载因子
125 this.loadFactor = loadFactor;
126 //下次扩容大小
127 threshold = initialCapacity;
128 init();
129 }
130
131 /**
132 * 生成一个空的HashMap,并指定其容量大小，负载因子使用默认的0.75
133 *
134 * @param initialCapacity 初始容量大小
135 * @throws IllegalArgumentException
136 */
137 public HashMap(int initialCapacity) {
138 this(initialCapacity, DEFAULT_LOAD_FACTOR);
139 }
140
141 /**
142 * 生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75
143 */
144 public HashMap() {
145 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
146 }
147
148 /**
149 * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
150 * @param m the map whose mappings are to be placed in this map
151 * @throws NullPointerException if the specified map is null
152 */
153 public HashMap(Map<? extends K, ? extends V> m) {
154 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
155 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
156 inflateTable(threshold);
157
158 putAllForCreate(m);
159 }
160
161 //返回>=number的最小2的n次方值，如number=5，则返回8
162 private static int roundUpToPowerOf2(int number) {
163 // assert number >= 0 : "number must be non-negative";
164 return number >= MAXIMUM_CAPACITY
165 ? MAXIMUM_CAPACITY
166 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
167 }
168
169 /**
170 * 对table扩容
171 */
172 private void inflateTable(int toSize) {
173 // Find a power of 2 >= toSize
174 //找一个值（2的n次方，且>=toSize）
175 int capacity = roundUpToPowerOf2(toSize);
176
177 //下次扩容阈值
178 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
179
180 table = new Entry[capacity];
181 initHashSeedAsNeeded(capacity);
182 }
183
184 // internal utilities
185
186 /**
187 * Initialization hook for subclasses. This method is called
188 * in all constructors and pseudo-constructors (clone, readObject)
189 * after HashMap has been initialized but before any entries have
190 * been inserted. (In the absence of this method, readObject would
191 * require explicit knowledge of subclasses.)
192 */
193 void init() {
194 }
195
196 /**
197 * Initialize the hashing mask value. We defer initialization until we
198 * really need it.
199 */
200 final boolean initHashSeedAsNeeded(int capacity) {
201 boolean currentAltHashing = hashSeed != 0;
202 boolean useAltHashing = sun.misc.VM.isBooted() &&
203 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
204 boolean switching = currentAltHashing ^ useAltHashing;
205 if (switching) {
206 hashSeed = useAltHashing
207 ? sun.misc.Hashing.randomHashSeed(this)
208 : 0;
209 }
210 return switching;
211 }
212
213 /**
214 * 生成hash值
215 */
216 final int hash(Object k) {
217 int h = hashSeed;
218
219 //如果key是字符串，调用un.misc.Hashing.stringHash32生成hash值，不调用String的
220 //Oracle表示能生成更好的hash分布，不过这在jdk8中已删除
221 if (0 != h && k instanceof String) {
222 return sun.misc.Hashing.stringHash32((String) k);
223 }
224 //一次散列，调用k的hashCode方法，获取hash值
225 h ^= k.hashCode();
226
227 // This function ensures that hashCodes that differ only by
228 // constant multiples at each bit position have a bounded
229 // number of collisions (approximately 8 at default load factor).
230 //二次散列，
231 h ^= (h >>> 20) ^ (h >>> 12);
232 return h ^ (h >>> 7) ^ (h >>> 4);
233 }
234
235 /**
236 * 返回hash值的索引
237 */
238 static int indexFor(int h, int length) {
239 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
240 return h & (length-1);
241 }
242
243 /**
244 * 返回key-value映射个数
245 */
246 public int size() {
247 return size;
248 }
249
250 /**
251 * 判断map是否为空
252 */
253 public boolean isEmpty() {
254 return size == 0;
255 }
256
257 /**
258 * 返回指定key对应的value
259 */
260 public V get(Object key) {
261 //key为null情况
262 if (key == null)
263 return getForNullKey();
264
265 //根据key查找节点
266 Entry<K,V> entry = getEntry(key);
267
268 //返回key对应的值
269 return null == entry ? null : entry.getValue();
270 }
271
272 /**
273 * 查找key为null的value，注意如果key为null，则其hash值为0，默认是放在table[0]里的
274 */
275 private V getForNullKey() {
276 if (size == 0) {
277 return null;
278 }
279 //在table[0]的链表上查找key为null的键值对，因为null默认是存在table[0]的桶里
280 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
281 if (e.key == null)
282 return e.value;
283 }
284 return null;
285 }
286
287 /**
288 *判断是否包含指定的key
289 */
290 public boolean containsKey(Object key) {
291 return getEntry(key) != null;
292 }
293
294 /**
295 * 根据key查找键值对，找不到返回null
296 */
297 final Entry<K,V> getEntry(Object key) {
298 if (size == 0) {
299 return null;
300 }
301 //如果key为null，hash值为0，否则调用hash方法，对key生成hash值
302 int hash = (key == null) ? 0 : hash(key);
303
304 //调用indexFor方法生成hash值的索引，遍历该索引下的链表，查找key“相等”的键值对
305 for (Entry<K,V> e = table[indexFor(hash, table.length)];
306 e != null;
307 e = e.next) {
308 Object k;
309 if (e.hash == hash &&
310 ((k = e.key) == key || (key != null && key.equals(k))))
311 return e;
312 }
313 return null;
314 }
315
316 /**
317 * 向map存入一个键值对，如果key已存在，则覆盖
318 */
319 public V put(K key, V value) {
320 //数组为空，对数组扩容
321 if (table == EMPTY_TABLE) {
322 inflateTable(threshold);
323 }
324
325 //对key为null的键值对调用putForNullKey处理
326 if (key == null)
327 return putForNullKey(value);
328
329 //生成hash值
330 int hash = hash(key);
331
332 //生成hash值索引
333 int i = indexFor(hash, table.length);
334
335 //查找是否有key“相等”的键值对，有的话覆盖
336 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
337 Object k;
338 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
339 V oldValue = e.value;
340 e.value = value;
341 e.recordAccess(this);
342 return oldValue;
343 }
344 }
345
346 //操作次数加一，用于迭代器快速失败行为
347 modCount++;
348
349 //在指定hash值索引处的链表上增加该键值对
350 addEntry(hash, key, value, i);
351 return null;
352 }
353
354 /**
355 * 存放key为null的键值对，存放在索引为0的链表上，已存在的话，替换
356 */
357 private V putForNullKey(V value) {
358 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
359 //已存在key为null，则替换
360 if (e.key == null) {
361 V oldValue = e.value;
362 e.value = value;
363 e.recordAccess(this);
364 return oldValue;
365 }
366 }
367 //操作次数加一，用于迭代器快速失败行为
368 modCount++;
369 //在指定hash值索引处的链表上增加该键值对
370 addEntry(0, null, value, 0);
371 return null;
372 }
373
374 /**
375 * 添加键值对
376 */
377 private void putForCreate(K key, V value) {
378 //生成hash值
379 int hash = null == key ? 0 : hash(key);
380
381 //生成hash值索引，
382 int i = indexFor(hash, table.length);
383
384 /**
385 * key“相等”，则替换
386 */
387 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
388 Object k;
389 if (e.hash == hash &&
390 ((k = e.key) == key || (key != null && key.equals(k)))) {
391 e.value = value;
392 return;
393 }
394 }
395 //在指定索引处的链表上创建该键值对
396 createEntry(hash, key, value, i);
397 }
398
399 //将制定map的键值对添加到map中
400 private void putAllForCreate(Map<? extends K, ? extends V> m) {
401 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
402 putForCreate(e.getKey(), e.getValue());
403 }
404
405 /**
406 * 对数组扩容
407 */
408 void resize(int newCapacity) {
409 Entry[] oldTable = table;
410 int oldCapacity = oldTable.length;
411
412 if (oldCapacity == MAXIMUM_CAPACITY) {
413 threshold = Integer.MAX_VALUE;
414 return;
415 }
416
417 //创建一个指定大小的数组
418 Entry[] newTable = new Entry[newCapacity];
419
420 transfer(newTable, initHashSeedAsNeeded(newCapacity));
421
422 //table索引替换成新数组
423 table = newTable;
424
425 //重新计算阈值
426 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
427 }
428
429 /**
430 * 拷贝旧的键值对到新的哈希表中
431 */
432 void transfer(Entry[] newTable, boolean rehash) {
433 int newCapacity = newTable.length;
434 //遍历旧的数组
435 for (Entry<K,V> e : table) {
436 while(null != e) {
437 Entry<K,V> next = e.next;
438 if (rehash) {
439 e.hash = null == e.key ? 0 : hash(e.key);
440 }
441 //根据新的数组长度，重新计算索引，
442 int i = indexFor(e.hash, newCapacity);
443
444 //插入到链表表头
445 e.next = newTable[i];
446
447 //将e放到索引为i处
448 newTable[i] = e;
449
450 //将e设置成下个节点
451 e = next;
452 }
453 }
454 }
455
456 /**
457 * 将制定map的键值对put到本map，key“相等”的直接覆盖
458 */
459 public void putAll(Map<? extends K, ? extends V> m) {
460 int numKeysToBeAdded = m.size();
461 if (numKeysToBeAdded == 0)
462 return;
463
464 //空map，扩容
465 if (table == EMPTY_TABLE) {
466 inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
467 }
468
469 /*
470 * 判断是否需要扩容
471 */
472 if (numKeysToBeAdded > threshold) {
473 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
474 if (targetCapacity > MAXIMUM_CAPACITY)
475 targetCapacity = MAXIMUM_CAPACITY;
476 int newCapacity = table.length;
477 while (newCapacity < targetCapacity)
478 newCapacity <<= 1;
479 if (newCapacity > table.length)
480 resize(newCapacity);
481 }
482
483 //依次遍历键值对，并put
484 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
485 put(e.getKey(), e.getValue());
486 }
487
488 /**
489 * 移除指定key的键值对
490 */
491 public V remove(Object key) {
492 Entry<K,V> e = removeEntryForKey(key);
493 return (e == null ? null : e.value);
494 }
495
496 /**
497 * 移除指定key的键值对
498 */
499 final Entry<K,V> removeEntryForKey(Object key) {
500 if (size == 0) {
501 return null;
502 }
503 //计算hash值及索引
504 int hash = (key == null) ? 0 : hash(key);
505 int i = indexFor(hash, table.length);
506
507 Entry<K,V> prev = table[i];
508 Entry<K,V> e = prev;
509
510 //头节点为table[i]的单链表上执行删除节点操作
511 while (e != null) {
512 Entry<K,V> next = e.next;
513 Object k;
514 //找到要删除的节点
515 if (e.hash == hash &&
516 ((k = e.key) == key || (key != null && key.equals(k)))) {
517 modCount++;
518 size--;
519 if (prev == e)
520 table[i] = next;
521 else
522 prev.next = next;
523 e.recordRemoval(this);
524 return e;
525 }
526 prev = e;
527 e = next;
528 }
529
530 return e;
531 }
532
533 /**
534 * 删除指定键值对对象(Entry对象)
535 */
536 final Entry<K,V> removeMapping(Object o) {
537 if (size == 0 || !(o instanceof Map.Entry))
538 return null;
539
540 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
541 Object key = entry.getKey();
542 int hash = (key == null) ? 0 : hash(key);
543 int i = indexFor(hash, table.length);
544 Entry<K,V> prev = table[i];
545 Entry<K,V> e = prev;
546
547 while (e != null) {
548 Entry<K,V> next = e.next;
549 if (e.hash == hash && e.equals(entry)) {
550 modCount++;
551 size--;
552 if (prev == e)
553 table[i] = next;
554 else
555 prev.next = next;
556 e.recordRemoval(this);
557 return e;
558 }
559 prev = e;
560 e = next;
561 }
562
563 return e;
564 }
565
566 /**
567 * 清空map，将table数组所有元素设为null
568 */
569 public void clear() {
570 modCount++;
571 Arrays.fill(table, null);
572 size = 0;
573 }
574
575 /**
576 * 判断是否含有指定value的键值对
577 */
578 public boolean containsValue(Object value) {
579 if (value == null)
580 return containsNullValue();
581
582 Entry[] tab = table;
583 for (int i = 0; i < tab.length ; i++)
584 for (Entry e = tab[i] ; e != null ; e = e.next)
585 if (value.equals(e.value))
586 return true;
587 return false;
588 }
589
590 /**
591 * 判断是否含有value为null的键值对
592 */
593 private boolean containsNullValue() {
594 Entry[] tab = table;
595 for (int i = 0; i < tab.length ; i++)
596 for (Entry e = tab[i] ; e != null ; e = e.next)
597 if (e.value == null)
598 return true;
599 return false;
600 }
601
602 /**
603 * 浅拷贝，键值对不复制
604 */
605 public Object clone() {
606 HashMap<K,V> result = null;
607 try {
608 result = (HashMap<K,V>)super.clone();
609 } catch (CloneNotSupportedException e) {
610 // assert false;
611 }
612 if (result.table != EMPTY_TABLE) {
613 result.inflateTable(Math.min(
614 (int) Math.min(
615 size * Math.min(1 / loadFactor, 4.0f),
616 // we have limits...
617 HashMap.MAXIMUM_CAPACITY),
618 table.length));
619 }
620 result.entrySet = null;
621 result.modCount = 0;
622 result.size = 0;
623 result.init();
624 result.putAllForCreate(this);
625
626 return result;
627 }
628
629 //节点对象
630 static class Entry<K,V> implements Map.Entry<K,V> {
631 final K key;
632 V value;
633 Entry<K,V> next;
634 int hash;
635
636 /**
637 * 创建节点
638 */
639 Entry(int h, K k, V v, Entry<K,V> n) {
640 value = v;
641 next = n;
642 key = k;
643 hash = h;
644 }
645
646 public final K getKey() {
647 return key;
648 }
649
650 public final V getValue() {
651 return value;
652 }
653
654 //设置新value，并返回旧的value
655 public final V setValue(V newValue) {
656 V oldValue = value;
657 value = newValue;
658 return oldValue;
659 }
660
661 //判断key和value是否相同
662 public final boolean equals(Object o) {
663 if (!(o instanceof Map.Entry))
664 return false;
665 Map.Entry e = (Map.Entry)o;
666 Object k1 = getKey();
667 Object k2 = e.getKey();
668 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
669 Object v1 = getValue();
670 Object v2 = e.getValue();
671 if (v1 == v2 || (v1 != null && v1.equals(v2)))
672 return true;
673 }
674 return false;
675 }
676
677 public final int hashCode() {
678 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
679 }
680
681 public final String toString() {
682 return getKey() + "=" + getValue();
683 }
684
685 /**
686 * This method is invoked whenever the value in an entry is
687 * overwritten by an invocation of put(k,v) for a key k that's already
688 * in the HashMap.
689 */
690 void recordAccess(HashMap<K,V> m) {
691 }
692
693 /**
694 * This method is invoked whenever the entry is
695 * removed from the table.
696 */
697 void recordRemoval(HashMap<K,V> m) {
698 }
699 }
700
701 /**
702 * 添加新节点，如有必要，执行扩容操作
703 */
704 void addEntry(int hash, K key, V value, int bucketIndex) {
705 if ((size >= threshold) && (null != table[bucketIndex])) {
706 resize(2 * table.length);
707 hash = (null != key) ? hash(key) : 0;
708 bucketIndex = indexFor(hash, table.length);
709 }
710
711 createEntry(hash, key, value, bucketIndex);
712 }
713
714 /**
715 * 插入单链表表头
716 */
717 void createEntry(int hash, K key, V value, int bucketIndex) {
718 Entry<K,V> e = table[bucketIndex];
719 table[bucketIndex] = new Entry<>(hash, key, value, e);
720 size++;
721 }
722
723 //hashmap迭代器
724 private abstract class HashIterator<E> implements Iterator<E> {
725 Entry<K,V> next; // 下个键值对索引
726 int expectedModCount; // 用于判断快速失败行为
727 int index; // current slot
728 Entry<K,V> current; // current entry
729
730 HashIterator() {
731 expectedModCount = modCount;
732 if (size > 0) { // advance to first entry
733 Entry[] t = table;
734 while (index < t.length && (next = t[index++]) == null)
735 ;
736 }
737 }
738
739 public final boolean hasNext() {
740 return next != null;
741 }
742
743 final Entry<K,V> nextEntry() {
744 if (modCount != expectedModCount)
745 throw new ConcurrentModificationException();
746 Entry<K,V> e = next;
747 if (e == null)
748 throw new NoSuchElementException();
749
750 if ((next = e.next) == null) {
751 Entry[] t = table;
752 while (index < t.length && (next = t[index++]) == null)
753 ;
754 }
755 current = e;
756 return e;
757 }
758
759 public void remove() {
760 if (current == null)
761 throw new IllegalStateException();
762 if (modCount != expectedModCount)
763 throw new ConcurrentModificationException();
764 Object k = current.key;
765 current = null;
766 HashMap.this.removeEntryForKey(k);
767 expectedModCount = modCount;
768 }
769 }
770
771 //ValueIterator迭代器
772 private final class ValueIterator extends HashIterator<V> {
773 public V next() {
774 return nextEntry().value;
775 }
776 }
777 //KeyIterator迭代器
778 private final class KeyIterator extends HashIterator<K> {
779 public K next() {
780 return nextEntry().getKey();
781 }
782 }
783 ////KeyIterator迭代器
784 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
785 public Map.Entry<K,V> next() {
786 return nextEntry();
787 }
788 }
789
790 // 返回迭代器方法
791 Iterator<K> newKeyIterator() {
792 return new KeyIterator();
793 }
794 Iterator<V> newValueIterator() {
795 return new ValueIterator();
796 }
797 Iterator<Map.Entry<K,V>> newEntryIterator() {
798 return new EntryIterator();
799 }
800
801
802 // Views
803
804 private transient Set<Map.Entry<K,V>> entrySet = null;
805
806 /**
807 * 返回一个set集合，包含key
808 */
809 public Set<K> keySet() {
810 Set<K> ks = keySet;
811 return (ks != null ? ks : (keySet = new KeySet()));
812 }
813
814 private final class KeySet extends AbstractSet<K> {
815 public Iterator<K> iterator() {
816 return newKeyIterator();
817 }
818 public int size() {
819 return size;
820 }
821 public boolean contains(Object o) {
822 return containsKey(o);
823 }
824 public boolean remove(Object o) {
825 return HashMap.this.removeEntryForKey(o) != null;
826 }
827 public void clear() {
828 HashMap.this.clear();
829 }
830 }
831
832 /**
833 * 返回一个value集合，包含value
834 */
835 public Collection<V> values() {
836 Collection<V> vs = values;
837 return (vs != null ? vs : (values = new Values()));
838 }
839
840 private final class Values extends AbstractCollection<V> {
841 public Iterator<V> iterator() {
842 return newValueIterator();
843 }
844 public int size() {
845 return size;
846 }
847 public boolean contains(Object o) {
848 return containsValue(o);
849 }
850 public void clear() {
851 HashMap.this.clear();
852 }
853 }
854
855 /**
856 * 返回一个键值对集合
857 */
858 public Set<Map.Entry<K,V>> entrySet() {
859 return entrySet0();
860 }
861
862 private Set<Map.Entry<K,V>> entrySet0() {
863 Set<Map.Entry<K,V>> es = entrySet;
864 return es != null ? es : (entrySet = new EntrySet());
865 }
866
867 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
868 public Iterator<Map.Entry<K,V>> iterator() {
869 return newEntryIterator();
870 }
871 public boolean contains(Object o) {
872 if (!(o instanceof Map.Entry))
873 return false;
874 Map.Entry<K,V> e = (Map.Entry<K,V>) o;
875 Entry<K,V> candidate = getEntry(e.getKey());
876 return candidate != null && candidate.equals(e);
877 }
878 public boolean remove(Object o) {
879 return removeMapping(o) != null;
880 }
881 public int size() {
882 return size;
883 }
884 public void clear() {
885 HashMap.this.clear();
886 }
887 }
888
889 /**
890 * map序列化
891 */
892 private void writeObject(java.io.ObjectOutputStream s)
893 throws IOException
894 {
895 // Write out the threshold, loadfactor, and any hidden stuff
896 s.defaultWriteObject();
897
898 // Write out number of buckets
899 if (table==EMPTY_TABLE) {
900 s.writeInt(roundUpToPowerOf2(threshold));
901 } else {
902 s.writeInt(table.length);
903 }
904
905 // Write out size (number of Mappings)
906 s.writeInt(size);
907
908 // Write out keys and values (alternating)
909 if (size > 0) {
910 for(Map.Entry<K,V> e : entrySet0()) {
911 s.writeObject(e.getKey());
912 s.writeObject(e.getValue());
913 }
914 }
915 }
916
917 private static final long serialVersionUID = 362498820763181265L;
918
919 /**
920 * 反序列化
921 */
922 private void readObject(java.io.ObjectInputStream s)
923 throws IOException, ClassNotFoundException
924 {
925 // Read in the threshold (ignored), loadfactor, and any hidden stuff
926 s.defaultReadObject();
927 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
928 throw new InvalidObjectException("Illegal load factor: " +
929 loadFactor);
930 }
931
932 // set other fields that need values
933 table = (Entry<K,V>[]) EMPTY_TABLE;
934
935 // Read in number of buckets
936 s.readInt(); // ignored.
937
938 // Read number of mappings
939 int mappings = s.readInt();
940 if (mappings < 0)
941 throw new InvalidObjectException("Illegal mappings count: " +
942 mappings);
943
944 // capacity chosen by number of mappings and desired load (if >= 0.25)
945 int capacity = (int) Math.min(
946 mappings * Math.min(1 / loadFactor, 4.0f),
947 // we have limits...
948 HashMap.MAXIMUM_CAPACITY);
949
950 // allocate the bucket array;
951 if (mappings > 0) {
952 inflateTable(capacity);
953 } else {
954 threshold = capacity;
955 }
956
957 init(); // Give subclass a chance to do its thing.
958
959 // Read the keys and values, and put the mappings in the HashMap
960 for (int i = 0; i < mappings; i++) {
961 K key = (K) s.readObject();
962 V value = (V) s.readObject();
963 putForCreate(key, value);
964 }
965 }
966
967 // These methods are used when serializing HashSets
968 int capacity() { return table.length; }
969 float loadFactor() { return loadFactor; }
970 }
jdk1.8后
说明：上图很形象的展示了HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。所以可见，在分析源码的时候我们不知不觉就温习了数据结构的知识点，一举两得。
HashMap源码分析
类的继承关系
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
可以看到HashMap继承自父类（AbstractMap），实现了Map、Cloneable、Serializable接口。其中，Map接口定义了一组通用的操作；Cloneable接口则表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；Serializable接口表示HashMap实现了序列化，即可以将HashMap对象保存至本地，之后可以恢复状态。
类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 树的最小的容量，至少是 4 x TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
说明：类的数据成员很重要，以上也解释得很详细了，其中有一个参数MIN_TREEIFY_CAPACITY，笔者暂时还不是太清楚，有读者知道的话欢迎指导。
类的构造函数
1. HashMap(int, float)型构造函数
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于0，不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
说明：tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值。
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;
}
说明：>>> 操作符表示无符号右移，高位取0。
2. HashMap(int)型构造函数。
public HashMap(int initialCapacity) {
// 调用HashMap(int, float)型构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3. HashMap()型构造函数。
public HashMap() {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
4. HashMap(Map<? extends K>)型构造函数。
public HashMap(Map<? extends K, ? extends V> m) {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将m中的所有元素添加至HashMap中
putMapEntries(m, false);
}
说明：putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
// 未初始化，s为m的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素个数大于阈值，进行扩容处理
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);
}
}
}
重要函数分析
1. putVal函数
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)
n = (tab = resize()).length;
// (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;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
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);
// 结点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
/用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
说明：HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。
2. getNode函数
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table已经初始化，长度大于0，根据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))))
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;
}
说明：HashMap并没有直接提供getNode接口给用户调用，而是提供的get函数，而get函数就是通过getNode来取得元素的。
3. resize函数
final Node<K,V>[] resize() {
// 当前table保存
Node<K,V>[] oldTab = table;
// 保存table大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存当前阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 之前table大小大于0
if (oldCap > 0) {
// 之前table大于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值为最大整形
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍，使用左移，效率更高
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值翻倍
newThr = oldThr << 1; // double threshold
}
// 之前阈值大于0
else if (oldThr > 0)
newCap = oldThr;
// oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 之前的table已经初始化过
if (oldTab != null) {
// 复制元素，重新进行hash
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
do {
next = e.next;
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;
}
说明：进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
在resize前和resize后的元素布局如下
说明：上图只是针对了数组下标为2的桶中的各个元素在扩容后的分配布局，其他各个桶中的元素布局可以以此类推。
针对HashMap的思考
关于扩容的思考
从putVal源代码中我们可以知道，当插入一个元素的时候size就加1，若size大于threshold的时候，就会进行扩容。假设我们的capacity大小为32，loadFator为0.75,则threshold为24 = 32 * 0.75，此时，插入了25个元素，并且插入的这25个元素都在同一个桶中，桶中的数据结构为红黑树，则还有31个桶是空的，也会进行扩容处理，其实，此时，还有31个桶是空的，好像似乎不需要进行扩容处理，但是是需要扩容处理的，因为此时我们的capacity大小可能不适当。我们前面知道，扩容处理会遍历所有的元素，时间复杂度很高；前面我们还知道，经过一次扩容处理后，元素会更加均匀的分布在各个桶中，会提升访问效率。所以，说尽量避免进行扩容处理，也就意味着，遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处。如果有读者有不同意见，也欢迎讨论~