JDK1.7保證線(xiàn)程安全

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

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

ConcurrentHashMap的主要類(lèi)是Segment。每個(gè)Segment是一個(gè)獨(dú)立的鎖，并且維護(hù)著一個(gè)HashEntry數(shù)組。HashEntry是鏈表節(jié)點(diǎn)，存儲(chǔ)了鍵值對(duì)。

首先，我們來(lái)看一下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;
}

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

接下來(lái)，我們看一下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é)點(diǎn)并添加到鏈表頭部
            oldValue = null;
            ++modCount;
            tab[index] = new HashEntry<K, V>(hash, key, value, first);
            count = c; // 更新元素?cái)?shù)量
        }
        return oldValue;
    } finally {
        unlock(); // 釋放當(dāng)前Segment的鎖
    }
}

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

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

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

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

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

JDK1.8保證線(xiàn)程安全

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

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

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

主要類(lèi)和數(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);
    }
    // 省略了紅黑樹(shù)相關(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)程安全實(shí)現(xiàn)原理：

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

插入操作

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

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

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

查詢(xún)操作

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

其他操作

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

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

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

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

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

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

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

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

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

總的來(lái)說(shuō)，JDK 1.8中的ConcurrentHashMap在數(shù)據(jù)結(jié)構(gòu)、CAS操作、鎖機(jī)制和鏈表/紅黑樹(shù)結(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如何保證線(xiàn)程安全的文章就介紹到這了,更多相關(guān)ConcurrentHashMap保證線(xiàn)程安全內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論