前言

對于初級和中級程序員來說，Java的Api是必須邁過的一個“坎”，許多程序員在對業(yè)務代碼麻木后就會對代碼的實現(xiàn)原理進行理解，而Java的Api中HashMap、ConcurrentHashMap可能是大家使用最為頻繁且面試最容易問到數(shù)據(jù)結(jié)構(gòu)，本文不會對HashMap、ConcurrentHashMap源碼進行逐行的解析，只是會對其中我感覺比較重要的點進行總結(jié)（建議對HashMap、ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)有基本了解后再讀下面章節(jié)的內(nèi)容），通過對比JDK7 、JDK8中的HashMap和ConcurrentHashMap，讓大家對其原理有一個深入的理解。

一、JDK7中的HashMap

1.HashMap中槽的默認大?。〝?shù)組長度）為什么要始終保持2的N次方?

• 性能：HashMap在進行元素的put操作時，要通過key的hash值定位對應的槽位，正常的操作一般都是hash%length，但“與”操作與“?！辈僮飨啾刃阅芤?，所以Api采用了hash&（length-1）的方式，這么做的一個前提就是length為2的N次方。
  hash=11 length=5： hash%length=11%5=1 hash&（length-1）=11&4=0
  hash=11 length=4： hash%length=11%4=3 hash&（length-1）=11&3=3
• 目標： 為了保持分布均勻而較少碰撞，如果length為2的N次方，那么length-1在二進制上后面的位都為1，這樣與hash進行運算會盡量多產(chǎn)生出結(jié)果，減少碰撞。
  length=9：hash&（length-1）=11&8=8 hash%length=15%8=8 ->產(chǎn)生碰撞
  length=8：hash&（length-1）=11&7=3 hash%length=15%7=7 ->避免碰撞

2.為什么計算完hashcode要再進行一次hash計算？

• hashcode：計算規(guī)則為s[0]*31^(n-1)+s[1]*31^(n-2)+...+s[n-1]，其中的31為奇數(shù)數(shù)，能夠保證31*i=（i<<5）-i

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

• hash：好多人給這一次哈希操作叫做“擾動函數(shù)”，hashCode返回的是Int的散列值，如果我們槽的數(shù)量比較少且是2的N次方，那反應到二進制上前幾位都為0，后幾位都為1（或高位值不同低位值相同），碰撞也會很嚴重，該算法將二進制的高半?yún)^(qū)與低半?yún)^(qū)進行了異或操作，來加大二進制低位取值的隨機性，將高低位的值反應到哈希值上，從而來減少碰撞。

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

3.什么是HashMap中的Fail-Fast機制？
在HashMap中有一個變量為modCount，它的類型為volatile，每次對HashMap進行修改都要修改該值，我們都知道HashMap線程不安全，該變量的作用就是確定在該線程感知其他線程是否對HashMap進行了修改，如果發(fā)現(xiàn)了則拋出異常，這個過程簡稱Fail-Fast，如我再遍歷HashMap所有的key與value，其他線程對HashMap進行了修改，當我判斷該值與之前取值不同時，則拋出異常。

4.HashMap在插入和擴容時有什么特點？

• 在插入時，若key為null，則插入到槽位0處，如插入的Entry存在哈希沖突，將新Entry值放到槽位，作為沖突鏈表的頭jiedian。
• 在擴容時，我們從原鏈表的頭結(jié)點開始逐一遍歷，遍歷到每一個Entry時就放到擴容的HashMap沖突鏈表的頭結(jié)點。

5.為什么HashMap線程不安全?

• 在put時引起數(shù)據(jù)不一致：若線程1執(zhí)行完了下方代碼的（1）操作后被掛起，線程2開始執(zhí)行，線程2完成了哈希沖突的put操作，在指定的槽位置插入了新的元素，線程1中e指向的元素成為了鏈表頭的next結(jié)點，這時線程1繼續(xù)執(zhí)行（2）操作，就會使槽位的元素設置為線程1要設置的元素值，刷新了線程2中設置的鏈表頭結(jié)點，從而造成了數(shù)據(jù)的不一致。

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];                      (1)
        table[bucketIndex] = new Entry<>(hash, key, value, e);  (2)
        size++;
    }

• 在resize時引起死循環(huán)（CPU100%）：若線程1進行擴容執(zhí)行下方代碼的（1）的操作后線程掛起，線程2同樣也執(zhí)行擴容，并完成了全部的擴容操作（假設擴容后的結(jié)點依舊在同一個槽位），由于JDK7中哈希沖突的鏈表采用的是“頭插法“，所以切換回線程1繼續(xù)執(zhí)行剩下的步驟，會出現(xiàn)Entry之間的循環(huán)引用，在get操作時會造成死循環(huán)，并吃掉所有CPU資源，具體流程見下圖。
  

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;                           (1)
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];                               (2)
            newTable[i] = e;                                    (3)
            e = next;                                           (4)
        }
    }
}

二、JDK7中的ConcurrentHashMap

1.ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)，為什么他是線程安全的？

• 數(shù)據(jù)結(jié)構(gòu)：在ConcurrentHashMap中外層是由segment組成的segment數(shù)組，每個segment中存在一個HashEntry數(shù)組（Segment類中有成員變量 HashEntry<K,V>[] table），如果key發(fā)生沖突，與HashMap一樣會形成HashEntry鏈表結(jié)構(gòu)，從大到小的數(shù)據(jù)結(jié)構(gòu)為ConcurrentHashMap->segment->HashEntry，在網(wǎng)上找到的ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)的示意圖如下。
  

• 線程安全：由于ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)中存在Segment，采用的是“分段鎖”的機制保證了ConcurrentHashMap的線程安全。Segment繼承ReentrantLock，相當于每個Segment都掌握一把鎖，在并發(fā)操作時，只鎖對應的Segment，而不會影響其他Segment的操作，但這也不代表整個ConcurrentHashMap不會上鎖，ConcurrentHashMap的size()等方法在某些條件下會鎖整個數(shù)據(jù)結(jié)構(gòu)，在并發(fā)時候應用UNSAFE類實現(xiàn)了可見性，UNSAFE類相當于可以直接操作內(nèi)存數(shù)據(jù)。

2.在ConcurrentHashMap中如何確定段（Segment）數(shù)和每段數(shù)組的大小等參數(shù)？

• 初始容量：ConcurrentHashMap默認大小為16，最大大小2³⁰，負載因子默認0.75，默認并發(fā)數(shù)（段數(shù)）16，最大分段數(shù)2¹⁶，每段的最小容量為2。
• 如何確定：首先根據(jù)并發(fā)數(shù)concurrencyLevel確定段數(shù)，段數(shù)為最靠近concurrencyLevel2的N次方（向上取）的數(shù)，如concurrencyLevel為15，那段數(shù)就應該為16，其次根據(jù)初始容量initialCapacity確定每段的數(shù)組大小，數(shù)組的大小為初始容量除以段數(shù)后最靠近2的N次方（向上?。┑臄?shù)，若初始容量為100，每段數(shù)組的大小應該為8（100/16=6，最后取8）。

public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel)

• 確定segment索引：在如何確定參數(shù)大小時，構(gòu)造函數(shù)中通過sshift、ssize計算出了參數(shù)的大小，segment索引的計算也是應用這兩個參數(shù)，具體的換算見下方，大體來說就是hash值的高sshift位于ssize-1（段數(shù)的掩碼）進行與運算，若不存在則參照segment[0]創(chuàng)建一個新的，確定了segment索引后，還要定位HashEntry數(shù)組的索引，這個方法與HashMap一致。

  int j = (hash >>> segmentShift) & segmentMask;
        = (hash >>> (32-sshift))&(ssize-1)

3.ConcurrentHashMap的各種操作在獲取鎖時有什么優(yōu)化？

• put：在獲取分段鎖的時候，如果沒獲取到鎖，ConcurrentHashMap不會阻塞，而是做了一定的優(yōu)化，總體來說可以是做了幾次鎖的自旋操作，在自旋中若沒有獲得鎖，會遍歷HashEntry數(shù)組來找到需要put的位置，并實例化目標HashEntry，如其他線程修改了HashEntry數(shù)組還需要重新來進行定位，當獲取鎖超過了設定的自旋的次數(shù)則會阻塞（默認自旋轉(zhuǎn)2次）。
• resize：擴容只針對每一個Segment進行擴容，基本思想與HashMap相同，對老Table進行遍歷，然后移動到新Table中，在其中會先找到一個子鏈表（該鏈表的所有結(jié)點均能定位到新槽位，且包含老Table中的最后一個結(jié)點），然后再遍歷其他的結(jié)點，采用“頭插”發(fā)插入到新Table中。
• size：利用每個segment的size方法獲得總數(shù)，連續(xù)獲得兩次總數(shù)，若兩次相同則認為是最終結(jié)果，若不是則鎖整個ConcurrentHashMap進行統(tǒng)計。

三、JDK8中的HashMap

1.JDK8中的HashMap數(shù)據(jù)結(jié)構(gòu)有什么優(yōu)化嘛？
數(shù)據(jù)結(jié)構(gòu)在用了數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)，主要解決了鏈表過長查詢的效率問題。當沖突少的時候使用的是鏈表來解決沖突，當沖突結(jié)點值大于TREEIFY_THRESHOLD值（默認為8）后，會將鏈表樹化（紅黑樹），當然這個前前提是HashMap的容量要大于64，如果容量小于64（MIN_TREEIFY_CAPACITY默認值）則會先擴容而不是樹化。

2.初始化HashMap容量大小時是否進行了優(yōu)化？
是的，JDK7中采用的是不斷移位-比較的算法，JDK8中采用的是移位-異或算法，不斷的將1從高位刷新到低位（指數(shù)移位），最終得到最接近2的N次方的數(shù)，之所以最開始減1后面加1是為了考慮n本身就為2的N次方的情況，這種情況如果不減1的話，最終的結(jié)果為N的二倍，總體來說該算法主要是為了提升計算HashMap容量初始值的效率問題。

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

3.兩次Hash算法是否進行了優(yōu)化？
是的，并沒有JDK7那么復雜，簡化了流程，高位與地位進行與運算，讓高位也參加到運算中，減少發(fā)生沖突的概率。

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

4.是否了解在沖突時的樹化和鏈化？

• 樹化：當鏈表的長度超過限定的值時，會將鏈表轉(zhuǎn)換成紅合樹，在轉(zhuǎn)換的過程中首先是先將Node結(jié)點轉(zhuǎn)換為TreeNode，TreeNode中依然保留了原鏈表的順序（指針），主要的目的是簡化鏈化的操作，然后，遍歷所有鏈表的結(jié)點，通過對比hash的值，構(gòu)造一顆紅黑樹。
  在比較結(jié)點的大小時先比較hash值的大小，若相同通過Comparable接口的方法進行比較，若還不能確定大小則使用下方的“加時賽”算法確定，底層調(diào)用的Native方法進行比較。

       static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

• 鏈化：按照NodeTree結(jié)點中的原來鏈表的順序構(gòu)造鏈表即可，該方法主要發(fā)生在擴容resize()后和刪除removeNode()操作。

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
    }

5.resize()方法是否進行了優(yōu)化？
在JDK8中的resize()方法根據(jù)沖突的數(shù)據(jù)結(jié)構(gòu)進行擴充，如果當前為鏈表則采用鏈表的擴容算法，若當前為紅黑樹則采用紅黑樹的擴容方法。擴容還是以二倍的方式進行擴容（一定要注意擴容永遠是針對槽位而言，也就是HashMap數(shù)據(jù)結(jié)構(gòu)中的數(shù)組）。

• 鏈表：假設老HashMap的容量為8，現(xiàn)對其中一個槽位的鏈表進行擴容，擴容后能夠保證原插入順序（而不是像JDK7一樣使用鏈表的頭插法）， 其中優(yōu)化了確定在新舊槽位的算法，新槽位的索引是原索引加上老HashMap的容量值，具體的計算過程如下。
  擴容前：
  
  
  擴容后如何判斷槽位：
  
  
  擴容后判斷結(jié)點處于新槽位還是舊槽位：
  
• 紅黑樹：在API中紅黑樹拆分的方法名為split，但其實并不復雜，因為TreeNode存有鏈表的順序，所以按照鏈表的順序遍歷紅黑樹，將其拆分成2個小鏈表，然后根據(jù)鏈表的長度來決定是否將小鏈表轉(zhuǎn)換為紅黑樹即可，之后如有插入紅黑樹的操作也始終維護該鏈表結(jié)構(gòu)。
  6.為什么HashMap的數(shù)組使用transient修飾符修飾？
  首先我們要了解transient修飾符的意義，用transient關(guān)鍵字標記的成員變量不參與序列化過程，HashMap之所以這么設計是因為它本身實現(xiàn)了反序列化方法（readObject、writeObject），這樣的做法有兩個好吃，一方面，HashMap的數(shù)組可能并不是所有的槽位都存儲滿，所以在一定程度上節(jié)約了空間，另一方面，因為Object類的hashCode方法是一個native方法，在不同的JVM下所產(chǎn)生的結(jié)果可能不一樣，不一樣的值會導致結(jié)點不在原本的槽的位置。

四、JDK8中的ConcurrentHashMap

1.JDK8中的ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)是否有改變？
是的，在JDK8中摒棄了原有的Segment的概念，而是直接采用數(shù)組+鏈表+紅黑樹+鎖的數(shù)據(jù)結(jié)構(gòu)。

2.ConcurrentHashMap如何初始化容量，如何計算hash值？
在之前三章的數(shù)據(jù)結(jié)構(gòu)中都是根據(jù)初始化值找到大于該值，且最接近2的N次方的數(shù)組，而在該算法中不再這樣，即使initialCapacity為2的N次方，那最后的容量也是initialCapacity的2倍，之所以這么考慮我想應該是盡可能的多申請一些空間，減少擴容和鎖帶來的性能問題。

  tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

在計算hash方面，與JDK8的HashMap很相似，但是唯一不同的是多了一步與操作 & HASH_BITS（0x7fffffff），主要的目的是確保最后的值是正數(shù)，在插入操作中也是用hash值的正負來判斷是鏈表節(jié)點還是樹節(jié)點。

 static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

3.ConcurrentHashMap如何初始化容量在擴容時與之前有什么差別？
當槽位的沖突的元素的個數(shù)超過8（TREEIFY_THRESHOLD）個時，會將鏈表轉(zhuǎn)成紅黑樹，但如果當前的ConcurrentHashMap數(shù)組大小小于64（MIN_TREEIFY_CAPACITY）時，則不會轉(zhuǎn)成紅黑樹，會優(yōu)先考慮對數(shù)組的大小進行擴容（tryPresize方法）。

java.util.concurrent.ConcurrentHashMap#treeifyBin
  if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);

ConcurrentHashMap的擴容不是僅僅2倍的擴容，而是2的N次方倍，如當前數(shù)組的長度為16，那執(zhí)行擴容方法tryPresize時參數(shù)為32，在方法中會確認最終的擴容大小，根據(jù)下方的算法可以確認擴容后的大小為64，tryPresize方法沒有加鎖，多線程環(huán)境下執(zhí)行，當前線程會幫助去擴容。

java.util.concurrent.ConcurrentHashMap#tryPresize
 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);

4.ConcurrentHashMap如何在多線程下進行擴容并保證線程安全？
在JDK8的ConcurrentHashMap中，有一個ForwardingNode的數(shù)據(jù)結(jié)構(gòu)，如果該槽位已經(jīng)完成擴容會將Node節(jié)點替換為ForwardingNode節(jié)點，其它線程如果發(fā)現(xiàn)該槽位沒有完成擴容會幫助其進行擴容，若發(fā)現(xiàn)已經(jīng)完成擴容則不會再進行擴容。
擴容的核心方法為transfer，第一個進行擴容的線程會創(chuàng)建2倍的數(shù)組容量來進行擴容。擴容的大體的過程是，每個線程在transfer都會領(lǐng)取任務，任務會說說明該線程需要遷移的節(jié)點的范圍，剩下的就是很多的判斷，如是否全部槽位已經(jīng)完成擴容、一個槽位是否已經(jīng)完成擴容，在擴容的時候與HashMap類似，對對應的槽位上鎖以后，則進行擴容，如果為鏈表則拆分為兩個鏈表，如果為紅黑樹則拆分為兩個紅黑樹，若紅黑樹的節(jié)點數(shù)小于8則再轉(zhuǎn)化為鏈表。