JDK1.7保證線程安全

ConcurrentHashMap在JDK 1.7和JDK 1.8版本保證線程安全及其底層數(shù)據(jù)結(jié)構(gòu)是不一樣的，這一塊是面試中的重點，接下來詳細(xì)介紹一下它們。

在JDK 1.7中，ConcurrentHashMap采用了分段鎖（Segment）的設(shè)計來保證線程安全。下面我們將通過詳細(xì)解讀其底層源碼，來介紹其線程安全實現(xiàn)原理。

ConcurrentHashMap的主要類是Segment。每個Segment是一個獨(dú)立的鎖，并且維護(hù)著一個HashEntry數(shù)組。HashEntry是鏈表節(jié)點，存儲了鍵值對。

首先，我們來看一下ConcurrentHashMap的基本數(shù)據(jù)結(jié)構(gòu)：

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;
    }
}
static final class Segment<K, V> extends ReentrantLock implements Serializable {
    static final float LOAD_FACTOR = 0.75f;
    transient volatile HashEntry<K, V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
}

每個Segment都是一個繼承自ReentrantLock的可重入鎖，具備獨(dú)立的線程安全性。table是Segment內(nèi)部的HashEntry數(shù)組，用于存儲鍵值對。count表示當(dāng)前Segment中的元素數(shù)量，modCount用于記錄修改次數(shù)，threshold表示擴(kuò)容的閾值，loadFactor表示加載因子。

接下來，我們看一下ConcurrentHashMap的put操作：

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key.hashCode());
    int segmentIndex = getSegmentIndex(hash);
    return segments[segmentIndex].put(key, hash, value, false);
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock(); // 獲取當(dāng)前Segment的鎖
    try {
        int c = count;
        if (c++ > threshold) // 判斷是否需要擴(kuò)容
            rehash();
        HashEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashEntry<K, V> first = tab[index];
        HashEntry<K, V> e = first;
        while (e != null && (e.hash != hash || !key.equals(e.key))) 
            e = e.next;
        V oldValue;
        if (e != null) { // 鍵存在，更新值
            oldValue = e.value;
            if (!onlyIfAbsent)
                e.value = value;
        } else { // 鍵不存在，創(chuàng)建新節(jié)點并添加到鏈表頭部
            oldValue = null;
            ++modCount;
            tab[index] = new HashEntry<K, V>(hash, key, value, first);
            count = c; // 更新元素數(shù)量
        }
        return oldValue;
    } finally {
        unlock(); // 釋放當(dāng)前Segment的鎖
    }
}

在put操作中，首先通過hash函數(shù)計算鍵的散列值hash，然后根據(jù)散列值獲取對應(yīng)的Segment。接著，通過Segment的鎖保證了當(dāng)前操作的線程安全。

在獲取到Segment的鎖之后，首先判斷當(dāng)前Segment中的元素數(shù)量count是否超過了閾值threshold，如果超過了則進(jìn)行擴(kuò)容。然后通過散列值和數(shù)組長度計算出鍵對應(yīng)的索引位置index，并從對應(yīng)的鏈表開始遍歷，尋找是否存在相同的鍵。

如果找到了相同的鍵，則更新對應(yīng)的值；如果沒有找到相同的鍵，則創(chuàng)建一個新的HashEntry節(jié)點，并將其添加到鏈表的頭部。

在完成操作后，釋放Segment的鎖。

通過分段鎖的設(shè)計，JDK 1.7的ConcurrentHashMap允許多個線程同時操作不同的Segment，從而提高了并發(fā)性能。雖然在高并發(fā)情況下仍可能存在競爭問題，但通過細(xì)粒度的鎖設(shè)計，可以減少鎖競爭的概率，提升整體性能。

JDK1.8保證線程安全

在JDK 1.8中，ConcurrentHashMap進(jìn)行了重大改進(jìn)，采用了更加高效的并發(fā)控制機(jī)制來保證線程安全。相較于JDK 1.7的分段鎖設(shè)計，JDK 1.8引入了基于CAS（Compare and Swap）操作和鏈表/紅黑樹結(jié)構(gòu)的鎖機(jī)制以及其他優(yōu)化，大大提高了并發(fā)性能。

底層數(shù)據(jù)結(jié)構(gòu)：

JDK 1.8中的ConcurrentHashMap采用了數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)。具體來說，它將整個哈希桶（Hash Bucket）劃分為若干個節(jié)點（Node）。每個節(jié)點代表一個存儲鍵值對的單元，可以是鏈表節(jié)點（普通節(jié)點）或紅黑樹節(jié)點（樹節(jié)點），這取決于節(jié)點內(nèi)的鍵值對數(shù)量是否達(dá)到閾值。使用紅黑樹結(jié)構(gòu)可以提高查找、插入、刪除等操作的效率。

主要類和數(shù)據(jù)結(jié)構(gòu)如下：

static final class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    volatile V value;
    volatile Node<K, V> next;
    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
static final class TreeNode<K, V> extends Node<K, V> {
    TreeNode(int hash, K key, V value, Node<K, V> next) {
        super(hash, key, value, next);
    }
    // 省略了紅黑樹相關(guān)的操作代碼
}
static final class ConcurrentHashMap<K, V> {
    transient volatile Node<K, V>[] table;
    transient volatile int sizeCtl;
    transient volatile int baseCount;
    transient volatile int modCount;
}

ConcurrentHashMap的線程安全實現(xiàn)原理：

初始狀態(tài)：在初始狀態(tài)下，table為null，sizeCtl為0。當(dāng)?shù)谝粋€元素被插入時，會根據(jù)并發(fā)級別（Concurrency Level）計算出數(shù)組的長度，并使用CAS操作將數(shù)組初始化為對應(yīng)長度的桶。

插入操作

put方法：當(dāng)進(jìn)行插入操作時，ConcurrentHashMap首先計算鍵的散列值，然后根據(jù)散列值和數(shù)組長度計算出對應(yīng)的桶位置。接著使用CAS操作嘗試插入新節(jié)點，如果成功則插入完成；如果失敗，則進(jìn)入下一步。

resize方法：插入節(jié)點時，若發(fā)現(xiàn)鏈表中的節(jié)點數(shù)量已經(jīng)達(dá)到閾值（默認(rèn)為8），則將鏈表轉(zhuǎn)化為紅黑樹，提高查找、插入、刪除等操作的效率。在轉(zhuǎn)化過程中，利用synchronized鎖住鏈表或紅黑樹所在的桶，并進(jìn)行相應(yīng)的操作。

forwardTable方法：若節(jié)點數(shù)量超過閾值（默認(rèn)為64）且table未被初始化，則使用CAS操作將table指向擴(kuò)容后的桶數(shù)組，并根據(jù)需要將鏈表或紅黑樹進(jìn)行分割，以減小線程之間的沖突。

查詢操作

get方法：當(dāng)進(jìn)行查詢操作時，首先計算鍵的散列值，然后根據(jù)散列值和數(shù)組長度計算出對應(yīng)的桶位置。接著從桶位置的鏈表或紅黑樹中查找對應(yīng)的節(jié)點。

其他操作

remove方法：當(dāng)進(jìn)行刪除操作時，首先計算鍵的散列值，然后根據(jù)散列值和數(shù)組長度計算出對應(yīng)的桶位置。接著使用synchronized鎖住桶，并進(jìn)行相應(yīng)的操作。

綜上所述，JDK 1.8的ConcurrentHashMap通過CAS操作、鎖機(jī)制（synchronized）以及鏈表/紅黑樹結(jié)構(gòu)來保證線程安全。CAS操作用于插入新節(jié)點和初始化桶數(shù)組，鎖機(jī)制用于鏈表/紅黑樹的轉(zhuǎn)化和刪除操作，鏈表/紅黑樹結(jié)構(gòu)用于提高查找、插入、刪除操作的效率。這些優(yōu)化措施使得ConcurrentHashMap在高并發(fā)環(huán)境下具有較好的性能表現(xiàn)。

JDK1.7和JDK1.8對比總結(jié)

在JDK 1.7和JDK 1.8中，ConcurrentHashMap有以下主要區(qū)別：

JDK 1.7中的實現(xiàn)方式：

• JDK 1.7中的ConcurrentHashMap使用分段鎖（Segment Locking）的設(shè)計。它將整個哈希表分成多個段（Segment），每個段都有自己的鎖。這樣可以降低并發(fā)操作時鎖的爭用范圍，提高并發(fā)性能。
• 每個段中包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結(jié)構(gòu)，用于解決哈希沖突。
• 由于每個段都有自己的鎖，不同的線程可以同時訪問不同的段，從而提高了并發(fā)度。

JDK 1.8中的改進(jìn)：

JDK 1.8中的ConcurrentHashMap采用了CAS操作、鎖機(jī)制以及鏈表/紅黑樹結(jié)構(gòu)的改進(jìn)。

• 數(shù)據(jù)結(jié)構(gòu)改進(jìn)：JDK 1.8中使用數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)，代替了JDK 1.7中的段+鏈表結(jié)構(gòu)。數(shù)組用于存儲桶，鏈表/紅黑樹用于解決哈希沖突。
• CAS操作：JDK 1.8使用CAS（Compare and Swap）操作來插入新節(jié)點和初始化桶數(shù)組。CAS操作是一種樂觀鎖機(jī)制，通過原子操作比較并交換的方式進(jìn)行，并發(fā)安全性更好。
• 鎖的改進(jìn)：JDK 1.8中引入了基于CAS操作和鏈表/紅黑樹結(jié)構(gòu)的鎖機(jī)制。對于鏈表/紅黑樹上的操作，使用synchronized鎖住桶，以保證操作的原子性。
• 鏈表轉(zhuǎn)化為紅黑樹：JDK 1.8在插入操作時，當(dāng)鏈表中的節(jié)點數(shù)量達(dá)到一定閾值時，會將鏈表轉(zhuǎn)化為紅黑樹，提高查找、插入、刪除等操作的效率。
• resize操作的改進(jìn)：JDK 1.8中的resize操作（擴(kuò)容）采用了分割鏈表/紅黑樹的方式，減小了線程沖突的概率。

總的來說，JDK 1.8中的ConcurrentHashMap在數(shù)據(jù)結(jié)構(gòu)、CAS操作、鎖機(jī)制和鏈表/紅黑樹結(jié)構(gòu)等方面進(jìn)行了改進(jìn)，相較于JDK 1.7，性能更好且并發(fā)度更高。這些改進(jìn)使得JDK 1.8中的ConcurrentHashMap在高并發(fā)環(huán)境下表現(xiàn)更優(yōu)秀。

到此這篇關(guān)于源碼分析ConcurrentHashMap如何保證線程安全的文章就介紹到這了,更多相關(guān)ConcurrentHashMap保證線程安全內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論