HashMap是一個常用的集合，日常使用可能我們并不關(guān)心它是如何實現(xiàn)的，不過它是面試中的常客。所以為了弄懂它，不妨看一看源碼，同時也可以學習一下大牛的編程思想。

一、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)。當鏈表長度達到閾值時，就會將鏈表轉(zhuǎn)成紅黑樹。

所以宏觀的來說，JDK1.8開始，HashMap是由(數(shù)組 + 鏈表 + 紅黑樹)實現(xiàn)的。首先是用hash去判斷元素應(yīng)該放到數(shù)組中的哪個位置，如果該位置已有元素，就判斷這兩個元素的key是否相同，相同就覆蓋，不同就生成鏈表，接在后面。當鏈表達到一定長度時，就轉(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ù)組并沒有初始化，那么當我們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，當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ù)組中的元素滿了才擴容的嗎？當然不是。

1 static final float DEFAULT_LOAD_FACTOR = 0.75f;

在源碼中有這么一個常量，暫且稱作擴容因子。當數(shù)組中元素個數(shù)達到了數(shù)組長度的四分之三的時候，就會進行擴容。上面也說了，數(shù)組長度必須是2的n次冪，所以擴容就會擴成兩倍。原來長度為16，當數(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ù)組中哪個位置。當兩個元素計算出來的值一樣時，如何處理？那么就會繼續(xù)通過equals方法方法判斷這兩個元素的key是否一樣，如果一樣，那么新的value就會覆蓋舊的value；如果不一樣，就會生成鏈表。在jdk 1.7的時候，用頭插法生成鏈表，jdk1.8開始，用尾插法生成鏈表。

7、為什么要有紅黑樹？什么時候生成紅黑樹？
上面說了什么時候生成鏈表，我們知道鏈表讀取數(shù)據(jù)很慢，如果鏈表太長，會導致讀取性能不好。所以就出現(xiàn)了紅黑樹。在源碼中，有如下常量：

1 static final int TREEIFY_THRESHOLD = 8;

也就是說，當鏈表的長度達到了8，就會將鏈表轉(zhuǎn)成紅黑樹，以提高讀取效率。還有一個常量：

1static final int UNTREEIFY_THRESHOLD = 6;

也就是說，當樹中元素個數(shù)少于6個時，那就將樹變回鏈表。

紅黑樹的平均查找長度為log(n)，鏈表的平均查找長度為 n/2。當元素個數(shù)為8時，使用鏈表平均查找長度為4，而使用紅黑樹的話平均查找長度為3，所以有必要轉(zhuǎn)成紅黑樹。當元素個數(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. 當數(shù)組中元素個數(shù)達到容量的 0.75 時，調(diào)用resize方法將容量擴為當前的兩倍。

• 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算法來保證線程的安全性。當有線程初始化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算法的工作原理，它如何保證線程安全，以后再寫個文章詳細說明，此處不多說。

• 3、 存放元素，這個過程肯定也會有線程安全問題。

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算法，也就是說，當要插入的位置沒有其他key時，也是用CAS保證線程的安全性的。如果要插入的位置有key存在呢，看接下來的代碼：

1 else {
2       synchronized (f) {
3       ......
4       }
5}

如果要插入的位置有key了，那么要判斷是替換還是生成鏈表還是生成紅黑樹，情況比較復(fù)雜。所以直接用synchronized代碼塊。鎖對象是當前操作的node節(jié)點，縮小了鎖的粒度也就是說，其他線程只是不能對當前節(jié)點進行操作，但可以對其他節(jié)點進行操作。

• 4、擴容和轉(zhuǎn)移數(shù)據(jù)：這個過程也會有線程安全問題。只能有一個線程進行擴容，當一個線程進行擴容的時候，其他線程也別閑著，其他線程就幫忙將舊數(shù)組的數(shù)據(jù)轉(zhuǎn)移到新數(shù)組。擴容的addCount方法也是通過CAS來保證線程安全的。在putVal方法中，好友一個判斷條件如下：

1else if ((fh = f.hash) == MOVED) // -1
2        tab = helpTransfer(tab, f);

當那個值等于-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保證安全性