深入Java集(ji)合學習系(xi)列：HashMap的(de)實現原(yuan)理
參考文獻
引(yin)用文獻：，大(da)部分參(can)考這篇博客(ke)，只對其中進行稍(shao)微修改(gai)
自己曾經寫過的：Hashmap實現原理
1. HashMap概述(shu)：
HashMap是基于哈希表的Map接口的非同步實現（Hashtable跟HashMap很像，唯一的區別是Hashtalbe中的方法是線程安全的，也就是同步的）。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
2. HashMap的數據結構：
在java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表的數組”的數據結構，每個元素存放鏈表頭結點的數組，即數(shu)組(zu)和鏈表的結合體。
從上圖中(zhong)可以看出(chu)，HashMap底(di)層就是一(yi)(yi)(yi)(yi)個數(shu)組結構(gou)，數(shu)組中(zhong)的(de)每一(yi)(yi)(yi)(yi)項又是一(yi)(yi)(yi)(yi)個鏈表。當新(xin)建一(yi)(yi)(yi)(yi)個HashMap的(de)時候，就會初始化一(yi)(yi)(yi)(yi)個數(shu)組。源碼如下(xia)：
View Code
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …… }
可以(yi)看出(chu)，Entry就(jiu)是數(shu)組中的元(yuan)素，每個 Map.Entry 其實就是一個key-value對，它持有(you)一個指(zhi)向(xiang)下(xia)一個元素的引用，這就構(gou)成了(le)鏈表(biao)。
3. HashMap的存取實現(xian)：
1) 存儲：
View Code
public V put(K key, V value) { // HashMap允許存放null鍵(jian)和(he)null值。 // 當key為null時，調用(yong)putForNullKey方法，將value放置(zhi)在數組第一(yi)個位置(zhi)。 if (key == null) return putForNullKey(value); // 根(gen)據(ju)key的hashCode重新計算hash值(zhi)。 int hash = hash(key.hashCode()); // 搜索(suo)指定hash值所對應(ying)table中(zhong)的索(suo)引。 int i = indexFor(hash, table.length); // 如果 i 索引處的 Entry 不為 null，通過循環不斷(duan)遍歷 e 元(yuan)素的下一個元(yuan)素。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如(ru)果i索引處的Entry為null，表明此處還沒有Entry。 // modCount記錄HashMap中(zhong)修(xiu)改(gai)結構的次數 modCount++; // 將key、value添(tian)加到i索引處(chu)。 addEntry(hash, key, value, i); return null; }
從上面(mian)的(de)(de)源代碼中可以看出：當(dang)我們往HashMap中put元(yuan)素的(de)(de)時候，先根據key的(de)(de)hashCode重(zhong)新計算(suan)hash值，根據hash值得到(dao)這(zhe)個元(yuan)素在數(shu)組(zu)中的(de)(de)位(wei)(wei)置(zhi)(zhi)（即下標），如果數(shu)組(zu)該位(wei)(wei)置(zhi)(zhi)上已經存放(fang)(fang)有其他元(yuan)素了，那么在這(zhe)個位(wei)(wei)置(zhi)(zhi)上的(de)(de)元(yuan)素將(jiang)以鏈表(biao)的(de)(de)形式存放(fang)(fang)，新加入的(de)(de)放(fang)(fang)在鏈頭，最先加入的(de)(de)放(fang)(fang)在鏈尾。如果數(shu)組(zu)該位(wei)(wei)置(zhi)(zhi)上沒有元(yuan)素，就直(zhi)接將(jiang)該元(yuan)素放(fang)(fang)到(dao)此數(shu)組(zu)中的(de)(de)該位(wei)(wei)置(zhi)(zhi)上。
addEntry(hash, key, value, i)方法根據計算出的hash值，將key-value對放在數組table的 i 索引處。addEntry 是HashMap 提供的一個包訪問權限的方法（就是沒有public，protected，private這三個訪問權限修飾詞修飾，為默認的訪問權限，用default表示，但在代碼中沒有這個default），代碼如下：
View Code
void addEntry(int hash, K key, V value, int bucketIndex) { // 獲(huo)取指定(ding) bucketIndex 索引處的(de) Entry Entry<K,V> e = table[bucketIndex]; // 將(jiang)新創建的(de)(de) Entry 放入 bucketIndex 索引處，并讓新的(de)(de) Entry 指(zhi)向原來的(de)(de) Entry table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 對的數(shu)量(liang)超過(guo)了極限 if (size++ >= threshold) // 把 table 對(dui)象的長度擴(kuo)充到原(yuan)來的2倍。 resize(2 * table.length); }
當系(xi)統決(jue)定(ding)存儲HashMap中的(de)key-value對時，完全(quan)沒有考慮(lv)Entry中的(de)value，僅(jin)僅(jin)只是根據key來(lai)計算并決(jue)定(ding)每個(ge)Entry的(de)存儲位置。我們完全(quan)可(ke)以(yi)把 Map 集合中的(de) value 當成 key 的(de)附屬，當系(xi)統決(jue)定(ding)了 key 的(de)存儲位置之后(hou)，value 隨(sui)之保存在那(nei)里即(ji)可(ke)。
hash(int h)方法(fa)根據key的hashCode重新計算(suan)一次散(san)列(lie)。此(ci)算(suan)法(fa)加入了高位(wei)(wei)計算(suan)，防止低位(wei)(wei)不變，高位(wei)(wei)變化(hua)時，造成的hash沖(chong)突。
View Code
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
我們可以看到在HashMap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置。如何計算這個位置就是hash算法。前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap里面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣(yang)就大大優化(hua)了查詢的效率。
對(dui)于任意給(gei)定的(de)(de)(de)對(dui)象，只(zhi)要它(ta)的(de)(de)(de) hashCode() 返回值(zhi)相同，那么程序調(diao)用 hash(int h) 方(fang)(fang)法所計算(suan)(suan)得到(dao)的(de)(de)(de) hash 碼值(zhi)總是相同的(de)(de)(de)。我們首先想(xiang)到(dao)的(de)(de)(de)就是把hash值(zhi)對(dui)數組(zu)長度取模運算(suan)(suan)，這(zhe)樣一來(lai)(lai)(lai)，元素的(de)(de)(de)分布相對(dui)來(lai)(lai)(lai)說是比較(jiao)均勻(yun)的(de)(de)(de)。但是，“模”運算(suan)(suan)的(de)(de)(de)消耗還是比較(jiao)大的(de)(de)(de)，在HashMap中是這(zhe)樣做的(de)(de)(de)：調(diao)用 indexFor(int h, int length) 方(fang)(fang)法來(lai)(lai)(lai)計算(suan)(suan)該對(dui)象應該保存(cun)在 table 數組(zu)的(de)(de)(de)哪個索引處。indexFor(int h, int length) 方(fang)(fang)法的(de)(de)(de)代碼如(ru)下：
View Code
static int indexFor(int h, int length) { return h & (length-1); }
這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對(dui)象的保存位，而(er)HashMap底(di)層(ceng)數組的(de)長(chang)度(du)總是 2 的n 次方，這是HashMap在速度上(shang)的優化(hua)。在 HashMap 構造(zao)器(qi)中(zhong)有如(ru)下代碼：
View Code
int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;
這段代(dai)碼(ma)保證初(chu)始化時HashMap的(de)容量(liang)總(zong)(zong)是(shi)2的(de)n次方，即底(di)層(ceng)數組(zu)的(de)長(chang)度總(zong)(zong)是(shi)為2的(de)n次方。
當length總是 2 的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。
這看上去很簡單(dan)，其實比較有玄機的，我們舉個例子來說明：
假設數組長度分別為15和16，優化后的hash碼分別為8和9，那么&運算后的(de)結果如下：
h & (table.length-1) hash table.length-1
8 & (15-1)： 0100 & 1110 = 0100
9 & (15-1)： 0101 & 1110 = 0100
-----------------------------------------------------------------------------------------------------------------------
8 & (16-1)： 0100 & 1111 = 0100
9 & (16-1)： 0101 & 1111 = 0101
-----------------------------------------------------------------------------------------------------------------------
從上面的例子中可以看出：當8、9兩個數和(15-1)2=(1110)進行“與運算&”的時候，產生了相同的結果，都為0100，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到數組中的同一個位置上形成鏈表，那么查詢的時候就需要遍歷這個鏈 表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hash值會與(15-1)2=(1110)進(jin)(jin)行“與運算&”，那么最(zui)后(hou)一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這(zhe)(zhe)幾(ji)(ji)個位置(zhi)(zhi)永遠都不能存放元素了(le)，空間浪費(fei)相當大(da)，更糟的是這(zhe)(zhe)種情況中，數(shu)組可以使(shi)用的位置(zhi)(zhi)比數(shu)組長度(du)小了(le)很多(duo)，這(zhe)(zhe)意味(wei)著進(jin)(jin)一步增加了(le)碰撞的幾(ji)(ji)率(lv)，減慢了(le)查詢的效率(lv)！
而當數組長度為16時，即為2的n次方時，2n-1得到的二進制數的每個位上的值都為1（比如(24-1)2=1111），這使得在低位上&時，得到的和原hash的低位相同，加之hash(int h)方法對key的hashCode的進一步優化，加入了高位計算，就使得只有相同的hash值的兩個值才會被放到數組中的同一個位置上形成鏈表。
所(suo)以(yi)說(shuo)，當數(shu)(shu)組長度為2的n次冪(mi)的時(shi)候，不(bu)同的key算得(de)得(de)index相(xiang)同的幾率(lv)較(jiao)小(xiao)，那么數(shu)(shu)據在(zai)數(shu)(shu)組上分布就(jiu)比較(jiao)均勻(yun)，也(ye)就(jiu)是(shi)說(shuo)碰撞的幾率(lv)小(xiao)，相(xiang)對的，查詢的時(shi)候就(jiu)不(bu)用遍歷(li)某個位(wei)置上的鏈表，這樣(yang)查詢效率(lv)也(ye)就(jiu)較(jiao)高了。
根據上面 put 方法的源代碼可以看出，當程序試圖將一個key-value對放入HashMap中時，程序首先根據該 key的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有Entry 的 value，但key不會覆蓋。如(ru)果這兩個(ge) Entry 的(de)(de) key 通過 equals 比較(jiao)返回 false，新添加(jia)的(de)(de) Entry 將(jiang)與集合中原(yuan)有 Entry 形成 Entry 鏈，而且(qie)新添加(jia)的(de)(de) Entry 位于 Entry 鏈的(de)(de)頭(tou)部——具體說明(ming)繼續看 addEntry() 方法的(de)(de)說明(ming)。
2) 讀取：
View Code
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
有了上面(mian)存儲時的hash算(suan)法(fa)作(zuo)為基礎，理解(jie)起來(lai)這段代(dai)碼(ma)就(jiu)很(hen)容易了。從上面(mian)的源代(dai)碼(ma)中可(ke)以看出(chu)：從HashMap中get元素時，首先計算(suan)key的hashCode，找到(dao)數組中對應位置的某一元素，然后(hou)通(tong)過key的equals方(fang)法(fa)在對應位置的鏈(lian)表中找到(dao)需要(yao)的元素。
3) 歸納(na)起來簡單地說，HashMap 在(zai)底(di)層(ceng)(ceng)將 key-value 當(dang)成(cheng)一(yi)個(ge)(ge)整(zheng)體進行處(chu)理，這個(ge)(ge)整(zheng)體就是(shi)一(yi)個(ge)(ge) Entry 對象(xiang)。HashMap 底(di)層(ceng)(ceng)采用一(yi)個(ge)(ge) Entry[] 數(shu)組來保存(cun)(cun)所(suo)有的(de) key-value 對，當(dang)需要存(cun)(cun)儲一(yi)個(ge)(ge) Entry 對象(xiang)時，會(hui)根(gen)據hash算法(fa)來決(jue)定其(qi)在(zai)數(shu)組中(zhong)的(de)存(cun)(cun)儲位(wei)置，在(zai)根(gen)據equals方法(fa)決(jue)定其(qi)在(zai)該數(shu)組位(wei)置上的(de)鏈表中(zhong)的(de)存(cun)(cun)儲位(wei)置；當(dang)需要取出(chu)一(yi)個(ge)(ge)Entry時，也會(hui)根(gen)據hash算法(fa)找到其(qi)在(zai)數(shu)組中(zhong)的(de)存(cun)(cun)儲位(wei)置，再根(gen)據equals方法(fa)從該位(wei)置上的(de)鏈表中(zhong)取出(chu)該Entry。
4. HashMap的resize（rehash）：
當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數組的長度是固定的。所以為了提高查詢的效率，就要對HashMap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，這是一個常用的操作，而在HashMap數組擴容之后，最消耗性能的點就出現了：原數組中的數據必須重新計算其在新數組中的位置，并放進去，這就是resize。
那么HashMap什么時候進行擴容呢？當HashMap中的元素個數超過數組大小*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小為16，那么當HashMap中元素個數超過16*0.75=12（這個值就是代碼中的threshold值(zhi)，也叫做臨界值(zhi)）的(de)(de)時候(hou)，就把數組的(de)(de)大(da)小擴展為 2*16=32，即擴大(da)一倍(bei)，然后重新(xin)計算每(mei)個元素在數組中的(de)(de)位置，而這是一個非(fei)常消耗性(xing)能(neng)的(de)(de)操(cao)作，所以如果我們已經預知HashMap中元素的(de)(de)個數，那么預設元素的(de)(de)個數能(neng)夠(gou)有效的(de)(de)提高(gao)HashMap的(de)(de)性(xing)能(neng)。
HashMap擴容的代碼如下所示：
View Code
//HashMap數組擴(kuo)容(rong) void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果當前的數組長度(du)已經(jing)達到(dao)最(zui)大值，則不在進行(xing)調整 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //根據傳入(ru)參(can)數(shu)的長度定義新的數(shu)組(zu) Entry[] newTable = new Entry[newCapacity]; //按照新的規則，將舊數組(zu)中(zhong)(zhong)的元素(su)轉移到新數組(zu)中(zhong)(zhong) transfer(newTable); table = newTable; //更新臨界(jie)值 threshold = (int)(newCapacity * loadFactor); } //舊數組中元素往新數組中遷移 void transfer(Entry[] newTable) { //舊(jiu)數組 Entry[] src = table; //新數組(zu)長(chang)度 int newCapacity = newTable.length; //遍歷舊數(shu)組 for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
5.HashMap的性能參數：
HashMap 包含如下(xia)幾個(ge)構造器：
- HashMap()：構建一個初始容量為 16，負載因子為 0.75 的 HashMap。
- HashMap(int initialCapacity)：構建一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子創建一個 HashMap。
- HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數，它們是初始容量initialCapacity和加載因子loadFactor。
- initialCapacity：HashMap的最大容量，即為底層數組的長度。
- loadFactor：負載因子loadFactor定義為：散列表的實際元素數目(n)/ 散列表的容量(m)。
負載(zai)因(yin)(yin)子(zi)(zi)(zi)衡(heng)量的(de)是(shi)一個散(san)列(lie)表(biao)(biao)的(de)空間的(de)使用(yong)程度，負載(zai)因(yin)(yin)子(zi)(zi)(zi)越大(da)表(biao)(biao)示(shi)散(san)列(lie)表(biao)(biao)的(de)裝填程度越高，反之愈小。對于(yu)使用(yong)鏈表(biao)(biao)法的(de)散(san)列(lie)表(biao)(biao)來說，查找(zhao)一個元素(su)的(de)平均時(shi)間是(shi)O(1+a)，因(yin)(yin)此如(ru)果(guo)負載(zai)因(yin)(yin)子(zi)(zi)(zi)越大(da)，對空間的(de)利用(yong)更充分，然(ran)而后果(guo)是(shi)查找(zhao)效率的(de)降低；如(ru)果(guo)負載(zai)因(yin)(yin)子(zi)(zi)(zi)太小，那么散(san)列(lie)表(biao)(biao)的(de)數(shu)據將過于(yu)稀疏，對空間造成嚴重浪費(fei)。
HashMap的實現中，通(tong)過(guo)threshold字段來判斷HashMap的最(zui)大容(rong)量：
threshold = (int)(capacity * loadFactor);
結(jie)合負載(zai)因子的定(ding)義公式可(ke)知，threshold就(jiu)是(shi)在此(ci)loadFactor和capacity對應下允許的最大元素數目，超過(guo)這個數目就重新resize，以降低(di)實(shi)際的負載因子(zi)（也(ye)就是說雖然(ran)數組長度是capacity，但(dan)其擴容的(de)(de)臨界值確是threshold）。默(mo)認(ren)的(de)(de)的(de)(de)負載因子0.75是對空間(jian)和時間(jian)效率(lv)的(de)(de)一個平衡選擇(ze)。當容量超出此最大容量時， resize后(hou)的(de)(de)HashMap容量是容量的(de)(de)兩倍：
if (size++ >= threshold) resize(2 * table.length);
6.Fail-Fast機制：
我們知道java.util.HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。（這個在core java這本書中也有提到。）
這一策略在源碼中的實現是通過modCount域，modCount顧名思義就是修改次數，對HashMap內容的修改(gai)都將(jiang)增加這(zhe)個(ge)值(zhi)，那么在迭(die)代器(qi)初始化過程中會(hui)將(jiang)這(zhe)個(ge)值(zhi)賦給迭(die)代器(qi)的expectedModCount。
View Code
HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } }
在(zai)迭代過程(cheng)中，判斷modCount跟(gen)expectedModCount是否相(xiang)等，如果(guo)不相(xiang)等就(jiu)表(biao)示已經有其(qi)他(ta)線程(cheng)修改了Map：
注意到modCount聲明為volatile，保證線程之間修改的可見性。（volatile之所以線程安全是因為被volatile修飾的變量不保存緩存，直接在內存中修改，因此能夠保證線程之間修改的可見性）。
final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException();
在HashMap的API中指出：
由所有(you)HashMap類的“collection 視圖方法”所返回的迭(die)代器(qi)都是快速失敗的：在迭(die)代器(qi)創建之后，如果從結構上(shang)對映射(she)進行修(xiu)改，除非通過迭(die)代器(qi)本身的 remove 方法，其(qi)他任(ren)何(he)(he)時間任(ren)何(he)(he)方式(shi)的修(xiu)改，迭(die)代器(qi)都將(jiang)拋(pao)出ConcurrentModificationException。因此，面對并發(fa)的修(xiu)改，迭(die)代器(qi)很快就會(hui)完全(quan)失敗，而不(bu)保證(zheng)在將(jiang)來不(bu)確(que)定的時間發(fa)生任(ren)意不(bu)確(que)定行為的風險。
注意(yi)，迭(die)代(dai)器的(de)快(kuai)速(su)失敗行為不(bu)能(neng)得到保證，一般(ban)來說，存(cun)在(zai)非同步的(de)并發修改時，不(bu)可能(neng)作出任何堅(jian)決的(de)保證。快(kuai)速(su)失敗迭(die)代(dai)器盡最大努力拋(pao)出 ConcurrentModificationException。因此，編寫依賴于此異(yi)常的(de)程序的(de)做(zuo)法是錯(cuo)誤的(de)，正確做(zuo)法是：迭(die)代(dai)器的(de)快(kuai)速(su)失敗行為應該僅用于檢測程序錯(cuo)誤。
參考資料：
JDK API HashMap
HashMap 源代碼(ma) ;