歡迎光臨
每天分享高質量文章

Java 經典面試題:為什麼 ConcurrentHashMap 的讀操作不需要加鎖?

  • ConcurrentHashMap的簡介
  • get操作原始碼
  • volatile登場
  • 是加在陣列上的volatile嗎?
  • 用volatile修飾的Node
  • 總結

我們知道,ConcurrentHashmap(1.8)這個併發集合框架是執行緒安全的,當你看到原始碼的get操作時,會發現get操作全程是沒有加任何鎖的,這也是這篇博文討論的問題——為什麼它不需要加鎖呢?

ConcurrentHashMap的簡介

我想有基礎的同學知道在jdk1.7中是採用Segment + HashEntry + ReentrantLock的方式進行實現的,而1.8中放棄了Segment臃腫的設計,取而代之的是採用Node + CAS + Synchronized來保證併發安全進行實現。

  • JDK1.8的實現降低鎖的粒度,JDK1.7版本鎖的粒度是基於Segment的,包含多個HashEntry,而JDK1.8鎖的粒度就是HashEntry(首節點)
  • JDK1.8版本的資料結構變得更加簡單,使得操作也更加清晰流暢,因為已經使用synchronized來進行同步,所以不需要分段鎖的概念,也就不需要Segment這種資料結構了,由於粒度的降低,實現的複雜度也增加了
  • JDK1.8使用紅黑樹來最佳化連結串列,基於長度很長的連結串列的遍歷是一個很漫長的過程,而紅黑樹的遍歷效率是很快的,代替一定閾值的連結串列,這樣形成一個最佳拍檔
img

get操作原始碼

  • 首先計算hash值,定位到該table索引位置,如果是首節點符合就傳回
  • 如果遇到擴容的時候,會呼叫標誌正在擴容節點ForwardingNode的find方法,查詢該節點,匹配就傳回
  • 以上都不符合的話,就往下遍歷節點,匹配就傳回,否則最後就傳回null
//會發現原始碼中沒有一處加了鎖
public V get(Object key) {
    Node[] tab; Node e, p; int n, eh; K ek;
    int h = spread(key.hashCode()); //計算hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {//讀取首節點的Node元素
        if ((eh = e.hash) == h) { //如果該節點就是首節點就傳回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值為負值表示正在擴容,這個時候查的是ForwardingNode的find方法來定位到nextTable來
        //eh=-1,說明該節點是一個ForwardingNode,正在遷移,此時呼叫ForwardingNode的find方法去nextTable裡找。
        //eh=-2,說明該節點是一個TreeBin,此時呼叫TreeBin的find方法遍歷紅黑樹,由於紅黑樹有可能正在旋轉變色,所以find裡會有讀寫鎖。
        //eh>=0,說明該節點下掛的是一個連結串列,直接遍歷該連結串列即可。
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首節點也不是ForwardingNode,那就往下遍歷
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

get沒有加鎖的話,ConcurrentHashMap是如何保證讀到的資料不是臟資料的呢?

volatile登場

對於可見性,Java提供了volatile關鍵字來保證可見性、有序性。但不保證原子性。

普通的共享變數不能保證可見性,因為普通共享變數被修改之後,什麼時候被寫入主存是不確定的,當其他執行緒去讀取時,此時記憶體中可能還是原來的舊值,因此無法保證可見性。

  • volatile關鍵字對於基本型別的修改可以在隨後對多個執行緒的讀保持一致,但是對於取用型別如陣列,物體bean,僅僅保證取用的可見性,但並不保證取用內容的可見性。。
  • 禁止進行指令重排序。

背景:為了提高處理速度,處理器不直接和記憶體進行通訊,而是先將系統記憶體的資料讀到內部快取(L1,L2或其他)後再進行操作,但操作完不知道何時會寫到記憶體。

  • 如果對宣告了volatile的變數進行寫操作,JVM就會向處理器傳送一條指令,將這個變數所在快取行的資料寫回到系統記憶體。但是,就算寫回到記憶體,如果其他處理器快取的值還是舊的,再執行計算操作就會有問題。
  • 在多處理器下,為了保證各個處理器的快取是一致的,就會實現快取一致性協議,當某個CPU在寫資料時,如果發現操作的變數是共享變數,則會通知其他CPU告知該變數的快取行是無效的,因此其他CPU在讀取該變數時,發現其無效會重新從主存中載入資料。
img

總結下來:

第一:使用volatile關鍵字會強制將修改的值立即寫入主存;

第二:使用volatile關鍵字的話,當執行緒2進行修改時,會導致執行緒1的工作記憶體中快取變數的快取行無效(反映到硬體層的話,就是CPU的L1或者L2快取中對應的快取行無效);

第三:由於執行緒1的工作記憶體中快取變數的快取行無效,所以執行緒1再次讀取變數的值時會去主存讀取。

是加在陣列上的volatile嗎?

/**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
    transient volatile Node[] table;

我們知道volatile可以修飾陣列的,只是意思和它錶面上看起來的樣子不同。舉個慄子,volatile int array[10]是指array的地址是volatile的而不是陣列元素的值是volatile的.

用volatile修飾的Node

get操作可以無鎖是由於Node的元素val和指標next是用volatile修飾的,在多執行緒環境下執行緒A修改結點的val或者新增節點的時候是對執行緒B可見的。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到這些都用了volatile修飾
    volatile V val;
    volatile Node next;

    Node(int hash, K key, V val, Node next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    /**
     * Virtualized support for map.get(); overridden in subclasses.
     */
    Node find(int h, Object k) {
        Node 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;
    }
}

既然volatile修飾陣列對get操作沒有效果那加在陣列上的volatile的目的是什麼呢?

其實就是為了使得Node陣列在擴容的時候對其他執行緒具有可見性而加的volatile

總結

  • 在1.8中ConcurrentHashMap的get操作全程不需要加鎖,這也是它比其他併發集合比如hashtable、用Collections.synchronizedMap()包裝的hashmap;安全效率高的原因之一。
  • get操作全程不需要加鎖是因為Node的成員val是用volatile修飾的和陣列用volatile修飾沒有關係。
  • 陣列用volatile修飾主要是保證在陣列擴容的時候保證可見性。
已同步到看一看
贊(0)

分享創造快樂