一藻三、集合框架源碼分析
- 集合框架 （第 01 篇） 源碼分析：Collection<E> 框架總覽
- 集合框架 （第 02 篇） 源碼分析：Map<K,V > 框架總覽
- 集合框架 （第 03 篇） 源碼分析：ArrayList<E>
- 集合框架 （第 04 篇） 源碼分析：LinkedList
- 集合框架 （第 05 篇） 源碼分析：Map<K, V>接口與其內(nèi)部接口Entry<K,V>
- 集合框架 （第 06 篇） 源碼分析：哈希沖突(哈希碰撞)與解決算法
- 集合框架 （第 07 篇） 源碼分析：jdk1.7版 HashMap
- 集合框架 （第 08 篇） 源碼分析：HashMap、Hashtable、ConcurrentHashMap之間的區(qū)別
- 集合框架 （第 09 篇） 源碼分析：jdk1.7版 ConcurrentHashMap
- 集合框架 （第 10 篇） 源碼分析：二叉樹摧冀、平衡二叉樹苛谷、二叉查找樹、AVL樹菩彬、紅黑樹
- 集合框架 （第 11 篇） 源碼分析：jdk1.8版 HashMap
- 集合框架 （第 12 篇） 源碼分析：jdk1.8版 ConcurrentHashMap
- 集合框架 （第 13 篇） 源碼分析：LinkedHashMap
- 集合框架 （第 14 篇） 源碼分析：TreeMap
- 集合框架 （第 15 篇） 源碼分析：Set<E> 集合
- 集合框架 （第 16 篇） 源碼分析：BlockingQueue 接口
- 集合框架 （第 17 篇） 源碼分析：CopyOnWriteArrayList 與 CopyOnWriteArraySet
原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore
正文
:relaxed:本文是基于
jdk1.8.0_151分析
如果你已經(jīng)閱讀了我之前寫的關(guān)于 jdk1.8 HashMap 和 jdk1.7 ConcurrentHashMap 文章醉顽，對于本篇
jdk1.8版的ConcurrentHashMap源碼分析更容量理解沼溜，不過沒關(guān)系，本篇文章也非常詳細地來分析游添。
一系草、ConcurrentHashMap的擴展關(guān)系
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable
從擴展關(guān)系上，沒有任何變化唆涝，但
ConcurrentMap<K, V>又添加幾個default方法找都，default的好處在上篇文章中已經(jīng)提到過：
/**
* forEach 迭代方法
*
* @throws NullPointerException {@inheritDoc}
* @since 1.8
*/
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
continue;
}
action.accept(k, v);
}
}
/** 其他略 */
??????
二、ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)
回顧 jdk 1.7 的 ConcurrentHashMap 的數(shù)據(jù)結(jié)構(gòu)
jdk 1.7的ConcurrentHashMap是基于 分段鎖 機制設(shè)計的廊酣，將一個大的Map分割成n個小的 段segment能耻，對每段進行加鎖，降低了容器加鎖的粒子度亡驰，每段(segment)各自加鎖晓猛，互不影響，當(dāng)一個線程訪問 Map 其中一段數(shù)據(jù)時凡辱，其他段的數(shù)據(jù)也能被線程正常訪問戒职。分段鎖使用的鎖是ReentrantLock可重入鎖。
ConcurrentHashMap1.7v
優(yōu)化后的 jdk 1.8 的 ConcurrentHashMap 的數(shù)據(jù)結(jié)構(gòu)
jdk 1.8的ConcurrentHashMap相對于較前的版本該動還是蠻大透乾。首先取消了
分段鎖的設(shè)計洪燥，而改用像jdk 1.8中HashMap那樣的數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 鏈表 + 紅黑樹（但依然保留著 分段鎖 的這種設(shè)計思想）磕秤。再次，在保證線程安全的問題了取消了
ReentrantLock改用CAS+synchronized保證并發(fā)的安全蚓曼。（當(dāng)然ReentrantLock 的原理也是基于CAS的）亲澡，在使用synchronized時并沒有像Hashtable那樣粗暴地鎖住整個數(shù)組钦扭，而它是鎖住單個節(jié)點纫版。
jdk1.8 ConcurrentHashMap
??重要的字段
/** 最大容量 10.7億+ */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/** table的默認初始容量 16，容量必須為 2 的次冪 */
private static final int DEFAULT_CAPACITY = 16;
/** table 默認并發(fā)等級 16 */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/** table的默認負載因子 0.75客情，可以通過構(gòu)造函數(shù)指定負載因子大小 */
private static final float LOAD_FACTOR = 0.75f;
/** （從鏈表上的元素個數(shù)來講）鏈表轉(zhuǎn)紅黑樹的閾值 */
static final int TREEIFY_THRESHOLD = 8;
/** （從紅黑樹上的元素個數(shù)來講）紅黑樹轉(zhuǎn)鏈表的閾值 */
static final int UNTREEIFY_THRESHOLD = 6;
/** 鏈表轉(zhuǎn)紅黑樹的另一個閾值(條件)：Map的容量至少為64. */
static final int MIN_TREEIFY_CAPACITY = 64;
/** 每次進行轉(zhuǎn)移的最小值 */
private static final int MIN_TRANSFER_STRIDE = 16;
/** 生成sizeCtl所使用的bit位數(shù) */
private static int RESIZE_STAMP_BITS = 16;
/** 進行擴容所允許的最大線程數(shù) */
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
/** 可以有效使用的 CPU 數(shù)量 */
static final int NCPU = Runtime.getRuntime().availableProcessors();
/** 首先哈希值不小于0其弊，下面的幾個常量相當(dāng)于標識位 */
/** 用于轉(zhuǎn)換節(jié)點的哈希值 */
static final int MOVED = -1;
/** 用于紅黑樹根節(jié)點的哈希碼的標識位 */
static final int TREEBIN = -2;
/** 容器中還有一個保留節(jié)點，此處也是有關(guān)的哈希碼的標識位 */
static final int RESERVED = -3;
/** 用于普通節(jié)點哈希碼的標識位 */
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
/** 容器的數(shù)組（哈希表膀斋、散列表）梭伐，在第一次插入元素時才初始化，大小總是2的次冪 */
transient volatile Node<K,V>[] table;
/** 擴容時使用的臨時過度的數(shù)組（僅使用于擴容） */
private transient volatile Node<K,V>[] nextTable;
/** 容器中實際存儲元素的數(shù)量仰担。(利用CAS自旋來更新其值) */
private transient volatile long baseCount;
/**
* 不同的值起到不同的作用糊识，但唯一功能是起到控制作用，你可以認為它是控制標識符
* sizeCtl小于0 標識容器正在初始化或擴容
* sizeCtl為-1 標識正式初始化
* sizeCtl為-N 標識有N-1個線程正在進行擴容操作
*/
private transient volatile int sizeCtl;
/** 調(diào)整表大小時使用摔蓝，下一個transfer任務(wù)的起始下標index 加上1 之后的值 */
private transient volatile int transferIndex;
/** 當(dāng)初始化或者擴容時赂苗，CAS自旋鎖的標識位 */
private transient volatile int cellsBusy;
/** 計數(shù)器池，非空時贮尉，大小為2的次冪 */
private transient volatile CounterCell[] counterCells;
三拌滋、ConcurrentHashMap中各種數(shù)據(jù)節(jié)點
jdk1.8 ConcurrentHashMap 中數(shù)據(jù)節(jié)點的種類比較多，比如 Node<K, V>猜谚、TreeNode<K, V>败砂、TreeBin<K, V>、ReservationNode<K,V>魏铅。正式這種獨具特色的設(shè)計昌犹，才擁有高性能的Map并發(fā)容器。
大多數(shù)用于存儲元素的 Node<K, V> 節(jié)點（鏈表必用的節(jié)點）
ConcurrentHashMap重點元素 項HashEntry<K, V> 在jdk1.8已改為 節(jié)點Node<K, V>览芳，與jdk1.7版本的自定義略有不同祭隔，jdk1.8中是實現(xiàn)于Map.Entry接口的。 下面就來分析一下jdk1.8的ConcurrentHashMapNode<K, V> 節(jié)點：??請注意：這個Node<K, V> 是大多數(shù) 用于存儲的元素節(jié)點路操，并不是全部疾渴，而紅黑樹 是用下面的 TreeNode<K, V> 節(jié)點作為元素存儲節(jié)點。因為 鏈表 中的節(jié)點只有一個后繼節(jié)點屯仗，而 TreeNode<K, V> 作為二叉樹中的節(jié)點搞坝，最多可有兩個后繼節(jié)點（既左、右子節(jié)點）魁袜。
/** 實現(xiàn)于 Map.Entry */
static class Node<K,V> implements Map.Entry<K,V> {
// // final 修飾的 哈希碼桩撮、key敦第，防止被重復(fù)賦值
final int hash;
final K key;
// 具有可見性的 val 和 next
volatile V val;
// 當(dāng)前節(jié)點指向的下一個節(jié)點
volatile Node<K,V> next;
/**
* 構(gòu)造方法用于注入 node節(jié)點 的屬性值(或引用)
* 參數(shù)從左至右依次是：key的哈希碼，key店量，value芜果，指向的下一個節(jié)點next
*/
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
// getter & toString 方法
public final K getKey() { return key; }
public final V getValue() { return val; }
public final String toString(){ return key + "=" + val; }
// 返回節(jié)點的哈希碼
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
// 設(shè)置 value 的方法，可能會拋出不支持的操作異常
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
// 用于節(jié)點比較是否相等的方法
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
// 返回判斷key融师、value是否相同的結(jié)果
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* 虛擬化地支持 map.get() 操作; 子類可以重寫此方法.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
// 循環(huán)遍歷鏈表
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;
}
}
專用于紅黑樹的 TreeNode<K, V> 節(jié)點
static final class TreeNode<K,V> extends Node<K,V> {
// 父節(jié)點
TreeNode<K,V> parent;
// 左子節(jié)點
TreeNode<K,V> left;
// 右子節(jié)點
TreeNode<K,V> right;
// 指向上一個節(jié)點（一般是父節(jié)點）右钾，刪除節(jié)點時會用到
TreeNode<K,V> prev;
// 紅黑標識：true表示此節(jié)點為紅色，false表示此節(jié)點為黑色
boolean red;
// 有參構(gòu)造方法
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);
}
/**
* 查找并返回紅黑樹中是存在的節(jié)點旱爆，不存在返回null
* 在上篇關(guān)于jdk1.8HashMap源碼分析的文章中舀射，分析過類似的（寫）操作
* 文章持續(xù)更新地址：https://github.com/about-cloud/JavaCore
*/
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
// 當(dāng)前節(jié)點
TreeNode<K,V> p = this;
// 循環(huán)遍歷平衡樹
do {
// ph：當(dāng)前節(jié)點的哈希碼，
// dir：搜索的方向怀伦，左或右：-1表示左脆烟，1表示右，
// pk：當(dāng)前節(jié)點的key
// q：當(dāng)前節(jié)點
int ph, dir; K pk; TreeNode<K,V> q;
// pl：當(dāng)前節(jié)點p的左子節(jié)點房待；pr：當(dāng)前節(jié)點p的右子節(jié)點
TreeNode<K,V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
// 當(dāng)前節(jié)點的哈希值大于指定的哈希值邢羔，指向左子節(jié)點
p = pl;
else if (ph < h)
// 當(dāng)前節(jié)點的哈希值小于指定的哈希值，指向右子節(jié)點
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
// 如果當(dāng)前節(jié)點的key與指定的k相同桑孩，那么就直接返回此節(jié)點
return p;
else if (pl == null)
// 如果左子節(jié)點為空拜鹤，就向右子節(jié)點查找
p = pr;
else if (pr == null)
// 如果右子節(jié)點為空，就向左子節(jié)點查找
p = pl;
// 判斷 k 的類是否實現(xiàn)了比較器
else if ((kc != null ||
// 判斷 k 的類是否實現(xiàn)了比較器
(kc = comparableClassFor(k)) != null) &&
// 這里實際是 pk == null || pk.getClass() != kc ? 0 :
// ((Comparable)pk).compareTo(pk)
// 下面是解讀這個三目運算：
// pk == null 表示判斷當(dāng)前節(jié)點是否為null
// pk.getClass() != kc 表示當(dāng)前節(jié)點對象的類和key的對象的類是否不同
// ((Comparable)k).compareTo(pk)表示將指定的key與當(dāng)前節(jié)點的key比較
(dir = compareComparables(kc, k, pk)) != 0)
// dir小于0表示向左子節(jié)點搜索
p = (dir < 0) ? pl : pr;
// 循環(huán)查找
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
方法使用的位置 保留節(jié)點
static final class ReservationNode<K,V> extends Node<K,V> {
ReservationNode() {
super(RESERVED, null, null, null);
}
Node<K,V> find(int h, Object k) {
return null;
}
}
持有紅黑樹根節(jié)點的容器
TreeBin 是保證 ConcurrentHashMap 線程安全的重要數(shù)據(jù)結(jié)構(gòu)洼怔，它自身維護著讀/寫鎖署惯。
static final class TreeBin<K,V> extends Node<K,V> {
// 紅黑樹的根節(jié)點
TreeNode<K,V> root;
// // 鏈表的頭節(jié)點（桶頂?shù)墓?jié)點）
volatile TreeNode<K,V> first;
// 最近一個設(shè)置 waiter 標識位的線程
volatile Thread waiter;
// 鎖狀態(tài)標識位
volatile int lockState;
static final int WRITER = 1; // 持有寫鎖時的狀態(tài)位
static final int WAITER = 2; // 正在等待寫鎖的狀態(tài)位
static final int READER = 4; // 設(shè)置讀鎖時的增量值
...其他方法跟 TreeNode 中的方法很相似
}
四钥飞、ConcurrentHashMap添加元素操作
面向用戶的 put 方法
public V put(K key, V value) {
return putVal(key, value, false);
}
面向 put 和 putIfAbsent 多用途的添加元素的方法
真正實現(xiàn)用于 put 和 putIfAbsent 的添加方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 不允許key搬素、value為null
// 將null值判斷提前，符合異常處理的規(guī)則（這里也是較上一版做了優(yōu)化）
if (key == null || value == null) throw new NullPointerException();
// 計算key的哈希碼
int hash = spread(key.hashCode());
// binCount 用來記錄鏈表中節(jié)點數(shù)量碘赖，進而判斷是否達到轉(zhuǎn)為紅黑樹的閾值
int binCount = 0;
// 遍歷table數(shù)組
for (Node<K,V>[] tab = table;;) {
// 要插入元素所在位置的節(jié)點
Node<K,V> f;
// n 表示數(shù)組長度安岂；i 表示索引轻猖；fh 表示要插入元素所在位置的節(jié)點的哈希碼
int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// 如果數(shù)組為null或者數(shù)組的大小為0，那么進行初始化數(shù)組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 通過指定key的哈希碼找到對應(yīng)的節(jié)點域那，
// 在節(jié)點為null的情況下咙边，通過CAS自旋方式將這個元素放入其中
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
// 如果通過CAS自旋成功添加元素，就直接跳出循環(huán)
// 否則就進入下一個循環(huán)
break;
}
else if ((fh = f.hash) == MOVED)
// 標識著要遷移數(shù)據(jù)
tab = helpTransfer(tab, f);
// 通過上面過濾的條件次员，在應(yīng)該能猜到下面不是關(guān)于鏈表就是關(guān)于紅黑樹
// 因為哈希槽的位置不為null
else {
// 舊值
V oldVal = null;
// 只給單個節(jié)點加鎖
synchronized (f) {
// 再次判斷節(jié)點
if (tabAt(tab, i) == f) {
// 判斷節(jié)點f的哈希碼是否不小于0
if (fh >= 0) {
// 大于等于0意味著該處有元素败许，記錄元素加1
binCount = 1;
// 從桶頂（哈希槽）開始遍歷鏈表
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 判斷key是否相同
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 如果相同的話，就準備獲取value
oldVal = e.val;
// onlyIfAbsent為true標識可以覆蓋value淑蔚，false標識不允許覆蓋
if (!onlyIfAbsent)
// 如果允許覆蓋value市殷，就覆蓋value
e.val = value;
break;
}
// 記錄下一個節(jié)點的上一個節(jié)點（目前以為著是當(dāng)前節(jié)點e）
Node<K,V> pred = e;
if ((e = e.next) == null) {
// 如果當(dāng)前節(jié)點的下一個節(jié)點為null，就把元素添加到鏈表的尾部
pred.next = new Node<K,V>(hash, key,
value, null);
// 添加完成后就直接跳出循環(huán)
break;
}
}
}
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;
// 是否可以覆蓋已有的value
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 判斷在鏈表不為空的情況下刹衫，是否達到轉(zhuǎn)為紅黑樹的閾值
if (binCount >= TREEIFY_THRESHOLD)
// 如果鏈表元素達到轉(zhuǎn)為紅黑樹的閾值醋寝，就轉(zhuǎn)為紅黑樹
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 添加計數(shù)
addCount(1L, binCount);
return null;
}
添加計數(shù) addCount
方法的實現(xiàn)很像 LongAdder
private final void addCount(long x, int check) {
// 計數(shù)池
CounterCell[] as;
// b表示實際存放元素的數(shù)量搞挣；s表示添加元素后的數(shù)量
long b, s;
if ((as = counterCells) != null ||
// 使用CAS自旋方式加上數(shù)量
!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();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
當(dāng)然后面還會持續(xù)更新本文，有興趣可以關(guān)注上面GitHub文章音羞。
