解析ConcurrentHashMap:成員屬性、內(nèi)部類(lèi)、構(gòu)造方法
更新時(shí)間：2021年06月10日 15:41:25 作者：興趣使然の草帽路飛
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment的結(jié)構(gòu)和HashMap類(lèi)似，是一種數(shù)組和鏈表結(jié)構(gòu)，今天給大家普及java面試常見(jiàn)問(wèn)題---ConcurrentHashMap知識(shí)，一起看看吧
1、簡(jiǎn)介
ConcurrentHashMap是HashMap的線程安全版本，內(nèi)部也是使用（數(shù)組 + 鏈表 + 紅黑樹(shù)）的結(jié)構(gòu)來(lái)存儲(chǔ)元素。相比于同樣線程安全的HashTable來(lái)說(shuō)，效率等各方面都有極大地提高。
在學(xué)習(xí)ConcurrentHashMap源碼之前，這里默認(rèn)大家已經(jīng)讀過(guò)HashMap源碼，了解LongAdder原子類(lèi)、紅黑樹(shù)。先簡(jiǎn)單介紹下
ConcurrentHashMap的整體流程：
整體流程跟HashMap比較類(lèi)似，大致是以下幾步：
（1）如果桶數(shù)組未初始化，則初始化；
（2）如果待插入的元素所在的桶為空，則嘗試把此元素直接插入到桶的第一個(gè)位置；
（3）如果正在擴(kuò)容，則當(dāng)前線程一起加入到擴(kuò)容的過(guò)程中；
（4）如果待插入的元素所在的桶不為空且不在遷移元素，則鎖住這個(gè)桶（分段鎖）；
（5）如果當(dāng)前桶中元素以鏈表方式存儲(chǔ)，則在鏈表中尋找該元素或者插入元素；
（6）如果當(dāng)前桶中元素以紅黑樹(shù)方式存儲(chǔ)，則在紅黑樹(shù)中尋找該元素或者插入元素；
（7）如果元素存在，則返回舊值；
（8）如果元素不存在，整個(gè)Map的元素個(gè)數(shù)加1，并檢查是否需要擴(kuò)容；
添加元素操作中使用的鎖主要有（自旋鎖 + CAS + synchronized + 分段鎖）。
為什么使用synchronized而不是ReentrantLock？
因?yàn)閟ynchronized已經(jīng)得到了極大地優(yōu)化，在特定情況下并不比ReentrantLock差。
2、JDK1.8 ConcurrentHashMap結(jié)構(gòu)圖
3、成員屬性
// 散列表數(shù)組最大容量值
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 散列表默認(rèn)容量值16
private static final int DEFAULT_CAPACITY = 16;
// 最大的數(shù)組大?。ǚ?的冪） toArray和相關(guān)方法需要(并不是核心屬性)
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// jdk1.7遺留下來(lái)的，用來(lái)表示并發(fā)級(jí)別的屬性
// jdk1.8只有在初始化的時(shí)候用到，不再表示并發(fā)級(jí)別了~ 1.8以后并發(fā)級(jí)別由散列表長(zhǎng)度決定
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 負(fù)載因子：表示散列表的填滿程度~ 在ConcurrentHashMap中，該屬性是固定值0.75，不可修改~
private static final float LOAD_FACTOR = 0.75f;
// 樹(shù)化閾值：散列表的一個(gè)桶中鏈表長(zhǎng)度達(dá)到8時(shí)候，可能發(fā)生鏈表樹(shù)化
static final int TREEIFY_THRESHOLD = 8;
// 反樹(shù)化閾值：散列表的一個(gè)桶中的紅黑樹(shù)元素個(gè)數(shù)小于6時(shí)候，將紅黑樹(shù)轉(zhuǎn)換回鏈表結(jié)構(gòu)
static final int UNTREEIFY_THRESHOLD = 6;
// 散列表長(zhǎng)度達(dá)到64，且某個(gè)桶位中的鏈表長(zhǎng)度達(dá)到8，才會(huì)發(fā)生樹(shù)化
static final int MIN_TREEIFY_CAPACITY = 64;
// 控制線程遷移數(shù)據(jù)的最小步長(zhǎng)(桶位的跨度~)
private static final int MIN_TRANSFER_STRIDE = 16;
// 固定值16，與擴(kuò)容相關(guān)，計(jì)算擴(kuò)容時(shí)會(huì)根據(jù)該屬性值生成一個(gè)擴(kuò)容標(biāo)識(shí)戳
private static int RESIZE_STAMP_BITS = 16;
// (1 << (32 - RESIZE_STAMP_BITS)) - 1 = 65535：1 << 16 -1
// 表示并發(fā)擴(kuò)容最多容納的線程數(shù)
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 也是擴(kuò)容相關(guān)屬性，在擴(kuò)容分析的時(shí)候會(huì)用到~
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// 當(dāng)node節(jié)點(diǎn)的hash值為-1：表示當(dāng)前節(jié)點(diǎn)是FWD(forwarding)節(jié)點(diǎn)(已經(jīng)被遷移的節(jié)點(diǎn))
static final int MOVED = -1;
// 當(dāng)node節(jié)點(diǎn)的hash值為-2：表示當(dāng)前節(jié)點(diǎn)已經(jīng)樹(shù)化，且當(dāng)前節(jié)點(diǎn)為T(mén)reeBin對(duì)象~，TreeBin對(duì)象代理操作紅黑樹(shù)
static final int TREEBIN = -2;
// 當(dāng)node節(jié)點(diǎn)的hash值為-3：
static final int RESERVED = -3;
// 0x7fffffff 十六進(jìn)制轉(zhuǎn)二進(jìn)制值為：1111111111111111111111111111111（31個(gè)1）
// 作用是將一個(gè)二進(jìn)制負(fù)數(shù)與1111111111111111111111111111111 進(jìn)行按位與(&)運(yùn)算時(shí)，會(huì)得到一個(gè)正數(shù)，但不是取絕對(duì)值
static final int HASH_BITS = 0x7fffffff;
// 當(dāng)前系統(tǒng)的CPU數(shù)量
static final int NCPU = Runtime.getRuntime().availableProcessors();
// JDK1.8 序列化為了兼容 JDK1.7的ConcurrentHashMap用到的屬性 (非核心屬性)
private static final ObjectStreamField[] serialPersistentFields = {
new ObjectStreamField("segments", Segment[].class),
new ObjectStreamField("segmentMask", Integer.TYPE),
new ObjectStreamField("segmentShift", Integer.TYPE)
};
// 散列表table
transient volatile Node<K,V>[] table;
// 新表的引用：擴(kuò)容過(guò)程中，會(huì)將擴(kuò)容中的新table賦值給nextTable，（保持引用），擴(kuò)容結(jié)束之后，這里就會(huì)被設(shè)置為NULL
private transient volatile Node<K,V>[] nextTable;
// 與LongAdder中的baseCount作用相同: 當(dāng)未發(fā)生線程競(jìng)爭(zhēng)或當(dāng)前LongAdder處于加鎖狀態(tài)時(shí)，增量會(huì)被累加到baseCount
private transient volatile long baseCount;
// 表示散列表table的狀態(tài):
// sizeCtl<0時(shí)：
// 情況一、sizeCtl=-1: 表示當(dāng)前table正在進(jìn)行初始化(即，有線程在創(chuàng)建table數(shù)組)，當(dāng)前線程需要自旋等待...
// 情況二、表示當(dāng)前table散列表正在進(jìn)行擴(kuò)容，高16位表示擴(kuò)容的標(biāo)識(shí)戳，低16位表示擴(kuò)容線程數(shù)：(1 + nThread) 即，當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量。
// sizeCtl=0時(shí)：表示創(chuàng)建table散列表時(shí)，使用默認(rèn)初始容量DEFAULT_CAPACITY=16
// sizeCtl>0時(shí)：
// 情況一、如果table未初始化，表示初始化大小
// 情況二、如果table已經(jīng)初始化，表示下次擴(kuò)容時(shí)，觸發(fā)條件(閾值)
private transient volatile int sizeCtl;
// 擴(kuò)容過(guò)程中，記錄當(dāng)前進(jìn)度。所有的線程都需要從transferIndex中分配區(qū)間任務(wù)，并去執(zhí)行自己的任務(wù)
private transient volatile int transferIndex;
// LongAdder中，cellsBusy表示對(duì)象的加鎖狀態(tài)：
// 0: 表示當(dāng)前LongAdder對(duì)象處于無(wú)鎖狀態(tài)
// 1: 表示當(dāng)前LongAdder對(duì)象處于加鎖狀態(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ò)計(jì)算hash值，去取到自己的cell，將增量累加到指定的cell中
// 總數(shù) = sum(cells) + baseCount
private transient volatile CounterCell[] counterCells;
4、靜態(tài)屬性
// Unsafe 類(lèi) private static final sun.misc.Unsafe U; // 表示sizeCtl屬性在ConcurrentHashMap中內(nèi)存的偏移地址 private static final long SIZECTL; // 表示transferIndex屬性在ConcurrentHashMap中內(nèi)存的偏移地址 private static final long TRANSFERINDEX; // 表示baseCount屬性在ConcurrentHashMap中內(nèi)存的偏移地址 private static final long BASECOUNT; // 表示cellsBusy屬性在ConcurrentHashMap中內(nèi)存的偏移地址 private static final long CELLSBUSY; // 表示cellsValue屬性在ConcurrentHashMap中內(nèi)存的偏移地址 private static final long CELLVALUE; // 表示數(shù)組第一個(gè)元素的偏移地址 private static final long ABASE; // 該屬性用于數(shù)組尋址，請(qǐng)繼續(xù)往下閱讀 private static final int ASHIFT;
5、靜態(tài)代碼塊
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> k = ConcurrentHashMap.class;
SIZECTL = U.objectFieldOffset
(k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy"));
Class<?> ck = CounterCell.class;
CELLVALUE = U.objectFieldOffset
(ck.getDeclaredField("value"));
Class<?> ak = Node[].class;
// 拿到數(shù)組第一個(gè)元素的偏移地址
ABASE = U.arrayBaseOffset(ak);
// 表示數(shù)組中每一個(gè)單元所占用的空間大小，即scale表示Node[]數(shù)組中每一個(gè)單元所占用的空間
int scale = U.arrayIndexScale(ak);
// (scale & (scale - 1)) != 0：判斷scale的數(shù)值是否是2的次冪數(shù)
// java語(yǔ)言規(guī)范中，要求數(shù)組中計(jì)算出的scale必須為2的次冪數(shù)
// 1 0000 % 0 1111 = 0
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
// numberOfLeadingZeros(scale) 根據(jù)scale，返回當(dāng)前數(shù)值轉(zhuǎn)換為二進(jìn)制后，從高位到地位開(kāi)始統(tǒng)計(jì)，統(tǒng)計(jì)有多少個(gè)0連續(xù)在一塊：eg, 8轉(zhuǎn)換二進(jìn)制=>1000 則 numberOfLeadingZeros(8)的結(jié)果就是28，為什么呢？因?yàn)镮nteger是32位，1000占4位，那么前面就有32-4個(gè)0，即連續(xù)最長(zhǎng)的0的個(gè)數(shù)為28個(gè)
// 4轉(zhuǎn)換二進(jìn)制=>100 則 numberOfLeadingZeros(8)的結(jié)果就是29
// ASHIFT = 31 - Integer.numberOfLeadingZeros(4) = 2 那么ASHIFT的作用是什么呢？其實(shí)它有數(shù)組尋址的一個(gè)作用：
// 拿到下標(biāo)為5的Node[]數(shù)組元素的偏移地址(存儲(chǔ)地址)：假設(shè)此時(shí) 根據(jù)scale計(jì)算得到的ASHIFT = 2
// ABASE + (5 << ASHIFT) == ABASE + (5 << 2) == ABASE + 5 * scale，就得到了下標(biāo)為5的數(shù)組元素的偏移地址
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw new Error(e);
}
}
6、內(nèi)部類(lèi)
6.1 Node節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {
// hash值
final int hash;
// key
final K key;
// value
volatile V val;
// 后驅(qū)節(jié)點(diǎn)
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode();
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
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)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
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;
}
}
6.2 ForwardingNode節(jié)點(diǎn)
這個(gè)內(nèi)部類(lèi)在之后分析擴(kuò)容的文章中會(huì)再仔細(xì)去探究，這里先熟悉一下~
// 如果是一個(gè)寫(xiě)的線程(eg：并發(fā)擴(kuò)容線程)，則需要為創(chuàng)建新表貢獻(xiàn)一份力
// 如果是一個(gè)讀的線程，則調(diào)用該內(nèi)部類(lèi)的find(int h, Object k)方法
static final class ForwardingNode<K,V> extends Node<K,V> {
// nextTable表示新散列表的引用
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
// 到新表上去讀數(shù)據(jù)
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: 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;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
6.3 TreeNode節(jié)點(diǎn)
TreeBin中需要用到該節(jié)點(diǎn)，之后會(huì)細(xì)說(shuō)~
static final class TreeNode<K,V> extends Node<K,V> {
// 父節(jié)點(diǎn)
TreeNode<K,V> parent; // red-black tree links
// 左子節(jié)點(diǎn)
TreeNode<K,V> left;
// 右節(jié)點(diǎn)
TreeNode<K,V> right;
// 前驅(qū)節(jié)點(diǎn)
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 節(jié)點(diǎn)有紅、黑兩種顏色~
boolean 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);
}
/**
* Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/
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;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
7、構(gòu)造方法
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;
}
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
構(gòu)造方法與HashMap對(duì)比可以發(fā)現(xiàn)，沒(méi)有了HashMap中的threshold和loadFactor，而是改用了sizeCtl來(lái)控制，而且只存儲(chǔ)了容量在里面，那么它是怎么用的呢？官方給出的解釋如下：
（1）-1，表示有線程正在進(jìn)行初始化操作。
（2）-(1 + nThreads)，表示有n個(gè)線程正在一起擴(kuò)容。
（3）0，默認(rèn)值，后續(xù)在真正初始化的時(shí)候使用默認(rèn)容量。
（4）> 0，初始化或擴(kuò)容完成后下一次的擴(kuò)容門(mén)檻 。
8、總結(jié)
文章會(huì)不定時(shí)更新，有時(shí)候一天多更新幾篇，如果幫助您復(fù)習(xí)鞏固了知識(shí)點(diǎn)，后續(xù)會(huì)億點(diǎn)點(diǎn)的更新！希望大家多多關(guān)注腳本之家的其他內(nèi)容！
相關(guān)文章
淺談Java實(shí)現(xiàn)回溯算法之八皇后問(wèn)題
八皇后問(wèn)題是一個(gè)古老而又著名的問(wèn)題，是學(xué)習(xí)回溯算法的一個(gè)經(jīng)典案例。今天我們就一起來(lái)探究一下吧2021-06-06
在最近的工作中，碰到一個(gè)比較復(fù)雜的返回結(jié)果，發(fā)現(xiàn)簡(jiǎn)單映射已經(jīng)解決不了這個(gè)問(wèn)題了，只好去求助百度，學(xué)習(xí)mybatis映射匹配應(yīng)該怎么寫(xiě)，將學(xué)習(xí)筆記結(jié)合工作碰到的問(wèn)題寫(xiě)下本文，供自身查漏補(bǔ)缺，同時(shí)已被不時(shí)之需2022-08-08
本篇文章主要介紹了springmvc限流攔截器的示例代碼，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-12-12
java中給實(shí)體對(duì)象屬性的空值賦默認(rèn)值
這篇文章主要介紹了java中給實(shí)體對(duì)象屬性的空值賦默認(rèn)值，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
Java 程序設(shè)計(jì)總復(fù)習(xí)題(java基礎(chǔ)代碼)
這篇文章主要介紹了Java 程序設(shè)計(jì)總復(fù)習(xí)題，主要是java基礎(chǔ)代碼，方便學(xué)習(xí)java的同學(xué)2021-05-05
學(xué)習(xí)SpringMVC——國(guó)際化+上傳+下載詳解
本篇文章主要介紹了學(xué)習(xí)SpringMVC——國(guó)際化+上傳+下載，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。2016-12-12
java selenium教程之selenium詳細(xì)介紹
本文主要介紹Java selenium,這里整理了selenium的一些基本資料，此軟件主要用于Web UI自動(dòng)測(cè)試框架,有興趣的同學(xué)可以看一下2016-08-08
學(xué)習(xí)SpringBoot容器功能及注解原理
這篇文章主要介紹了學(xué)習(xí)SpringBoot容器功能及注解原理，文中通過(guò)詳細(xì)的代碼示例對(duì)SpringBoot容器功能及注解原理進(jìn)行了解析，有需要的朋友可以借鑒參考下2021-09-09
IDEA導(dǎo)入JDBC驅(qū)動(dòng)的jar包步驟詳解
JDBC是一種底層的API，是連接數(shù)據(jù)庫(kù)和Java應(yīng)用程序的紐帶，因此我們?cè)谠L問(wèn)數(shù)據(jù)庫(kù)時(shí)需要在業(yè)務(wù)邏輯層中嵌入SQL語(yǔ)句，這篇文章主要介紹了IDEA導(dǎo)入JDBC驅(qū)動(dòng)的jar包,需要的朋友可以參考下2023-07-07
基于Java實(shí)現(xiàn)收發(fā)電子郵件功能
Email就是電子郵件，我們平常使用的QQ郵箱，網(wǎng)易郵箱，F(xiàn)oxmail都是用來(lái)收發(fā)郵件的，利用Java程序也可以完成收發(fā)電子郵件的功能，本文就來(lái)為大家詳細(xì)講講實(shí)現(xiàn)步驟2022-07-07