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