原文出處 javadoop
今天發(fā)一篇"水文"裳食，可能很多讀者都會(huì)表示不理解骂际，不過(guò)我想把它作為并發(fā)序列文章中不可缺少的一塊來(lái)介紹豹绪。本來(lái)以為花不了多少時(shí)間的墅拭，不過(guò)最終還是投入了挺多時(shí)間來(lái)完成這篇文章的淤齐。
網(wǎng)上關(guān)于 HashMap 和 ConcurrentHashMap 的文章確實(shí)不少股囊，不過(guò)缺斤少兩的文章比較多，所以才想自己也寫(xiě)一篇更啄，把細(xì)節(jié)說(shuō)清楚說(shuō)透稚疹，尤其像 Java8 中的 ConcurrentHashMap，大部分文章都說(shuō)不清楚祭务。終歸是希望能降低大家學(xué)習(xí)的成本内狗，不希望大家到處找各種不是很靠譜的文章，看完一篇又一篇义锥，可是還是模模糊糊柳沙。
閱讀建議：四節(jié)基本上可以進(jìn)行獨(dú)立閱讀，建議初學(xué)者可按照 Java7 HashMap -> Java7 ConcurrentHashMap -> Java8 HashMap -> Java8 ConcurrentHashMap 順序進(jìn)行閱讀缨该，可適當(dāng)降低閱讀門(mén)檻偎行。
閱讀前提：本文分析的是源碼肋拔，所以至少讀者要熟悉它們的接口使用烹俗，同時(shí)，對(duì)于并發(fā)塌衰，讀者至少要知道 CAS膨更、ReentrantLock妙真、UNSAFE 操作這幾個(gè)基本的知識(shí)，文中不會(huì)對(duì)這些知識(shí)進(jìn)行介紹荚守。Java8 用到了紅黑樹(shù)珍德，不過(guò)本文不會(huì)進(jìn)行展開(kāi)，感興趣的讀者請(qǐng)自行查找相關(guān)資料矗漾。
Java7 HashMap
HashMap 是最簡(jiǎn)單的锈候，一來(lái)我們非常熟悉，二來(lái)就是它不支持并發(fā)操作敞贡，所以源碼也非常簡(jiǎn)單泵琳。
首先，我們用下面這張圖來(lái)介紹 HashMap 的結(jié)構(gòu)誊役。
這個(gè)僅僅是示意圖获列，因?yàn)闆](méi)有考慮到數(shù)組要擴(kuò)容的情況，具體的后面再說(shuō)蛔垢。
大方向上击孩，HashMap 里面是一個(gè)數(shù)組，然后數(shù)組中每個(gè)元素是一個(gè)單向鏈表鹏漆。
上圖中巩梢，每個(gè)綠色的實(shí)體是嵌套類(lèi) Entry 的實(shí)例创泄，Entry 包含四個(gè)屬性：key, value, hash 值和用于單向鏈表的 next。
capacity：當(dāng)前數(shù)組容量且改，始終保持 2^n验烧，可以擴(kuò)容，擴(kuò)容后數(shù)組大小為當(dāng)前的 2 倍又跛。
loadFactor：負(fù)載因子碍拆，默認(rèn)為 0.75。
threshold：擴(kuò)容的閾值慨蓝，等于 capacity * loadFactor
put 過(guò)程分析
還是比較簡(jiǎn)單的感混，跟著代碼走一遍吧。
public V put(K key, V value) {
// 當(dāng)插入第一個(gè)元素的時(shí)候礼烈，需要先初始化數(shù)組大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 為 null弧满，感興趣的可以往里看，最終會(huì)將這個(gè) entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到對(duì)應(yīng)的數(shù)組下標(biāo)
int i = indexFor(hash, table.length);
// 3. 遍歷一下對(duì)應(yīng)下標(biāo)處的鏈表此熬，看是否有重復(fù)的 key 已經(jīng)存在庭呜，
// 如果有，直接覆蓋犀忱，put 方法返回舊值就結(jié)束了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 4. 不存在重復(fù)的 key募谎，將此 entry 添加到鏈表中，細(xì)節(jié)后面說(shuō)
addEntry(hash, key, value, i);
return null;
}
數(shù)組初始化
在第一個(gè)元素插入 HashMap 的時(shí)候做一次數(shù)組的初始化阴汇，就是先確定初始的數(shù)組大小数冬，并計(jì)算數(shù)組擴(kuò)容的閾值。
private void inflateTable(int toSize) {
// 保證數(shù)組大小一定是 2 的 n 次方搀庶。
// 比如這樣初始化：new HashMap(20)拐纱，那么處理成初始數(shù)組大小是 32
int capacity = roundUpToPowerOf2(toSize);
// 計(jì)算擴(kuò)容閾值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 算是初始化數(shù)組吧
table = new Entry[capacity];
initHashSeedAsNeeded(capacity); //ignore
}
這里有一個(gè)將數(shù)組大小保持為 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相應(yīng)的要求哥倔，只不過(guò)實(shí)現(xiàn)的代碼稍微有些不同秸架，后面再看到的時(shí)候就知道了。
計(jì)算具體數(shù)組位置
這個(gè)簡(jiǎn)單咆蒿，我們自己也能 YY 一個(gè)：使用 key 的 hash 值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模就可以了东抹。
static int indexFor(int hash, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return hash & (length-1);
}
這個(gè)方法很簡(jiǎn)單，簡(jiǎn)單說(shuō)就是取 hash 值的低 n 位蜡秽。如在數(shù)組長(zhǎng)度為 32 的時(shí)候府阀，其實(shí)取的就是 key 的 hash 值的低 5 位缆镣，作為它在數(shù)組中的下標(biāo)位置芽突。
添加節(jié)點(diǎn)到鏈表中
找到數(shù)組下標(biāo)后，會(huì)先進(jìn)行 key 判重董瞻，如果沒(méi)有重復(fù)寞蚌，就準(zhǔn)備將新值放入到鏈表的表頭田巴。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果當(dāng)前 HashMap 大小已經(jīng)達(dá)到了閾值，并且新值要插入的數(shù)組位置已經(jīng)有元素了挟秤，那么要擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴(kuò)容壹哺，后面會(huì)介紹一下
resize(2 * table.length);
// 擴(kuò)容以后，重新計(jì)算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新計(jì)算擴(kuò)容后的新的下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
// 往下看
createEntry(hash, key, value, bucketIndex);
}
// 這個(gè)很簡(jiǎn)單艘刚，其實(shí)就是將新值放到鏈表的表頭管宵，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
這個(gè)方法的主要邏輯就是先判斷是否需要擴(kuò)容，需要的話(huà)先擴(kuò)容攀甚，然后再將這個(gè)新的數(shù)據(jù)插入到擴(kuò)容后的數(shù)組的相應(yīng)位置處的鏈表的表頭箩朴。
數(shù)組擴(kuò)容
前面我們看到，在插入新值的時(shí)候秋度，如果當(dāng)前的 size 已經(jīng)達(dá)到了閾值炸庞，并且要插入的數(shù)組位置上已經(jīng)有元素，那么就會(huì)觸發(fā)擴(kuò)容荚斯，擴(kuò)容后埠居，數(shù)組大小為原來(lái)的 2 倍。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將原來(lái)數(shù)組中的值遷移到新的更大的數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
擴(kuò)容就是用一個(gè)新的大數(shù)組替換原來(lái)的小數(shù)組事期，并將原來(lái)數(shù)組中的值遷移到新的數(shù)組中滥壕。
由于是雙倍擴(kuò)容，遷移過(guò)程中刑赶，會(huì)將原來(lái) table[i] 中的鏈表的所有節(jié)點(diǎn)捏浊，分拆到新的數(shù)組的 newTable[i] 和 newTable[i + oldLength] 位置上。如原來(lái)數(shù)組長(zhǎng)度是 16撞叨，那么擴(kuò)容后金踪，原來(lái) table[0] 處的鏈表中的所有元素會(huì)被分配到新數(shù)組中 newTable[0] 和 newTable[16] 這兩個(gè)位置。代碼比較簡(jiǎn)單牵敷，這里就不展開(kāi)了胡岔。
get 過(guò)程分析
相對(duì)于 put 過(guò)程，get 過(guò)程是非常簡(jiǎn)單的枷餐。
- 根據(jù) key 計(jì)算 hash 值靶瘸。
- 找到相應(yīng)的數(shù)組下標(biāo)：hash & (length - 1)。
- 遍歷該數(shù)組位置處的鏈表毛肋，直到找到相等(==或equals)的 key怨咪。
public V get(Object key) {
// 之前說(shuō)過(guò)，key 為 null 的話(huà)润匙，會(huì)被放到 table[0]诗眨，所以只要遍歷下 table[0] 處的鏈表就可以了
if (key == null)
return getForNullKey();
//
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getEntry(key):
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 確定數(shù)組下標(biāo)，然后從頭開(kāi)始遍歷鏈表孕讳，直到找到為止
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
Java7 ConcurrentHashMap
ConcurrentHashMap 和 HashMap 思路是差不多的匠楚，但是因?yàn)樗С植l(fā)操作巍膘，所以要復(fù)雜一些。
整個(gè) ConcurrentHashMap 由一個(gè)個(gè) Segment 組成芋簿，Segment 代表”部分“或”一段“的意思峡懈，所以很多地方都會(huì)將其描述為分段鎖。注意与斤，行文中肪康，我很多地方用了“槽”來(lái)代表一個(gè) segment。
簡(jiǎn)單理解就是撩穿，ConcurrentHashMap 是一個(gè) Segment 數(shù)組梅鹦，Segment 通過(guò)繼承 ReentrantLock 來(lái)進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個(gè) segment冗锁，這樣只要保證每個(gè) Segment 是線(xiàn)程安全的齐唆，也就實(shí)現(xiàn)了全局的線(xiàn)程安全。
concurrencyLevel：并行級(jí)別冻河、并發(fā)數(shù)箍邮、Segment 數(shù)，怎么翻譯不重要叨叙，理解它锭弊。默認(rèn)是 16，也就是說(shuō) ConcurrentHashMap 有 16 個(gè) Segments擂错，所以理論上味滞，這個(gè)時(shí)候，最多可以同時(shí)支持 16 個(gè)線(xiàn)程并發(fā)寫(xiě)钮呀，只要它們的操作分別分布在不同的 Segment 上剑鞍。這個(gè)值可以在初始化的時(shí)候設(shè)置為其他值，但是一旦初始化以后爽醋，它是不可以擴(kuò)容的蚁署。
再具體到每個(gè) Segment 內(nèi)部，其實(shí)每個(gè) Segment 很像之前介紹的 HashMap蚂四，不過(guò)它要保證線(xiàn)程安全光戈，所以處理起來(lái)要麻煩些。
初始化
initialCapacity：初始容量遂赠，這個(gè)值指的是整個(gè) ConcurrentHashMap 的初始容量久妆，實(shí)際操作的時(shí)候需要平均分給每個(gè) Segment。
loadFactor：負(fù)載因子跷睦，之前我們說(shuō)了筷弦，Segment 數(shù)組不可以擴(kuò)容，所以這個(gè)負(fù)載因子是給每個(gè) Segment 內(nèi)部使用的送讲。
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;
// 計(jì)算并行級(jí)別 ssize奸笤，因?yàn)橐３植⑿屑?jí)別是 2 的 n 次方
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 我們這里先不要那么燒腦，用默認(rèn)值哼鬓，concurrencyLevel 為 16监右，sshift 為 4
// 那么計(jì)算出 segmentShift 為 28，segmentMask 為 15异希，后面會(huì)用到這兩個(gè)值
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// initialCapacity 是設(shè)置整個(gè) map 初始的大小健盒，
// 這里根據(jù) initialCapacity 計(jì)算 Segment 數(shù)組中每個(gè)位置可以分到的大小
// 如 initialCapacity 為 64，那么每個(gè) Segment 或稱(chēng)之為"槽"可以分到 4 個(gè)
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
// 默認(rèn) MIN_SEGMENT_TABLE_CAPACITY 是 2称簿，這個(gè)值也是有講究的扣癣，因?yàn)檫@樣的話(huà)，對(duì)于具體的槽上憨降，
// 插入一個(gè)元素不至于擴(kuò)容父虑，插入第二個(gè)的時(shí)候才會(huì)擴(kuò)容
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 創(chuàng)建 Segment 數(shù)組，
// 并創(chuàng)建數(shù)組的第一個(gè)元素 segment[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];
// 往數(shù)組寫(xiě)入 segment[0]
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
初始化完成授药，我們得到了一個(gè) Segment 數(shù)組士嚎。
我們就當(dāng)是用 new ConcurrentHashMap() 無(wú)參構(gòu)造函數(shù)進(jìn)行初始化的，那么初始化完成后：
- Segment 數(shù)組長(zhǎng)度為 16悔叽，不可以擴(kuò)容
- Segment[i] 的默認(rèn)大小為 2莱衩，負(fù)載因子是 0.75，得出初始閾值為 1.5娇澎，也就是以后插入第一個(gè)元素不會(huì)觸發(fā)擴(kuò)容笨蚁，插入第二個(gè)會(huì)進(jìn)行第一次擴(kuò)容
- 這里初始化了 segment[0]，其他位置還是 null趟庄，至于為什么要初始化 segment[0]括细，后面的代碼會(huì)介紹
- 當(dāng)前 segmentShift 的值為 32 - 4 = 28，segmentMask 為 16 - 1 = 15戚啥，姑且把它們簡(jiǎn)單翻譯為移位數(shù)和掩碼勒极，這兩個(gè)值馬上就會(huì)用到
put 過(guò)程分析
我們先看 put 的主流程，對(duì)于其中的一些關(guān)鍵細(xì)節(jié)操作虑鼎，后面會(huì)進(jìn)行詳細(xì)介紹辱匿。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. 計(jì)算 key 的 hash 值
int hash = hash(key);
// 2. 根據(jù) hash 值找到 Segment 數(shù)組中的位置 j
// hash 是 32 位，無(wú)符號(hào)右移 segmentShift(28) 位炫彩，剩下高 4 位匾七，
// 然后和 segmentMask(15) 做一次與操作，也就是說(shuō) j 是 hash 值的高 4 位江兢，也就是槽的數(shù)組下標(biāo)
int j = (hash >>> segmentShift) & segmentMask;
// 剛剛說(shuō)了昨忆，初始化的時(shí)候初始化了 segment[0]，但是其他位置還是 null杉允，
// ensureSegment(j) 對(duì) segment[j] 進(jìn)行初始化
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// 3. 插入新值到 槽 s 中
return s.put(key, hash, value, false);
}
第一層皮很簡(jiǎn)單邑贴，根據(jù) hash 值很快就能找到相應(yīng)的 Segment席里，之后就是 Segment 內(nèi)部的 put 操作了。
Segment 內(nèi)部是由 數(shù)組+鏈表 組成的拢驾。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 在往該 segment 寫(xiě)入前奖磁，需要先獲取該 segment 的獨(dú)占鎖
// 先看主流程，后面還會(huì)具體介紹這部分內(nèi)容
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
// 這個(gè)是 segment 內(nèi)部的數(shù)組
HashEntry<K,V>[] tab = table;
// 再利用 hash 值繁疤，求應(yīng)該放置的數(shù)組下標(biāo)
int index = (tab.length - 1) & hash;
// first 是數(shù)組該位置處的鏈表的表頭
HashEntry<K,V> first = entryAt(tab, index);
// 下面這串 for 循環(huán)雖然很長(zhǎng)咖为，不過(guò)也很好理解，想想該位置沒(méi)有任何元素和已經(jīng)存在一個(gè)鏈表這兩種情況
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;
}
break;
}
// 繼續(xù)順著鏈表走
e = e.next;
}
else {
// node 到底是不是 null稠腊，這個(gè)要看獲取鎖的過(guò)程躁染，不過(guò)和這里都沒(méi)有關(guān)系。
// 如果不為 null架忌，那就直接將它設(shè)置為鏈表表頭吞彤；如果是null，初始化并設(shè)置為鏈表表頭叹放。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 如果超過(guò)了該 segment 的閾值备畦，這個(gè) segment 需要擴(kuò)容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // 擴(kuò)容后面也會(huì)具體分析
else
// 沒(méi)有達(dá)到閾值，將 node 放到數(shù)組 tab 的 index 位置许昨，
// 其實(shí)就是將新的節(jié)點(diǎn)設(shè)置成原鏈表的表頭
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 解鎖
unlock();
}
return oldValue;
}
整體流程還是比較簡(jiǎn)單的懂盐，由于有獨(dú)占鎖的保護(hù)，所以 segment 內(nèi)部的操作并不復(fù)雜糕档。至于這里面的并發(fā)問(wèn)題莉恼，我們稍后再進(jìn)行介紹。
到這里 put 操作就結(jié)束了速那，接下來(lái)俐银，我們說(shuō)一說(shuō)其中幾步關(guān)鍵的操作。
初始化槽: ensureSegment
ConcurrentHashMap 初始化的時(shí)候會(huì)初始化第一個(gè)槽 segment[0]端仰，對(duì)于其他槽來(lái)說(shuō)捶惜，在插入第一個(gè)值的時(shí)候進(jìn)行初始化。
這里需要考慮并發(fā)荔烧，因?yàn)楹芸赡軙?huì)有多個(gè)線(xiàn)程同時(shí)進(jìn)來(lái)初始化同一個(gè)槽 segment[k]吱七，不過(guò)只要有一個(gè)成功了就可以。
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[0] 了鹤竭，
// 使用當(dāng)前 segment[0] 處的數(shù)組長(zhǎng)度和負(fù)載因子來(lái)初始化 segment[k]
// 為什么要用“當(dāng)前”踊餐，因?yàn)?segment[0] 可能早就擴(kuò)容過(guò)了
Segment<K,V> proto = ss[0];
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
// 初始化 segment[k] 內(nèi)部的數(shù)組
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // 再次檢查一遍該槽是否被其他線(xiàn)程初始化了。
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// 使用 while 循環(huán)臀稚，內(nèi)部用 CAS吝岭，當(dāng)前線(xiàn)程成功設(shè)值或其他線(xiàn)程成功設(shè)值后，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
總的來(lái)說(shuō)，ensureSegment(int k) 比較簡(jiǎn)單窜管，對(duì)于并發(fā)操作使用 CAS 進(jìn)行控制散劫。
我沒(méi)搞懂這里為什么要搞一個(gè) while 循環(huán)，CAS 失敗不就代表有其他線(xiàn)程成功了嗎幕帆，為什么要再進(jìn)行判斷获搏？
感謝評(píng)論區(qū)的李子木，如果當(dāng)前線(xiàn)程 CAS 失敗蜓肆，這里的 while 循環(huán)是為了將 seg 賦值返回。
獲取寫(xiě)入鎖: scanAndLockForPut
前面我們看到谋币，在往某個(gè) segment 中 put 的時(shí)候仗扬，首先會(huì)調(diào)用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，也就是說(shuō)先進(jìn)行一次 tryLock() 快速獲取該 segment 的獨(dú)占鎖蕾额，如果失敗早芭，那么進(jìn)入到 scanAndLockForPut 這個(gè)方法來(lái)獲取鎖。
下面我們來(lái)具體分析這個(gè)方法中是怎么控制加鎖的诅蝶。
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
// 循環(huán)獲取鎖
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
// 進(jìn)到這里說(shuō)明數(shù)組該位置的鏈表是空的退个，沒(méi)有任何元素
// 當(dāng)然，進(jìn)到這里的另一個(gè)原因是 tryLock() 失敗调炬，所以該槽存在并發(fā)语盈，不一定是該位置
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
// 順著鏈表往下走
e = e.next;
}
// 重試次數(shù)如果超過(guò) MAX_SCAN_RETRIES（單核1多核64），那么不搶了缰泡，進(jìn)入到阻塞隊(duì)列等待鎖
// lock() 是阻塞方法刀荒，直到獲取鎖后返回
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) == 0 &&
// 這個(gè)時(shí)候是有大問(wèn)題了，那就是有新的元素進(jìn)到了鏈表棘钞，成為了新的表頭
// 所以這邊的策略是缠借，相當(dāng)于重新走一遍這個(gè) scanAndLockForPut 方法
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
這個(gè)方法有兩個(gè)出口，一個(gè)是 tryLock() 成功了宜猜，循環(huán)終止泼返，另一個(gè)就是重試次數(shù)超過(guò)了 MAX_SCAN_RETRIES，進(jìn)到 lock() 方法姨拥，此方法會(huì)阻塞等待绅喉，直到成功拿到獨(dú)占鎖。
這個(gè)方法就是看似復(fù)雜叫乌，但是其實(shí)就是做了一件事霹疫，那就是獲取該 segment 的獨(dú)占鎖，如果需要的話(huà)順便實(shí)例化了一下 node综芥。
擴(kuò)容: rehash
重復(fù)一下丽蝎，segment 數(shù)組不能擴(kuò)容，擴(kuò)容是 segment 數(shù)組某個(gè)位置內(nèi)部的數(shù)組 HashEntry<K,V>[] 進(jìn)行擴(kuò)容，擴(kuò)容后屠阻，容量為原來(lái)的 2 倍红省。
首先，我們要回顧一下觸發(fā)擴(kuò)容的地方国觉，put 的時(shí)候吧恃，如果判斷該值的插入會(huì)導(dǎo)致該 segment 的元素個(gè)數(shù)超過(guò)閾值，那么先進(jìn)行擴(kuò)容麻诀，再插值痕寓，讀者這個(gè)時(shí)候可以回去 put 方法看一眼。
該方法不需要考慮并發(fā)蝇闭，因?yàn)榈竭@里的時(shí)候呻率，是持有該 segment 的獨(dú)占鎖的。
// 方法參數(shù)上的 node 是這次擴(kuò)容后呻引，需要添加到新的數(shù)組中的數(shù)據(jù)礼仗。
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// 2 倍
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
// 創(chuàng)建新數(shù)組
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
// 新的掩碼，如從 16 擴(kuò)容到 32逻悠，那么 sizeMask 為 31元践，對(duì)應(yīng)二進(jìn)制 ‘000...00011111’
int sizeMask = newCapacity - 1;
// 遍歷原數(shù)組，老套路童谒，將原數(shù)組位置 i 處的鏈表拆分到 新數(shù)組位置 i 和 i+oldCap 兩個(gè)位置
for (int i = 0; i < oldCapacity ; i++) {
// e 是鏈表的第一個(gè)元素
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
// 計(jì)算應(yīng)該放置在新數(shù)組中的位置单旁，
// 假設(shè)原數(shù)組長(zhǎng)度為 16，e 在 oldTable[3] 處饥伊，那么 idx 只可能是 3 或者是 3 + 16 = 19
int idx = e.hash & sizeMask;
if (next == null) // 該位置處只有一個(gè)元素慎恒，那比較好辦
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
// e 是鏈表表頭
HashEntry<K,V> lastRun = e;
// idx 是當(dāng)前鏈表的頭結(jié)點(diǎn) e 的新位置
int lastIdx = idx;
// 下面這個(gè) for 循環(huán)會(huì)找到一個(gè) lastRun 節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)之后的所有元素是將要放到一起的
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 將 lastRun 及其之后的所有節(jié)點(diǎn)組成的這個(gè)鏈表放到 lastIdx 這個(gè)位置
newTable[lastIdx] = lastRun;
// 下面的操作是處理 lastRun 之前的節(jié)點(diǎn)撵渡，
// 這些節(jié)點(diǎn)可能分配在另一個(gè)鏈表中融柬，也可能分配到上面的那個(gè)鏈表中
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);
}
}
}
}
// 將新來(lái)的 node 放到新數(shù)組中剛剛的 兩個(gè)鏈表之一 的 頭部
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
這里的擴(kuò)容比之前的 HashMap 要復(fù)雜一些，代碼難懂一點(diǎn)趋距。上面有兩個(gè)挨著的 for 循環(huán)粒氧，第一個(gè) for 有什么用呢？
仔細(xì)一看發(fā)現(xiàn)节腐，如果沒(méi)有第一個(gè) for 循環(huán)外盯，也是可以工作的，但是翼雀，這個(gè) for 循環(huán)下來(lái)饱苟，如果 lastRun 的后面還有比較多的節(jié)點(diǎn)，那么這次就是值得的狼渊。因?yàn)槲覀冎恍枰寺?lastRun 前面的節(jié)點(diǎn)箱熬，后面的一串節(jié)點(diǎn)跟著 lastRun 走就是了类垦，不需要做任何操作。
我覺(jué)得 Doug Lea 的這個(gè)想法也是挺有意思的城须，不過(guò)比較壞的情況就是每次 lastRun 都是鏈表的最后一個(gè)元素或者很靠后的元素蚤认，那么這次遍歷就有點(diǎn)浪費(fèi)了。不過(guò) Doug Lea 也說(shuō)了糕伐，根據(jù)統(tǒng)計(jì)砰琢，如果使用默認(rèn)的閾值，大約只有 1/6 的節(jié)點(diǎn)需要克隆良瞧。
get 過(guò)程分析
相對(duì)于 put 來(lái)說(shuō)陪汽，get 真的不要太簡(jiǎn)單。
- 計(jì)算 hash 值褥蚯，找到 segment 數(shù)組中的具體位置挚冤，或我們前面用的“槽”
- 槽中也是一個(gè)數(shù)組，根據(jù) hash 找到數(shù)組中具體的位置
- 到這里是鏈表了遵岩，順著鏈表進(jìn)行查找即可
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
// 1. hash 值
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 2. 根據(jù) hash 找到對(duì)應(yīng)的 segment
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
// 3. 找到segment 內(nèi)部數(shù)組相應(yīng)位置的鏈表你辣，遍歷
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;
}
并發(fā)問(wèn)題分析
現(xiàn)在我們已經(jīng)說(shuō)完了 put 過(guò)程和 get 過(guò)程巡通，我們可以看到 get 過(guò)程中是沒(méi)有加鎖的尘执，那自然我們就需要去考慮并發(fā)問(wèn)題。
添加節(jié)點(diǎn)的操作 put 和刪除節(jié)點(diǎn)的操作 remove 都是要加 segment 上的獨(dú)占鎖的宴凉，所以它們之間自然不會(huì)有問(wèn)題誊锭，我們需要考慮的問(wèn)題就是 get 的時(shí)候在同一個(gè) segment 中發(fā)生了 put 或 remove 操作。
-
put 操作的線(xiàn)程安全性弥锄。
- 初始化槽丧靡，這個(gè)我們之前就說(shuō)過(guò)了，使用了 CAS 來(lái)初始化 Segment 中的數(shù)組籽暇。
- 添加節(jié)點(diǎn)到鏈表的操作是插入到表頭的温治，所以，如果這個(gè)時(shí)候 get 操作在鏈表遍歷的過(guò)程已經(jīng)到了中間戒悠，是不會(huì)影響的熬荆。當(dāng)然，另一個(gè)并發(fā)問(wèn)題就是 get 操作在 put 之后绸狐，需要保證剛剛插入表頭的節(jié)點(diǎn)被讀取卤恳，這個(gè)依賴(lài)于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject询吴。
- 擴(kuò)容熊镣。擴(kuò)容是新創(chuàng)建了數(shù)組郎逃，然后進(jìn)行遷移數(shù)據(jù)藕赞，最后面將 newTable 設(shè)置給屬性 table今布。所以染突，如果 get 操作此時(shí)也在進(jìn)行唁情，那么也沒(méi)關(guān)系，如果 get 先行冠息，那么就是在舊的 table 上做查詢(xún)操作挪凑；而 put 先行，那么 put 操作的可見(jiàn)性保證就是 table 使用了 volatile 關(guān)鍵字逛艰。
-
remove 操作的線(xiàn)程安全性躏碳。
remove 操作我們沒(méi)有分析源碼，所以這里說(shuō)的讀者感興趣的話(huà)還是需要到源碼中去求實(shí)一下的散怖。
get 操作需要遍歷鏈表菇绵，但是 remove 操作會(huì)"破壞"鏈表。
如果 remove 破壞的節(jié)點(diǎn) get 操作已經(jīng)過(guò)去了镇眷，那么這里不存在任何問(wèn)題咬最。
如果 remove 先破壞了一個(gè)節(jié)點(diǎn)，分兩種情況考慮欠动。 1永乌、如果此節(jié)點(diǎn)是頭結(jié)點(diǎn)，那么需要將頭結(jié)點(diǎn)的 next 設(shè)置為數(shù)組該位置的元素具伍，table 雖然使用了 volatile 修飾翅雏，但是 volatile 并不能提供數(shù)組內(nèi)部操作的可見(jiàn)性保證，所以源碼中使用了 UNSAFE 來(lái)操作數(shù)組人芽，請(qǐng)看方法 setEntryAt望几。2、如果要?jiǎng)h除的節(jié)點(diǎn)不是頭結(jié)點(diǎn)萤厅，它會(huì)將要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)接到前驅(qū)節(jié)點(diǎn)中橄抹，這里的并發(fā)保證就是 next 屬性是 volatile 的。
Java8 HashMap
Java8 對(duì) HashMap 進(jìn)行了一些修改惕味，最大的不同就是利用了紅黑樹(shù)楼誓，所以其由 數(shù)組+鏈表+紅黑樹(shù) 組成。
根據(jù) Java7 HashMap 的介紹名挥，我們知道疟羹，查找的時(shí)候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo)躺同，但是之后的話(huà)阁猜，需要順著鏈表一個(gè)個(gè)比較下去才能找到我們需要的，時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度蹋艺，為 O(n)剃袍。
為了降低這部分的開(kāi)銷(xiāo)，在 Java8 中捎谨，當(dāng)鏈表中的元素達(dá)到了 8 個(gè)時(shí)民效，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)憔维，在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為 O(logN)。
來(lái)一張圖簡(jiǎn)單示意一下吧：
注意畏邢，上圖是示意圖业扒，主要是描述結(jié)構(gòu)，不會(huì)達(dá)到這個(gè)狀態(tài)的舒萎，因?yàn)檫@么多數(shù)據(jù)的時(shí)候早就擴(kuò)容了程储。
下面，我們還是用代碼來(lái)介紹吧臂寝，個(gè)人感覺(jué)章鲤，Java8 的源碼可讀性要差一些，不過(guò)精簡(jiǎn)一些咆贬。
Java7 中使用 Entry 來(lái)代表每個(gè) HashMap 中的數(shù)據(jù)節(jié)點(diǎn)败徊，Java8 中使用 Node，基本沒(méi)有區(qū)別掏缎，都是 key皱蹦，value，hash 和 next 這四個(gè)屬性眷蜈，不過(guò)沪哺，Node 只能用于鏈表的情況，紅黑樹(shù)的情況需要使用 TreeNode端蛆。
我們根據(jù)數(shù)組元素中凤粗，第一個(gè)節(jié)點(diǎn)數(shù)據(jù)類(lèi)型是 Node 還是 TreeNode 來(lái)判斷該位置下是鏈表還是紅黑樹(shù)的酥泛。
put 過(guò)程分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第三個(gè)參數(shù) onlyIfAbsent 如果是 true今豆，那么只有在不存在該 key 時(shí)才會(huì)進(jìn)行 put 操作
// 第四個(gè)參數(shù) evict 我們這里不關(guān)心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的時(shí)候，會(huì)觸發(fā)下面的 resize()柔袁，類(lèi)似 java7 的第一次 put 也要初始化數(shù)組長(zhǎng)度
// 第一次 resize 和后續(xù)的擴(kuò)容有些不一樣呆躲，因?yàn)檫@次是數(shù)組從 null 初始化到默認(rèn)的 16 或自定義的初始容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具體的數(shù)組下標(biāo)，如果此位置沒(méi)有值捶索，那么直接初始化一下 Node 并放置在這個(gè)位置就可以了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// 數(shù)組該位置有數(shù)據(jù)
Node<K,V> e; K k;
// 首先插掂，判斷該位置的第一個(gè)數(shù)據(jù)和我們要插入的數(shù)據(jù)，key 是不是"相等"腥例，如果是辅甥，取出這個(gè)節(jié)點(diǎn)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果該節(jié)點(diǎn)是代表紅黑樹(shù)的節(jié)點(diǎn)，調(diào)用紅黑樹(shù)的插值方法燎竖，本文不展開(kāi)說(shuō)紅黑樹(shù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 到這里璃弄，說(shuō)明數(shù)組該位置上是一個(gè)鏈表
for (int binCount = 0; ; ++binCount) {
// 插入到鏈表的最后面(Java7 是插入到鏈表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 為 8，所以构回，如果新插入的值是鏈表中的第 8 個(gè)
// 會(huì)觸發(fā)下面的 treeifyBin夏块，也就是將鏈表轉(zhuǎn)換為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在該鏈表中找到了"相等"的 key(== 或 equals)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此時(shí) break疏咐，那么 e 為鏈表中[與要插入的新值的 key "相等"]的 node
break;
p = e;
}
}
// e!=null 說(shuō)明存在舊值的key與要插入的key"相等"
// 對(duì)于我們分析的put操作，下面這個(gè) if 其實(shí)就是進(jìn)行 "值覆蓋"脐供，然后返回舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入這個(gè)值導(dǎo)致 size 已經(jīng)超過(guò)了閾值浑塞，需要進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
和 Java7 稍微有點(diǎn)不一樣的地方就是，Java7 是先擴(kuò)容后插入新值的政己，Java8 先插值再擴(kuò)容酌壕，不過(guò)這個(gè)不重要。
數(shù)組擴(kuò)容
resize() 方法用于初始化數(shù)組或數(shù)組擴(kuò)容歇由，每次擴(kuò)容后仅孩，容量為原來(lái)的 2 倍，并進(jìn)行數(shù)據(jù)遷移印蓖。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 對(duì)應(yīng)數(shù)組擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 將數(shù)組大小擴(kuò)大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 將閾值擴(kuò)大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 對(duì)應(yīng)使用 new HashMap(int initialCapacity) 初始化后辽慕，第一次 put 的時(shí)候
newCap = oldThr;
else {// 對(duì)應(yīng)使用 new HashMap() 初始化后，第一次 put 的時(shí)候
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 用新的數(shù)組大小初始化新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化數(shù)組赦肃，到這里就結(jié)束了溅蛉，返回 newTab 即可
if (oldTab != null) {
// 開(kāi)始遍歷原數(shù)組，進(jìn)行數(shù)據(jù)遷移他宛。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果該數(shù)組位置上只有單個(gè)元素船侧，那就簡(jiǎn)單了，簡(jiǎn)單遷移這個(gè)元素就可以了
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹(shù)厅各，具體我們就不展開(kāi)了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 這塊是處理鏈表的情況镜撩，
// 需要將此鏈表拆成兩個(gè)鏈表，放到新的數(shù)組中队塘，并且保留原來(lái)的先后順序
// loHead袁梗、loTail 對(duì)應(yīng)一條鏈表，hiHead憔古、hiTail 對(duì)應(yīng)另一條鏈表遮怜，代碼還是比較簡(jiǎn)單的
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 第一條鏈表
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 第二條鏈表的新的位置是 j + oldCap，這個(gè)很好理解
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get 過(guò)程分析
相對(duì)于 put 來(lái)說(shuō)鸿市，get 真的太簡(jiǎn)單了锯梁。
- 計(jì)算 key 的 hash 值，根據(jù) hash 值找到對(duì)應(yīng)數(shù)組下標(biāo): hash & (length-1)
- 判斷數(shù)組該位置處的元素是否剛好就是我們要找的焰情，如果不是陌凳，走第三步
- 判斷該元素類(lèi)型是否是 TreeNode，如果是内舟，用紅黑樹(shù)的方法取數(shù)據(jù)合敦，如果不是，走第四步
- 遍歷鏈表谒获，直到找到相等(==或equals)的 key
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷第一個(gè)節(jié)點(diǎn)是不是就是需要的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判斷是否是紅黑樹(shù)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 鏈表遍歷
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Java8 ConcurrentHashMap
Java7 中實(shí)現(xiàn)的 ConcurrentHashMap 說(shuō)實(shí)話(huà)還是比較復(fù)雜的蛤肌，Java8 對(duì) ConcurrentHashMap 進(jìn)行了比較大的改動(dòng)壁却。建議讀者可以參考 Java8 中 HashMap 相對(duì)于 Java7 HashMap 的改動(dòng)，對(duì)于 ConcurrentHashMap裸准，Java8 也引入了紅黑樹(shù)展东。
說(shuō)實(shí)話(huà)，Java8 ConcurrentHashMap 源碼真心不簡(jiǎn)單炒俱，最難的在于擴(kuò)容盐肃，數(shù)據(jù)遷移操作不容易看懂。
我們先用一個(gè)示意圖來(lái)描述下其結(jié)構(gòu)：
結(jié)構(gòu)上和 Java8 的 HashMap 基本上一樣权悟，不過(guò)它要保證線(xiàn)程安全性砸王，所以在源碼上確實(shí)要復(fù)雜一些。
初始化
// 這構(gòu)造函數(shù)里峦阁，什么都不干
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
這個(gè)初始化方法有點(diǎn)意思谦铃，通過(guò)提供初始容量，計(jì)算了 sizeCtl榔昔，sizeCtl = 【 (1.5 * initialCapacity + 1)驹闰，然后向上取最近的 2 的 n 次方】。如 initialCapacity 為 10撒会，那么得到 sizeCtl 為 16嘹朗，如果 initialCapacity 為 11，得到 sizeCtl 為 32诵肛。
sizeCtl 這個(gè)屬性使用的場(chǎng)景很多屹培，不過(guò)只要跟著文章的思路來(lái)，就不會(huì)被它搞暈了怔檩。
如果你愛(ài)折騰褪秀，也可以看下另一個(gè)有三個(gè)參數(shù)的構(gòu)造方法，這里我就不說(shuō)了珠洗，大部分時(shí)候溜歪，我們會(huì)使用無(wú)參構(gòu)造函數(shù)進(jìn)行實(shí)例化若专，我們也按照這個(gè)思路來(lái)進(jìn)行源碼分析吧许蓖。
put 過(guò)程分析
仔細(xì)地一行一行代碼看下去：
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 得到 hash 值
int hash = spread(key.hashCode());
// 用于記錄相應(yīng)鏈表的長(zhǎng)度
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果數(shù)組"空"，進(jìn)行數(shù)組初始化
if (tab == null || (n = tab.length) == 0)
// 初始化數(shù)組调衰，后面會(huì)詳細(xì)介紹
tab = initTable();
// 找該 hash 值對(duì)應(yīng)的數(shù)組下標(biāo)膊爪，得到第一個(gè)節(jié)點(diǎn) f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果數(shù)組該位置為空，
// 用一次 CAS 操作將這個(gè)新值放入其中即可嚎莉，這個(gè) put 操作差不多就結(jié)束了米酬，可以拉到最后面了
// 如果 CAS 失敗，那就是有并發(fā)操作趋箩，進(jìn)到下一個(gè)循環(huán)就好了
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// hash 居然可以等于 MOVED赃额，這個(gè)需要到后面才能看明白加派，不過(guò)從名字上也能猜到，肯定是因?yàn)樵跀U(kuò)容
else if ((fh = f.hash) == MOVED)
// 幫助數(shù)據(jù)遷移跳芳，這個(gè)等到看完數(shù)據(jù)遷移部分的介紹后芍锦，再理解這個(gè)就很簡(jiǎn)單了
tab = helpTransfer(tab, f);
else { // 到這里就是說(shuō)，f 是該位置的頭結(jié)點(diǎn)飞盆，而且不為空
V oldVal = null;
// 獲取數(shù)組該位置的頭結(jié)點(diǎn)的監(jiān)視器鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 頭結(jié)點(diǎn)的 hash 值大于 0娄琉，說(shuō)明是鏈表
// 用于累加，記錄鏈表的長(zhǎng)度
binCount = 1;
// 遍歷鏈表
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果發(fā)現(xiàn)了"相等"的 key吓歇，判斷是否要進(jìn)行值覆蓋孽水，然后也就可以 break 了
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 到了鏈表的最末端，將這個(gè)新值放到鏈表的最后面
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) { // 紅黑樹(shù)
Node<K,V> p;
binCount = 2;
// 調(diào)用紅黑樹(shù)的插值方法插入新節(jié)點(diǎn)
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 判斷是否要將鏈表轉(zhuǎn)換為紅黑樹(shù)城看，臨界值和 HashMap 一樣女气，也是 8
if (binCount >= TREEIFY_THRESHOLD)
// 這個(gè)方法和 HashMap 中稍微有一點(diǎn)點(diǎn)不同，那就是它不是一定會(huì)進(jìn)行紅黑樹(shù)轉(zhuǎn)換测柠，
// 如果當(dāng)前數(shù)組的長(zhǎng)度小于 64主卫，那么會(huì)選擇進(jìn)行數(shù)組擴(kuò)容，而不是轉(zhuǎn)換為紅黑樹(shù)
// 具體源碼我們就不看了鹃愤，擴(kuò)容部分后面說(shuō)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//
addCount(1L, binCount);
return null;
}
put 的主流程看完了簇搅，但是至少留下了幾個(gè)問(wèn)題，第一個(gè)是初始化软吐，第二個(gè)是擴(kuò)容瘩将，第三個(gè)是幫助數(shù)據(jù)遷移，這些我們都會(huì)在后面進(jìn)行一一介紹凹耙。
初始化數(shù)組：initTable
這個(gè)比較簡(jiǎn)單姿现，主要就是初始化一個(gè)合適大小的數(shù)組，然后會(huì)設(shè)置 sizeCtl肖抱。
初始化方法中的并發(fā)問(wèn)題是通過(guò)對(duì) sizeCtl 進(jìn)行一個(gè) CAS 操作來(lái)控制的备典。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 初始化的"功勞"被其他線(xiàn)程"搶去"了
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// CAS 一下，將 sizeCtl 設(shè)置為 -1意述，代表?yè)尩搅随i
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// DEFAULT_CAPACITY 默認(rèn)初始容量是 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化數(shù)組提佣，長(zhǎng)度為 16 或初始化時(shí)提供的長(zhǎng)度
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 將這個(gè)數(shù)組賦值給 table，table 是 volatile 的
table = tab = nt;
// 如果 n 為 16 的話(huà)荤崇，那么這里 sc = 12
// 其實(shí)就是 0.75 * n
sc = n - (n >>> 2);
}
} finally {
// 設(shè)置 sizeCtl 為 sc拌屏，我們就當(dāng)是 12 吧
sizeCtl = sc;
}
break;
}
}
return tab;
}
鏈表轉(zhuǎn)紅黑樹(shù): treeifyBin
前面我們?cè)?put 源碼分析也說(shuō)過(guò)，treeifyBin 不一定就會(huì)進(jìn)行紅黑樹(shù)轉(zhuǎn)換术荤，也可能是僅僅做數(shù)組擴(kuò)容倚喂。我們還是進(jìn)行源碼分析吧。
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// MIN_TREEIFY_CAPACITY 為 64
// 所以瓣戚，如果數(shù)組長(zhǎng)度小于 64 的時(shí)候端圈，其實(shí)也就是 32 或者 16 或者更小的時(shí)候焦读，會(huì)進(jìn)行數(shù)組擴(kuò)容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 后面我們?cè)僭敿?xì)分析這個(gè)方法
tryPresize(n << 1);
// b 是頭結(jié)點(diǎn)
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 加鎖
synchronized (b) {
if (tabAt(tab, index) == b) {
// 下面就是遍歷鏈表，建立一顆紅黑樹(shù)
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 將紅黑樹(shù)設(shè)置到數(shù)組相應(yīng)位置中
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
擴(kuò)容：tryPresize
如果說(shuō) Java8 ConcurrentHashMap 的源碼不簡(jiǎn)單舱权，那么說(shuō)的就是擴(kuò)容操作和遷移操作吨灭。
這個(gè)方法要完完全全看懂還需要看之后的 transfer 方法，讀者應(yīng)該提前知道這點(diǎn)刑巧。
這里的擴(kuò)容也是做翻倍擴(kuò)容的喧兄，擴(kuò)容后數(shù)組容量為原來(lái)的 2 倍。
// 首先要說(shuō)明的是啊楚，方法參數(shù) size 傳進(jìn)來(lái)的時(shí)候就已經(jīng)翻了倍了
private final void tryPresize(int size) {
// c：size 的 1.5 倍吠冤，再加 1，再往上取最近的 2 的 n 次方恭理。
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 這個(gè) if 分支和之前說(shuō)的初始化數(shù)組的代碼基本上是一樣的拯辙，在這里，我們可以不用管這塊代碼
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2); // 0.75 * n
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// 我沒(méi)看懂 rs 的真正含義是什么颜价，不過(guò)也關(guān)系不大
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. 用 CAS 將 sizeCtl 加 1涯保，然后執(zhí)行 transfer 方法
// 此時(shí) nextTab 不為 null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 1. 將 sizeCtl 設(shè)置為 (rs << RESIZE_STAMP_SHIFT) + 2)
// 我是沒(méi)看懂這個(gè)值真正的意義是什么？不過(guò)可以計(jì)算出來(lái)的是周伦，結(jié)果是一個(gè)比較大的負(fù)數(shù)
// 調(diào)用 transfer 方法夕春，此時(shí) nextTab 參數(shù)為 null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
這個(gè)方法的核心在于 sizeCtl 值的操作，首先將其設(shè)置為一個(gè)負(fù)數(shù)专挪，然后執(zhí)行 transfer(tab, null)及志，再下一個(gè)循環(huán)將 sizeCtl 加 1，并執(zhí)行 transfer(tab, nt)寨腔，之后可能是繼續(xù) sizeCtl 加 1速侈，并執(zhí)行 transfer(tab, nt)。
所以迫卢，可能的操作就是執(zhí)行 1 次 transfer(tab, null) + 多次 transfer(tab, nt)倚搬，這里怎么結(jié)束循環(huán)的需要看完 transfer 源碼才清楚。
數(shù)據(jù)遷移：transfer
下面這個(gè)方法很點(diǎn)長(zhǎng)乾蛤，將原來(lái)的 tab 數(shù)組的元素遷移到新的 nextTab 數(shù)組中每界。
雖然我們之前說(shuō)的 tryPresize 方法中多次調(diào)用 transfer 不涉及多線(xiàn)程，但是這個(gè) transfer 方法可以在其他地方被調(diào)用幻捏，典型地盆犁，我們之前在說(shuō) put 方法的時(shí)候就說(shuō)過(guò)了，請(qǐng)往上看 put 方法篡九，是不是有個(gè)地方調(diào)用了 helpTransfer 方法，helpTransfer 方法會(huì)調(diào)用 transfer 方法的醋奠。
此方法支持多線(xiàn)程執(zhí)行榛臼，外圍調(diào)用此方法的時(shí)候伊佃，會(huì)保證第一個(gè)發(fā)起數(shù)據(jù)遷移的線(xiàn)程，nextTab 參數(shù)為 null沛善，之后再調(diào)用此方法的時(shí)候航揉，nextTab 不會(huì)為 null。
閱讀源碼之前金刁，先要理解并發(fā)操作的機(jī)制帅涂。原數(shù)組長(zhǎng)度為 n，所以我們有 n 個(gè)遷移任務(wù)尤蛮，讓每個(gè)線(xiàn)程每次負(fù)責(zé)一個(gè)小任務(wù)是最簡(jiǎn)單的媳友，每做完一個(gè)任務(wù)再檢測(cè)是否有其他沒(méi)做完的任務(wù)，幫助遷移就可以了产捞，而 Doug Lea 使用了一個(gè) stride醇锚，簡(jiǎn)單理解就是步長(zhǎng)，每個(gè)線(xiàn)程每次負(fù)責(zé)遷移其中的一部分坯临，如每次遷移 16 個(gè)小任務(wù)焊唬。所以，我們就需要一個(gè)全局的調(diào)度者來(lái)安排哪個(gè)線(xiàn)程執(zhí)行哪幾個(gè)任務(wù)看靠，這個(gè)就是屬性 transferIndex 的作用赶促。
第一個(gè)發(fā)起數(shù)據(jù)遷移的線(xiàn)程會(huì)將 transferIndex 指向原數(shù)組最后的位置，然后從后往前的 stride 個(gè)任務(wù)屬于第一個(gè)線(xiàn)程挟炬，然后將 transferIndex 指向新的位置芳杏，再往前的 stride 個(gè)任務(wù)屬于第二個(gè)線(xiàn)程，依此類(lèi)推辟宗。當(dāng)然爵赵，這里說(shuō)的第二個(gè)線(xiàn)程不是真的一定指代了第二個(gè)線(xiàn)程，也可以是同一個(gè)線(xiàn)程泊脐，這個(gè)讀者應(yīng)該能理解吧空幻。其實(shí)就是將一個(gè)大的遷移任務(wù)分為了一個(gè)個(gè)任務(wù)包。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// stride 在單核下直接等于 n容客，多核模式下為 (n>>>3)/NCPU秕铛，最小值是 16
// stride 可以理解為”步長(zhǎng)“，有 n 個(gè)位置是需要進(jìn)行遷移的缩挑，
// 將這 n 個(gè)任務(wù)分為多個(gè)任務(wù)包但两，每個(gè)任務(wù)包有 stride 個(gè)任務(wù)
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果 nextTab 為 null，先進(jìn)行一次初始化
// 前面我們說(shuō)了供置，外圍會(huì)保證第一個(gè)發(fā)起遷移的線(xiàn)程調(diào)用此方法時(shí)谨湘，參數(shù) nextTab 為 null
// 之后參與遷移的線(xiàn)程調(diào)用此方法時(shí)，nextTab 不會(huì)為 null
if (nextTab == null) {
try {
// 容量翻倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
// nextTable 是 ConcurrentHashMap 中的屬性
nextTable = nextTab;
// transferIndex 也是 ConcurrentHashMap 的屬性，用于控制遷移的位置
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode 翻譯過(guò)來(lái)就是正在被遷移的 Node
// 這個(gè)構(gòu)造方法會(huì)生成一個(gè)Node紧阔，key坊罢、value 和 next 都為 null，關(guān)鍵是 hash 為 MOVED
// 后面我們會(huì)看到擅耽，原數(shù)組中位置 i 處的節(jié)點(diǎn)完成遷移工作后活孩，
// 就會(huì)將位置 i 處設(shè)置為這個(gè) ForwardingNode，用來(lái)告訴其他線(xiàn)程該位置已經(jīng)處理過(guò)了
// 所以它其實(shí)相當(dāng)于是一個(gè)標(biāo)志乖仇。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// advance 指的是做完了一個(gè)位置的遷移工作憾儒，可以準(zhǔn)備做下一個(gè)位置的了
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
/*
* 下面這個(gè) for 循環(huán)，最難理解的在前面乃沙，而要看懂它們起趾，應(yīng)該先看懂后面的，然后再倒回來(lái)看
*
*/
// i 是位置索引崔涂，bound 是邊界阳掐，注意是從后往前
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 下面這個(gè) while 真的是不好理解
// advance 為 true 表示可以進(jìn)行下一個(gè)位置的遷移了
// 簡(jiǎn)單理解結(jié)局：i 指向了 transferIndex，bound 指向了 transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
// 將 transferIndex 值賦給 nextIndex
// 這里 transferIndex 一旦小于等于 0冷蚂，說(shuō)明原數(shù)組的所有位置都有相應(yīng)的線(xiàn)程去處理了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// 看括號(hào)中的代碼缭保，nextBound 是這次遷移任務(wù)的邊界，注意蝙茶，是從后往前
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// 所有的遷移操作已經(jīng)完成
nextTable = null;
// 將新的 nextTab 賦值給 table 屬性艺骂，完成遷移
table = nextTab;
// 重新計(jì)算 sizeCtl：n 是原數(shù)組長(zhǎng)度，所以 sizeCtl 得出的值將是新數(shù)組長(zhǎng)度的 0.75 倍
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 之前我們說(shuō)過(guò)隆夯，sizeCtl 在遷移前會(huì)設(shè)置為 (rs << RESIZE_STAMP_SHIFT) + 2
// 然后钳恕，每有一個(gè)線(xiàn)程參與遷移就會(huì)將 sizeCtl 加 1，
// 這里使用 CAS 操作對(duì) sizeCtl 進(jìn)行減 1蹄衷，代表做完了屬于自己的任務(wù)
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 任務(wù)結(jié)束忧额，方法退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 到這里，說(shuō)明 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT愧口，
// 也就是說(shuō)睦番，所有的遷移任務(wù)都做完了，也就會(huì)進(jìn)入到上面的 if(finishing){} 分支了
finishing = advance = true;
i = n; // recheck before commit
}
}
// 如果位置 i 處是空的耍属，沒(méi)有任何節(jié)點(diǎn)托嚣，那么放入剛剛初始化的 ForwardingNode ”空節(jié)點(diǎn)“
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 該位置處是一個(gè) ForwardingNode，代表該位置已經(jīng)遷移過(guò)了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 對(duì)數(shù)組該位置處的結(jié)點(diǎn)加鎖厚骗，開(kāi)始處理數(shù)組該位置處的遷移工作
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 頭結(jié)點(diǎn)的 hash 大于 0示启，說(shuō)明是鏈表的 Node 節(jié)點(diǎn)
if (fh >= 0) {
// 下面這一塊和 Java7 中的 ConcurrentHashMap 遷移是差不多的，
// 需要將鏈表一分為二领舰，
// 找到原鏈表中的 lastRun夫嗓，然后 lastRun 及其之后的節(jié)點(diǎn)是一起進(jìn)行遷移的
// lastRun 之前的節(jié)點(diǎn)需要進(jìn)行克隆迟螺，然后分到兩個(gè)鏈表中
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 其中的一個(gè)鏈表放在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 另一個(gè)鏈表放在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設(shè)置為 fwd，代表該位置已經(jīng)處理完畢啤月，
// 其他線(xiàn)程一旦看到該位置的 hash 值為 MOVED煮仇，就不會(huì)進(jìn)行遷移了
setTabAt(tab, i, fwd);
// advance 設(shè)置為 true劳跃，代表該位置已經(jīng)遷移完畢
advance = true;
}
else if (f instanceof TreeBin) {
// 紅黑樹(shù)的遷移
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果一分為二后谎仲，節(jié)點(diǎn)數(shù)少于 8，那么將紅黑樹(shù)轉(zhuǎn)換回鏈表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 將 ln 放置在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 將 hn 放置在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設(shè)置為 fwd刨仑，代表該位置已經(jīng)處理完畢郑诺，
// 其他線(xiàn)程一旦看到該位置的 hash 值為 MOVED，就不會(huì)進(jìn)行遷移了
setTabAt(tab, i, fwd);
// advance 設(shè)置為 true杉武，代表該位置已經(jīng)遷移完畢
advance = true;
}
}
}
}
}
}
說(shuō)到底辙诞，transfer 這個(gè)方法并沒(méi)有實(shí)現(xiàn)所有的遷移任務(wù)，每次調(diào)用這個(gè)方法只實(shí)現(xiàn)了 transferIndex 往前 stride 個(gè)位置的遷移工作轻抱，其他的需要由外圍來(lái)控制飞涂。
這個(gè)時(shí)候，再回去仔細(xì)看 tryPresize 方法可能就會(huì)更加清晰一些了祈搜。
get 過(guò)程分析
get 方法從來(lái)都是最簡(jiǎn)單的较店，這里也不例外：
- 計(jì)算 hash 值
- 根據(jù) hash 值找到數(shù)組對(duì)應(yīng)位置: (n - 1) & h
- 根據(jù)該位置處結(jié)點(diǎn)性質(zhì)進(jìn)行相應(yīng)查找
- 如果該位置為 null，那么直接返回 null 就可以了
- 如果該位置處的節(jié)點(diǎn)剛好就是我們需要的容燕，返回該節(jié)點(diǎn)的值即可
- 如果該位置節(jié)點(diǎn)的 hash 值小于 0梁呈，說(shuō)明正在擴(kuò)容，或者是紅黑樹(shù)蘸秘，后面我們?cè)俳榻B find 方法
- 如果以上 3 條都不滿(mǎn)足官卡，那就是鏈表，進(jìn)行遍歷比對(duì)即可
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) {
// 判斷頭結(jié)點(diǎn)是否就是我們需要的節(jié)點(diǎn)
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果頭結(jié)點(diǎn)的 hash 小于 0醋虏，說(shuō)明 正在擴(kuò)容寻咒，或者該位置是紅黑樹(shù)
else if (eh < 0)
// 參考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
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;
}
簡(jiǎn)單說(shuō)一句，此方法的大部分內(nèi)容都很簡(jiǎn)單颈嚼，只有正好碰到擴(kuò)容的情況毛秘，F(xiàn)orwardingNode.find(int h, Object k) 稍微復(fù)雜一些，不過(guò)在了解了數(shù)據(jù)遷移的過(guò)程后粘舟，這個(gè)也就不難了熔脂，所以限于篇幅這里也不展開(kāi)說(shuō)了。
