ConcurrentHashMap源码剖析（1.8版本）
生活随笔
收集整理的這篇文章主要介紹了
ConcurrentHashMap源码剖析（1.8版本）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
目錄
- ConcurrentHashMap源碼剖析
- 數據結構
- Node
- ForwardingNode
- TreeNode
- TreeBin
- 核心成員
- 核心函數
- ConcurrentHashMap(int initialCapacity)
- initTable
- put
- get
- treeifyBin
- tryPresize
- transfer
- addCount
- 數據結構
ConcurrentHashMap源碼剖析
基于jdk1.8。
參考文章：
https://yq.aliyun.com/articles/36781
http://blog.csdn.net/u012834750/article/details/71536618
數據結構
僅列出最重要的代碼片段
Node
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;volatile V val;volatile Node<K,V> next;/*** 子類中重寫了這個方法，這里的find實現了在鏈表中查找hash值等于h且key等于k的節點*/Node<K,V> find(int h, Object k) {Node<K,V> e = this;if (k != null) {do {K ek;if (e.hash == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;} while ((e = e.next) != null);}return null;}}ForwardingNode
/*** A node inserted at head of bins during transfer operations.*/// 并不是我們傳統的包含key-value的節點，只是一個標志節點，并且指向nextTable，提供find方法而已。生命周期：僅存活于擴容操作且bin不為null時，一定會出現在每個bin的首位。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;}Node<K,V> find(int h, Object k) {// loop to avoid arbitrarily deep recursion on forwarding nodesouter: 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)// 頭結點存在e中return null;for (;;) {// 檢查頭結點是否為要找的nodeint eh; K ek;if ((eh = e.hash) == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;// 如果頭結點不是要找的節點if (eh < 0) {// 頭結點hash值小于0// 如果頭結點是ForwardingNode，那么繼續下一個ForwardingNode的find邏輯if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;continue outer;}// 如果頭結點不是ForwardingNode，就進行相應的find邏輯elsereturn e.find(h, k);}// 查找到尾部仍然沒有找到對應的nodeif ((e = e.next) == null)return null;}}}}TreeNode
紅黑樹中的節點類，值得注意的是：TreeNode可用于構造雙向鏈表，Node包含next成員，同時，TreeNode加入了prev成員。
static final class TreeNode<K,V> extends Node<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next,TreeNode<K,V> parent) {super(hash, key, val, next);this.parent = parent;}Node<K,V> find(int h, Object k) {return findTreeNode(h, k, null);}final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {if (k != null) {TreeNode<K,V> p = this;do {int ph, dir; K pk; TreeNode<K,V> q;TreeNode<K,V> pl = p.left, pr = p.right;if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;else if ((pk = p.key) == k || (pk != null && k.equals(pk)))return p;// hash值相等，key不等，左子樹不存在，搜索右子樹else if (pl == null)p = pr;// hash值相等，key不等，右子樹不存在，搜索左子樹else if (pr == null)p = pl;/** comparableClassFor的作用是:* 如果k實現了Comparable接口，返回k的Class,* 否則返回null。* compareComparables的作用是：* 將k與pk做比較* 如果TreeNode的Key可以作比較，就可以繼續在樹中搜索*/else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;// 由于hash相等，key無法做比較，因此先在右子樹中找else if ((q = pr.findTreeNode(h, k, kc)) != null)return q;// 右子樹沒有找到，繼續從當前的節點的左子樹中找elsep = pl;} while (p != null);}return null;}}TreeBin
TreeBin封裝了紅黑樹的邏輯，有關紅黑樹, 可以參考的資料有《Algorithm》網站 以及 中文翻譯
也可以試玩Red/Black Tree Visualization 。
附文章中提到的紅黑樹旋轉的動圖與TreeBin中的rotateLeft、rotateRight代碼片段幫助理解。
左旋：
對應代碼
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> r, pp, rl;// p是圖中的E節點，r是圖中的S節點if (p != null && (r = p.right) != null) {if ((rl = p.right = r.left) != null)rl.parent = p;// p是根節點，則根節點需要變化if ((pp = r.parent = p.parent) == null)(root = r).red = false;// p不是根節點，如果p是pp的左節點，就更新pp的leftelse if (pp.left == p)pp.left = r;elsepp.right = r;// 把p放在左子樹中r.left = p;p.parent = r;}return root;}右旋：
對應代碼
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> l, pp, lr;// p是途中的S，l是圖中的Eif (p != null && (l = p.left) != null) {if ((lr = p.left = l.right) != null)lr.parent = p;// p是根節點，則根節點需要變化if ((pp = l.parent = p.parent) == null)(root = l).red = false;else if (pp.right == p)pp.right = l;elsepp.left = l;l.right = p;p.parent = l;}return root;}僅列出Treebin數據成員以及部分方法：
// 維護了一個紅黑樹 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;/*** 返回匹配的node或者沒有匹配的就返回null. 在樹中從根節點開始比較，* 當鎖不可用的時候進行線性搜索*/final Node<K,V> find(int h, Object k) {if (k != null) {for (Node<K,V> e = first; e != null; ) {int s; K ek;// 鎖不可用，lockState包含了WAITER或者WRITER標志位if (((s = lockState) & (WAITER|WRITER)) != 0) {if (e.hash == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;e = e.next;}// 鎖可用，當前對象設置為READER狀態else if (U.compareAndSwapInt(this, LOCKSTATE, s,s + READER)) {TreeNode<K,V> r, p;try {// 在樹中查找匹配的節點p = ((r = root) == null ? null :r.findTreeNode(h, k, null));} finally {Thread w;// 取消當前鎖的READER狀態if (U.getAndAddInt(this, LOCKSTATE, -READER) ==(READER|WAITER) && (w = waiter) != null)LockSupport.unpark(w);}return p;}}}return null;}// 尋找或者添加一個節點final TreeNode<K,V> putTreeVal(int h, K k, V v) {Class<?> kc = null;boolean searched = false;for (TreeNode<K,V> p = root;;) {int dir, ph; K pk;// 紅黑樹是空，直接插入到根節點if (p == null) {first = root = new TreeNode<K,V>(h, k, v, null, null);break;}// 根據hash值設置標記位else if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;// hash值相同，并且k與pk相等（equals），直接返回else if ((pk = p.key) == k || (pk != null && k.equals(pk)))return p;// hash相同，p與pk不equals，但是按照比較接口發現p與pk相等else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {TreeNode<K,V> q, ch;searched = true;if (((ch = p.left) != null &&(q = ch.findTreeNode(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.findTreeNode(h, k, kc)) != null))return q;}// 根據一種確定的規則來進行比較，至于規則本身具體是什么病不重要dir = tieBreakOrder(k, pk);}// 程序運行到這里，說明當前節點不匹配，但子樹中可能會有匹配的NodeTreeNode<K,V> xp = p;// 根據大小關系移動p到左子樹或者右子樹// 如果滿足p為null，則說明樹中沒有節點能與之匹配，應當在p位置插入新節點，然后維護紅黑樹的性質if ((p = (dir <= 0) ? p.left : p.right) == null) {TreeNode<K,V> x, f = first;first = x = new TreeNode<K,V>(h, k, v, f, xp);if (f != null)f.prev = x;if (dir <= 0)xp.left = x;elsexp.right = x;// 優先將新節點染為紅色if (!xp.red)x.red = true;else {lockRoot();try {root = balanceInsertion(root, x);} finally {unlockRoot();}}break;}}assert checkInvariants(root);return null;} }// 紅黑樹的平衡插入 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {x.red = true; // 將x染成紅色for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {// 根節點必須是黑色if ((xp = x.parent) == null) {x.red = false;return x;}// 父節點是黑色或者父節點是根節點// 總之父節點是黑色，那么不會違反紅黑樹性質// 不需要調整結構，直接返回根節點即可else if (!xp.red || (xpp = xp.parent) == null)return root;// 父節點是紅色（需要調整），且在祖父節點的左子樹中if (xp == (xppl = xpp.left)) {// 因為父節點為紅色，所以xppr必須是紅色或空，不可能是黑色// 祖父節點的右節點為紅色if ((xppr = xpp.right) != null && xppr.red) {/*** 黑 紅* / \ （染色后） / \* 紅 紅 -> 黑 黑* / /* 紅 紅* * 可見通過調整顏色后，子樹不需要旋轉就可以滿足紅黑樹的性質* 但由于xpp變成了紅色，有可能違反紅黑樹性質，仍然需要向上調整*/xppr.red = false;xp.red = false;xpp.red = true;x = xpp;}// xppr是空else {/*** 黑* /* 紅 * \* 紅*/if (x == xp.right) {/*** 進行左旋操作，變為以下形式，* 可以看出此時任然違反紅黑樹的性質，* 然而x仍然指向了最下面沖突的紅色節點，* 此處僅僅調整了樹的形狀** 黑* /* 紅* /* 紅*/root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}/** 由于調整了樹的形狀，因此此時樹一定長成這個樣子* * 黑* /* 紅* /* 紅* * 在染色并右旋之后，變為* * 黑* / \* 紅 紅*/if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateRight(root, xpp);}}}}// x在祖父節點的右子樹中，這種情況與x在祖父節點左子樹中類似，因此不多作解釋，不明白的話類比即可。else {/*** 黑 紅* / \ (染色后) / \* 紅 紅 -> 黑 黑* \ \* 紅 紅色*/if (xppl != null && xppl.red) {xppl.red = false;xp.red = false;xpp.red = true;x = xpp;}else {if (x == xp.left) {root = rotateRight(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateLeft(root, xpp);}}}}}}核心成員
// ForwardingNode的hash值都是-1static final int MOVED = -1; // Treebin的hash值是-1static final int TREEBIN = -2; /*** 在第一次insert的時候才進行初始化(延遲初始化)* Size總是2的冪. 直接通過迭代器訪問.*/transient volatile Node<K,V>[] table;// nextTable的用途：只有在擴容時是非空的private transient volatile Node<K,V>[] nextTable;/*** Base counter value, used mainly when there is no contention,* but also as a fallback during table initialization* races. Updated via CAS.*/private transient volatile long baseCount;/*** sizeCtl是控制標識符，不同的值表示不同的意義。* -1代表正在初始化； * -(1+有效擴容線程的數量)，比如，-N 表示有N-1個線程正在進行擴容操作；* 0 表示還未進行初始化* 正數代表初始化或下一次進行擴容的大小，類似于擴容閾值。它的值始終是當前ConcurrentHashMap容量的0.75倍，這與loadfactor是對應的。實際容量>=sizeCtl，則擴容。*/private transient volatile int sizeCtl;// 擴容的時候，next數組下標+1private transient volatile int transferIndex;/*** Spinlock (locked via CAS) used when resizing and/or creating CounterCells.*/private transient volatile int cellsBusy;/*** Table of counter cells. When non-null, size is a power of 2.*/private transient volatile CounterCell[] counterCells;// 視圖private transient KeySetView<K,V> keySet;private transient ValuesView<K,V> values;private transient EntrySetView<K,V> entrySet;核心函數
ConcurrentHashMap(int initialCapacity)
之所以列出這個函數，是因為這個函數初始化了sizeCtl，并且可以看出table在這里并沒有被初始化，而是在插入元素的時候進行延遲初始化。
我們要注意的是table的長度始終是2的冪，sizeCtl的值為正數時表示擴容的最小閥值。
initTable
// 初始化table，使用sizeCtl記錄table的容量// 為了保證并發訪問不會出現沖突，使用了Unsafe的CAS操作private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;// tab是空的while ((tab = table) == null || tab.length == 0) {// 如果已經初始化過if ((sc = sizeCtl) < 0)Thread.yield(); // 退出初始化數組的競爭; just spin// 如果沒有線程在初始化，將sizeCtl設置為-1，表示正在初始化// CAS操作，由此可見sizeCtl維護table的并發訪問else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {// 再次檢查table是否為空if ((tab = table) == null || tab.length == 0) {// 計算分配多少個Node// sc大于0的時候表示要分配的大小// 否則默認分配16個nodeint n = (sc > 0) ? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;// 下次擴容的最小閥值0.75*n// 注意0.75 * n < n，而且它很可能不是2的冪，// 例如n = 16， 則sc = 12；// 因此這個閥值在后續擴容情況下實際上不會成為數組的容量值，但它可以用來能保證用戶提供了容量大小時，能夠容納用戶要求數目的元素。sc = n - (n >>> 2);}} finally {sizeCtl = sc;}break;}}return tab;}put
put過程的描述：
為表述方便，用符號i 來表示 (n - 1) & hash，用newNode表示使用key,value創建的節點
loop: {if table == null{初始化一個默認長度為16的數組}else table[i] == null{ table[i] = newNode}else hash == -1，table[i]是ForwardingNode{進行整合表的操作}else{if hash >= 0，table[i]不是特殊Node(鏈表中的Node){將newNode插入到鏈表中}else table[i]是TreeBin{newNode插入到TreeNode中}}addCount(1L, binCount); }通過研讀代碼，發現Doug Lea使用了一種有效且高效的技巧：
在循環里面嵌套使用CAS操作。這種技巧把臨界區變得很小，因此比較高效。
put源碼如下：
public V put(K key, V value) {return putVal(key, value, false);}/** put和putIfAbsent都是通過調用putVal方法來實現的*/final V putVal(K key, V value, boolean onlyIfAbsent) {// ConcurrentHashMap不支持key和value是nullif (key == null || value == null) throw new NullPointerException();// 獲取hash值int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;// case 1：tab為null，需要初始化tabif (tab == null || (n = tab.length) == 0)tab = initTable();// case 2: 沒有任何節點hash值與當前要插入的節點相同else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break; // no lock when adding to empty bin}// case 3: 當遇到表連接點時，需要進行整合表的操作// 需要注意的是，遇到連接點的時候，并沒有插入新節點，僅僅幫助擴容，因為當前線程迫切需要盡快插入新節點，只能等待擴容完畢才有可能插入新節點else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);// case 4: 找到對應于hash值的鏈表首節點，且該節點不是連接節點else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;// 如果找到相同key的node，根據onlyIfAbsent來更新node的值if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}// 如果一直到鏈表的尾部都沒有找到任何node的key與key相同，就插入到鏈表的尾部Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}// 如果該節點是TreeBin，就插入到TreeBin中else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;// 當存在相同的key時，putTreeVal不會修改那個TreeNode，而是返回給p，由onlyIfAbsent決定是否修改p.valif ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}// 若鏈表長度不低于8，就將鏈表轉換為樹if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}// 添加計數，如有需要，擴容addCount(1L, binCount);return null;}// 給tab[i]賦值// 如果tab[i]等于c,就將tab[i]與v交換數值static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) {return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);}/*** 協助擴容方法。* 多線程下，當前線程檢測到其他線程正進行擴容操作，則協助其一起擴容；*（只有這種情況會被調用）從某種程度上說，其“優先級”很高，* 只要檢測到擴容，就會放下其他工作，先擴容。* 調用之前，nextTable一定已存在。*/final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;// 如果f是tab中的連接節點，并且它所連接的table非空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;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab);break;}}return nextTab;}return table;}get
get方法比較簡單，沒有使用鎖，而是用Unsafe來保證獲取的頭結點是volatile的
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 獲取hash值hint h = spread(key.hashCode());// tab只是保存了hash值相同的頭結點if ((tab = table) != null && (n = tab.length) > 0 && // table里面有元素(e = tabAt(tab, (n - 1) & h)) != null) {// 根據h來獲取頭結點e// hash值相同，如果找到key，直接返回if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// todo：看一下hash值什么時候小于0else 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;}//tableAt方法使用了Unsafe對象來獲取數組中下標為i的對象 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {// 第i個元素實際地址i * (2^ASHIFT) + ABASEreturn (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);}treeifyBin
// 如果tab的長度很小，小于64個，就嘗試進行擴容為兩倍，// 否則就將以tab[index]開頭的鏈表轉換為Treebinprivate final void treeifyBin(Node<K,V>[] tab, int index) {Node<K,V> b; int n, sc;if (tab != null) {// tab的長度小于64，就嘗試進行擴容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) {TreeNode<K,V> hd = null, tl = null;// 這個循環建立了TreeNode中的雙向鏈表，hd保存了雙向鏈表的頭結點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;elsetl.next = p;tl = p;}setTabAt(tab, index, new TreeBin<K,V>(hd));}}}}}tryPresize
有關擴容，可以參考深入分析 ConcurrentHashMap 1.8 的擴容實現 這篇文章。
// 嘗試擴容使它能放size個元素private final void tryPresize(int size) {// 計算擴容后的數量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;// 如果tab是空的，直接擴容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;// 下次擴容的容量閥值是0.75 * nsc = n - (n >>> 2);}} finally {sizeCtl = sc;}}}// 容量已經夠用，不需要進行擴容；或者容量太大，無法進行擴容。else if (c <= sc || n >= MAXIMUM_CAPACITY)break;// 仍然需要擴容else if (tab == table) {int rs = resizeStamp(n);// todo：不是很懂為什么會出現 sc < 0 ？先看一下transfer的實現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;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);}}}transfer
偽代碼：n = table.lengthnextTable = new Node[2 * n]forwardingNode = new ForwardingNodeforwardingNode.nextTable = nextTable;for(table[i] : table) {for(p = table[i]; p != null ; p = p.next){if(p.hash & n == 0)將p放入nextTable[i]的數據集合中else將p放入nextTable[i+n]的數據集合中}table[i] = forwardingNode; }table = nextTable;nextTable = null;數學公式：
已知：n = 2 ^ k ， hash & (n-1) = i，顯而易見：
（1）若 hash & n = 0， 則 hash &(2n - 1) = i ；
（2）若 hash & n != 0, 則 hash&(2n - 1) = i + n。
源代碼在此：
// 把table中所有的Node放入新的table中private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // subdivide rangeif (nextTab == null) { // initiatingtry {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) { // try to cope with OOMEsizeCtl = 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; // to ensure sweep before committing nextTabfor (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;}else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {bound = nextBound;i = nextIndex - 1;advance = false;}}if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) {nextTable = null;table = nextTab;sizeCtl = (n << 1) - (n >>> 1);return;}if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;finishing = advance = true;i = n; // recheck before commit}}else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {synchronized (f) {if (tabAt(tab, i) == f) {Node<K,V> ln, hn;if (fh >= 0) {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);elsehn = new Node<K,V>(ph, pk, pv, hn);}setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);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;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;elseloTail.next = p;loTail = p;++lc;}else {if ((p.prev = hiTail) == null)hi = p;elsehiTail.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;}}}}}}addCount
/*** Adds to count, and if table is too small and not already* resizing, initiates transfer. If already resizing, helps* perform transfer if work is available. Rechecks occupancy* after a transfer to see if another resize is already needed* because resizings are lagging additions.** @param x the count to add* @param check if <0, don't check resize, if <= 1 only check if uncontended*/// 添加計數，如果table太小且table沒有在擴容，就進行擴容private final void addCount(long x, int check) {CounterCell[] as; long b, s;// 利用CAS快速更新baseCount的值if ((as = counterCells) != null ||!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {CounterCell a; long v; int m;boolean uncontended = true;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);return;}if (check <= 1)return;s = sumCount();}// 當之前檢查的節點個數大于等于0時，才考慮擴容if (check >= 0) {Node<K,V>[] tab, nt; int n, sc;while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {// 為當前的n保留一個數，不同的數組n（這里n=2^k）得到的結果必然不同，可類比時間戳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();}}}轉載于:https://www.cnblogs.com/mcai/p/9628512.html
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的ConcurrentHashMap源码剖析（1.8版本）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mysql 外键关联
- 下一篇： svn安装配置