由于作者水平有限，如有什么錯誤點，多謝指出，
ConcurrentHashMap
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
//保存K-V 節點
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 轉為 TreeNode 節點，繼承了Node節點
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
}
//鏈表Node轉為紅黑樹，放在 陣列位置上的頭節點，本身不保存資料
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter; //等待執行緒
volatile int lockState; //鎖狀態
static final int WRITER = 1; // 寫鎖
static final int WAITER = 2; // 等待寫鎖
static final int READER = 4; // 讀鎖
}
//保存資料的陣列 2的倍數
transient volatile Node<K,V>[] table;
/*擴容時候生成的下一個陣列 */
private transient volatile Node<K,V>[] nextTable;
/*計數器 */
private transient volatile long baseCount;
/*用于控制hash表的初始化和擴容，-1：hash初始化，-1+參與擴容操作的執行緒數：用于擴容操作，正數：hash表的容量 */
private transient volatile int sizeCtl;
/*在擴容時，多執行緒競爭轉移 槽 區間時使用 */
private transient volatile int transferIndex;
/*在擴容時自旋鎖使用 */
private transient volatile int cellsBusy;
/* CounterCell hash表，如果不為空，那么肯定是2的倍數 */
private transient volatile CounterCell[] counterCells;
// 通過迭代器遍歷時候 的 幾種視圖
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;
static final int MOVED = -1; // resize時 forwarding 節點 的hash值
static final int TREEBIN = -2; // 紅黑樹根節點的hash值
static final int RESERVED = -3; // 創建 reservationNode 節點的hash值
static final int HASH_BITS = 0x7fffffff; // 正常hash用的位數
static final class ReservationNode<K,V> extends Node<K,V> {
ReservationNode() {
super(RESERVED, null, null, null);
}
}
//創建初始容量的
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
//最大容量 MAXIMUM_CAPACITY = 1<<30
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
//此時保存 hash表的最大容量
this.sizeCtl = cap;
}
//轉移操作時，如果slot沒有節點可以轉移或已經轉移成功，將在相應的slot放上這個類的物件
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;
}
}
//減少hash沖突，異或的結果繼續和HASH_BITS 與運算
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;//0x7fffffff
}
}
put
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(); //不允許放入空值
int hash = spread(key.hashCode()); //計算 hash
int binCount = 0; //記錄元素個數
for (Node<K,V>[] tab = table;;) { //回圈直到 插入成功
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)//為空 初始化 hash表
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//根據hash值找到應該保存的陣列的位置，如果沒放入，通過CAS，封裝成 Node物件放入索引位 i的位置
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
//這里，f就是找到下標位i的node元素，這時根據MOVED標志看看是陣列正在擴容還是資料遷移，如果遷移，那么呼叫helpTransfer方法幫助完成遷移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { //對f上鎖
if (tabAt(tab, i) == f) { //索引下標 i 處節點沒有被更改
if (fh >= 0) { //鏈表
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {//遍歷鏈表
K ek;
//當前與 要放入的 hash 相同
if (e.hash == hash &&
((ek = e.key) == key || //比較 地址
//比較 equals
(ek != null && key.equals(ek)))) {
oldVal = e.val; //保存找到的舊值
if (!onlyIfAbsent)//如果沒有設定 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;
}
}
}//紅黑樹操作
else if (f instanceof TreeBin) {
//紅黑樹，在 slot中放置了一個 TreeBin物件 ，然后才是根節點 所以直接設定2
Node<K,V> p;
binCount = 2;
//插入紅黑樹，如果回傳值不為空，說明紅黑樹包含了K，根據onlyIfAbsent 來決定是否覆寫原來的值
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//節點超過 TREEIFY_THRESHOLD = 8
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);//轉換為紅黑樹
if (oldVal != null)//如果發生了沖突，替換原來的值，則回傳
return oldVal;
break;
}
}
}
addCount(1L, binCount);//增加一個節點計數，看看是否需要擴容
return null;
}
initTable初始化程序
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {//回圈直到成功
if ((sc = sizeCtl) < 0)
Thread.yield();
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {//雙重判斷，避免CAS成功，但后面釋放了sc后 又有執行緒進入
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//默認16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//創建陣列
table = tab = nt;
//sc保存最大的數量，這個n是 0.75
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
addCount
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||//已經創建
//直接在baseCount 變數上計數，如果失敗進入初始化 as，
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
//初始化as
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);//創建as或者添加計數器
return;
}
if (check <= 1)//如果check<= 1 直接退出
return;
s = sumCount();//獲取當前hash表的資料量
}
if (check >= 0) {//檢查表的大小，要不要擴容
Node<K,V>[] tab, nt; int n, sc;
//s是當前資料量，大于等于 當前容量 && 陣列不為空 && 陣列小于最大容量
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n); //計算擴容時 使用的stamp
if (sc < 0) { //如果sc小于0，表明已經開始擴容
//stamp 已經改變 || 達到最大幫助resize的執行緒數 MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//nextTable 為空，擴容完畢
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//增加幫助 resize 的執行緒數
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt); //如果成功 開始擴容
}
//將 sc設定為 (rs << RESIZE_STAMP_SHIFT) + 2)
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);//開始擴容
s = sumCount(); //重新計算 資料量
}
}
}
transfer擴容
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//計算每個執行緒負責的區間，單核就單執行緒
//否則(n >>> 3) / NCPU， 最小值MIN_TRANSFER_STRIDE = 16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
if (nextTab == null) { // 初始化目標陣列
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; //2倍擴容
nextTab = nt;
} catch (Throwable ex) { // OOM例外，設定 sizeCtl 回傳
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; //設定 原來陣列的長度
}
int nextn = nextTab.length; //目標陣列長度
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); //創建轉移節點
boolean advance = true;
boolean finishing = false;
for (int i = 0, bound = 0;;) { //回圈直到擴容成功
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
//如果 尋找的區間 還沒有完成
if (--i >= bound || finishing)//如果完成遷移 那么不需要繼續前進
advance = false;
else if ((nextIndex = transferIndex) <= 0) {//沒有可分的區間了，也不需要前進
i = -1;
advance = false;
}
//原子分割區間 ：通過操作 transferIndex 變數
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
//如果可以繼續分，獲取區間的長度，否則設定0
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound; //獲得的區間
i = nextIndex - 1; //設定開始轉移的下標i為nextIndex - 1（
advance = false;
}
}
//沒有可分的區間 || i>=陣列長度 || 開始下標+n >= 擴容后的陣列長度
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { //擴容完成
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1); //重新設定sizeCtl
return;
}
//幫助執行緒數 - 1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//如果 resizeStamp 改變 直接退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // 開始下標設定為 陣列大小
}
}
//如果當前索引下標 i 處沒有存放元素，那么將其設定為 fwd = ForwardingNode
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)//節點的 hash 值為 MOVED，表示當前節點已經洗掉
advance = true;
else {
//對 頭節點上鎖 避免別的執行緒在轉移期間進行插入操作
synchronized (f) {
if (tabAt(tab, i) == f) { //如果頭節點沒有發生變化 進行轉移，否則重試
Node<K,V> ln, hn;
if (fh >= 0) { //當前節點為鏈表結構
int runBit = fh & n; //獲取當前頭節點 對原陣列長度對應 的 runBit
Node<K,V> lastRun = f; // lastRun 節點
//遍歷鏈表
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;//當前節點hash & 陣列長度
//如果當前節點的b和上一個b不同，將當前節點的b位設定位新的runBit，并且將當前節點p設定為lastRun
if (b != runBit) {
runBit = b;
lastRun = p;
}
}//runBit = 0，將 lastRun保存 ln
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {//到否則保存 hn
hn = lastRun;
ln = null;
}
//從頭節點開始遍歷，直到 找到 lastRun節點
for (Node<K,V> p = f; p != lastRun; p = p.next) {
//當前節點的 hash key val
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)//如果 為0 ，那么連接到 ln中
ln = new Node<K,V>(ph, pk, pv, ln);
else//否則 hn中
hn = new Node<K,V>(ph, pk, pv, hn);
}
//ln放入 nextTab 的原理index位置
setTabAt(nextTab, i, ln);
//hn放入 i + n
setTabAt(nextTab, i + n, hn);
//鏈表已轉移 用 fwd 來補填原來的位置
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {//紅黑樹的情況
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;//lo 頭節點和 loTail尾節點
TreeNode<K,V> hi = null, hiTail = null;//h 的
int lc = 0, hc = 0;
//從第一個節點開始遍歷 生成 lo ho 兩個鏈表
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash; //當前節點的 hash值
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {// 為0 的情況 lo鏈表
//將loTail賦值給 prev，如果當前為null，將當前p節點作為lo頭節點
if ((p.prev = loTail) == null)
lo = p;
else// 否則通過 next 變數來構造雙向鏈表
loTail.next = p;
loTail = p;
++lc;
}
else {//hi 鏈表
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
//類似于鏈表 多了判斷是否 要不要轉回鏈表
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);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
helpTransfer方法
多執行緒幫助resize
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//陣列不為空 && f ForwardingNode && nextTab不為空
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length); // 保存 rs
//在轉移程序中 && 原陣列未 改變 && 仍在進行轉移
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
//如果 sc 已經改變 幫助轉移執行緒已達最大 沒有可以獲取的幫助區間 拜拜
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
//CAS 增加幫助執行緒數量 開始幫助
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
treeifyBin
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
//陣列長度 <64 的時候 resize
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {// 嘗試將鏈表轉化為紅黑樹
synchronized (b) { //上鎖
if (tabAt(tab, index) == b) {//當前slot 節點仍未改變
TreeNode<K,V> hd = null, tl = null;
//遍歷整個鏈表 生成TreeNode
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;
}
// 創建紅黑樹 并將TreeBin節點放到 陣列上
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
remove洗掉
public V remove(Object key) {
return replaceNode(key, null, null);
}
// 將節點值替換為v，如果cv非空，則將cv匹配為條件， 如果結果值為空，則洗掉，
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode()); //計算hash
for (Node<K,V>[] tab = table;;) { //回圈
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 || //陣列長度
(f = tabAt(tab, i = (n - 1) & hash)) == null) //要洗掉的 k 存在不存在
break;
else if ((fh = f.hash) == MOVED) //如果正在擴容遷移陣列，那么幫助
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) { //查找下標 i處節點有沒有發生變化
if (fh >= 0) { //鏈表結構
validated = true;
//遍歷鏈表
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash && //當前節點的hash值 與 要洗掉的 相同
((ek = e.key) == key || //地址相同或者 equals 判斷相同
(ek != null && key.equals(ek)))) {
V ev = e.val;
//cv 為空 比較值 和當前 地址相同 再通過equals方法判斷
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev; //保存替換掉的值
if (value != null) //替換原來的 V 為空不替換
e.val = value;
else if (pred != null) //洗掉時 前一個節點是不是根節點
pred.next = e.next;
else//前一個節點為頭節點 直接替換原來的頭節點
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;//轉為 TreeBin
TreeNode<K,V> r, p;
//根節點 找到要洗掉節點
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val; //獲取 val
//如果 cv 為空 如上述一樣
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));
}
}
}
}
}
//如果替換或洗掉的K在hash表中存在
if (validated) {
if (oldVal != null) { //如果找到了替換掉的值
if (value == null) //洗掉節點
addCount(-1L, -1); //減少節點計數
return oldVal;
}
break;
}
}
}
return null;
}
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()); //計算hash
//陣列檢查
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//通過hash 比較
if ((eh = e.hash) == h) {
//通過地址和 equals 比較
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val; //找到回傳它
}
else if (eh < 0)
// 呼叫 find 查找
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/392093.html
標籤：java