国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > Java > 正文

Java集合類框架學習 5.2 —— ConcurrentHashMap(JDK1.7)

2019-11-06 07:08:53
字體:
來源:轉載
供稿:網友
以下內容,如有問題,煩請指出,謝謝!jdk1.7的ConcurrentHashMap整體設計、存儲結構、思路,和1.6的基本一樣,都是用代理給相應的Segment進行對應的操作。設計實現上一個比較大的改變就HashEntry的next指針不再是final的,改為volatile,并且用Unsafe提供的操作進行有序的延遲寫入(lazySet)。理解1.7的代碼,需要對sun.misc.Unsafe有基本的了解,可以看下這里,然后我下面也有說。零、主要改動1、jdk1.7開始,集合類大多使用懶初始化,也就是默認構造的集合類,底層的存儲結構使用盡量少的空間,等真正添加元素時才真正初始化。1.7的ConcurrentHashMap默認構造時只初始化 index = 0 的Segment,其余的都是put時初始化,另外會出現Segment = null的情況,需要多判斷下。2、大量使用 sun,misc.Unsafe 提供的底層操作方法,代替了一些實現比較簡單的方法,稍微強化了方法的在并發上功能(比如對普通變量,也能夠進行volatile讀寫),另外也帶來了一些效率的提升。3、修復1.6的一些小問題(具體看后面的代碼分析注釋)。一、基本性質跟1.6基本一樣,沒涉及這方面的修改。二、常量和變量1、常量

這塊因為Unsafe的引入,多了一些相關的常量。

static final int DEFAULT_INITIAL_CAPACITY = 16;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int DEFAULT_CONCURRENCY_LEVEL = 16;static final int MAXIMUM_CAPACITY = 1 << 30;static final int MAX_SEGMENTS = 1 << 16;static final int RETRIES_BEFORE_LOCK = 2;// 每個段的最小容量。段容量必須是2^n,最少是2能夠保證在初始化一個Segment后的第一次put時不會立即擴容// 1.6的Segment最小容量是1,第一次put就會用滿結合1.6的構造方法和Segment.put中擴容部分一起看static final int MIN_SEGMENT_TABLE_CAPACITY = 2;// 下面的全都是Unsafe有關的// Unsafe mechanicsPRivate static final sun.misc.Unsafe UNSAFE;// Segment數組的每個實例的內存結構中,存儲數組第一個元素的地址相對于該對象實例起始地址的偏移量// 此值和對象指針(對象引用)結合使用,可以得到數組首地址// java對象會有對象頭,數組對象還有length屬性,因此Java數組的第一個元素的地址不再是C語言中數組實例的首地址// 可以理解為C結構體中有個數組,求這個數組的第一個元素的地址相對結構體實例地址的偏移量private static final long SBASE;// Segment數組的每個元素在Segment實例的內存中占用的空間,基本類型就是基本類型的字節大小,引用類型存儲的是指針,具體根據系統環境確定// 相當于C語言中 *(p+1) 中這個1實際代表多少字節private static final int SSHIFT;// 同上面兩個private static final long TBASE;private static final int TSHIFT;// 下面幾個相當于C語言結構體中屬性相對實例地址的偏移量,知道起始地址、偏移量、變量類型,就能用 * 運算快速讀寫變量的值private static final long HASHSEED_OFFSET;private static final long SEGSHIFT_OFFSET;private static final long SEGMASK_OFFSET;private static final long SEGMENTS_OFFSET;static {    int ss, ts;    try {        UNSAFE = sun.misc.Unsafe.getUnsafe();        Class tc = HashEntry[].class;        Class sc = Segment[].class;        TBASE = UNSAFE.arrayBaSEOffset(tc);        SBASE = UNSAFE.arrayBaseOffset(sc);        ts = UNSAFE.arrayIndexScale(tc);        ss = UNSAFE.arrayIndexScale(sc);        HASHSEED_OFFSET = UNSAFE.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("hashSeed"));        SEGSHIFT_OFFSET = UNSAFE.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("segmentShift"));        SEGMASK_OFFSET = UNSAFE.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("segmentMask"));        SEGMENTS_OFFSET = UNSAFE.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("segments"));    } catch (Exception e) {        throw new Error(e);    }    if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)        throw new Error("data type scale not a power of two");    // 下面的是求 lb(ss),lb = log2,具體可以看下Integer.numberOfLeadingZeros的實現和注釋    // 這個方法求一個int二進制中從左邊開始最長的連續的0的數目(最左邊的符號位不算),因為ss是2^n,這里可以看做是求這個n    // 本人環境 Java(TM) SE Runtime Environment (build 1.8.0_111-b14) Java HotSpot(TM) 64-Bit Server VM (build 25.111-b14, mixed mode)    //     默認開啟指針壓縮,一個指針(引用)占用4字節時    // 那么ss = ts = 4,得到SSHIFT = TSHIFT = 2    // 下面兩個值主要是為了用位運算代替乘法提高效率    SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);    TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);}

關于偏移量有關的,可以用下面兩個C語言的例子了解下。這幾個偏移量只和Java虛擬機有關,一次程序運行過程中它們是確定的。

#include <stdio.h>#include <stdlib.h>int main(int argc, char *argv[]) {    int a[] = {0, 1, 2, 3, 4, 5}; /* 這里就用簡單的數組,實際比較像C結構體中有個數組類型的屬性 */    /* SBASE相當于數組首地址base */    /* 你可以把 Unsafe.arrayBaseOffset 看出是求數組首地址 base ,實際中更像是求一個結構體中某個類型為數組的成員變量的 0 下標的地址*/    int* base = a;    int x = base;    /* 指針的加減運算會特殊處理,這里的加1,實際上是加上 sizeof(int) */    /* SSHIFT相當于shift,是指針移動一個單元的實際字節偏移量,這里是一個int的字節大小,在我的環境64bit windows下是4字節 */    /* arrayIndexScale 可以看做是求 base + 1 中這個 1 的實際字節數,也就是 sizeof(實際類型) */    int y = base + 1;    int shift = y - x;    return 0;    /* ConcurrentHashMap源碼中的s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE),相當于就是 *(base + j),也就是讀取segments[j] */}
#include <stdio.h>#include <stdlib.h>#pragma pack(4) /* 4字節內存對齊,下面的struct不會有填充空間 */typedef struct chm {    int hashseed;    int segshift;    int segmask;    long long otherValue;    int* p;} s_chm;int main(int argc, char *argv[]) {    int a[] = {100, 101, 102, 103, 104, 105};    s_chm c;    long long x;    long long hashseed_offset, segshift_offset, segmask_offset, otherValue_offset, p_offset;    c.hashseed = 0;    c.segshift = 28;    c.segmask = 15;    c.p = a;    c.otherValue = 12;    s_chm* pC = &c;    x = pC;    /* 求偏移量,也就是內存地址之間的差,直觀但是不通用 */    /* 可以把 Unsafe.objectFieldOffset 看出是進行下面這種運算求得的值 */    hashseed_offset = (long long)&c.hashseed - (long long)&c;    segshift_offset = (long long)&c.segshift - (long long)&c;    segmask_offset = (long long)&c.segmask - (long long)&c;    otherValue_offset = (long long)&c.otherValue - (long long)&c;    p_offset = (long long)&c.p - (long long)&c;    printf("hashseed_offset = %d/n", hashseed_offset);     // hashseed_offset = 0    printf("segshift_offset = %d/n", segshift_offset);     // segshift_offset = 4    printf("segmask_offset = %d/n", segmask_offset);       // segmask_offset = 8    printf("otherValue_offset = %d/n", otherValue_offset); // otherValue_offset = 12    printf("p_offset = %d/n", p_offset);                   // p_offset = 20    /* 已知偏移量和實例的起始地址,就可以用 * 運算讀取變量的值,需要用強轉指明類型 */    /* Unsafe.getObjectVolatile/getObject(Object obj, long offset),中,obj == x == &c,offset就是offset */    /* Unsafe中這兩個方法主要的功能就相當于是C語言的 * 運算,getObject(Object obj, long offset)相當于 "p = obj + offset, return *p" */    printf("hashseed = %d/n", *(int*)(x + hashseed_offset));      // hashseed = 0    printf("segshift = %d/n", *(int*)(x + segshift_offset));      // segshift = 28    printf("segmask = %d/n", *(int*)(x + segmask_offset));        // segmask = 15    printf("otherValue = %d/n", *(long*)(x + otherValue_offset)); // otherValue = 12    printf("*p = %d/n", **(int**)(x + p_offset));                 // *p = 100,也就是a[0]    system("pause");    return 0;    /* Unsafe.putObject/putObjectVolatile(Object obj, long offset, Object value) 這幾個put方法,就相當于 "p = obj + offset, *(類型指針)(p) = value " */}2、變量一點點變化,1.7的HashMap中說了,hashseed不影響基本流程。
// 跟 jdk1.7 的HashMap一樣,會根據系統屬性生成一個 hashSeed,提高hash隨機性。// 不過Entry的hash值是不會變的,這一點跟1.6的一樣private transient final int hashSeed = randomHashSeed(this);final int segmentMask;final int segmentShift;final Segment<K,V>[] segments;transient Set<K> keySet;transient Set<Map.Entry<K,V>> entrySet;transient Collection<V> values;三、基本類
static final class HashEntry<K,V> {    final int hash; // hash是final的,1.7的HashMap中不是final的,用final對擴容比較友好    final K key;    volatile V value;    volatile HashEntry<K,V> next; // jdk1.7中next指針不再是final的,改為volatile,使用 setNext 方法(內部用Unsafe的提供的方法)更新    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {        this.hash = hash;        this.key = key;        this.value = value;        this.next = next;    }    // putOrderedObject,這個方法只有作用于volatile才有效,它能保證寫操作的之間的順序性,但是不保證能立馬被其他線程讀取到最新結果,是一種lazySet,效率比volatile高,但是只有volatile的“一半”的效果    // 普通的volatile保證寫操作的結果能立馬被其他線程看到,不論其他線程是讀操作還寫操作    // putOrderedObject能保證其他線程在寫操作時一定能看到這個方法對變量的改變,但是其他線程只是進行讀操作時,不一定能看到這個方法對變量的改變    final void setNext(HashEntry<K,V> n) {        UNSAFE.putOrderedObject(this, nextOffset, n);    }    // 初始化執行Unsafe有關的操作    static final sun.misc.Unsafe UNSAFE;    static final long nextOffset;    static {        try {            UNSAFE = sun.misc.Unsafe.getUnsafe();            Class k = HashEntry.class;            nextOffset = UNSAFE.objectFieldOffset                (k.getDeclaredField("next"));        } catch (Exception e) {            throw new Error(e);        }    }}jdk1.7的Segment
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;    Segment(float lf, int threshold, HashEntry<K,V>[] tab) {        this.loadFactor = lf;        this.threshold = threshold;        this.table = tab;    }    // jdk1.6中的 newArray、setTable 這兩個方法因為實現太簡單了,直接不用了    // jdk1.6中的 get、containsKey、containsValue 這幾個方法,因為都是讀操作,實現基本類似,用 Unsafe 提供的一些底層操作代替了    // jdk1.6中的 getFirst 雖然實現也很簡單,但還是用 Unsafe 提供的一些底層方法強化了這個操作,    //     保證了對數組元素的volatile讀取,1.6的只保證對整個數組的讀取是volatile    // jdk1.6中的 readValueUnderLock 在1.7中徹底去掉了        // 1.7多了個scanAndLockForPut的操作,也完善了put觸發擴容的機制(見1.6版本我在Segment.put中觸發擴容處寫的注釋),同時處理了超過最大容量的情況,其余的跟1.6差不多    final V put(K key, int hash, V value, boolean onlyIfAbsent) {        HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); // 看scanAndLockForPut方法的注釋        V oldValue;        try {            HashEntry<K,V>[] tab = table;            int index = (tab.length - 1) & hash;            HashEntry<K,V> first = entryAt(tab, index);            for (HashEntry<K,V> e = first;;) {                if (e != null) {                    K k;                    if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {                        oldValue = e.value;                        if (!onlyIfAbsent) {                            e.value = value;                            ++modCount; // 1.7的put相同的key(這時候相當于replace)時也會修改modCount了,1.6是不會的,能夠更大地保證containValue這個方法的準確性                        }                        break;                    }                    e = e.next;                }                else {                    if (node != null)                        node.setNext(first); // 嘗試添加在鏈表頭部                    else                        node = new HashEntry<K,V>(hash, key, value, first);                    int c = count + 1; // 先加1                    if (c > threshold && tab.length < MAXIMUM_CAPACITY) // 超過最大容量的情況,在put這里一并處理了                        rehash(node);                    else                        setEntryAt(tab, index, node); // 不擴容時,直接讓新節點成為頭節點                    ++modCount;                    count = c;                    oldValue = null;                    break;                }            }        } finally {            unlock();        }        return oldValue;    }    // 1.7的rehash方法帶有參數了,這個參數node就是要新put進去的node,新的rehash方法帶有部分put的功能    // 節點遷移的基本思路還是和1.6的一樣    @SuppressWarnings("unchecked")    private void rehash(HashEntry<K,V> node) {        HashEntry<K,V>[] oldTable = table;        int oldCapacity = oldTable.length;        int newCapacity = oldCapacity << 1;        threshold = (int)(newCapacity * loadFactor);        HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];        int sizeMask = newCapacity - 1;        for (int i = 0; i < oldCapacity ; i++) {            HashEntry<K,V> e = oldTable[i];            if (e != null) {                HashEntry<K,V> next = e.next;                int idx = e.hash & sizeMask;                if (next == null) //  Single node on list 只有一個節點,簡單處理                    newTable[idx] = e;                else { // Reuse consecutive sequence at same slot 最大地重用鏈表尾部的一段連續的節點(這些節點擴容后在新數組中的同一個hash桶中),并標記位置                    HashEntry<K,V> lastRun = e;                    int lastIdx = idx;                    for (HashEntry<K,V> last = next;                         last != null;                         last = last.next) {                        int k = last.hash & sizeMask;                        if (k != lastIdx) {                            lastIdx = k;                            lastRun = last;                        }                    }                    newTable[lastIdx] = lastRun;                    // Clone remaining nodes 對標記之前的不能重用的節點進行復制,再重新添加到新數組對應的hash桶中去                    for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {                        V v = p.value;                        int h = p.hash;                        int k = h & sizeMask;                        HashEntry<K,V> n = newTable[k];                        newTable[k] = new HashEntry<K,V>(h, p.key, v, n);                    }                }            }        }        int nodeIndex = node.hash & sizeMask; // add the new node 部分的put功能,把新節點添加到鏈表的最前面        node.setNext(newTable[nodeIndex]);        newTable[nodeIndex] = node;        table = newTable;    }    // 為put方法而編寫的,在嘗試獲取鎖的同時時進行一些準備工作的方法    // 獲取不到鎖時,會嘗試一定次數的準備工作,這個準備工作指的是“遍歷并預先創建要被添加的新節點,同時監測鏈表是否改變”    // 這樣有可能在獲取到鎖時新的要被put的節點已經創建了,可以在put時少做一些工作    // 準備工作中也會不斷地嘗試獲取鎖,超過最大準備工作嘗試次數就直接阻塞等待地獲取鎖    private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {        HashEntry<K,V> first = entryForHash(this, hash);        HashEntry<K,V> e = first;        HashEntry<K,V> node = null;        int retries = -1; // negative while locating node        while (!tryLock()) {            HashEntry<K,V> f; // to recheck first below            if (retries < 0) {                if (e == null) { // 這條鏈表上沒有“相等”的節點                    if (node == null) // speculatively create node 預先創建要被添加的新節點                        node = new HashEntry<K,V>(hash, key, value, null);                    retries = 0;  // 遍歷完都沒碰見“相等”,不再遍歷了,改為 嘗試直接獲取鎖,沒獲取到鎖時嘗試監測鏈表是否改變                }                else if (key.equals(e.key)) // 碰見“相等”,不再遍歷了,改為 嘗試直接獲取鎖,沒獲取到鎖時嘗試監測鏈表是否改變                    retries = 0;                else             // 遍歷鏈表                    e = e.next;            }            else if (++retries > MAX_SCAN_RETRIES) { // 超過最大的準備工作嘗試次數,放棄準備工作嘗試,直接阻塞等待地獲取鎖                lock();                break;            }            else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { // 間隔一次判斷是否有新節點添加進去                e = first = f; // re-traverse if entry changed 如果鏈表改變,就重新遍歷一次鏈表                retries = -1; // 重置次數            }        }        return node;    }    // 基本同scanAndLockForPut,但是更簡單些,只用遍歷鏈表并監測改變,不用創建新節點    private void scanAndLock(Object key, int hash) {        HashEntry<K,V> first = entryForHash(this, hash);        HashEntry<K,V> e = first;        int retries = -1;        while (!tryLock()) {            HashEntry<K,V> f;            if (retries < 0) {                if (e == null || key.equals(e.key))                    retries = 0;                else                    e = e.next;            }            else if (++retries > MAX_SCAN_RETRIES) {                lock();                break;            }            else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {                e = first = f;                retries = -1;            }        }    }    // 因為1.7的HashEntry.next是volatile的,可以修改,因此remove操作簡單了很多,就是基本的鏈表刪除操作。    final V remove(Object key, int hash, Object value) {        if (!tryLock())            scanAndLock(key, hash);        V oldValue = null;        try {            HashEntry<K,V>[] tab = table;            int index = (tab.length - 1) & hash;            HashEntry<K,V> e = entryAt(tab, index);            HashEntry<K,V> pred = null;            while (e != null) {                K k;                HashEntry<K,V> next = e.next;                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {                    V v = e.value;                    if (value == null || value == v || value.equals(v)) {                        if (pred == null)                            setEntryAt(tab, index, next); // remove的是第一個節點                        else                            pred.setNext(next); // 直接鏈表操作,前面說了1.7的HashEntry.next是volatile的,可以修改,不再跟1.6一樣是final的!!!                        ++modCount;                        --count;                        oldValue = v;                    }                    break;                }                pred = e;                e = next;            }        } finally {            unlock();        }        return oldValue;    }    // 1.7相對1.6的兩點改動:    // 1、多了個scanAndLock操作;2、會修改modCount    final boolean replace(K key, int hash, V oldValue, V newValue) {        if (!tryLock())            scanAndLock(key, hash);        boolean replaced = false;        try {            HashEntry<K,V> e;            for (e = entryForHash(this, hash); e != null; e = e.next) {                K k;                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {                    if (oldValue.equals(e.value)) {                        e.value = newValue;                        ++modCount; // 1.7的replace方法也會修改modCount了,1.6是不會的,能夠更大地保證containValue這個方法                        replaced = true;                    }                    break;                }            }        } finally {            unlock();        }        return replaced;    }    // 基本同replace(K key, int hash, V oldValue, V newValue)    final V replace(K key, int hash, V value) {        if (!tryLock())            scanAndLock(key, hash);        V oldValue = null;        try {            HashEntry<K,V> e;            for (e = entryForHash(this, hash); e != null; e = e.next) {                K k;                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {                    oldValue = e.value;                    e.value = value;                    ++modCount; // 1.7的replace方法也會修改modCount了,1.6是不會的,能夠更大地保證containValue這個方法                    break;                }            }        } finally {            unlock();        }        return oldValue;    }    // 基本沒改變    final void clear() {        lock();        try {            HashEntry<K,V>[] tab = table;            for (int i = 0; i < tab.length ; i++)                setEntryAt(tab, i, null);            ++modCount;            count = 0;        } finally {            unlock();        }    }}

四、構造方法

主要改變是使用懶初始化,只初始化Sgement數組的第一個Segment,剩下的Segment都是使用時再參照第一個Segment的參數初始化,相對 jdk1.6 整體沒多大變化。
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)        throw new IllegalArgumentException();    if (concurrencyLevel > MAX_SEGMENTS)        concurrencyLevel = MAX_SEGMENTS;    // Find power-of-two sizes best matching arguments    int sshift = 0;    int ssize = 1;    while (ssize < concurrencyLevel) {        ++sshift;        ssize <<= 1;    }    this.segmentShift = 32 - sshift;    this.segmentMask = ssize - 1;    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    int c = initialCapacity / ssize;    if (c * ssize < initialCapacity)        ++c;    int cap = MIN_SEGMENT_TABLE_CAPACITY;    while (cap < c)        cap <<= 1;    // create segments and segments[0] 構造方法只構造第一個Segment,后面懶初始化時構造的其余的 Segment 使用的參數,都從 segments[0] 中讀取    Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]);    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]    this.segments = ss;}// 其余的幾個不說

五、一些內部方法

主要改變也是使用Unsafe來進行底層操作代替普通的Java方法1、hash函數使用了jdk 1.7 HashMap的設計,引入了 hashseed ,會根據系統屬性生成一個 hashSeed,提高hash隨機性。hash的具體計算跟 ConcurrentHashMap 1.6的一樣。
private int hash(Object k) {    int h = hashSeed;    if ((0 != h) && (k instanceof String)) {        return sun.misc.Hashing.stringHash32((String) k);    }    h ^= k.hashCode();    // Spread bits to regularize both segment and index locations,    // using variant of single-Word Wang/Jenkins hash.    h += (h <<  15) ^ 0xffffcd7d;    h ^= (h >>> 10);    h += (h <<   3);    h ^= (h >>>  6);    h += (h <<   2) + (h << 14);    return h ^ (h >>> 16);}

2、Segment/Entry定位方法

使用Unsafe提供的功能強大的底層操作代替普通的Java操作,增強方法的性能(運行速度,CAS,普通變量的volatile讀寫,volatile變量的lazySet)

// 通過下標定位到Segment中下標為 i 的hash桶的第一個節點,也就是鏈表的頭結點,用 Unsafe 提供對數組元素的 volatile 讀取,還要處理下Segment為null的情況static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {    return (tab == null) ? null : (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)i << TSHIFT) + TBASE);}// 設置某個Segment中下標為 i 的hash桶的第一個節點,也就是鏈表的頭結點為e,使用的是lazySet提高效率static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i, HashEntry<K,V> e) {    UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);}// 使用Unsafe提供的volatile讀取功能,通過下標求segments[j]// segments是用final修飾的,構造方法保證它會在ConcurrentHashMap的實例被引用前初始化成正確的值,null的情況只在反序列化時才會出現static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {    long u = (j << SSHIFT) + SBASE; // 計算實際的字節偏移量    return ss == null ? null : (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);}// 確保Segment被初始化// 因為懶初始化的原因,只有segments[0]在構造方法中被初始化,其余的都是后面按需初始化,此方法就是做這個初始化的// 使用 CAS 不加鎖,同時也能保證每個Segment只被初始化一次private Segment<K,V> ensureSegment(int k) {    final Segment<K,V>[] ss = this.segments;    long u = (k << SSHIFT) + SBASE; // raw offset 實際的字節偏移量    Segment<K,V> seg;    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {        Segment<K,V> proto = ss[0]; // use segment 0 as prototype        int cap = proto.table.length;        float lf = proto.loadFactor;        int threshold = (int)(cap * lf);        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck 再檢查一次是否已經被初始化            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) // 使用 CAS 確保只被初始化一次                    break;            }        }    }    return seg;}// 使用hash定位Segment,相對于 segmentAt 多一次用 (h >>> segmentShift) & segmentMask 求下標過程private Segment<K,V> segmentForHash(int h) {    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;    return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);}// 使用hash定位頭結點,相對于 entryAt 多用一次 (tab.length - 1) & h 求下標的過程static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {    HashEntry<K,V>[] tab;    return (seg == null || (tab = seg.table) == null) ? null :        (HashEntry<K,V>) UNSAFE.getObjectVolatile        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);}

六、常用方法

理解了下面三個:1、jdk 1.7 的 HashMap(可以看我寫的這篇)2、jdk 1.6 的 ConcurrentHashMap(可以看我寫的這篇)3、jdk 1.7 的 ConcurrentHashMap 相對 jdk 1.6 的總體變化(看上面)就可以一個個方法過流水帳了,基本思路還是一樣,通過hash定位到Segment,交給相應的Segment去執行。

讀方法

// isEmpty方法,實現思路跟1.6的基本一樣,利用modCount單調遞增的性質偷了個懶,只進行sum(modCount)的前后比較,不用一個個單獨地前后比較public boolean isEmpty() {    long sum = 0L;    final Segment<K,V>[] segments = this.segments;    for (int j = 0; j < segments.length; ++j) {        Segment<K,V> seg = segmentAt(segments, j);        if (seg != null) {            if (seg.count != 0)                return false;            sum += seg.modCount;        }    }    if (sum != 0L) { // recheck unless no modifications        for (int j = 0; j < segments.length; ++j) {            Segment<K,V> seg = segmentAt(segments, j);            if (seg != null) {                if (seg.count != 0)                    return false;                sum -= seg.modCount; // 1.6這里的一個個modCount對比,1.7改為總體對比一次,因為modCount的單調遞增的,不會有count可能出現的 ABA 問題            }        }        if (sum != 0L)            return false;    }    return true;}// size方法,實現思路跟1.6的基本一樣,也利用了modCount單調遞增的性質偷了個懶public int size() {    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 (;;) {            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;}// get方法整體實現思路跟1.6基本一樣// 1.7的使用了Unsafe.getObjectVolatile,它能為普通對象提供volatile讀取功能,能夠強化這里的get方法// get方法的操作都比較簡單,就都把操作集中在這里,省略了Segment.get,減少方法調用帶來的開銷,抽象性層次性也沒有變差public V get(Object key) {    Segment<K,V> s; // manually integrate access methods to reduce overhead 集中在這里手動訪問減少方法調用開銷    HashEntry<K,V>[] tab;    int h = hash(key);    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&(tab = s.table) != null) {        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);            e != null; e = e.next) {            K k;            if ((k = e.key) == key || (e.hash == h && key.equals(k)))                return e.value;        }    }    return null;}// 跟上面的get幾乎一樣public boolean containsKey(Object key);// 基本同size方法// 1.6中put相同的key不改變modCount的問題,在上面說了,因此也提高了containsValue方法的準確性public boolean containsValue(Object value) {    // Same idea as size()    if (value == null)        throw new NullPointerException();    final Segment<K,V>[] segments = this.segments;    boolean found = false;    long last = 0;    int retries = -1;    try {        outer: for (;;) {            if (retries++ == RETRIES_BEFORE_LOCK) {                for (int j = 0; j < segments.length; ++j)                    ensureSegment(j).lock(); // force creation            }            long hashSum = 0L;            int sum = 0;            for (int j = 0; j < segments.length; ++j) {                HashEntry<K,V>[] tab;                Segment<K,V> seg = segmentAt(segments, j);                if (seg != null && (tab = seg.table) != null) {                    for (int i = 0 ; i < tab.length; i++) {                        HashEntry<K,V> e;                        for (e = entryAt(tab, i); e != null; e = e.next) {                            V v = e.value;                            if (v != null && value.equals(v)) {                                found = true;                                break outer; // 這里就算是contains也會再執行一次,1.6如果第一次contains就直接return,不會執行第二次                            }                        }                    }                    sum += seg.modCount;                }            }            if (retries > 0 && sum == last)                break;            last = sum;        }    } finally {        if (retries > RETRIES_BEFORE_LOCK) {            for (int j = 0; j < segments.length; ++j)                segmentAt(segments, j).unlock();        }    }    return found;}// 等價于containsValuepublic boolean contains(Object value);寫方法
// 1.7開始大部分集合類都是懶初始化,put這里處理下懶初始化,其余基本思路跟1.6的差不多,都是代理給相應的Segment的同名方法public V put(K key, V value) {    Segment<K,V> s;    if (value == null)        throw new NullPointerException();    int hash = hash(key);    int j = (hash >>> segmentShift) & segmentMask;    if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) // nonvolatile; recheck in ensureSegment 非volatile方式讀取,在ensureSegment中再檢查一次        s = ensureSegment(j); // 處理Segment的初始化,上面第五點中說了    return s.put(key, hash, value, false);}// 同putpublic V putIfAbsent(K key, V value);// 跟1.6一樣,都是循環put,不用全局鎖,其他線程還是可以在這個方法執行期間成功進行寫操作public void putAll(Map<? extends K, ? extends V> m);public void clear();// 額外處理下Segment為null的情況,其余基本同1.6,代理給相應的Segement的同名方法public V remove(Object key) {    int hash = hash(key);    Segment<K,V> s = segmentForHash(hash);    return s == null ? null : s.remove(key, hash, null); // 1.7使用懶初始化,會出現Segment為null的情況}// 同removepublic boolean remove(Object key, Object value);// 學remove一樣額外處理下Segment為null的情況,其余思路跟1.6差不多,都是代理給相應的Segement的同名方法public boolean replace(K key, V oldValue, V newValue);public V replace(K key, V value);

七、視圖和迭代器

除了Unsafe導致的一些讀取方式變化外,其余的基本和 jdk1.6的保持不變,思路還是一樣的。1.7相對1.6,主要的改動還是Unsafe那塊的,基本設計上的改動并不大。一些方法看起來差異大,是因為Unsafe的操作就是那樣原始,邏輯上還是跟1.6對應的基本操作等價,理解起來不算難。

以上內容,如有問題,煩請指出,謝謝!


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 连州市| 北安市| 永兴县| 肥东县| 永嘉县| 长丰县| 永清县| 舒兰市| 新郑市| 汪清县| 新昌县| 寿宁县| 商河县| 北海市| 靖西县| 进贤县| 呼和浩特市| 扶绥县| 巴林左旗| 深泽县| 得荣县| 濮阳县| 宁陕县| 临猗县| 淮阳县| 凤冈县| 东乡族自治县| 汽车| 二连浩特市| 修武县| 武汉市| 胶南市| 石楼县| 榕江县| 靖西县| 宜兰市| 连云港市| 高雄市| 林芝县| 高碑店市| 苏尼特左旗|