JDK 1.7
數(shù)據(jù)結(jié)構(gòu)
JDK 1.7 結(jié)構(gòu)
Segment 分段鎖
依舊是數(shù)組+鏈表哭尝，Segment 是一個(gè) ReentrantLock 可重入鎖：
static final class Segment<K,V> extends ReentrantLock implements Serializable
數(shù)據(jù)操作的時(shí)候巩步，先定位到 Segment 數(shù)組的位置蝠引，然后嘗試獲取鎖孵睬。某個(gè)線程獲取鎖成功就進(jìn)行數(shù)據(jù)添加止毕、移除等操作植旧，這時(shí)其它線程需要操作數(shù)據(jù)，會(huì)進(jìn)入 Segment 的鎖隊(duì)列（AQS）并根據(jù)情況進(jìn)入阻塞狀態(tài)慕淡。等待獨(dú)占線程釋放鎖后背伴，后面的線程接著進(jìn)行數(shù)據(jù)操作。
每一個(gè) Segment 都是一個(gè)鎖峰髓，各個(gè)鎖之間互不影響傻寂。也就是當(dāng) Segment A 被某線程操作數(shù)據(jù)的時(shí)候，Segment B 依舊可以進(jìn)行數(shù)據(jù)操作携兵，這就是所謂 “鎖分離” 的大概原理疾掰。這樣分段鎖的效率要高于整個(gè)數(shù)據(jù)加鎖、也高于 synchronized 對(duì)方法加鎖徐紧。
元素個(gè)體 HashEntry
HashEntry 數(shù)組是真正存放數(shù)據(jù)的地方：
static final class HashEntry<K,V> {
final int hash; // hash值
final K key; // key
volatile V value; // value
volatile HashEntry<K,V> next; // 下一個(gè)結(jié)點(diǎn)
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
要注意的是 value 和 next 結(jié)點(diǎn)都是 volatile 修飾的静檬，保證了其可見性炭懊，也就是在讀取的時(shí)候都是最新的值。
構(gòu)造器
/**
* 默認(rèn)的初始容量 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 默認(rèn)的負(fù)載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 默認(rèn)的并發(fā)數(shù)量,會(huì)影響segments數(shù)組的長(zhǎng)度(初始化后不能修改)
*/
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/**
* 最大容量,構(gòu)造ConcurrentHashMap時(shí)指定的值超過(guò),就用該值替換
* ConcurrentHashMap大小必須是2^n,且小于等于2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 允許最大segment數(shù)量,用于限定concurrencyLevel的邊界,必須是2^n
*/
static final int MAX_SEGMENTS = 1 << 16;
/**
* 非鎖定情況下調(diào)用size和contains方法的重試次數(shù),避免由于table連續(xù)被修改導(dǎo)致無(wú)限重試
*/
static final int RETRIES_BEFORE_LOCK = 2;
/**
* segments數(shù)組
*/
final Segment<K,V>[] segments;
構(gòu)造器可指定默認(rèn)初始容量拂檩，增長(zhǎng)因子侮腹，并發(fā)等級(jí)（決定同一時(shí)間允許線程操作的數(shù)據(jù)）。
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// MAX_SEGMENTS 為最大 Segment 數(shù)量广恢，默認(rèn) 1<<16=65536
// 如果超過(guò)了最大容量凯旋，直接設(shè)置為最大
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// 找到距離并發(fā)數(shù)最大的 2 的冪數(shù)，作為 Segment 數(shù)組的容量
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;
// 根據(jù)傳來(lái)的參數(shù)钉迷，創(chuàng)建 Segment 模板 s0
// 放置元素時(shí)需要初始化 Segment至非，需要用到這個(gè)模板
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;
}
數(shù)據(jù)存放
public V put(K key, V value) {
Segment<K,V> s;
// value 不可為 null
if (value == null)
throw new NullPointerException();
// key 不可為 null，否則 hashCode 方法空指針
int hash = hash(key.hashCode());
// hash 碼進(jìn)行運(yùn)算糠聪，相當(dāng)于擾動(dòng)一下
int j = (hash >>> segmentShift) & segmentMask;
// 根據(jù) hash 值獲取對(duì)應(yīng)的 Segment
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
ConcurrentHashMap 鍵值不可為 null荒椭。至于為什么這么設(shè)計(jì)，有一種說(shuō)法是為了避免多線程下獲取數(shù)據(jù)舰蟆，無(wú)法區(qū)分到底是沒(méi)有該數(shù)據(jù)趣惠，還是該數(shù)據(jù)為 null 的情況。
定位 Segment 位置身害，如果不存在則創(chuàng)建 Segment味悄。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 嘗試加鎖
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
// & 運(yùn)算獲取下標(biāo)，類似取模但是效率高于取模
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
// 遍歷鏈表
for (HashEntry<K,V> e = first;;) {
if (e != null) { // 鏈表結(jié)點(diǎn)不為空
K k;
// key 相同則準(zhǔn)備覆蓋值塌鸯，覆蓋成功跳出循環(huán)
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {// 鏈表頭結(jié)點(diǎn)為空
// 不為 null
if (node != null)
// 將新結(jié)點(diǎn)放進(jìn)鏈表首位侍瑟，調(diào)用 putOrderedObject 進(jìn)行內(nèi)存地址偏移確定位置
node.setNext(first);
else
// 創(chuàng)建新結(jié)點(diǎn)
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 容量不夠進(jìn)行擴(kuò)容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
// 頭結(jié)點(diǎn)放在下標(biāo)處，會(huì)調(diào)用 putOrderedObject 確定位置
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 最后釋放鎖
unlock();
}
return oldValue;
}
- 某個(gè)線程來(lái)到該方法丙猬，首先嘗試獲取鎖涨颜。獲取成功執(zhí)行后續(xù) put 操作，失敗進(jìn)行自旋嘗試獲取茧球。如果重試次數(shù)最大則進(jìn)入 AQS 隊(duì)列庭瑰，再根據(jù)其狀態(tài)進(jìn)行阻塞或中斷等待獲取。
scanAndLockForPut 再次嘗試獲取鎖或阻塞抢埋。
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();// 進(jìn)入 ReetLock 的 lock 方法弹灭，會(huì)進(jìn)行排隊(duì)或阻塞
break;
}
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
- 根據(jù) hash 計(jì)算出下標(biāo)，根據(jù)下標(biāo)定位 HashEntry 數(shù)組的位置揪垄，新增的元素即將插入該位置并作為頭結(jié)點(diǎn)鲤屡。
- 緊接著遍歷鏈表，如果新元素下標(biāo)與已存在的相同福侈，則覆蓋值并退出循環(huán)。
- 遍歷出現(xiàn) null 的情況卢未，要么是空桶肪凛、要么是遍歷完了鏈表堰汉。然后將新增的元素添加到鏈表首位，UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e) 相當(dāng)于把數(shù)據(jù)存放到合適的地址中去伟墙。
確定容量
每個(gè) Segment 進(jìn)行數(shù)據(jù)存放或刪除時(shí)翘鸭，會(huì)統(tǒng)計(jì) modCount（編輯次數(shù)）和 count（元素?cái)?shù)量）。
計(jì)算 size 時(shí)戳葵，進(jìn)行三次遍歷就乓。如果最后兩次的 modCount 相同說(shuō)明近期沒(méi)有發(fā)生數(shù)據(jù)變化，可以樂(lè)觀的認(rèn)為計(jì)算出的 count 就是最終數(shù)量拱烁。
如果最后兩次統(tǒng)計(jì)的 modCount 不一致生蚁，說(shuō)明近期數(shù)據(jù)可能發(fā)生了變化。只能把每個(gè) Segment 鎖住戏自，然后計(jì)算它們的容量返回結(jié)果邦投，最后釋放鎖。這個(gè)過(guò)程就挺悲觀的了擅笔。
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
final Segment<K,V>[] segments = this.segments;
final int segmentCount = segments.length;
long previousSum = 0L;
for (int retries = -1; retries < RETRIES_BEFORE_LOCK; retries++) {
long sum = 0L; // sum of modCounts
long size = 0L;
for (int i = 0; i < segmentCount; i++) {
Segment<K,V> segment = segmentAt(segments, i);
if (segment != null) {
sum += segment.modCount;
size += segment.count;
}
}
if (sum == previousSum)
return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
previousSum = sum;
}
long size = 0L;
for (int i = 0; i < segmentCount; i++) {
Segment<K,V> segment = ensureSegment(i);
segment.lock();
size += segment.count;
}
for (int i = 0; i < segmentCount; i++)
segments[i].unlock();
return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
}
擴(kuò)容機(jī)制 rehash
當(dāng)數(shù)組容量到達(dá)一定值(threshold)時(shí)志衣，進(jìn)行擴(kuò)容。
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
threshold = 數(shù)組容量*增長(zhǎng)因子猛们。
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length; // 舊數(shù)組長(zhǎng)度
int newCapacity = oldCapacity << 1; // 翻倍
threshold = (int)(newCapacity * loadFactor); // 新的閾值（大于該值擴(kuò)容）
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry<?,?>[newCapacity]; // 創(chuàng)建新數(shù)組
int sizeMask = newCapacity - 1; // 生成新掩碼念脯，用于生成下標(biāo)
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; // 根據(jù) hash 和新的掩碼生成下標(biāo)
if (next == null) // 只有一個(gè)元素的鏈表，直接放就好
newTable[idx] = e;
else { // 不止一個(gè)元素弯淘，遍歷它绿店，重新確定位置
HashEntry<K,V> lastRun = e; // 標(biāo)記原來(lái)的結(jié)點(diǎn)
int lastIdx = idx; // 標(biāo)記原來(lái)的值
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) { // 新的下標(biāo)和原來(lái)的下標(biāo)不一樣，標(biāo)記一下
lastIdx = k;
lastRun = last; // 標(biāo)記一下位置發(fā)生變化的結(jié)點(diǎn)耳胎，后續(xù)遍歷重新放置位置
}
}
newTable[lastIdx] = lastRun;
// 如果 p==lastRun 說(shuō)明所有元素下標(biāo)都未發(fā)生變化惯吕，也就不需要遍歷了
// 反之，把發(fā)生變化的鏈表位置重新歸置一下
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);
}
}
}
}
// 把新加入的結(jié)點(diǎn)作為首節(jié)點(diǎn)放置
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
因?yàn)閿U(kuò)容之前已經(jīng)進(jìn)行了加鎖處理怕午，所以無(wú)需考慮同步問(wèn)題废登。
get 獲取元素
get 的過(guò)程是不加鎖的，效率較高郁惜。首先根據(jù) hash 值定位到 Segment 位置堡距，然后再進(jìn)行鏈表的遍歷直到搜索到元素即可。
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key.hashCode());
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) {
// 弱一致性的的原因兆蕉，遍歷時(shí)該 Segment 可能已經(jīng)更新
// contains 方法也有同樣的問(wèn)題
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
為什么 get 過(guò)程不加鎖羽戒，首先獲取 Segment 的時(shí)使用的 UNSAFE.getObjectVolatile 方法，進(jìn)行 volatile語(yǔ)義的讀取虎韵。volatile 讀取保證了該 Segment 在讀取時(shí)是最新的易稠，但是在遍歷的時(shí)候，原 Segment 可能已經(jīng)發(fā)生了變化包蓝，在使用時(shí)需要注意驶社。
remove 移除元素
同樣是先找到相應(yīng)的 Segment企量，然后加鎖進(jìn)行移除，移除完畢釋放鎖亡电。
public V remove(Object key) {
int hash = hash(key.hashCode());
Segment<K,V> s = segmentForHash(hash);
return s == null ? null : s.remove(key, hash, null);
}
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);
else
pred.setNext(next);
++modCount;
--count;
oldValue = v;
}
break;
}
pred = e;
e = next;
}
} finally {
unlock();
}
return oldValue;
}
JDK 1.8
數(shù)據(jù)結(jié)構(gòu)
不再采用多個(gè) Segment 結(jié)構(gòu)届巩，而是 Node 數(shù)組+鏈表/紅黑樹來(lái)存儲(chǔ)數(shù)據(jù)。這樣做優(yōu)化了查詢速度份乒，由原來(lái)的鏈表查詢 O(n) 優(yōu)化為紅黑樹 O(logn)恕汇。
JDK 1.8 數(shù)據(jù)結(jié)構(gòu)
元素個(gè)體：Node<K,V>
Node 結(jié)點(diǎn)的值 val 和 下一個(gè)結(jié)點(diǎn) Node 都是 volatile 修飾的，保證了可見性（保證讀取時(shí)是最新的）或辖。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> 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 Helpers.mapEntryToString(key, val);
}
...
構(gòu)造器
構(gòu)造器之一瘾英，參數(shù)最多就貼出來(lái)。
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
- initialCapacity：指定初始容量孝凌，默認(rèn)的是 16方咆。需要注意的是當(dāng)初始容量小于并發(fā)數(shù)量，會(huì)直接等于并發(fā)數(shù)蟀架。
- loadFactor：指定閾值瓣赂，當(dāng)容量大于該值進(jìn)行擴(kuò)容。
- concurrencyLevel：并發(fā)數(shù)片拍。
數(shù)據(jù)存放
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 不可為 null
if (key == null || value == null) throw new NullPointerException();
// 1. hash 值處理
int hash = spread(key.hashCode());
int binCount = 0;
// 遍歷
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
2. 初始化
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// volaite 讀取煌集，要插入的位置為 null 說(shuō)明當(dāng)前下標(biāo)沒(méi)有數(shù)據(jù)，可創(chuàng)建頭結(jié)點(diǎn)
// CAS 插入數(shù)據(jù)捌省，期望值 null 要修改的值新 Node
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 3. 正在擴(kuò)容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 4. volatile 只保證了 Node 值和下一個(gè)結(jié)點(diǎn)的可見性苫纤，并不保證原子性
// 所以需要加鎖
synchronized (f) {
// 找到結(jié)點(diǎn)下標(biāo)位置
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// 遍歷這串鏈表
for (Node<K,V> e = f;; ++binCount) {
K ek;
// key 相同，覆蓋 value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 尾插法
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 添加樹節(jié)點(diǎn)
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
// 超過(guò) 8 個(gè)轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 5. 容量計(jì)算
addCount(1L, binCount);
return null;
}
- spread 方法先進(jìn)行高 16 位與低 16 位進(jìn)行異或纲缓，進(jìn)行擾動(dòng)卷拘。然后再和 HASH_BITS 進(jìn)行 & 運(yùn)算，也就是與 0111 1111X7 進(jìn)行 & 運(yùn)算祝高，保證 hash 值不為負(fù)數(shù)順便又進(jìn)行一次擾動(dòng)栗弟。
因?yàn)樨?fù)數(shù)定位了一些數(shù)據(jù)正在參與擴(kuò)容、樹節(jié)點(diǎn)轉(zhuǎn)換工闺、反轉(zhuǎn)等信息乍赫，避免沖突。
static final int HASH_BITS = 0x7fffffff;
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
- table 為空的初始化陆蟆，經(jīng)典的 自旋+CAS雷厂。如果有線程正在初始化，則 CAS 標(biāo)記一個(gè)數(shù)值表示正在初始化叠殷。當(dāng)別的線程進(jìn)來(lái)時(shí)改鲫，發(fā)現(xiàn)正在初始化，則 yield 讓出 CPU。下次再進(jìn)入自旋循環(huán)時(shí)钩杰，可能已經(jīng)初始化完畢纫塌，進(jìn)行后面的 put 操作了。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0) // 小于 0 說(shuō)明可能正在初始化中讲弄，轉(zhuǎn)換為就緒狀態(tài)，讓出 cpu
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// CAS 一下依痊，期望值 sc避除，要修改的值 -1。保證其它線程來(lái)到這里時(shí)不會(huì)影響正常初始化
try {
if ((tab = table) == null || tab.length == 0) {
// 默認(rèn) 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 減去除以 4胸嘁，相當(dāng)于 %75
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
如果 hash 值為 MOVE瓶摆，說(shuō)明正在擴(kuò)容
結(jié)點(diǎn)加同步，之后無(wú)非就是進(jìn)行遍歷性宏。查詢新插入的 key 是否重復(fù)群井，如果重復(fù)覆蓋值。
容量計(jì)算毫胜，ConCurrentHashMap 使用一個(gè) volatile 的 baseCount 來(lái)表示當(dāng)前修改過(guò)后元素的個(gè)數(shù)书斜。
private transient volatile long baseCount;
容量計(jì)算
ConCurrentHashMap 使用 CounterCells[] 數(shù)組和 baseCount 來(lái)存放和計(jì)算容量：
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
// 初始容量和遍歷 CounterCell 數(shù)組存儲(chǔ)的數(shù)量
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
CounterCells 對(duì)象包含一個(gè)數(shù)量屬性，CounterCells 數(shù)組所有元素的數(shù)量屬性加起來(lái)再加上 ConCurrentHashMap 的 baseCount 就是容量了酵使。
CounterCells 初始化時(shí)默認(rèn)容量是 2荐吉。當(dāng)一個(gè)線程添加數(shù)據(jù)時(shí)，首先生成線程的哈希指針（相當(dāng)于隨機(jī)數(shù)口渔，但是比 Radom 性能要好）样屠，然后將哈希指針和 CounterCells 容量-1 進(jìn)行 & 運(yùn)算。這與 HashMap 確認(rèn)下標(biāo)的過(guò)程類似缺脉，然后將創(chuàng)建 CounterCells 對(duì)象設(shè)置容量痪欲，再賦值到 CounterCells 數(shù)組中。
擴(kuò)容機(jī)制
擴(kuò)容條件：當(dāng)前容量超過(guò)閾值攻礼。
transfer 當(dāng)容量不足時(shí)進(jìn)行擴(kuò)容业踢。這塊內(nèi)容比較復(fù)雜，暫時(shí)略過(guò)秘蛔。
private final void addCount(long x, int check) {
...
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// s 是計(jì)算出的元素?cái)?shù)量陨亡，超過(guò)閾值 sizeCtl 觸發(fā)擴(kuò)容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
get 獲取元素
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
get 比較簡(jiǎn)單，先確認(rèn) hash 桶的位置深员，然后遍歷直到找到并返回 value 為止负蠕。找不到返回 null。
這個(gè)過(guò)程無(wú)需加鎖倦畅，效率較高遮糖。因?yàn)?Node 結(jié)點(diǎn)的 value 是 volatile 修飾的，保證了讀取的可見性叠赐。
