重要參數(shù)
// 散列表最大值
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 負(fù)載因子，負(fù)責(zé)計(jì)算擴(kuò)容閾值
private static final float LOAD_FACTOR = 0.75f;
// 樹(shù)化閾值
static final int TREEIFY_THRESHOLD = 8;
// 非樹(shù)化的閾值
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹(shù)化容量，散列表的容量達(dá)到 64 且鏈表長(zhǎng)度達(dá)到 8 的時(shí)候才可以進(jìn)行樹(shù)化
static final int MIN_TREEIFY_CAPACITY = 64;
// 每個(gè)線程遷移數(shù)據(jù)時(shí)，桶位的最小步長(zhǎng)
private static final int MIN_TRANSFER_STRIDE = 16;
// 擴(kuò)容的標(biāo)識(shí)戳
private static final int RESIZE_STAMP_BITS = 16;
// 最大線程數(shù)量 65535
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 正在遷移數(shù)據(jù) ForwardingNode 用到
static final int MOVED = -1;
// 樹(shù)化結(jié)構(gòu)
static final int TREEBIN = -2;
// 0x7fffffff 相當(dāng)于 31個(gè)1 在與負(fù)數(shù)進(jìn)行按位與運(yùn)算時(shí)會(huì)得到一個(gè)正數(shù)
static final int HASH_BITS = 0x7fffffff
// 裝載數(shù)據(jù)的桶
transient volatile Node<K,V>[] table;
// 擴(kuò)容過(guò)程中使用的數(shù)組，擴(kuò)容結(jié)束后指向 NULL,會(huì)賦值給 ForwardingNode
private transient volatile Node<K,V>[] nextTable;
// 當(dāng)數(shù)組未發(fā)生競(jìng)爭(zhēng)或者數(shù)組中要修改的位置被其他線程正在修改時(shí)，將要修改的值記錄到 baseCount 中
private transient volatile long baseCount;
// 表示當(dāng)前是否有其他線程正在操作數(shù)組，通過(guò)循環(huán)和 CAS 來(lái)修改 cellsBusy 的值來(lái)表示鎖，1 代表被上鎖，0 代表無(wú)鎖狀態(tài)
private transient volatile int cellsBusy;
// LongAdder 中的 cells 數(shù)組，當(dāng) BaseCount 發(fā)生競(jìng)爭(zhēng)后，會(huì)創(chuàng)建 Cells 數(shù)組。線程會(huì)通過(guò) hash 值取到自己的 cell. 將增量累加到指定的 cell 中?？倲?shù)
private transient volatile CounterCell[] counterCells;
// 表示 table 的狀態(tài)
// -1 表示當(dāng)前的 table 正在初始化
// sizeCtl!=-1 && sizeCtl<0 時(shí) 表示正在擴(kuò)容，高 16 位表示擴(kuò)容的標(biāo)識(shí)戳，低 16 位表示有多少個(gè)線程正在參與擴(kuò)容
// 0 表示創(chuàng)建 table 時(shí)使用 default capacity
// 大于 0 時(shí)：
// 如果 table 未初始化化，表示要初始化的大小
// 如果 table 已經(jīng)初始化，表示下一次要擴(kuò)容的閾值
private transient volatile int sizeCtl
// Node 節(jié)點(diǎn)，可以形成單向鏈表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;}
// 重定向節(jié)點(diǎn)，擴(kuò)容時(shí)使用，指向擴(kuò)容后的 table
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
// native 層對(duì)應(yīng)的地址的偏移 因?yàn)?CAS 是一個(gè) Native 的操作，Java 層要知道取那段內(nèi)存表示 native 層對(duì)應(yīng)的值
private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final int ABASE;
private static final int ASHIFT;
static {
try {
SIZECTL = U.objectFieldOffset
(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(ConcurrentHashMap.class.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
CELLVALUE = U.objectFieldOffset
(CounterCell.class.getDeclaredField("value"));
ABASE = U.arrayBaseOffset(Node[].class);
int scale = U.arrayIndexScale(Node[].class);
if ((scale & (scale - 1)) != 0)
throw new Error("array index scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
}.....
}
Spread 函數(shù)再 hash
使用擾動(dòng)函數(shù)對(duì) hash 值進(jìn)行重新的計(jì)算，讓高 16 位參通過(guò)異或算法（不同返回1）參與到 hash 的計(jì)算中，讓 hash 值更散列。不經(jīng)過(guò)擾動(dòng)函數(shù)處理 hash 值，在數(shù)組比較小的時(shí)候，會(huì)只有低 16 位參與到計(jì)算，散列程度不夠，容易發(fā)生碰撞
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
計(jì)算擴(kuò)容標(biāo)識(shí)
只有當(dāng)擴(kuò)容標(biāo)識(shí)一致時(shí)，其他線程才可以參與擴(kuò)容
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
tableSizeOf
返回傳入數(shù)字的最小的 2 的平方數(shù)
- 傳入 7 返回 8
- 傳入 16 返回 16
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
put 操作
put 函數(shù)是通過(guò)自旋和 CAS 方式實(shí)現(xiàn)的。
- 首先判斷數(shù)組容器是否初始化了，如果沒(méi)有進(jìn)行初始化
- 如果當(dāng)前插入位置沒(méi)有元素，在當(dāng)前位置插入元素
- 如果當(dāng)前位置是 FWD 節(jié)點(diǎn)參與擴(kuò)容
- 如果當(dāng)前位置有元素，如果是鏈表且沒(méi)有重復(fù)插入在尾部，如果重復(fù)了進(jìn)行替換
- 如果插入位置是樹(shù)，如果重復(fù)了同樣進(jìn)行替換
- 插入后，如果插入的位置達(dá)到了樹(shù)化閾值，進(jìn)行擴(kuò)容
- 插入后，如果達(dá)到了擴(kuò)容閾值，進(jìn)行擴(kuò)容
final V putVal(K key, V value, boolean onlyIfAbsent) {
// ConcurrentHashMap 插入的 key 和 value 不能為空
if (key == null || value == null) throw new NullPointerException();
// 對(duì) key 的 hash 值進(jìn)行擾動(dòng)，讓 hash 值更散列
int hash = spread(key.hashCode());
// 插入的節(jié)點(diǎn)在 鏈表 中的位置
int binCount = 0;
// tab 持有了 table，也就是 ConcurrentHashMap 數(shù)組的引用
for (Node<K,V>[] tab = table;;) {
// f 表示頭結(jié)點(diǎn)
// n 表示數(shù)組的長(zhǎng)度
// i 表示 index，要插入的位置
// fh 表示節(jié)點(diǎn)處理后的 hash 值
Node<K,V> f; int n, i, fh;
// Case 1: 第一次插入，先初始化數(shù)組，懶加載的方式
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// Case 2: 如果插入位置的頭結(jié)點(diǎn)是 null，也就是當(dāng)前位置還沒(méi)有元素，直接插入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果在這個(gè)位置通過(guò) CAS 插入成功了，終止循環(huán)，
// 如果返回 false 代表有其他線程先一步在這里插入了，繼續(xù)自旋，嘗試重新插入
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// Case 3:如果當(dāng)前是 Forward 節(jié)點(diǎn)，代表正在擴(kuò)容，協(xié)助擴(kuò)容，F(xiàn)orward 節(jié)點(diǎn)的 hash 值固定是 MOVED （-2）
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// Case 4:如果是樹(shù)或者鏈表
else {
// 記錄舊節(jié)點(diǎn)，在節(jié)點(diǎn)重復(fù)時(shí)使用
V oldVal = null;
// 鎖住修改桶位的頭結(jié)點(diǎn)。
synchronized (f) {
// 確保沒(méi)有其他線程修改了頭結(jié)點(diǎn)，導(dǎo)致鎖加錯(cuò)
if (tabAt(tab, i) == f) {
// hash 值大于 0 表示該節(jié)點(diǎn)沒(méi)有在擴(kuò)容
if (fh >= 0) {
// 記錄桶的元素個(gè)數(shù)
binCount = 1;
// 遍歷當(dāng)前位置的所有節(jié)點(diǎn)
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果插入的元素一致，進(jìn)行替換
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 如果沒(méi)有重復(fù)，作為尾節(jié)點(diǎn)插入
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果是樹(shù) 按照樹(shù)的方式進(jì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) {
// 如果修改位置的元素長(zhǎng)度達(dá)到了 樹(shù)化閾值(一定是鏈表),進(jìn)行樹(shù)化
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 插入元素后，判斷桶的長(zhǎng)度是否達(dá)到了擴(kuò)容閾值
addCount(1L, binCount);
return null;
}
初始化數(shù)組
private final Node<K,V>[] initTable() {
// tab 表示 ConcurrentHashMap 的數(shù)組
// sc 表示 sizeCtl
// -1 表示正在被其他線程初始化
// <0 表示正在被擴(kuò)容
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 當(dāng)前線程沒(méi)有爭(zhēng)搶都初始化鎖，繼續(xù)自旋
if ((sc = sizeCtl) < 0)
// 讓出一下 cpu
Thread.yield(); // lost initialization race; just spin
// 嘗試爭(zhēng)搶鎖 通過(guò) CAS 的方式將 sizeCtl 修改成為 -1，
// 修改成功代表獲取鎖成功，修改失敗繼續(xù)自旋
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// 如果 sc > 0 使用 sc 的值進(jìn)行初始化
// 如果 sc == 0 使用 默認(rèn)容量進(jìn)行初始化
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 計(jì)算下一次擴(kuò)容的值
// 向右移動(dòng) 4 位，代表除以 4
// n - (1/4n) = 3/4n = 0.75n
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
統(tǒng)計(jì)散列表中元素個(gè)數(shù)以及數(shù)組擴(kuò)容
addCount 函數(shù)上半段表示統(tǒng)計(jì)散列表中元素個(gè)數(shù) 通過(guò) CellCounter 來(lái)實(shí)現(xiàn)。下半段為擴(kuò)容函數(shù)
- 采用了CAS+BaseCount+自旋鎖的方式
- 當(dāng)沒(méi)有發(fā)生爭(zhēng)搶時(shí)，就將當(dāng)前線程記錄的數(shù)值累加到 baseCount 上
- 如果發(fā)生了爭(zhēng)搶，就將值寫到當(dāng)前線程在 Cells 數(shù)組對(duì)應(yīng)的位置上
- 在計(jì)算元素總和時(shí)，將 Cells 數(shù)組中的值和 BaseCount 進(jìn)行累加
- 通過(guò) CAS 修改 sizeCtl 的結(jié)果，判斷是否滿足擴(kuò)容條件。
- 如果是第一個(gè)擴(kuò)容線程，需要準(zhǔn)備一個(gè)新的數(shù)組
- 如果是參與擴(kuò)容的線程，需要傳遞擴(kuò)容后的數(shù)組來(lái)參與擴(kuò)容
// 計(jì)算散列表中元素的個(gè)數(shù)，如果達(dá)到擴(kuò)容閾值，進(jìn)行擴(kuò)容
private final void addCount(long x, int check) {
// as 當(dāng)前線程經(jīng)經(jīng)過(guò)尋址計(jì)算后在數(shù)組對(duì)應(yīng)位置存儲(chǔ)值
// b baseCount 在沒(méi)有發(fā)生競(jìng)爭(zhēng)時(shí)，值保存在 baseCount 中
// s 表示當(dāng)前散列表中的元素
CounterCell[] as; long b, s;
// 條件1 counterCells 已經(jīng)創(chuàng)建好了
// 條件2 U.compareAndSwapLong 更新 base 失敗了，表示有其他線程修改過(guò)了，發(fā)生了競(jìng)爭(zhēng)，取反后表示 false 進(jìn)入循環(huán)
// 注意 這里是或關(guān)系，滿足一個(gè)條件就進(jìn)入循環(huán)
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 當(dāng)前線程在 CounterCell 中對(duì)應(yīng)的元素
// v 更新的值
// m Cells 數(shù)組的元素個(gè)數(shù)
CounterCell a; long v; int m;
// 是否沒(méi)有競(jìng)爭(zhēng)
boolean uncontended = true;
// 條件1 as == null || (m = as.length - 1) < 0
// true 表示當(dāng)前線程是通過(guò)寫 base 競(jìng)爭(zhēng)失敗進(jìn)入的循環(huán)
// 條件2 a = as[ThreadLocalRandom.getProbe() & m]) == null
// true 表示當(dāng)前線程所對(duì)應(yīng)的位置沒(méi)有存儲(chǔ)值
// 條件3 !(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
// true 表示當(dāng)前線程更新對(duì)應(yīng)位置的值失敗，發(fā)生了競(jìng)爭(zhēng)關(guān)系
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
// 因?yàn)?fullAddCount 是很耗時(shí)的方法，后面是擴(kuò)容方法，所以在這里就直接返回，不參與擴(kuò)容操作了
return;
}
if (check <= 1)
return;
// 獲取當(dāng)前散列表中元素的個(gè)數(shù)，是一個(gè)期望值。是一個(gè)最終一致性的。
s = sumCount();
}
// 表示是 put 操作調(diào)用的 addCount 操作
if (check >= 0) {
// 進(jìn)行擴(kuò)容
// tab: map 的散列表數(shù)組
// n: 散列表元素的個(gè)數(shù)
// sc:sizeCtl: 表示當(dāng)前是否正在擴(kuò)容
Node<K,V>[] tab, nt; int n, sc;
// True 表示可以擴(kuò)容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 計(jì)算一個(gè)擴(kuò)容標(biāo)志，當(dāng)其他線程加入時(shí)使用
int rs = resizeStamp(n);
// sizeCtl 小于0 表示當(dāng)前正在擴(kuò)容，判斷是否可以加入擴(kuò)容過(guò)程中
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))
// 協(xié)助擴(kuò)容 帶有 nexttable
transfer(tab, nt);
}
// 第一個(gè)擴(kuò)容的線程
// sizeCtl 大于 0 表示達(dá)到了擴(kuò)容閾值，可以擴(kuò)容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 第一個(gè)擴(kuò)容的線程
transfer(tab, null);
s = sumCount();
}
}
}
數(shù)據(jù)遷移 Transfer
- 擴(kuò)容時(shí)會(huì)計(jì)算擴(kuò)容的步長(zhǎng)，就是每個(gè)線程負(fù)責(zé)桶位哪個(gè)區(qū)間的擴(kuò)容
- 然后通過(guò)自旋加 CAS 的方式更新節(jié)點(diǎn)
- 如果當(dāng)前節(jié)點(diǎn)沒(méi)有元素，就在原表中該位置處插入一個(gè) FWD 的節(jié)點(diǎn)
- 如果當(dāng)前節(jié)點(diǎn)是一個(gè)鏈表，會(huì)將該鏈表分為高位鏈表和低位鏈表（高位鏈表和新數(shù)組長(zhǎng)度相與后是 1 ，低位相與后是 0 ），然后通過(guò) CAS 的方式將低位鏈表放到新數(shù)組中，位置不變
- 高位鏈表放到原位置加上原數(shù)組長(zhǎng)度的位置處，并將原數(shù)組對(duì)應(yīng)位置更新為 FWD 節(jié)點(diǎn)
- 如果是樹(shù)，同樣區(qū)分為高低位節(jié)點(diǎn)，移動(dòng)到新數(shù)組中，并且檢查是否可以退化為鏈表
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
// n 原數(shù)組的長(zhǎng)度
// stride:步長(zhǎng)，表示每個(gè)數(shù)據(jù)負(fù)責(zé)遷移一段數(shù)據(jù)區(qū)間的長(zhǎng)度
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果是第一個(gè)擴(kuò)容的線程，創(chuàng)建一個(gè)新表
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
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 = nextTab;
// 記錄擴(kuò)容進(jìn)度的線程
transferIndex = n;
}
// 新表長(zhǎng)度
int nextn = nextTab.length;
// 重定向節(jié)點(diǎn)，記錄新表的位置，當(dāng)有其他線程訪問(wèn)正在擴(kuò)容的節(jié)點(diǎn)時(shí)，會(huì)直接通過(guò) FWD 去訪問(wèn)新表
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 推進(jìn)標(biāo)記
boolean advance = true;
// 完成標(biāo)記
boolean finishing = false; // to ensure sweep before committing nextTab
// i 表示當(dāng)前線程正在處理第幾個(gè)位置
// bound 表示處理的上限，達(dá)到上限（也就是步長(zhǎng)指定的位置就不能繼續(xù)處理了）
// 自旋的操作
for (int i = 0, bound = 0;;) {
// f 當(dāng)前桶位的頭結(jié)點(diǎn)
// fh hash 值
Node<K,V> f; int fh;
// 1 給當(dāng)前線程分配任務(wù)區(qū)間
// 2 維護(hù)任務(wù)的進(jìn)度
while (advance) {
// nextIndex 任務(wù)開(kāi)始下標(biāo)
// nextBound 任務(wù)結(jié)束下標(biāo)
int nextIndex, nextBound;
// 表示當(dāng)前線程還有任務(wù)沒(méi)有處理完,
// --i>= bound 就是當(dāng)前要處理的下一個(gè)任務(wù)還沒(méi)有達(dá)到邊界
if (--i >= bound || finishing)
advance = false;
// 表示還沒(méi)有分配任務(wù)區(qū)間
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// 根據(jù)步長(zhǎng)分配任務(wù)區(qū)間
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 擴(kuò)容完畢
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// sc - 1 表示擴(kuò)容讓 sizeCtl 的記錄擴(kuò)容線程數(shù) -1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 如果當(dāng)前線程不是最后一個(gè)退出的線程，直接退出循環(huán)
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 是最后一個(gè)退出的線程，重新檢查一遍數(shù)組
finishing = advance = true;
i = n; // recheck before commit
}
}
// 進(jìn)行擴(kuò)容
// 條件1：當(dāng)前節(jié)點(diǎn)沒(méi)有要遷移的元素，直接在該位置添加 FWD 節(jié)點(diǎn)
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 如果當(dāng)前節(jié)點(diǎn)已經(jīng)在遷移中，繼續(xù)遷移
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 給頭結(jié)點(diǎn)加鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
// ln 表示低位節(jié)點(diǎn)
// hn 表示高位節(jié)點(diǎn)
Node<K,V> ln, hn;
if (fh >= 0) {
// 使用 runBit 來(lái)區(qū)分高位節(jié)點(diǎn)和低位節(jié)點(diǎn)
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;
}
}
// 低位節(jié)點(diǎn)相與后是 0
if (runBit == 0) {
ln = lastRun;
hn = null;
}
// 高位節(jié)點(diǎn)相與后是 1
else {
hn = lastRun;
ln = null;
}
// 構(gòu)建 ln 和 hn
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);
}
// 將低位鏈表放回原來(lái)的位置
setTabAt(nextTab, i, ln);
// 高位鏈表放到原來(lái)位置加上原來(lái)表長(zhǎng)度的位置上
setTabAt(nextTab, i + n, hn);
// 將舊表的位置改為 FWD 節(jié)點(diǎn)。
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
// lo 低位鏈頭節(jié)點(diǎn) loTail 低位鏈尾結(jié)點(diǎn)
TreeNode<K,V> lo = null, loTail = null;
// hi 高位鏈頭結(jié)點(diǎn) hiTail 高位鏈尾節(jié)點(diǎn)
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
// 遍歷樹(shù)的所有節(jié)點(diǎn)
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);
// 構(gòu)建低位節(jié)點(diǎn)
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
// 構(gòu)建高位節(jié)點(diǎn)
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 檢查高位和低位節(jié)點(diǎn)是否可以轉(zhuǎn)變?yōu)殒湵? 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;
// 在新表中原位置插入低位鏈表
setTabAt(nextTab, i, ln);
// 在新表的原位置加上鏈表長(zhǎng)度處加上高位節(jié)點(diǎn)
setTabAt(nextTab, i + n, hn);
// 將該節(jié)點(diǎn)在原表處設(shè)置為 Forward 節(jié)點(diǎn)
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
參與擴(kuò)容 helpTransfer
- 參與擴(kuò)容時(shí)首先會(huì)判斷當(dāng)前是否已經(jīng)擴(kuò)容完成了
- 當(dāng)前參與的線程沒(méi)有達(dá)到最大并發(fā)數(shù)
- 當(dāng)前要遷移的元素沒(méi)有被分配完
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 如果更新成功，就將擴(kuò)容線程數(shù)+1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 將新表傳遞進(jìn)去參與擴(kuò)容
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
獲取元素 get
public V get(Object key) {
// e 頭結(jié)點(diǎn)
// p 目標(biāo)節(jié)點(diǎn)
// n 是當(dāng)前數(shù)組長(zhǎng)度
// eh e的hash 值
// ek 當(dāng)前節(jié)點(diǎn)的 key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// 如果 table 已經(jīng)初始化了，key 所對(duì)應(yīng)的位置有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 如果頭節(jié)點(diǎn)的 hash 值和內(nèi)容符合要求，返回頭結(jié)點(diǎn)對(duì)應(yīng)的 value
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果當(dāng)前節(jié)點(diǎn)正在擴(kuò)容，向新數(shù)組中去查找
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 如果頭節(jié)點(diǎn)是一個(gè)鏈表，遍歷鏈表查找對(duì)應(yīng)的元素
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ForwardingNode 的 find 方法
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer:
// e = tabAt(tab, (n - 1) & h)) 在新表中重新進(jìn)行尋址，找到對(duì)應(yīng)位置的頭節(jié)點(diǎn)
for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {
int eh; K ek;
// 如果新表命中直接返回對(duì)應(yīng)的元素
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {
// 如果是一個(gè) forward 節(jié)點(diǎn)，繼續(xù)去新表中查詢
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
// 去 TreeBin 中查詢
else
return e.find(h, k);
}
// 如果是鏈表繼續(xù)遍歷
if ((e = e.next) == null)
return null;
}
}
}
刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)實(shí)際上是節(jié)點(diǎn)的替換
public V remove(Object key) {
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
// 進(jìn)行尋址
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
// f 頭結(jié)點(diǎn) n 數(shù)組長(zhǎng)度 i 目標(biāo)元素下表 fh 頭結(jié)點(diǎn)的hash值
Node<K,V> f; int n, i, fh;
// case1 tab 尚未初始化
// case2 當(dāng)前位置沒(méi)有元素
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// 如果當(dāng)前正在擴(kuò)容，需要參與到擴(kuò)容過(guò)程中
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 加鎖是否成功的標(biāo)識(shí)
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// 加鎖成功
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
// 如果頭節(jié)點(diǎn)命中
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
// 如果 cv 傳入的是 null 就是一個(gè)刪除操作
// 如果 cv == ev 就是一個(gè)替換操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 記錄移除的值
oldVal = ev;
// 如果傳入 value 不是 null 進(jìn)行替換
if (value != null)
e.val = value;
// 刪除操作
else if (pred != null)
// 非頭結(jié)點(diǎn) 刪除節(jié)點(diǎn)前一個(gè)指向刪除節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)
pred.next = e.next;
else
// 頭結(jié)點(diǎn)
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
// 刪除成功計(jì)數(shù)減1
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
