[TOC]

一、頂部注釋分析

1.1 數(shù)據(jù)結構

1.1.1 JDK1.7實現(xiàn)

• 在 JDK1.7中，ConcurrentHashMap 通過“鎖分段”來實現(xiàn)線程安全
• 通過將哈希表分成許多片段 (segments) ，每一個片段 (table) 都類似于 HashMap，有一個HashEntry 數(shù)組，數(shù)組的每項又是 HashEntry 組成的鏈表
• Segment 繼承了ReentrantLock，所以 Segment 本質上是一個可重入的互斥鎖
• 在訪問某個鍵值對時，需要先獲取該鍵值對所在的 segment 上的鎖，獲取鎖后，其他線程就不能訪問此segment了，但可以訪問其他的segment，從而避免了把整個哈希表都鎖住

image

1.1.2 JDK1.8實現(xiàn)

• JDK1.8中放棄了鎖分段的方式，結構和 HashMap 相同，也是數(shù)組+鏈表+紅黑樹的方式
• 但是通過 CAS 和部分加鎖的方式來實現(xiàn)線程安全

image

1.2 從注釋中得到的結論

• A hash table supporting full concurrency of retrievals and high expected concurrency for updates：ConcurrentHashMap 是一個支持高并發(fā)檢索和更新的哈希表
• ConcurrentHashMap 是線程安全的，但不是靠阻塞和封鎖整個哈希表來實現(xiàn)的
• get 操作不是阻塞的，因此可以和一些更新操作并行，如 put 和 remove
• 一些和統(tǒng)計相關的方法，如 size、isEmpty、containsValue 最好在單線程環(huán)境下使用，在多線程環(huán)境下只能反應一個暫時的狀態(tài)，可用于估計或監(jiān)視，但可能無法返回準確值，除非此時沒有發(fā)生并發(fā)的修改
• 當散列碰撞過多時，ConcurrentHashMap 會動態(tài)增長。但是擴容非常消耗資源，因此最好提前估計好容量
• ConcurrentHashMap 不允許 key 或 value 為 null

二、源碼分析

2.1 定義

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> 
        implements ConcurrentMap<K,V>, Serializable

• ConcurrentHashMap<K,V>：HashMap 是以 key-value 形式存儲數(shù)據(jù)的
• extends AbstractMap<K,V>：繼承自 AbstractMap，大大減少了實現(xiàn) Map 接口時需要的工作量
• implements ConcurrentMap<K,V>：實現(xiàn)了 ConcurrentMap 接口，一個提供線程安全性和原子性保證的 Map
• implements Serializable：可以序列化

2.2 字段

// 哈希表數(shù)組，用volatile修飾，大小總是為2的整數(shù)次冪
transient volatile Node<K,V>[] table;

// 基礎計數(shù)器，通過CAS來更新
 private transient volatile long baseCount;
 
/** 
 * 用于控制初始化和擴容
 * 當為負數(shù)時，表示正在進行初始化或擴容操作：
 *    -1 表示正在初始化
 *    -N 表示有N-1個線程正在進行擴容操作
 * 
 * 默認值為0
 * 當初始化之后，保存下一次的擴容值
 */
private transient volatile int sizeCtl;

// 用于計算size
private transient volatile CounterCell[] counterCells

2.3 Node靜態(tài)內部類

• 與 HashMap 中的 Node 相似，但有如下區(qū)別：
  1. 對 value 和 next 屬性設置了 volatile 同步鎖；
  2. 不允許調用 setValue 方法直接改變 Node 的 value，否則會拋出異常
  3. 增加了 find 方法用于輔助 get 方法

static class Node<K,V> implements Map.Entry<K,V> 
{
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) 
    {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
    
    public final V setValue(V value) 
    {
        throw new UnsupportedOperationException();
    }
    
    Node<K,V> find(int h, Object k) 
    {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h && 
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

2.4 構造方法

1. public ConcurrentHashMap()：構建一個空ConcurrentHashMap，默認容量為16
2. public ConcurrentHashMap(int initialCapacity)：構建一個空ConcurrentHashMap并根據(jù)參數(shù)設置下次擴容值
3. public ConcurrentHashMap(Map<? extends K, ? extends V> m)：根據(jù)給定的 Map 進行構建
4. public ConcurrentHashMap(int initialCapacity, float loadFactor)：根據(jù)給定的參數(shù)設置下次擴容值和加載因子，默認并行度為1
5. public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)：根據(jù)給定的參數(shù)設置下次擴容值和加載因子，且容量至少為估計的線程數(shù) concurrencyLevel

2.5 put 操作

2.5.1 put 方法大致步驟

1. 計算 key 的哈希值；
2. 如果 table 數(shù)組為空，則先進行初始化 (2.5.2節(jié))；
3. 根據(jù) hash 值計算出 key 在表中所處的位置，即 (n - 1) & hash：

• 如果該位置沒有值 ，則直接放入，且不需要加鎖；
• 如果插入位置是連接點，說明正在進行擴容，則幫助當前線程擴容；
• 否則加鎖，然后根據(jù)鏈表或樹結構遍歷查找 key 值，找到則進行更新，否則新增節(jié)點插入；

4. 與 HashMap 類似，若鏈表長度超過閾值，則轉為紅黑樹；
5. 如果操作3中執(zhí)行的是替換操作，返回被替換的value；
6. 否則說明節(jié)點是被新插入的，因此將元素數(shù)量加1

整個過程中只有3中的第三步需要加鎖，從而提高并行性能

2.5.2 初始化 table 數(shù)組

• 調用 ConcurrentHashMap 的構造方法僅僅只是設置了一些參數(shù)，而整個 table 的初始化是在向其中插入元素的時候發(fā)生的，例如 put 方法
• 初始化方法主要應用了關鍵屬性 sizeCtl，如果 sizeCtl < 0，表示其他線程正在進行初始化，就放棄操作，從而保證只讓一個線程對 table 進行初始化
• 如果獲得了初始化權限，就先用 CAS 方法將 sizeCtl 置為-1，防止后續(xù)其他線程進入
• 初始化完成后，將 sizeCtl 的值設為n - (n >>> 2))，即 0.75 × n

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); // 0.75 × n
                }   
            } 
            finally 
            {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

2.6 get 操作

• get 方法沒有進行加鎖，其大致步驟為：
  1. 計算 key 的哈希值；
  2. 根據(jù)哈希值查找節(jié)點位置；
  3. 如果節(jié)點直接在桶的頭節(jié)點上，則直接返回；
  4. 否則說明有碰撞，根據(jù)樹形結構或鏈表結構使用不同的方法繼續(xù)查找；
  5. 如果找到則返回對應值，否則返回 null

// 從源碼中可以看出，get方法沒有加鎖

public V get(Object key) 
{
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) 
    {
        if ((eh = e.hash) == h) 
        {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
            return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) 
        {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}