這塊因為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的Segmentstatic 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對應的基本操作等價,理解起來不算難。以上內容,如有問題,煩請指出,謝謝!
新聞熱點
疑難解答