HashMap是一個常用的集合,，日常使用可能我們并不關(guān)心它是如何實現(xiàn)的,，不過它是面試中的常客,。所以為了弄懂它,，不妨看一看源碼，同時也可以學(xué)習(xí)一下大牛的編程思想,。
一,、HashMap的宏觀實現(xiàn)
1、HashMap數(shù)據(jù)結(jié)構(gòu):
HashMap采用 數(shù)組 + 鏈表 的方式來實現(xiàn)數(shù)據(jù)的存儲,。為什么使用這種方式呢,？鏈表什么時候產(chǎn)生呢？
首先HashMap主要還是用數(shù)組來存儲元素的。它通過key的hash來計算元素應(yīng)該放在數(shù)組中的哪個位置,。如果有兩個key的hash都一樣,，該怎么處理呢？這時候會去判斷這兩個key是否相等,，如果相等,，那就直接用新的value覆蓋舊的value；如果這兩個key不相等,，那么就連接在第一個key的后面,，用頭插法形成鏈表(JDK1.8開始用尾插法),。由此鏈表就誕生了,。
JDK1.8開始，又對HashMap進行了優(yōu)化,。我們知道鏈表讀取數(shù)據(jù)不方便,，所以為了避免鏈表太長，又加入了紅黑樹結(jié)構(gòu),。當(dāng)鏈表長度達到閾值時,，就會將鏈表轉(zhuǎn)成紅黑樹。
所以宏觀的來說,，JDK1.8開始,，HashMap是由(數(shù)組 + 鏈表 + 紅黑樹)實現(xiàn)的。首先是用hash去判斷元素應(yīng)該放到數(shù)組中的哪個位置,，如果該位置已有元素,，就判斷這兩個元素的key是否相同，相同就覆蓋,，不同就生成鏈表,，接在后面。當(dāng)鏈表達到一定長度時,，就轉(zhuǎn)成紅黑樹,。同時數(shù)組的元素個數(shù)達到一定值時，就會進行擴容,。擴容之后再將數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組,。
二、HashMap實現(xiàn)細節(jié)
1,、用什么存儲元素,？
根據(jù)上面的宏觀描述，可以知道,，我們需要一個Node類,，里面有四個屬性，分別是 key、value,、hash,、next。其中next是Node類型,，表示下一個節(jié)點,，用于生成鏈表。同時需要一個Node[ ] 數(shù)組,，用來存儲每個節(jié)點,。如下代碼所示：
1// 這是源碼中的節(jié)點內(nèi)部類。
2 static class Node<K,V> implements Map.Entry<K,V> {
3 final int hash;
4 final K key;
5 V value;
6 Node<K,V> next;
7 ...
8}
9// 源碼中的節(jié)點數(shù)組
10 transient Node<K,V>[] table;
2,、數(shù)組如何初始化,？
從上面我們可以看到，這個數(shù)組并沒有初始化,，那么當(dāng)我們put元素的時候,，這個數(shù)組是如何初始化的呢？
通過源碼可以發(fā)現(xiàn),，put方法里面調(diào)用了一個putVal方法,，在putVal方法中，首先判斷數(shù)組長度是不是沒有初始化,，如果是,，就調(diào)用resize方法進行初始化。
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
2 Node<K,V>[] tab; Node<K,V> p; int n, i;
3 if ((tab = table) == null || (n = tab.length) == 0)
4 n = (tab = resize()).length;
5 ...
6}
接下來看看resize方法是怎么初始化數(shù)組的,。
1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
這個是數(shù)組初始化默認的大小,。
1 ...
2 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
3 table = newTab;
4 ...
5 return newTab;
在這個方法中，其他的先不用看,，就看這幾行代碼,，其中newCap的值就是與上面數(shù)組默認初始化大小值一樣，也就是16,。也就是說,，使用HashMap的時候，首先會初始化一個長度為16的數(shù)組,，用來存儲元素,。
3、如何將元素放入數(shù)組,？
初始化了一個長度為16的數(shù)組,，那么索引就是 0 ~ 15，當(dāng)put元素的時候,，如何知曉元素是放入哪個位置呢,？Node內(nèi)部類的hash屬性就起作用了,。首先來看看這個hash屬性是怎么來的。
1static final int hash(Object key) {
2 int h;
3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4}
在HasnMap中有一個hash方法,，該方法返回key的hashCode值的高16與低16位進行異或運算(科普一下：異或運算,，將運算數(shù)轉(zhuǎn)成二進制，1\^1=0,，1\^0=1,，0\^0=0 ，0^1=1,，也就是說,，相等為0，不等為1,；與運算,，將運算數(shù)轉(zhuǎn)成二進制，1&1=1,，1&0=0,，0&1=0，0&0=0,；或運算，將運算數(shù)轉(zhuǎn)成二進制,，1|1=1,，1|0=1，0|1=1,，0|0=0),，該值就是hash。為什么要這樣計算hash的值,，而不直接使用hashCode方法計算的值,？hashCode方法返回值是一個32位的二進制數(shù)，等下在計算元素索引的時候,，這32位并沒有都參與運算,，這樣的話，兩個key計算出來的索引一致的概率就更大,，所以要讓這32位充分利用起來,，都參與計算，所以先用hashCode值的高16位與低16位進行異或運算,。那么為什么是異或,，而不是其他運算呢？從上面括號內(nèi)的說明可以知道,，只有異或運算,，得到1和0的概率都是0.5。為了不影響計算結(jié)果，所以選擇了異或,。
有了hash后,，如何計算出索引？
1...
2 if ((p = tab[i = (n - 1) & hash]) == null)
3 tab[i] = newNode(hash, key, value, null);
4
5...
6}
在putVal方法中,，有這樣一段代碼,。索引 i 就是 hash 和 n ( n是數(shù)組長度 - 1) 進行與運算得來的。為什么這樣算呢,？上面說了,，數(shù)組默認初始化長度為16，二進制就是 10000,，減一后結(jié)果就是 01111,。再用 hash 和 01111 進行與運算，其結(jié)果一定是在 0 到 01111 這個范圍的,，也就是 0 到 15 之間,。而數(shù)組索引也是 0 到 15，這樣便達到了目的,。計算出來的結(jié)果是 n,，那就放入數(shù)組索引為 n 的位置。
問題來了,，因為數(shù)組默認初始化長度是16,，是2的n次冪。(length - 1) 就是奇數(shù),，最后一位是1,。這樣就保證了 hash & (length - 1) 的計算結(jié)果可能為奇數(shù)也可能為偶數(shù)，保證了散列的均勻性,。
4,、如果我們給的初始化大小不是2的n次冪怎么辦？
HashMap還有個構(gòu)造方法,，我們可以自己傳入一個數(shù)組初始化容量,。如下：
1HashMap<Integer,String> map = new HashMap<>(20);
根據(jù)上面的分析，我們知道數(shù)組的大小一定得是2的n次冪,，才能保證散列均勻分布,。如果我傳入不是2的n次冪，比如是20,，那么如何處理,？
通過源碼我們可以發(fā)現(xiàn)如下的一個方法：
1static final int tableSizeFor(int cap) {
2 int n = cap - 1;
3 n |= n >>> 1;
4 n |= n >>> 2;
5 n |= n >>> 4;
6 n |= n >>> 8;
7 n |= n >>> 16;
8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9 }
這個方法的作用就是，如果用戶傳入的不是2的n次冪,，那么就會return一個大于和用戶傳入的數(shù)最接近的2的n次冪的數(shù),。比如傳入20,，那么實際上數(shù)組的大小將會是32。
5,、數(shù)組何時進行擴容,？如何擴容？
resize方法不僅是用來初始化的,，也是用來擴容的,。那么什么時候進行擴容？是數(shù)組中的元素滿了才擴容的嗎,？當(dāng)然不是,。
1 static final float DEFAULT_LOAD_FACTOR = 0.75f;
在源碼中有這么一個常量，暫且稱作擴容因子,。當(dāng)數(shù)組中元素個數(shù)達到了數(shù)組長度的四分之三的時候,，就會進行擴容。上面也說了,，數(shù)組長度必須是2的n次冪,，所以擴容就會擴成兩倍。原來長度為16,，當(dāng)數(shù)組中有12個元素了,，就會進行擴容，擴成32,。那么舊數(shù)組的數(shù)據(jù)如何移動到新數(shù)組呢,？有三種情況：
如果是單個元素，那就用 hash & (newLength - 1 ),；
如果是鏈表，那么就用看 hash & oldLength 的計算結(jié)果是否為0(oldLength表示舊數(shù)組的容量),，如果為0,，放在原位置，如果不為0,，放在 (原來的index + 舊數(shù)組容量) 的位置,。
如果是紅黑樹，那么將樹打散,，根據(jù) hash & (newLength - 1 ) 重新分配位置,。
所以總結(jié)起來就是，要么在原來的位置,，要么在原來索引加上原數(shù)組容量的位置,。
6、什么時候會生成鏈表,？
上面說了HashMap通過計算 hash & (數(shù)組長度 - 1 ) 的值來確定元素放入數(shù)組中哪個位置,。當(dāng)兩個元素計算出來的值一樣時,，如何處理？那么就會繼續(xù)通過equals方法方法判斷這兩個元素的key是否一樣,，如果一樣,，那么新的value就會覆蓋舊的value；如果不一樣,，就會生成鏈表,。在jdk 1.7的時候，用頭插法生成鏈表,，jdk1.8開始,，用尾插法生成鏈表。
7,、為什么要有紅黑樹,？什么時候生成紅黑樹？
上面說了什么時候生成鏈表,，我們知道鏈表讀取數(shù)據(jù)很慢,，如果鏈表太長，會導(dǎo)致讀取性能不好,。所以就出現(xiàn)了紅黑樹,。在源碼中，有如下常量：
1 static final int TREEIFY_THRESHOLD = 8;
也就是說,，當(dāng)鏈表的長度達到了8,，就會將鏈表轉(zhuǎn)成紅黑樹，以提高讀取效率,。還有一個常量：
1static final int UNTREEIFY_THRESHOLD = 6;
也就是說,，當(dāng)樹中元素個數(shù)少于6個時，那就將樹變回鏈表,。
紅黑樹的平均查找長度為log(n),，鏈表的平均查找長度為 n/2。當(dāng)元素個數(shù)為8時,，使用鏈表平均查找長度為4,，而使用紅黑樹的話平均查找長度為3，所以有必要轉(zhuǎn)成紅黑樹,。當(dāng)元素個數(shù)小于等于6時,，用鏈表平均查找長度是3，速度已經(jīng)很快了,，所以沒必要轉(zhuǎn)紅黑樹,。
小結(jié)：往HashMap中put元素主要分為以下幾個步驟：
1. hash(key)，計算key的hash,，用key的hashCode值的高16位和低16位進行異或運算,；
2. 調(diào)用resize方法初始化數(shù)組,，默認初始化大小為 16 ，如果自定義的初始化大小x不是2的n次冪,，就會轉(zhuǎn)成比x大的最接近x的2的n次冪,；
3. hash和數(shù)組長度減一的值進行與運算，判斷元素在數(shù)組中的存儲位置,，如果這個位置沒有其他key,，直接存入該位置，如果有其他的key,，那么又有三種情況：
--- ：如果key相等,，直接替換
--- ：如果key不等，生成鏈表
--- ：如果鏈表長度達到 8 了,，那就轉(zhuǎn)成紅黑樹
4. 當(dāng)數(shù)組中元素個數(shù)達到容量的 0.75 時,，調(diào)用resize方法將容量擴為當(dāng)前的兩倍。
5. 擴容后數(shù)據(jù)的轉(zhuǎn)移有兩種情況：
--- ：如果是單個元素或者是紅黑樹,，根據(jù) hash ^ （newLength - 1）的方式存儲,；
---：如果是鏈表，判斷 hash ^ oldLength 的值是否為0,，如果是,，放在原位置，不為0,，放在 (原index + 舊數(shù)組容量) 的位置,。
三、ConcurrentHashMap
1,、為什么要有ConcurrentHashMap,？
看了HashMap的源碼之后，可以發(fā)現(xiàn)HashMap并不是同步的,。如果在多線程環(huán)境中同時對一個HashMap進行讀寫操作,，肯定是會出問題的。那么如何保證在多線程中的安全問題呢,？加鎖！沒錯,，最熟悉的就是 synchronized 了,。只要在HashMap的每個方法中都加上 synchronized 關(guān)鍵字，就安全了,。確實可以,，HashTable就是這樣做的，所以它被淘汰了,，因為這樣性能很低,。接下來就該ConcurrentHashMap上場表演了,。
2、ConcurrentHashMap如何保證線程安全,？
說這個問題之前,，先回到HashMap的小結(jié)中的5個過程，看看5個過程哪幾個過程在多線程環(huán)境中可能出現(xiàn)線程安全問題,。
1. hash(key),，這個過程不管多少個線程同時操作，計算出的hash都是一樣的,，不會有線程安全問題,。所以ConcurrentHashMap中這個過程沒做處理。
2. 初始化數(shù)組,，這個過程肯定會有問題,。比如一個線程要初始化容量為16，另一個線程要初始化容量為32,，那么怎么辦,？ConcurrentHashMap采用了CAS算法來保證線程的安全性。當(dāng)有線程初始化map了,，其他線程就yield,，禮讓一下。初始化數(shù)組的 initTable 方法如下：
1private final Node<K,V>[] initTable() {
2 Node<K,V>[] tab; int sc;
3 while ((tab = table) == null || tab.length == 0) {
4 if ((sc = sizeCtl) < 0)
5 Thread.yield(); // lost initialization race; just spin
6 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
7 try {
8 if ((tab = table) == null || tab.length == 0) {
9 int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
10 @SuppressWarnings("unchecked")
11 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
12 table = tab = nt;
13 sc = n - (n >>> 2);
14 }
15 } finally {
16 sizeCtl = sc;
17 }
18 break;
19 }
20 }
21 return tab;
22 }
關(guān)于CAS算法的工作原理,，它如何保證線程安全,，以后再寫個文章詳細說明，此處不多說,。
1 if (tab == null || (n = tab.length) == 0)
2 tab = initTable();
3 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
4 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
5 break; // no lock when adding to empty bin
6 }
先看這段代碼,，首先判斷數(shù)組是否為空，為空,，那么就調(diào)用initTable進行初始化,。如果不為空，并且要插入的位置沒有元素,，就執(zhí)行casTabAt方法,。下面來看一個這個方法：
1 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
2 return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
3 }
這個方法也是使用了CAS算法，也就是說,，當(dāng)要插入的位置沒有其他key時,，也是用CAS保證線程的安全性的。如果要插入的位置有key存在呢，看接下來的代碼：
1 else {
2 synchronized (f) {
3 ......
4 }
5}
如果要插入的位置有key了,，那么要判斷是替換還是生成鏈表還是生成紅黑樹,，情況比較復(fù)雜。所以直接用synchronized代碼塊,。鎖對象是當(dāng)前操作的node節(jié)點,，縮小了鎖的粒度也就是說，其他線程只是不能對當(dāng)前節(jié)點進行操作,，但可以對其他節(jié)點進行操作,。
4、擴容和轉(zhuǎn)移數(shù)據(jù)：這個過程也會有線程安全問題,。只能有一個線程進行擴容,，當(dāng)一個線程進行擴容的時候，其他線程也別閑著,，其他線程就幫忙將舊數(shù)組的數(shù)據(jù)轉(zhuǎn)移到新數(shù)組,。擴容的addCount方法也是通過CAS來保證線程安全的。在putVal方法中,，好友一個判斷條件如下：
1else if ((fh = f.hash) == MOVED) // -1
2 tab = helpTransfer(tab, f);
當(dāng)那個值等于-1時,，那么就調(diào)用helpTransfer方法去幫忙進行數(shù)據(jù)的轉(zhuǎn)移。
小結(jié)：ConcurrentHashMap在put元素時主要邏輯如下：
1 if (tab == null || (n = tab.length) == 0) // 數(shù)組為空
2 tab = initTable(); // 初始化,，CAS保證線程安全
3 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { // 要插入的位置key為null
4 // casTabAt 方法用CAS保證線程安全
5 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
6 delta = 1;
7 val = value;
8 break;
9 }
10 }
11 else if ((fh = f.hash) == MOVED) // f.hash == MOVED(-1)
12 tab = helpTransfer(tab, f); // 幫忙轉(zhuǎn)移元素到擴容后的數(shù)組,，CAS保證安全性
13 else { // 要插入的位置key不為null
14 synchronized (f) { // 同步代碼塊保證線程安全
15 ......
16 }
17 }
18 if (delta != 0)
19 addCount((long)delta, binCount); // 擴容，CAS保證安全性
