第四篇：JAVA集合之HashMap源碼剖析

HashMap簡介

    HashMap是基于哈希表實作的，每一個元素是一個key-value對，其内部通過單連結清單解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。

    HashMap是非線程安全的，隻是用于單線程環境下，多線程環境下可以采用concurrent并發包下的concurrentHashMap。

    HashMap 實作了Serializable接口，是以它支援序列化，實作了Cloneable接口，能被克隆。

HashMap源碼剖析

    HashMap的源碼如下(加入了比較詳細的注釋)：

[java]  view plain  copy

1. package java.util;    
2. import java.io.*;    
3. public class HashMap<K,V>    
4.     extends AbstractMap<K,V>    
5.     implements Map<K,V>, Cloneable, Serializable    
6. {    
7.     // 預設的初始容量（容量為HashMap中槽的數目）是16，且實際容量必須是2的整數次幂。    
8.     static final int DEFAULT_INITIAL_CAPACITY = 16;    
9.     // 最大容量（必須是2的幂且小于2的30次方，傳入容量過大将被這個值替換）    
10.     static final int MAXIMUM_CAPACITY = 1 << 30;    
11.     // 預設加載因子為0.75   
12.     static final float DEFAULT_LOAD_FACTOR = 0.75f;    
13.     // 存儲資料的Entry數組，長度是2的幂。    
14.     // HashMap采用連結清單法解決沖突，每一個Entry本質上是一個單向連結清單    
15.     transient Entry[] table;    
16.     // HashMap的底層數組中已用槽的數量    
17.     transient int size;    
18.     // HashMap的門檻值，用于判斷是否需要調整HashMap的容量（threshold = 容量*加載因子）    
19.     int threshold;    
20.     // 加載因子實際大小    
21.     final float loadFactor;    
22.     // HashMap被改變的次數    
23.     transient volatile int modCount;    
24.     // 指定“容量大小”和“加載因子”的構造函數    
25.     public HashMap(int initialCapacity, float loadFactor) {    
26.         if (initialCapacity < 0)    
27.             throw new IllegalArgumentException("Illegal initial capacity: " +    
28.                                                initialCapacity);    
29.         // HashMap的最大容量隻能是MAXIMUM_CAPACITY    
30.         if (initialCapacity > MAXIMUM_CAPACITY)    
31.             initialCapacity = MAXIMUM_CAPACITY;    
32.         //加載是以不能小于0  
33.         if (loadFactor <= 0 || Float.isNaN(loadFactor))    
34.             throw new IllegalArgumentException("Illegal load factor: " +    
35.                                                loadFactor);    
36.         // 找出“大于initialCapacity”的最小的2的幂    
37.         int capacity = 1;    
38.         while (capacity < initialCapacity)    
39.             capacity <<= 1;    
40.         // 設定“加載因子”    
41.         this.loadFactor = loadFactor;    
42.         // 設定“HashMap門檻值”，當HashMap中存儲資料的數量達到threshold時，就需要将HashMap的容量加倍。    
43.         threshold = (int)(capacity * loadFactor);    
44.         // 建立Entry數組，用來儲存資料    
45.         table = new Entry[capacity];    
46.         init();    
47.     }    
48.     // 指定“容量大小”的構造函數    
49.     public HashMap(int initialCapacity) {    
50.         this(initialCapacity, DEFAULT_LOAD_FACTOR);    
51.     }    
52.     // 預設構造函數。    
53.     public HashMap() {    
54.         // 設定“加載因子”為預設加載因子0.75    
55.         this.loadFactor = DEFAULT_LOAD_FACTOR;    
56.         // 設定“HashMap門檻值”，當HashMap中存儲資料的數量達到threshold時，就需要将HashMap的容量加倍。    
57.         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);    
58.         // 建立Entry數組，用來儲存資料    
59.         table = new Entry[DEFAULT_INITIAL_CAPACITY];    
60.         init();    
61.     }    
62.     // 包含“子Map”的構造函數    
63.     public HashMap(Map<? extends K, ? extends V> m) {    
64.         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,    
65.                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);    
66.         // 将m中的全部元素逐個添加到HashMap中    
67.         putAllForCreate(m);    
68.     }    
69.     //求hash值的方法，重新計算hash值  
70.     static int hash(int h) {    
71.         h ^= (h >>> 20) ^ (h >>> 12);    
72.         return h ^ (h >>> 7) ^ (h >>> 4);    
73.     }    
74.     // 傳回h在數組中的索引值，這裡用&代替取模，旨在提升效率   
75.     // h & (length-1)保證傳回值的小于length    
76.     static int indexFor(int h, int length) {    
77.         return h & (length-1);    
78.     }    
79.     public int size() {    
80.         return size;    
81.     }    
82.     public boolean isEmpty() {    
83.         return size == 0;    
84.     }    
85.     // 擷取key對應的value    
86.     public V get(Object key) {    
87.         if (key == null)    
88.             return getForNullKey();    
89.         // 擷取key的hash值    
90.         int hash = hash(key.hashCode());    
91.         // 在“該hash值對應的連結清單”上查找“鍵值等于key”的元素    
92.         for (Entry<K,V> e = table[indexFor(hash, table.length)];    
93.              e != null;    
94.              e = e.next) {    
95.             Object k;    
96.             //判斷key是否相同  
97.             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
98.                 return e.value;    
99.         }  
100.         //沒找到則傳回null  
101.         return null;    
102.     }    
103.     // 擷取“key為null”的元素的值    
104.     // HashMap将“key為null”的元素存儲在table[0]位置，但不一定是該連結清單的第一個位置！    
105.     private V getForNullKey() {    
106.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
107.             if (e.key == null)    
108.                 return e.value;    
109.         }    
110.         return null;    
111.     }    
112.     // HashMap是否包含key    
113.     public boolean containsKey(Object key) {    
114.         return getEntry(key) != null;    
115.     }    
116.     // 傳回“鍵為key”的鍵值對    
117.     final Entry<K,V> getEntry(Object key) {    
118.         // 擷取哈希值    
119.         // HashMap将“key為null”的元素存儲在table[0]位置，“key不為null”的則調用hash()計算哈希值    
120.         int hash = (key == null) ? 0 : hash(key.hashCode());    
121.         // 在“該hash值對應的連結清單”上查找“鍵值等于key”的元素    
122.         for (Entry<K,V> e = table[indexFor(hash, table.length)];    
123.              e != null;    
124.              e = e.next) {    
125.             Object k;    
126.             if (e.hash == hash &&    
127.                 ((k = e.key) == key || (key != null && key.equals(k))))    
128.                 return e;    
129.         }    
130.         return null;    
131.     }    
132.     // 将“key-value”添加到HashMap中    
133.     public V put(K key, V value) {    
134.         // 若“key為null”，則将該鍵值對添加到table[0]中。    
135.         if (key == null)    
136.             return putForNullKey(value);    
137.         // 若“key不為null”，則計算該key的哈希值，然後将其添加到該哈希值對應的連結清單中。    
138.         int hash = hash(key.hashCode());    
139.         int i = indexFor(hash, table.length);    
140.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
141.             Object k;    
142.             // 若“該key”對應的鍵值對已經存在，則用新的value取代舊的value。然後退出！    
143.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
144.                 V oldValue = e.value;    
145.                 e.value = value;    
146.                 e.recordAccess(this);    
147.                 return oldValue;    
148.             }    
149.         }    
150.         // 若“該key”對應的鍵值對不存在，則将“key-value”添加到table中    
151.         modCount++;  
152.         //将key-value添加到table[i]處  
153.         addEntry(hash, key, value, i);    
154.         return null;    
155.     }    
156.     // putForNullKey()的作用是将“key為null”鍵值對添加到table[0]位置    
157.     private V putForNullKey(V value) {    
158.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
159.             if (e.key == null) {    
160.                 V oldValue = e.value;    
161.                 e.value = value;    
162.                 e.recordAccess(this);    
163.                 return oldValue;    
164.             }    
165.         }    
166.         // 如果沒有存在key為null的鍵值對，則直接題阿見到table[0]處!    
167.         modCount++;    
168.         addEntry(0, null, value, 0);    
169.         return null;    
170.     }    
171.     // 建立HashMap對應的“添加方法”，    
172.     // 它和put()不同。putForCreate()是内部方法，它被構造函數等調用，用來建立HashMap    
173.     // 而put()是對外提供的往HashMap中添加元素的方法。    
174.     private void putForCreate(K key, V value) {    
175.         int hash = (key == null) ? 0 : hash(key.hashCode());    
176.         int i = indexFor(hash, table.length);    
177.         // 若該HashMap表中存在“鍵值等于key”的元素，則替換該元素的value值    
178.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
179.             Object k;    
180.             if (e.hash == hash &&    
181.                 ((k = e.key) == key || (key != null && key.equals(k)))) {    
182.                 e.value = value;    
183.                 return;    
184.             }    
185.         }    
186.         // 若該HashMap表中不存在“鍵值等于key”的元素，則将該key-value添加到HashMap中    
187.         createEntry(hash, key, value, i);    
188.     }    
189.     // 将“m”中的全部元素都添加到HashMap中。    
190.     // 該方法被内部的構造HashMap的方法所調用。    
191.     private void putAllForCreate(Map<? extends K, ? extends V> m) {    
192.         // 利用疊代器将元素逐個添加到HashMap中    
193.         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    
194.             Map.Entry<? extends K, ? extends V> e = i.next();    
195.             putForCreate(e.getKey(), e.getValue());    
196.         }    
197.     }    
198.     // 重新調整HashMap的大小，newCapacity是調整後的容量    
199.     void resize(int newCapacity) {    
200.         Entry[] oldTable = table;    
201.         int oldCapacity = oldTable.length;   
202.         //如果就容量已經達到了最大值，則不能再擴容，直接傳回  
203.         if (oldCapacity == MAXIMUM_CAPACITY) {    
204.             threshold = Integer.MAX_VALUE;    
205.             return;    
206.         }    
207.         // 建立一個HashMap，将“舊HashMap”的全部元素添加到“新HashMap”中，    
208.         // 然後，将“新HashMap”指派給“舊HashMap”。    
209.         Entry[] newTable = new Entry[newCapacity];    
210.         transfer(newTable);    
211.         table = newTable;    
212.         threshold = (int)(newCapacity * loadFactor);    
213.     }    
214.     // 将HashMap中的全部元素都添加到newTable中    
215.     void transfer(Entry[] newTable) {    
216.         Entry[] src = table;    
217.         int newCapacity = newTable.length;    
218.         for (int j = 0; j < src.length; j++) {    
219.             Entry<K,V> e = src[j];    
220.             if (e != null) {    
221.                 src[j] = null;    
222.                 do {    
223.                     Entry<K,V> next = e.next;    
224.                     int i = indexFor(e.hash, newCapacity);    
225.                     e.next = newTable[i];    
226.                     newTable[i] = e;    
227.                     e = next;    
228.                 } while (e != null);    
229.             }    
230.         }    
231.     }    
232.     // 将"m"的全部元素都添加到HashMap中    
233.     public void putAll(Map<? extends K, ? extends V> m) {    
234.         // 有效性判斷    
235.         int numKeysToBeAdded = m.size();    
236.         if (numKeysToBeAdded == 0)    
237.             return;    
238.         // 計算容量是否足夠，    
239.         // 若“目前閥值容量 < 需要的容量”，則将容量x2。    
240.         if (numKeysToBeAdded > threshold) {    
241.             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);    
242.             if (targetCapacity > MAXIMUM_CAPACITY)    
243.                 targetCapacity = MAXIMUM_CAPACITY;    
244.             int newCapacity = table.length;    
245.             while (newCapacity < targetCapacity)    
246.                 newCapacity <<= 1;    
247.             if (newCapacity > table.length)    
248.                 resize(newCapacity);    
249.         }    
250.         // 通過疊代器，将“m”中的元素逐個添加到HashMap中。    
251.         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    
252.             Map.Entry<? extends K, ? extends V> e = i.next();    
253.             put(e.getKey(), e.getValue());    
254.         }    
255.     }    
256.     // 删除“鍵為key”元素    
257.     public V remove(Object key) {    
258.         Entry<K,V> e = removeEntryForKey(key);    
259.         return (e == null ? null : e.value);    
260.     }    
261.     // 删除“鍵為key”的元素    
262.     final Entry<K,V> removeEntryForKey(Object key) {    
263.         // 擷取哈希值。若key為null，則哈希值為0；否則調用hash()進行計算    
264.         int hash = (key == null) ? 0 : hash(key.hashCode());    
265.         int i = indexFor(hash, table.length);    
266.         Entry<K,V> prev = table[i];    
267.         Entry<K,V> e = prev;    
268.         // 删除連結清單中“鍵為key”的元素    
269.         // 本質是“删除單向連結清單中的節點”    
270.         while (e != null) {    
271.             Entry<K,V> next = e.next;    
272.             Object k;    
273.             if (e.hash == hash &&    
274.                 ((k = e.key) == key || (key != null && key.equals(k)))) {    
275.                 modCount++;    
276.                 size--;    
277.                 if (prev == e)    
278.                     table[i] = next;    
279.                 else   
280.                     prev.next = next;    
281.                 e.recordRemoval(this);    
282.                 return e;    
283.             }    
284.             prev = e;    
285.             e = next;    
286.         }    
287.         return e;    
288.     }    
289.     // 删除“鍵值對”    
290.     final Entry<K,V> removeMapping(Object o) {    
291.         if (!(o instanceof Map.Entry))    
292.             return null;    
293.         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;    
294.         Object key = entry.getKey();    
295.         int hash = (key == null) ? 0 : hash(key.hashCode());    
296.         int i = indexFor(hash, table.length);    
297.         Entry<K,V> prev = table[i];    
298.         Entry<K,V> e = prev;    
299.         // 删除連結清單中的“鍵值對e”    
300.         // 本質是“删除單向連結清單中的節點”    
301.         while (e != null) {    
302.             Entry<K,V> next = e.next;    
303.             if (e.hash == hash && e.equals(entry)) {    
304.                 modCount++;    
305.                 size--;    
306.                 if (prev == e)    
307.                     table[i] = next;    
308.                 else   
309.                     prev.next = next;    
310.                 e.recordRemoval(this);    
311.                 return e;    
312.             }    
313.             prev = e;    
314.             e = next;    
315.         }    
316.         return e;    
317.     }    
318.     // 清空HashMap，将所有的元素設為null    
319.     public void clear() {    
320.         modCount++;    
321.         Entry[] tab = table;    
322.         for (int i = 0; i < tab.length; i++)    
323.             tab[i] = null;    
324.         size = 0;    
325.     }    
326.     // 是否包含“值為value”的元素    
327.     public boolean containsValue(Object value) {    
328.     // 若“value為null”，則調用containsNullValue()查找    
329.     if (value == null)    
330.             return containsNullValue();    
331.     // 若“value不為null”，則查找HashMap中是否有值為value的節點。    
332.     Entry[] tab = table;    
333.         for (int i = 0; i < tab.length ; i++)    
334.             for (Entry e = tab[i] ; e != null ; e = e.next)    
335.                 if (value.equals(e.value))    
336.                     return true;    
337.     return false;    
338.     }    
339.     // 是否包含null值    
340.     private boolean containsNullValue() {    
341.     Entry[] tab = table;    
342.         for (int i = 0; i < tab.length ; i++)    
343.             for (Entry e = tab[i] ; e != null ; e = e.next)    
344.                 if (e.value == null)    
345.                     return true;    
346.     return false;    
347.     }    
348.     // 克隆一個HashMap，并傳回Object對象    
349.     public Object clone() {    
350.         HashMap<K,V> result = null;    
351.         try {    
352.             result = (HashMap<K,V>)super.clone();    
353.         } catch (CloneNotSupportedException e) {    
354.             // assert false;    
355.         }    
356.         result.table = new Entry[table.length];    
357.         result.entrySet = null;    
358.         result.modCount = 0;    
359.         result.size = 0;    
360.         result.init();    
361.         // 調用putAllForCreate()将全部元素添加到HashMap中    
362.         result.putAllForCreate(this);    
363.         return result;    
364.     }    
365.     // Entry是單向連結清單。    
366.     // 它是 “HashMap鍊式存儲法”對應的連結清單。    
367.     // 它實作了Map.Entry 接口，即實作getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數    
368.     static class Entry<K,V> implements Map.Entry<K,V> {    
369.         final K key;    
370.         V value;    
371.         // 指向下一個節點    
372.         Entry<K,V> next;    
373.         final int hash;    
374.         // 構造函數。    
375.         // 輸入參數包括"哈希值(h)", "鍵(k)", "值(v)", "下一節點(n)"    
376.         Entry(int h, K k, V v, Entry<K,V> n) {    
377.             value = v;    
378.             next = n;    
379.             key = k;    
380.             hash = h;    
381.         }    
382.         public final K getKey() {    
383.             return key;    
384.         }    
385.         public final V getValue() {    
386.             return value;    
387.         }    
388.         public final V setValue(V newValue) {    
389.             V oldValue = value;    
390.             value = newValue;    
391.             return oldValue;    
392.         }    
393.         // 判斷兩個Entry是否相等    
394.         // 若兩個Entry的“key”和“value”都相等，則傳回true。    
395.         // 否則，傳回false    
396.         public final boolean equals(Object o) {    
397.             if (!(o instanceof Map.Entry))    
398.                 return false;    
399.             Map.Entry e = (Map.Entry)o;    
400.             Object k1 = getKey();    
401.             Object k2 = e.getKey();    
402.             if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
403.                 Object v1 = getValue();    
404.                 Object v2 = e.getValue();    
405.                 if (v1 == v2 || (v1 != null && v1.equals(v2)))    
406.                     return true;    
407.             }    
408.             return false;    
409.         }    
410.         // 實作hashCode()    
411.         public final int hashCode() {    
412.             return (key==null   ? 0 : key.hashCode()) ^    
413.                    (value==null ? 0 : value.hashCode());    
414.         }    
415.         public final String toString() {    
416.             return getKey() + "=" + getValue();    
417.         }    
418.         // 當向HashMap中添加元素時，繪調用recordAccess()。    
419.         // 這裡不做任何處理    
420.         void recordAccess(HashMap<K,V> m) {    
421.         }    
422.         // 當從HashMap中删除元素時，繪調用recordRemoval()。    
423.         // 這裡不做任何處理    
424.         void recordRemoval(HashMap<K,V> m) {    
425.         }    
426.     }    
427.     // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。    
428.     void addEntry(int hash, K key, V value, int bucketIndex) {    
429.         // 儲存“bucketIndex”位置的值到“e”中    
430.         Entry<K,V> e = table[bucketIndex];    
431.         // 設定“bucketIndex”位置的元素為“新Entry”，    
432.         // 設定“e”為“新Entry的下一個節點”    
433.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
434.         // 若HashMap的實際大小 不小于 “門檻值”，則調整HashMap的大小    
435.         if (size++ >= threshold)    
436.             resize(2 * table.length);    
437.     }    
438.     // 建立Entry。将“key-value”插入指定位置。    
439.     void createEntry(int hash, K key, V value, int bucketIndex) {    
440.         // 儲存“bucketIndex”位置的值到“e”中    
441.         Entry<K,V> e = table[bucketIndex];    
442.         // 設定“bucketIndex”位置的元素為“新Entry”，    
443.         // 設定“e”為“新Entry的下一個節點”    
444.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
445.         size++;    
446.     }    
447.     // HashIterator是HashMap疊代器的抽象出來的父類，實作了公共了函數。    
448.     // 它包含“key疊代器(KeyIterator)”、“Value疊代器(ValueIterator)”和“Entry疊代器(EntryIterator)”3個子類。    
449.     private abstract class HashIterator<E> implements Iterator<E> {    
450.         // 下一個元素    
451.         Entry<K,V> next;    
452.         // expectedModCount用于實作fast-fail機制。    
453.         int expectedModCount;    
454.         // 目前索引    
455.         int index;    
456.         // 目前元素    
457.         Entry<K,V> current;    
458.         HashIterator() {    
459.             expectedModCount = modCount;    
460.             if (size > 0) { // advance to first entry    
461.                 Entry[] t = table;    
462.                 // 将next指向table中第一個不為null的元素。    
463.                 // 這裡利用了index的初始值為0，從0開始依次向後周遊，直到找到不為null的元素就退出循環。    
464.                 while (index < t.length && (next = t[index++]) == null)    
465.                     ;    
466.             }    
467.         }    
468.         public final boolean hasNext() {    
469.             return next != null;    
470.         }    
471.         // 擷取下一個元素    
472.         final Entry<K,V> nextEntry() {    
473.             if (modCount != expectedModCount)    
474.                 throw new ConcurrentModificationException();    
475.             Entry<K,V> e = next;    
476.             if (e == null)    
477.                 throw new NoSuchElementException();    
478.             // 注意！！！    
479.             // 一個Entry就是一個單向連結清單    
480.             // 若該Entry的下一個節點不為空，就将next指向下一個節點;    
481.             // 否則，将next指向下一個連結清單(也是下一個Entry)的不為null的節點。    
482.             if ((next = e.next) == null) {    
483.                 Entry[] t = table;    
484.                 while (index < t.length && (next = t[index++]) == null)    
485.                     ;    
486.             }    
487.             current = e;    
488.             return e;    
489.         }    
490.         // 删除目前元素    
491.         public void remove() {    
492.             if (current == null)    
493.                 throw new IllegalStateException();    
494.             if (modCount != expectedModCount)    
495.                 throw new ConcurrentModificationException();    
496.             Object k = current.key;    
497.             current = null;    
498.             HashMap.this.removeEntryForKey(k);    
499.             expectedModCount = modCount;    
500.         }    
501.     }    
502.     // value的疊代器    
503.     private final class ValueIterator extends HashIterator<V> {    
504.         public V next() {    
505.             return nextEntry().value;    
506.         }    
507.     }    
508.     // key的疊代器    
509.     private final class KeyIterator extends HashIterator<K> {    
510.         public K next() {    
511.             return nextEntry().getKey();    
512.         }    
513.     }    
514.     // Entry的疊代器    
515.     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {    
516.         public Map.Entry<K,V> next() {    
517.             return nextEntry();    
518.         }    
519.     }    
520.     // 傳回一個“key疊代器”    
521.     Iterator<K> newKeyIterator()   {    
522.         return new KeyIterator();    
523.     }    
524.     // 傳回一個“value疊代器”    
525.     Iterator<V> newValueIterator()   {    
526.         return new ValueIterator();    
527.     }    
528.     // 傳回一個“entry疊代器”    
529.     Iterator<Map.Entry<K,V>> newEntryIterator()   {    
530.         return new EntryIterator();    
531.     }    
532.     // HashMap的Entry對應的集合    
533.     private transient Set<Map.Entry<K,V>> entrySet = null;    
534.     // 傳回“key的集合”，實際上傳回一個“KeySet對象”    
535.     public Set<K> keySet() {    
536.         Set<K> ks = keySet;    
537.         return (ks != null ? ks : (keySet = new KeySet()));    
538.     }    
539.     // Key對應的集合    
540.     // KeySet繼承于AbstractSet，說明該集合中沒有重複的Key。    
541.     private final class KeySet extends AbstractSet<K> {    
542.         public Iterator<K> iterator() {    
543.             return newKeyIterator();    
544.         }    
545.         public int size() {    
546.             return size;    
547.         }    
548.         public boolean contains(Object o) {    
549.             return containsKey(o);    
550.         }    
551.         public boolean remove(Object o) {    
552.             return HashMap.this.removeEntryForKey(o) != null;    
553.         }    
554.         public void clear() {    
555.             HashMap.this.clear();    
556.         }    
557.     }    
558.     // 傳回“value集合”，實際上傳回的是一個Values對象    
559.     public Collection<V> values() {    
560.         Collection<V> vs = values;    
561.         return (vs != null ? vs : (values = new Values()));    
562.     }    
563.     // “value集合”    
564.     // Values繼承于AbstractCollection，不同于“KeySet繼承于AbstractSet”，    
565.     // Values中的元素能夠重複。因為不同的key可以指向相同的value。    
566.     private final class Values extends AbstractCollection<V> {    
567.         public Iterator<V> iterator() {    
568.             return newValueIterator();    
569.         }    
570.         public int size() {    
571.             return size;    
572.         }    
573.         public boolean contains(Object o) {    
574.             return containsValue(o);    
575.         }    
576.         public void clear() {    
577.             HashMap.this.clear();    
578.         }    
579.     }    
580.     // 傳回“HashMap的Entry集合”    
581.     public Set<Map.Entry<K,V>> entrySet() {    
582.         return entrySet0();    
583.     }    
584.     // 傳回“HashMap的Entry集合”，它實際是傳回一個EntrySet對象    
585.     private Set<Map.Entry<K,V>> entrySet0() {    
586.         Set<Map.Entry<K,V>> es = entrySet;    
587.         return es != null ? es : (entrySet = new EntrySet());    
588.     }    
589.     // EntrySet對應的集合    
590.     // EntrySet繼承于AbstractSet，說明該集合中沒有重複的EntrySet。    
591.     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {    
592.         public Iterator<Map.Entry<K,V>> iterator() {    
593.             return newEntryIterator();    
594.         }    
595.         public boolean contains(Object o) {    
596.             if (!(o instanceof Map.Entry))    
597.                 return false;    
598.             Map.Entry<K,V> e = (Map.Entry<K,V>) o;    
599.             Entry<K,V> candidate = getEntry(e.getKey());    
600.             return candidate != null && candidate.equals(e);    
601.         }    
602.         public boolean remove(Object o) {    
603.             return removeMapping(o) != null;    
604.         }    
605.         public int size() {    
606.             return size;    
607.         }    
608.         public void clear() {    
609.             HashMap.this.clear();    
610.         }    
611.     }    
612.     // java.io.Serializable的寫入函數    
613.     // 将HashMap的“總的容量，實際容量，所有的Entry”都寫入到輸出流中    
614.     private void writeObject(java.io.ObjectOutputStream s)    
615.         throws IOException    
616.     {    
617.         Iterator<Map.Entry<K,V>> i =    
618.             (size > 0) ? entrySet0().iterator() : null;    
619.         // Write out the threshold, loadfactor, and any hidden stuff    
620.         s.defaultWriteObject();    
621.         // Write out number of buckets    
622.         s.writeInt(table.length);    
623.         // Write out size (number of Mappings)    
624.         s.writeInt(size);    
625.         // Write out keys and values (alternating)    
626.         if (i != null) {    
627.             while (i.hasNext()) {    
628.             Map.Entry<K,V> e = i.next();    
629.             s.writeObject(e.getKey());    
630.             s.writeObject(e.getValue());    
631.             }    
632.         }    
633.     }    
634.     private static final long serialVersionUID = 362498820763181265L;    
635.     // java.io.Serializable的讀取函數：根據寫入方式讀出    
636.     // 将HashMap的“總的容量，實際容量，所有的Entry”依次讀出    
637.     private void readObject(java.io.ObjectInputStream s)    
638.          throws IOException, ClassNotFoundException    
639.     {    
640.         // Read in the threshold, loadfactor, and any hidden stuff    
641.         s.defaultReadObject();    
642.         // Read in number of buckets and allocate the bucket array;    
643.         int numBuckets = s.readInt();    
644.         table = new Entry[numBuckets];    
645.         init();  // Give subclass a chance to do its thing.    
646.         // Read in size (number of Mappings)    
647.         int size = s.readInt();    
648.         // Read the keys and values, and put the mappings in the HashMap    
649.         for (int i=0; i<size; i++) {    
650.             K key = (K) s.readObject();    
651.             V value = (V) s.readObject();    
652.             putForCreate(key, value);    
653.         }    
654.     }    
655.     // 傳回“HashMap總的容量”    
656.     int   capacity()     { return table.length; }    
657.     // 傳回“HashMap的加載因子”    
658.     float loadFactor()   { return loadFactor;   }    
659. }   

幾點總結

    1、首先要清楚HashMap的存儲結構，如下圖所示：

    圖中，紫色部分即代表哈希表，也稱為哈希數組，數組的每個元素都是一個單連結清單的頭節點，連結清單是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就将其放入單連結清單中。

    2、首先看連結清單中節點的資料結構：

[java]  view plain  copy

1. // Entry是單向連結清單。    
2. // 它是 “HashMap鍊式存儲法”對應的連結清單。    
3. // 它實作了Map.Entry 接口，即實作getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數    
4. static class Entry<K,V> implements Map.Entry<K,V> {    
5.     final K key;    
6.     V value;    
7.     // 指向下一個節點    
8.     Entry<K,V> next;    
9.     final int hash;    
10.     // 構造函數。    
11.     // 輸入參數包括"哈希值(h)", "鍵(k)", "值(v)", "下一節點(n)"    
12.     Entry(int h, K k, V v, Entry<K,V> n) {    
13.         value = v;    
14.         next = n;    
15.         key = k;    
16.         hash = h;    
17.     }    
18.     public final K getKey() {    
19.         return key;    
20.     }    
21.     public final V getValue() {    
22.         return value;    
23.     }    
24.     public final V setValue(V newValue) {    
25.         V oldValue = value;    
26.         value = newValue;    
27.         return oldValue;    
28.     }    
29.     // 判斷兩個Entry是否相等    
30.     // 若兩個Entry的“key”和“value”都相等，則傳回true。    
31.     // 否則，傳回false    
32.     public final boolean equals(Object o) {    
33.         if (!(o instanceof Map.Entry))    
34.             return false;    
35.         Map.Entry e = (Map.Entry)o;    
36.         Object k1 = getKey();    
37.         Object k2 = e.getKey();    
38.         if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
39.             Object v1 = getValue();    
40.             Object v2 = e.getValue();    
41.             if (v1 == v2 || (v1 != null && v1.equals(v2)))    
42.                 return true;    
43.         }    
44.         return false;    
45.     }    
46.     // 實作hashCode()    
47.     public final int hashCode() {    
48.         return (key==null   ? 0 : key.hashCode()) ^    
49.                (value==null ? 0 : value.hashCode());    
50.     }    
51.     public final String toString() {    
52.         return getKey() + "=" + getValue();    
53.     }    
54.     // 當向HashMap中添加元素時，繪調用recordAccess()。    
55.     // 這裡不做任何處理    
56.     void recordAccess(HashMap<K,V> m) {    
57.     }    
58.     // 當從HashMap中删除元素時，繪調用recordRemoval()。    
59.     // 這裡不做任何處理    
60.     void recordRemoval(HashMap<K,V> m) {    
61.     }    
62. }    

    它的結構元素除了key、value、hash外，還有next，next指向下一個節點。另外，這裡覆寫了equals和hashCode方法來保證鍵值對的獨一無二。

    3、HashMap共有四個構造方法。構造方法中提到了兩個很重要的參數：初始容量和加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中槽的數量（即哈希數組的長度），初始容量是建立哈希表時的容量（從構造函數中可以看出，如果不指明，則預設為16），加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 resize 操作（即擴容）。

    下面說下加載因子，如果加載因子越大，對空間的利用更充分，但是查找效率會降低（連結清單長度會越來越長）；如果加載因子太小，那麼表中的資料将過于稀疏（很多空間還沒用，就開始擴容了），對空間造成嚴重浪費。如果我們在構造方法中不指定，則系統預設加載因子為0.75，這是一個比較理想的值，一般情況下我們是無需修改的。

    另外，無論我們指定的容量為多少，構造方法都會将實際容量設為不小于指定容量的2的次方的一個數，且最大值不能超過2的30次方

    4、HashMap中key和value都允許為null。

    5、要重點分析下HashMap中用的最多的兩個方法put和get。先從比較簡單的get方法着手，源碼如下：

[java]  view plain  copy

1. // 擷取key對應的value    
2. public V get(Object key) {    
3.     if (key == null)    
4.         return getForNullKey();    
5.     // 擷取key的hash值    
6.     int hash = hash(key.hashCode());    
7.     // 在“該hash值對應的連結清單”上查找“鍵值等于key”的元素    
8.     for (Entry<K,V> e = table[indexFor(hash, table.length)];    
9.          e != null;    
10.          e = e.next) {    
11.         Object k;    
12. /判斷key是否相同  
13.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
14.             return e.value;    
15.     }  
16. 沒找到則傳回null  
17.     return null;    
18. }    
19. // 擷取“key為null”的元素的值    
20. // HashMap将“key為null”的元素存儲在table[0]位置，但不一定是該連結清單的第一個位置！    
21. private V getForNullKey() {    
22.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
23.         if (e.key == null)    
24.             return e.value;    
25.     }    
26.     return null;    
27. }    

    首先，如果key為null，則直接從哈希表的第一個位置table[0]對應的連結清單上查找。記住，key為null的鍵值對永遠都放在以table[0]為頭結點的連結清單中，當然不一定是存放在頭結點table[0]中。

    如果key不為null，則先求的key的hash值，根據hash值找到在table中的索引，在該索引對應的單連結清單中查找是否有鍵值對的key與目标key相等，有就傳回對應的value，沒有則傳回null。

    put方法稍微複雜些，代碼如下：

[java]  view plain  copy

1.   // 将“key-value”添加到HashMap中    
2.   public V put(K key, V value) {    
3.       // 若“key為null”，則将該鍵值對添加到table[0]中。    
4.       if (key == null)    
5.           return putForNullKey(value);    
6.       // 若“key不為null”，則計算該key的哈希值，然後将其添加到該哈希值對應的連結清單中。    
7.       int hash = hash(key.hashCode());    
8.       int i = indexFor(hash, table.length);    
9.       for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
10.           Object k;    
11.           // 若“該key”對應的鍵值對已經存在，則用新的value取代舊的value。然後退出！    
12.           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
13.               V oldValue = e.value;    
14.               e.value = value;    
15.               e.recordAccess(this);    
16.               return oldValue;    
17.           }    
18.       }    
19.       // 若“該key”對應的鍵值對不存在，則将“key-value”添加到table中    
20.       modCount++;  
21. //将key-value添加到table[i]處  
22.       addEntry(hash, key, value, i);    
23.       return null;    
24.   }   

    如果key為null，則将其添加到table[0]對應的連結清單中，putForNullKey的源碼如下：

[java]  view plain  copy

1. // putForNullKey()的作用是将“key為null”鍵值對添加到table[0]位置    
2. private V putForNullKey(V value) {    
3.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
4.         if (e.key == null) {    
5.             V oldValue = e.value;    
6.             e.value = value;    
7.             e.recordAccess(this);    
8.             return oldValue;    
9.         }    
10.     }    
11.     // 如果沒有存在key為null的鍵值對，則直接題阿見到table[0]處!    
12.     modCount++;    
13.     addEntry(0, null, value, 0);    
14.     return null;    
15. }   

    如果key不為null，則同樣先求出key的hash值，根據hash值得出在table中的索引，而後周遊對應的單連結清單，如果單連結清單中存在與目标key相等的鍵值對，則将新的value覆寫舊的value，比将舊的value傳回，如果找不到與目标key相等的鍵值對，或者該單連結清單為空，則将該鍵值對插入到改單連結清單的頭結點位置（每次新插入的節點都是放在頭結點的位置），該操作是有addEntry方法實作的，它的源碼如下：

[java]  view plain  copy

1. // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。    
2. void addEntry(int hash, K key, V value, int bucketIndex) {    
3.     // 儲存“bucketIndex”位置的值到“e”中    
4.     Entry<K,V> e = table[bucketIndex];    
5.     // 設定“bucketIndex”位置的元素為“新Entry”，    
6.     // 設定“e”為“新Entry的下一個節點”    
7.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
8.     // 若HashMap的實際大小 不小于 “門檻值”，則調整HashMap的大小    
9.     if (size++ >= threshold)    
10.         resize(2 * table.length);    
11. }    

    注意這裡倒數第三行的構造方法，将key-value鍵值對賦給table[bucketIndex]，并将其next指向元素e，這便将key-value放到了頭結點中，并将之前的頭結點接在了它的後面。該方法也說明，每次put鍵值對的時候，總是将新的該鍵值對放在table[bucketIndex]處（即頭結點處）。

    兩外注意最後兩行代碼，每次加入鍵值對時，都要判斷目前已用的槽的數目是否大于等于閥值（容量*加載因子），如果大于等于，則進行擴容，将容量擴為原來容量的2倍。

    6、關于擴容。上面我們看到了擴容的方法，resize方法，它的源碼如下：

[java]  view plain  copy

1. // 重新調整HashMap的大小，newCapacity是調整後的機關    
2. void resize(int newCapacity) {    
3.     Entry[] oldTable = table;    
4.     int oldCapacity = oldTable.length;    
5.     if (oldCapacity == MAXIMUM_CAPACITY) {    
6.         threshold = Integer.MAX_VALUE;    
7.         return;    
8.     }    
9.     // 建立一個HashMap，将“舊HashMap”的全部元素添加到“新HashMap”中，    
10.     // 然後，将“新HashMap”指派給“舊HashMap”。    
11.     Entry[] newTable = new Entry[newCapacity];    
12.     transfer(newTable);    
13.     table = newTable;    
14.     threshold = (int)(newCapacity * loadFactor);    
15. }    

    很明顯，是建立了一個HashMap的底層數組，而後調用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新計算元素在新的數組中的索引位置）。transfer方法的源碼如下：

[java]  view plain  copy

1. // 将HashMap中的全部元素都添加到newTable中    
2. void transfer(Entry[] newTable) {    
3.     Entry[] src = table;    
4.     int newCapacity = newTable.length;    
5.     for (int j = 0; j < src.length; j++) {    
6.         Entry<K,V> e = src[j];    
7.         if (e != null) {    
8.             src[j] = null;    
9.             do {    
10.                 Entry<K,V> next = e.next;    
11.                 int i = indexFor(e.hash, newCapacity);    
12.                 e.next = newTable[i];    
13.                 newTable[i] = e;    
14.                 e = next;    
15.             } while (e != null);    
16.         }    
17.     }    
18. }    

    很明顯，擴容是一個相當耗時的操作，因為它需要重新計算這些元素在新的數組中的位置并進行複制處理。是以，我們在用HashMap的時，最好能提前預估下HashMap中元素的個數，這樣有助于提高HashMap的性能。

    7、注意containsKey方法和containsValue方法。前者直接可以通過key的哈希值将搜尋範圍定位到指定索引對應的連結清單，而後者要對哈希數組的每個連結清單進行搜尋。

    8、我們重點來分析下求hash值和索引值的方法，這兩個方法便是HashMap設計的最為核心的部分，二者結合能保證哈希表中的元素盡可能均勻地散列。

    計算哈希值的方法如下：

[java]  view plain  copy

1. static int hash(int h) {  
2.         h ^= (h >>> 20) ^ (h >>> 12);  
3.         return h ^ (h >>> 7) ^ (h >>> 4);  
4.     }  

    它隻是一個數學公式，IDK這樣設計對hash值的計算，自然有它的好處，至于為什麼這樣設計，我們這裡不去追究，隻要明白一點，用的位的操作使hash值的計算效率很高。

    由hash值找到對應索引的方法如下：

[java]  view plain  copy

1. static int indexFor(int h, int length) {  
2.         return h & (length-1);  
3.     }  

    這個我們要重點說下，我們一般對哈希表的散列很自然地會想到用hash值對length取模（即除法散列法），Hashtable中也是這樣實作的，這種方法基本能保證元素在哈希表中散列的比較均勻，但取模會用到除法運算，效率很低，HashMap中則通過h&(length-1)的方法來代替取模，同樣實作了均勻的散列，但效率要高很多，這也是HashMap對Hashtable的一個改進。

    接下來，我們分析下為什麼哈希表的容量一定要是2的整數次幂。首先，length為2的整數次幂的話，h&(length-1)就相當于對length取模，這樣便保證了散列的均勻，同時也提升了效率；其次，length為2的整數次幂的話，為偶數，這樣length-1為奇數，奇數的最後一位是1，這樣便保證了h&(length-1)的最後一位可能為0，也可能為1（這取決于h的值），即與後的結果可能為偶數，也可能為奇數，這樣便可以保證散列的均勻性，而如果length為奇數的話，很明顯length-1為偶數，它的最後一位是0，這樣h&(length-1)的最後一位肯定為0，即隻能為偶數，這樣任何hash值都隻會被散列到數組的偶數下标位置上，這便浪費了近一半的空間，是以，length取2的整數次幂，是為了使不同hash值發生碰撞的機率較小，這樣就能使元素在哈希表中均勻地散列。