HashMap是Java程序猿平時用的較多的一種數(shù)據(jù)結(jié)構(gòu)，也經(jīng)常會在各種面試中被問起。喜歡看JDK源碼的同學(xué)肯定會發(fā)現(xiàn)隨著JDK版本的更新迭代，HashMap的底層實現(xiàn)也在不斷地優(yōu)化,那么本文我們就來聊聊HashMap的實現(xiàn)結(jié)構(gòu)和原理吧
概述
java.util.Map接口主要有四個常用的實現(xiàn)類，分別是HashMap、Hashtable、LinkedHashMap，和TreeMap，類繼承關(guān)系如下圖所示：
1.HashMap：它根據(jù)鍵的hashCode值存儲數(shù)據(jù)，HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。HashMap非線程安全，如果需要線程安全，可以用Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。
2.Hashtable：Hashtable繼承自Dictionary類，線程安全的，任一時間只有一個線程能寫Hashtable，并發(fā)性不如ConcurrentHashMap，因為ConcurrentHashMap使用分段鎖。Hashtable不建議使用，需要線程安全的場合可以用ConcurrentHashMap替換。
3.LinkedHashMap：LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，使用Iterator遍歷時，先得到的記錄肯定是先插入的。
4.TreeMap：TreeMap實現(xiàn)SortedMap接口，保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器。如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。
存儲結(jié)構(gòu)
從JDK1.8之后，HashMap的存儲結(jié)構(gòu)使用哈希桶數(shù)組+鏈表/紅黑樹實現(xiàn)。為了解決哈希沖突，HashMap采用了鏈地址法，但是這樣避免不了鏈表過長導(dǎo)致HashMap性能嚴(yán)重下降。所以當(dāng)鏈表長度超過默認(rèn)值8的時候，鏈表就會轉(zhuǎn)為紅黑樹。紅黑樹是一棵二叉查找樹，但它在二叉查找樹的基礎(chǔ)上增加了相關(guān)特性使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)。
重要方法
1.tableSizeFor()
源碼
/**
* 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;
}
調(diào)用的地方
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
HashMap的capacity都是2的冪，這個方法是用于找到大于或者等于initialCapacity的最小的2的冪（initialCapacity如果就是2的冪，則返回的還是這個數(shù)，這就是為什么第一步需要int n = cap -1的原因。
下面看看這幾個無符號右移操作：
第一次右移
n |= n >>> 1;
由于n不等于0，則n的二進(jìn)制表示中總會有一bit為1，這時考慮最高位的1，假設(shè)n為01xxxxxxx。通過無符號右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進(jìn)制表示中與最高位的1緊鄰的右邊一位也為1，如011xxxxxxxx。
第二次右移
n |= n >>> 2;
此時n為011xxxxxxxx ，則n無符號右移兩位，會將最高位兩個連續(xù)的1右移兩位，然后再與原來的n做或操作，這樣n的二進(jìn)制表示的高位中會有4個連續(xù)的1。如01111xxxxxx。
第三次右移
n |= n >>> 4;
這次把已經(jīng)有的高位中的連續(xù)的4個1，右移4位，再做或操作，這樣n的二進(jìn)制表示的高位中會有8個連續(xù)的1。如011111111xxxxxx 。
。。。
以此類推,容量最大也就是32bit的正數(shù)，因此最后n |= n >>> 16 ，最多也就32個1，但是這時已經(jīng)大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY,不大于MAXIMUM_CAPACITY的時候則n+1,這樣就華麗麗的取到了大于或等于n的那個最大2次冪值，作為HashMap的容量。還是蠻巧妙的一個算法哈~
2.hash()
1.8版本
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.7版本
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
這段代碼其實叫擾動函數(shù)，為啥要這樣搞呢，不能取到key的hashCode的時候直接用下面的方法去求模找對應(yīng)哈希桶數(shù)組的下標(biāo)位置嗎？
static int indexFor(int h, int length) {
//jdk1.7的源碼，jdk1.8沒有這個方法，但是實現(xiàn)原理一樣的
return h & (length-1);
}
順帶說一下，這也正好解釋了為什么HashMap的數(shù)組長度要取2的整次冪。因為這樣（數(shù)組長度-1）正好相當(dāng)于一個"低位掩碼"?！芭c”操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來做數(shù)組下標(biāo)訪問。以初始長度16為例，16-1=15。2進(jìn)制表示是<b>00000000 00000000 00001111</b>。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值。
10100101 11000100 00100101
00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴(yán)重。更要命的是如果散列本身做得不好，分布上成等差數(shù)列的漏洞，恰好使最后幾個低位呈現(xiàn)規(guī)律性重復(fù)，就無比蛋疼。
這時候“<b>擾動函數(shù)</b>”的價值就體現(xiàn)出來了，說到這里大家應(yīng)該猜出來了?？聪旅孢@個圖:
向位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
但明顯Java 8覺得擾動做一次就夠了，像1.7做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。
