ConcurrentHashMap源碼分析

前言

JDK中的Hashtable是一個(gè)線程安全的K-V形式的容器，它實(shí)現(xiàn)線程安全的原理十分簡(jiǎn)單恩脂，就是在所有涉及對(duì)該哈希表操作的方法上都加上了synchronized關(guān)鍵字，進(jìn)行加鎖操作趣斤。這么做實(shí)現(xiàn)了線程安全俩块，但是效率非常低。

//通過synchronized在每次進(jìn)入方法時(shí)獲取hashmap的鎖浓领，高并發(fā)情況下會(huì)出現(xiàn)爭(zhēng)用沖突
public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

ConcurrentHashMap使用了分段鎖的設(shè)計(jì)玉凯，只有在每個(gè)段上才會(huì)存在并發(fā)爭(zhēng)用，不同的段之間不存在鎖的競(jìng)爭(zhēng)联贩，提高了該hashmap的并發(fā)訪問效率漫仆。但也是由于ConcurrentHashMap的分段設(shè)計(jì)，某些需要掃描所有段的操作如size()等方法實(shí)現(xiàn)上比較復(fù)雜撑蒜，并且并不能保證強(qiáng)一致性歹啼，這個(gè)在某些情況下需要注意。由于ConcurrentHashMap在各個(gè)JDK版本下的實(shí)現(xiàn)是有區(qū)別的座菠，特說(shuō)明本文基于jdk1.7源碼狸眼，我們下面一起通過其源碼來(lái)分析它的實(shí)現(xiàn)原理。

ConcurrentHashMap的組成

查看源碼浴滴，我們可以通過ConcurrentHashMap的成員變量拓萌，了解該數(shù)據(jù)結(jié)構(gòu)的基本組成。

    final int segmentMask;//作為查找segments的掩碼升略，前幾個(gè)bit用來(lái)選擇segment

    final int segmentShift;

    final Segment<K,V>[] segments;//每個(gè)segment都是一個(gè)hashtable

ConcurrentHashMap內(nèi)部有一個(gè)segments數(shù)組微王，每個(gè)segment都是一個(gè)hashtable ，由于Segment繼承自ReentrantLock 品嚣，因此Segment本身就是鎖炕倘，對(duì)每個(gè)Segment的加鎖就是調(diào)用自身的acquire()方法。Segment的基本組成如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
        transient volatile HashEntry<K,V>[] table;//存入ConcurrentHashMap的k-v數(shù)據(jù)都存在這里
        transient int count;//該segment內(nèi)的HashEntry計(jì)數(shù)(如put/remove/replace/clear)
        transient int modCount;//對(duì)該segment的修改操作數(shù)量
        final float loadFactor;//hashtable的負(fù)載因子
. . . . . . . . .
}

HashEntry是最終存儲(chǔ)每一對(duì)k-v的最底層數(shù)據(jù)結(jié)構(gòu)翰撑，它的結(jié)構(gòu)為：

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

value為volatile罩旋，在多線程環(huán)境下可以保持可見性，因此可以不加鎖直接讀取眶诈。
ConcurrentHashMap的整體數(shù)據(jù)結(jié)構(gòu)如圖