我們了解到關(guān)于 HashMap 和 Hashtable 這兩種集合谨娜。其中 HashMap 是非線程安全的渠旁，當(dāng)我們只有一個(gè)線程在使用 HashMap 的時(shí)候竭翠，自然不會(huì)有問題脑蠕，但如果涉及到多個(gè)線程酌泰，并且有讀有寫的過程中媒佣，HashMap 就不能滿足我們的需要了(fail-fast)。在不考慮性能問題的時(shí)候陵刹，我們的解決方案有 Hashtable 或者Collections.synchronizedMap(hashMap)默伍，這兩種方式基本都是對整個(gè) hash 表結(jié)構(gòu)做鎖定操作的，這樣在鎖表的期間衰琐，別的線程就需要等待了也糊，無疑性能不高。
所以我們學(xué)習(xí)一個(gè) util.concurrent 包的重要成員羡宙，ConcurrentHashMap狸剃。
ConcurrentHashMap 的實(shí)現(xiàn)是依賴于 Java 內(nèi)存模型，所以我們在了解 ConcurrentHashMap 的前提是必須了解Java 內(nèi)存模型狗热。但 Java 內(nèi)存模型并不是本文的重點(diǎn)捕捂，所以我假設(shè)讀者已經(jīng)對 Java 內(nèi)存模型有所了解。
ConcurrentHashMap 分析
ConcurrentHashMap 的結(jié)構(gòu)是比較復(fù)雜的斗搞，都深究去本質(zhì)，其實(shí)也就是數(shù)組和鏈表而已慷妙。我們由淺入深慢慢的分析其結(jié)構(gòu)僻焚。
先簡單分析一下，ConcurrentHashMap 的成員變量中膝擂，包含了一個(gè) Segment 的數(shù)組（final Segment<K,V>[] segments;
）虑啤，而 Segment 是 ConcurrentHashMap 的內(nèi)部類，然后在 Segment 這個(gè)類中架馋，包含了一個(gè) HashEntry 的數(shù)組（transient volatile HashEntry<K,V>[] table;
）狞山。而 HashEntry 也是 ConcurrentHashMap 的內(nèi)部類。HashEntry 中叉寂，包含了 key 和 value 以及 next 指針（類似于 HashMap 中 Entry）萍启，所以 HashEntry 可以構(gòu)成一個(gè)鏈表。
所以通俗的講屏鳍，ConcurrentHashMap 數(shù)據(jù)結(jié)構(gòu)為一個(gè) Segment 數(shù)組勘纯，Segment 的數(shù)據(jù)結(jié)構(gòu)為 HashEntry 的數(shù)組，而 HashEntry 存的是我們的鍵值對钓瞭，可以構(gòu)成鏈表驳遵。
首先，我們看一下 HashEntry 類山涡。
HashEntry
HashEntry 用來封裝散列映射表中的鍵值對堤结。在 HashEntry 類中唆迁，key，hash 和 next 域都被聲明為 final 型竞穷，value 域被聲明為 volatile 型唐责。其類的定義為：

static final class HashEntry<K,V> { 
    final int hash; 
    final K key; 
    volatile V value;
    volatile HashEntry<K,V> next; 
    HashEntry(int hash, K key, V value, HashEntry<K,V> next) { 
        this.hash = hash; 
        this.key = key; 
        this.value = value; 
        this.next = next; 
    } ... ...
}

HashEntry 的學(xué)習(xí)可以類比著 HashMap 中的 Entry。我們的存儲(chǔ)鍵值對的過程中来庭，散列的時(shí)候如果發(fā)生“碰撞”妒蔚，將采用“分離鏈表法”來處理碰撞：把碰撞的 HashEntry 對象鏈接成一個(gè)鏈表。
如下圖月弛，我們在一個(gè)空桶中插入 A肴盏、B、C 兩個(gè) HashEntry 對象后的結(jié)構(gòu)圖（其實(shí)應(yīng)該為鍵值對帽衙，在這進(jìn)行了簡化以方便更容易理解）：

圖1

Segment

Segment 的類定義為
static final class Segment<K,V> extends ReentrantLock implements Serializable

菜皂。其繼承于 ReentrantLock 類，從而使得 Segment 對象可以充當(dāng)鎖的角色厉萝。Segment 中包含HashEntry 的數(shù)組恍飘，其可以守護(hù)其包含的若干個(gè)桶（HashEntry的數(shù)組）。Segment 在某些意義上有點(diǎn)類似于 HashMap了谴垫，都是包含了一個(gè)數(shù)組章母，而數(shù)組中的元素可以是一個(gè)鏈表。
table:table 是由 HashEntry 對象組成的數(shù)組如果散列時(shí)發(fā)生碰撞翩剪，碰撞的 HashEntry 對象就以鏈表的形式鏈接成一個(gè)鏈表table數(shù)組的數(shù)組成員代表散列映射表的一個(gè)桶每個(gè) table 守護(hù)整個(gè) ConcurrentHashMap 包含桶總數(shù)的一部分如果并發(fā)級別為 16乳怎，table 則守護(hù) ConcurrentHashMap 包含的桶總數(shù)的 1/16。
count 變量是計(jì)算器前弯，表示每個(gè) Segment 對象管理的 table 數(shù)組（若干個(gè) HashEntry 的鏈表）包含的HashEntry 對象的個(gè)數(shù)蚪缀。之所以在每個(gè)Segment對象中包含一個(gè) count 計(jì)數(shù)器，而不在 ConcurrentHashMap 中使用全局的計(jì)數(shù)器恕出，是為了避免出現(xiàn)“熱點(diǎn)域”而影響并發(fā)性询枚。

/** 
  * Segments are specialized versions of hash tables. This  
  * subclasses from ReentrantLock opportunistically, just to 
  * simplify some locking and avoid separate construction. 
  */ 
static final class Segment<K,V> extends ReentrantLock implements Serializable { 
   /** 
     * The per-segment table. Elements are accessed via 
     * entryAt/setEntryAt providing volatile semantics. 
     */ 
    transient volatile HashEntry<K,V>[] table; 
    /** 
      * The number of elements. Accessed only either within locks 
      * or among other volatile reads that maintain visibility. 
      */ 
     transient int count; transient int modCount; 
     /** 
       * 裝載因子 
       */ 
     final float loadFactor; 
}

我們通過下圖來展示一下插入 ABC 三個(gè)節(jié)點(diǎn)后，Segment 的示意圖：

圖2

其實(shí)從我個(gè)人角度來說浙巫，Segment結(jié)構(gòu)是與HashMap很像的金蜀。
ConcurrentHashMap
ConcurrentHashMap 的結(jié)構(gòu)中包含的 Segment 的數(shù)組，在默認(rèn)的并發(fā)級別會(huì)創(chuàng)建包含 16 個(gè) Segment 對象的數(shù)組的畴。通過我們上面的知識(shí)才沧，我們知道每個(gè) Segment 又包含若干個(gè)散列表的桶淮椰，每個(gè)桶是由 HashEntry 鏈接起來的一個(gè)鏈表。如果 key 能夠均勻散列，每個(gè) Segment 大約守護(hù)整個(gè)散列表桶總數(shù)的 1/16漆弄。
下面我們還有通過一個(gè)圖來演示一下 ConcurrentHashMap 的結(jié)構(gòu)：

圖3

/** 
  * Maps the specified key to the specified value in this table. 
  * Neither the key nor the value can be null. 
  * 
  * <p> The value can be retrieved by calling the <tt>get</tt> method 
  * with a key that is equal to the original key. 
  * 
  * @param key key with which the specified value is to be associated 
  * @param value value to be associated with the specified key 
  * @return the previous value associated with <tt>key</tt>, or 
  * <tt>null</tt> if there was no mapping for <tt>key</tt> 
  * @throws NullPointerException if the specified key or value is null 
   */ 
@SuppressWarnings("unchecked") 
public V put(K key, V value) { 
    Segment<K,V> s; 
    if (value == null) 
        throw new NullPointerException(); 
    int hash = hash(key); 
    int j = (hash >>> segmentShift) & segmentMask; 
    if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; 
        recheck (segments, (j << SSHIFT) + SBASE)) == null)// in ensureSegment 
        s = ensureSegment(j); 
    return s.put(key, hash, value, false); 
}

我們通過注釋可以了解到抑进，ConcurrentHashMap 不允許空值。該方法首先有一個(gè) Segment 的引用 s睡陪，然后會(huì)通過 hash() 方法對 key 進(jìn)行計(jì)算寺渗，得到哈希值；繼而通過調(diào)用 Segment 的 put(K key, int hash, V value, boolean onlyIfAbsent)方法進(jìn)行存儲(chǔ)操作兰迫。該方法源碼為：

final V put(K key, int hash, V value, boolean onlyIfAbsent) { 
    //加鎖信殊，這里是鎖定的Segment而不是整個(gè)  
    ConcurrentHashMap HashEntry<K,V> node = tryLock() ? null :scanAndLockForPut(key, hash, value);
    V oldValue; try { HashEntry<K,V>[] tab = table; 
    //得到hash對應(yīng)的table中的索引index 
    int index = (tab.length - 1) & hash; 
   //找到hash對應(yīng)的是具體的哪個(gè)桶，也就是哪個(gè)HashEntry鏈表 
    HashEntry<K,V> first = entryAt(tab, index); 
    for (HashEntry<K,V> e = first;;) { 
        if (e != null) { K k; if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 
           oldValue = e.value; 
          if (!onlyIfAbsent) { 
            e.value = value; ++modCount; 
          } 
           break; 
          } 
         e = e.next; 
       } else { 
           if (node != null) 
                 node.setNext(first); 
           else 
                 node = new HashEntry<K,V>(hash, key, value, first); 
                 int c = count + 1; 
                 if (c > threshold && tab.length < MAXIMUM_CAPACITY) 
                     rehash(node); 
                  else setEntryAt(tab, index, node);   
              ++modCount; 
                count = c; 
               oldValue = null; 
               break; 
             } 
            }
          } finally { 
              //解鎖 unlock(); 
           }
           return oldValue;
  }

關(guān)于該方法的某些關(guān)鍵步驟汁果，在源碼上加上了注釋涡拘。
需要注意的是：加鎖操作是針對的 hash 值對應(yīng)的某個(gè) Segment，而不是整個(gè) ConcurrentHashMap据德。因?yàn)?put 操作只是在這個(gè) Segment 中完成鳄乏，所以并不需要對整個(gè) ConcurrentHashMap 加鎖。所以棘利，此時(shí)橱野，其他的線程也可以對另外的 Segment 進(jìn)行 put 操作，因?yàn)殡m然該 Segment 被鎖住了善玫，但其他的 Segment 并沒有加鎖水援。同時(shí)，讀線程并不會(huì)因?yàn)楸揪€程的加鎖而阻塞蝌焚。
正是因?yàn)槠鋬?nèi)部的結(jié)構(gòu)以及機(jī)制，所以 ConcurrentHashMap 在并發(fā)訪問的性能上要比Hashtable和同步包裝之后的HashMap的性能提高很多誓斥。在理想狀態(tài)下只洒，ConcurrentHashMap 可以支持 16 個(gè)線程執(zhí)行并發(fā)寫操作（如果并發(fā)級別設(shè)置為 16），及任意數(shù)量線程的讀操作劳坑。
總結(jié)
在實(shí)際的應(yīng)用中毕谴，散列表一般的應(yīng)用場景是：除了少數(shù)插入操作和刪除操作外，絕大多數(shù)都是讀取操作距芬，而且讀操作在大多數(shù)時(shí)候都是成功的涝开。正是基于這個(gè)前提，ConcurrentHashMap 針對讀操作做了大量的優(yōu)化框仔。通過 HashEntry 對象的不變性和用 volatile 型變量協(xié)調(diào)線程間的內(nèi)存可見性舀武，使得 大多數(shù)時(shí)候，讀操作不需要加鎖就可以正確獲得值离斩。這個(gè)特性使得 ConcurrentHashMap 的并發(fā)性能在分離鎖的基礎(chǔ)上又有了近一步的提高银舱。
ConcurrentHashMap 是一個(gè)并發(fā)散列映射表的實(shí)現(xiàn)瘪匿，它允許完全并發(fā)的讀取，并且支持給定數(shù)量的并發(fā)更新寻馏。相比于 HashTable 和用同步包裝器包裝的 HashMap（Collections.synchronizedMap(new HashMap())）棋弥，ConcurrentHashMap 擁有更高的并發(fā)性。在 HashTable 和由同步包裝器包裝的 HashMap 中诚欠，使用一個(gè)全局的鎖來同步不同線程間的并發(fā)訪問顽染。同一時(shí)間點(diǎn)，只能有一個(gè)線程持有鎖轰绵，也就是說在同一時(shí)間點(diǎn)粉寞，只能有一個(gè)線程能訪問容器。這雖然保證多線程間的安全并發(fā)訪問藏澳，但同時(shí)也導(dǎo)致對容器的訪問變成串行化的了仁锯。
ConcurrentHashMap 的高并發(fā)性主要來自于三個(gè)方面：
用分離鎖實(shí)現(xiàn)多個(gè)線程間的更深層次的共享訪問。
用 HashEntery 對象的不變性來降低執(zhí)行讀操作的線程在遍歷鏈表期間對加鎖的需求翔悠。
通過對同一個(gè) Volatile 變量的寫 / 讀訪問业崖，協(xié)調(diào)不同線程間讀 / 寫操作的內(nèi)存可見性。

使用分離鎖蓄愁，減小了請求 同一個(gè)鎖的頻率双炕。
通過 HashEntery 對象的不變性及對同一個(gè) Volatile 變量的讀 / 寫來協(xié)調(diào)內(nèi)存可見性，使得 讀操作大多數(shù)時(shí)候不需要加鎖就能成功獲取到需要的值撮抓。由于散列映射表在實(shí)際應(yīng)用中大多數(shù)操作都是成功的 讀操作妇斤，所以 2 和 3 既可以減少請求同一個(gè)鎖的頻率，也可以有效減少持有鎖的時(shí)間丹拯。通過減小請求同一個(gè)鎖的頻率和盡量減少持有鎖的時(shí)間 站超，使得 ConcurrentHashMap 的并發(fā)性相對于 HashTable 和用同步包裝器包裝的 HashMap有了質(zhì)的提高。

推薦文章：https://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/