如何理解Java 容器中并發容器的源碼分析

這期內容當中小編將會給大家帶來有關如何理解Java 容器中并發容器的源碼分析，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

如果沒有特別說明，以下源碼分析基于 JDK 1.8。

CopyOnWriteArrayList

1.讀寫分離

寫操作在一個復制的數組上進行，讀操作還是在原始數組中進行，讀寫分離，互不影響。

寫操作需要加鎖，防止并發寫入時導致寫入數據丟失。

寫操作結束之后需要把原始數組指向新的復制數組。

public Boolean add(E e) {
    //加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // newElements 是一個復制的數組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        // 寫操作在一個復制的數組上進行
        setArray(newElements);
        return true;
    }
    finally {
        lock.unlock();
    }
}
final void setArray(Object[] a) {
    array = a;
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    //讀取操作仍然在原始的數組中
    return (E) a[index];
}

2.適用場景

CopyOnWriteArrayList 在寫操作的同時允許讀操作，大大提高了讀操作的性能，很適合讀多寫少的應用場景。

CopyOnWriteArrayList 有其缺陷：

• 內存占用：在寫操作時需要復制一個新的數組，使得內存占用為原來的兩倍左右；

• 數據不一致：讀操作不能讀取實時性的數據，因為部分寫操作的數據還未同步到讀數組中。

所以 CopyOnWriteArrayList 不適合內存敏感以及對實時性要求很高的場景。

二、ConcurrentHashMap

1. 存儲結構

static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;
}

ConcurrentHashMap 和 HashMap 實現上類似，最主要的差別是 ConcurrentHashMap 采用了分段鎖（Segment），每個分段鎖維護著幾個桶（HashEntry），多個線程可以同時訪問不同分段鎖上的桶， 從而使其并發度更高（并發度就是 Segment 的個數）。

Segment 繼承自 ReentrantLock。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    static final int MAX_SCAN_RETRIES =
            Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
    transient volatile HashEntry<K,V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
}

final Segment<K,V>[] segments;

默認的并發級別為 16，也就是說默認創建 16 個 Segment。

static final int DEFAULT_CONCURRENCY_LEVEL = 16;

2. size 操作
每個 Segment 維護了一個 count 變量來統計該 Segment 中的鍵值對個數。

/**
 * The number of elements. Accessed only either within locks
 * or among other volatile reads that maintain visibility.
 */
transient int count;

在執行 size 操作時，需要遍歷所有 Segment 然后把 count 累計起來。

ConcurrentHashMap 在執行 size 操作時先嘗試不加鎖，如果連續兩次不加鎖操作得到的結果一致，那么可以認為這個結果是正確的。

嘗試次數使用 RETRIES_BEFORE_LOCK 定義，該值為 2，retries 初始值為 -1，因此嘗試次數為 3。

如果嘗試的次數超過 3 次，就需要對每個 Segment 加鎖。

/**
 * Number of unsynchronized retries in size and containsValue
 * methods before resorting to locking. This is used to avoid
 * unbounded retries if tables undergo continuous modification
 * which would make it impossible to obtain an accurate result.
 */
static final int RETRIES_BEFORE_LOCK = 2;
public int size() {
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    final Segment<K,V>[] segments = this.segments;
    int size;
    Boolean overflow;
    // true if size overflows 32 bits
    long sum;
    // sum of modCounts
    long last = 0L;
    // previous sum
    int retries = -1;
    // first iteration isn't retry
    try {
        for (;;) {
            // 超過嘗試次數，則對每個 Segment 加鎖
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                                    ensureSegment(j).lock();
                // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                                            overflow = true;
                }
            }
            // 連續兩次得到的結果一致，則認為這個結果是正確的
            if (sum == last)
                            break;
            last = sum;
        }
    }
    finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                            segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

3. JDK 1.8 的改動

ConcurrentHashMap 取消了 Segment 分段鎖。

JDK 1.8 使用 CAS 操作來支持更高的并發度，在 CAS 操作失敗時使用內置鎖 synchronized。

數據結構與HashMap 1.8 的結構類似，數組+鏈表 / 紅黑二叉樹（鏈表長度 > 8 時，轉換為紅黑樹 ）。synchronized 只鎖定當前鏈表或紅黑二叉樹的首節點，這樣只要 Hash 值不沖突，就不會產生并發。

4. JDK 1.8 中的 put 方法

①. hash 算法

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

②. 定位索引位置

i = (n - 1) & hash

③. 獲取 table 中對應索引的元素 f

f = tabAt(tab, i = (n - 1) & hash
// Unsafe.getObjectVolatile 獲取 f
// 因為可以直接指定內存中的數據，保證了每次拿到的數據都是新的
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}Copy to clipboardErrorCopied

④. 如果 f 是 null，說明 table 中是第一次插入數據，利用

• 如果 CAS 成功，說明 Node 節點插入成功

• 如果 CAS 失敗，說明有其他線程提前插入了節點，自旋重新嘗試在該位置插入 Node

⑤. 其余情況把新的 Node 節點按鏈表或紅黑樹的方式插入到合適位置，這個過程采用內置鎖實現并發。

5. 和 Hashtable 的區別

①. 底層數據結構：

• JDK1.7 的ConcurrentHashMap底層采用分段的數組+鏈表實現， JDK1.8 的ConcurrentHashMap底層采用的數據結構與JDK1.8 的HashMap的結構一樣，數組+鏈表/紅黑二叉樹。

• Hashtable和JDK1.8 之前的HashMap的底層數據結構類似都是采用數組+鏈表的形式， 數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的。

②. 實現線程安全的方式

• JDK1.7的ConcurrentHashMap（分段鎖）對整個桶數組進行了分割分段(Segment)， 每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高并發訪問度。 JDK 1.8 采用數組+鏈表/紅黑二叉樹的數據結構來實現，并發控制使用synchronized和CAS來操作。

• Hashtable:使用 synchronized 來保證線程安全，效率非常低下。 當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態， 如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈。

上述就是小編為大家分享的如何理解Java 容器中并發容器的源碼分析了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。