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

歡迎大家關(guān)注我的公眾號 javawebkf含末，目前正在慢慢地將簡書文章搬到公眾號猜拾，以后簡書和公眾號文章將同步更新，且簡書上的付費文章在公眾號上將免費佣盒。

一挎袜、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é)點蹋辅。如下代碼所示：

// 這是源碼中的節(jié)點內(nèi)部類钱贯。
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}
// 源碼中的節(jié)點數(shù)組
 transient Node<K,V>[] table;

2、數(shù)組如何初始化侦另？
從上面我們可以看到秩命，這個數(shù)組并沒有初始化，那么當我們put元素的時候褒傅，這個數(shù)組是如何初始化的呢弃锐？
通過源碼可以發(fā)現(xiàn)，put方法里面調(diào)用了一個putVal方法殿托，在putVal方法中霹菊，首先判斷數(shù)組長度是不是沒有初始化，如果是碌尔，就調(diào)用resize方法進行初始化浇辜。

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        ...
}

接下來看看resize方法是怎么初始化數(shù)組的。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

這個是數(shù)組初始化默認的大小唾戚。

 ...
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 ...
 return newTab;

在這個方法中，其他的先不用看待诅，就看這幾行代碼叹坦，其中newCap的值就是與上面數(shù)組默認初始化大小值一樣，也就是16卑雁。也就是說募书，使用HashMap的時候，首先會初始化一個長度為16的數(shù)組测蹲，用來存儲元素莹捡。

3、如何將元素放入數(shù)組扣甲？
初始化了一個長度為16的數(shù)組篮赢，那么索引就是 0 ~ 15，當put元素的時候琉挖，如何知曉元素是放入哪個位置呢启泣？Node內(nèi)部類的hash屬性就起作用了。首先來看看這個hash屬性是怎么來的示辈。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在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后挑随，如何計算出索引？

...
 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

...
}

在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ù)組初始化容量扰付。如下：

HashMap<Integer,String> map = new HashMap<>(20);

根據(jù)上面的分析，我們知道數(shù)組的大小一定得是2的n次冪仁讨，才能保證散列均勻分布羽莺。如果我傳入不是2的n次冪，比如是20洞豁，那么如何處理盐固？

通過源碼我們可以發(fā)現(xiàn)如下的一個方法：

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;
 }

這個方法的作用就是，如果用戶傳入的不是2的n次冪丈挟，那么就會return一個大于和用戶傳入的數(shù)最接近的2的n次冪的數(shù)刁卜。比如傳入20，那么實際上數(shù)組的大小將會是32曙咽。

5蛔趴、數(shù)組何時進行擴容？如何擴容例朱？
resize方法不僅是用來初始化的孝情，也是用來擴容的鱼蝉。那么什么時候進行擴容？是數(shù)組中的元素滿了才擴容的嗎箫荡？當然不是魁亦。

 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)了紅黑樹灰殴。在源碼中敬特，有如下常量：

 static final int TREEIFY_THRESHOLD = 8;

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

static 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 方法如下：

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

關(guān)于CAS算法的工作原理，它如何保證線程安全箫攀，以后再寫個文章詳細說明肠牲，此處不多說。

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

 if (tab == null || (n = tab.length) == 0)
         tab = initTable();
 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
         if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
               break;                   // no lock when adding to empty bin
 }

先看這段代碼梢睛，首先判斷數(shù)組是否為空肥印，為空，那么就調(diào)用initTable進行初始化绝葡。如果不為空深碱，并且要插入的位置沒有元素，就執(zhí)行casTabAt方法藏畅。下面來看一個這個方法：

 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
 }

這個方法也是使用了CAS算法敷硅，也就是說趣兄，當要插入的位置沒有其他key時潭枣，也是用CAS保證線程的安全性的。如果要插入的位置有key存在呢终畅，看接下來的代碼：

 else {
       synchronized (f) {
       ......
       }
}

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

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

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

當那個值等于-1時肉盹，那么就調(diào)用helpTransfer方法去幫忙進行數(shù)據(jù)的轉(zhuǎn)移。

小結(jié)：ConcurrentHashMap在put元素時主要邏輯如下：

 if (tab == null || (n = tab.length) == 0) // 數(shù)組為空
         tab = initTable(); // 初始化疹尾，CAS保證線程安全
 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { // 要插入的位置key為null 
         // casTabAt 方法用CAS保證線程安全
         if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) { 
             delta = 1;
             val = value;
             break;
          }
 }
 else if ((fh = f.hash) == MOVED) // f.hash == MOVED(-1)
          tab = helpTransfer(tab, f); // 幫忙轉(zhuǎn)移元素到擴容后的數(shù)組上忍，CAS保證安全性
 else { // 要插入的位置key不為null 
          synchronized (f) { // 同步代碼塊保證線程安全
                   ......
          }
 }
 if (delta != 0) 
          addCount((long)delta, binCount); // 擴容，CAS保證安全性