1. 各種map線程安全介紹
1.1 HashMap
HashMap是線程不安全的，在并發(fā)環(huán)境下，可能會形成環(huán)狀鏈表（擴(kuò)容時可能造成，具體原因自行百度google或查看源碼分析），導(dǎo)致get操作時，cpu空轉(zhuǎn)，所以，在并發(fā)環(huán)境中使用HashMap是非常危險的。
1.2 HashTable
HashTable和HashMap的實現(xiàn)原理幾乎一樣，差別：
- 1.HashTable不允許key和value為null；
- 2.HashTable是線程安全的。
但是HashTable線程安全的策略實現(xiàn)代價卻太大，get/put所有相關(guān)操作都是synchronized的，相當(dāng)于給整個哈希表加了一把大鎖，多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞，相當(dāng)于將所有的操作串行化。
1.3 JDK1.7的ConcurrentHashMap
- ConcurrentHashMap采用了非常精妙的"分段鎖"策略，ConcurrentHashMap的主干是個Segment數(shù)組。
- Segment繼承了ReentrantLock，所以它就是一種可重入鎖（ReentrantLock)。在ConcurrentHashMap，一個Segment就是一個子哈希表，Segment里維護(hù)了一個HashEntry數(shù)組，并發(fā)環(huán)境下，對于不同Segment的數(shù)據(jù)進(jìn)行操作是不用考慮鎖競爭的。
- 所以，對于同一個Segment的操作才需考慮線程同步，不同的Segment則無需考慮。
- 使用ConConcurrentHashMap時候有時候會遇到跨段的問題，跨段的時候[size()、containsValue()]，可能需要鎖定部分段或者全段，當(dāng)操作結(jié)束之后，又回按照順序進(jìn)行釋放每一段的鎖。注意是按照順序解鎖的。，每個Segment又包含了多個HashEntry.
主要結(jié)構(gòu)：ReentrantLock+Segment+HashEntry
1.7的ConcurrentHashMap源碼：
JDK1.8的ConcurrentHashMap
JDK1.8的實現(xiàn)已經(jīng)拋棄了Segment分段鎖機(jī)制，利用CAS+Synchronized來保證并發(fā)更新的安全。數(shù)據(jù)結(jié)構(gòu)采用：數(shù)組+鏈表+紅黑樹。
從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹。
2. JDK1.8的ConcurrentHashMap
2.1 put()
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw newNullPointerException(); // 鍵或值為空，拋出異常
// 鍵的hash值經(jīng)過計算獲得hash值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) { // 無限循環(huán)
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //表為空或者表的長度為0
// 初始化表
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash))== null) { //表不為空并且表的長度大于0，并且該桶不為空
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key,value, null))) //比較并且交換值，如tab的第i項空則用新生成的node替換
break; // no lockwhen adding to empty bin
}
else if ((fh = f.hash) == MOVED) //該結(jié)點(diǎn)的hash值為MOVED
// 進(jìn)行結(jié)點(diǎn)的轉(zhuǎn)移（在擴(kuò)容的過程中）
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { // 加鎖同步
if (tabAt(tab, i) == f) {//找到table表下標(biāo)為i的節(jié)點(diǎn)
if (fh >= 0) { // 該table表中該結(jié)點(diǎn)的hash值大于0
// binCount賦值為1
binCount = 1;
for (Node<K,V> e = f;; ++binCount) { // 無限循環(huán)
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) { // 結(jié)點(diǎn)的hash值相等并且key也相等
// 保存該結(jié)點(diǎn)的val值
oldVal = e.val;
if (!onlyIfAbsent) // 進(jìn)行判斷
// 將指定的value保存至結(jié)點(diǎn)，即進(jìn)行了結(jié)點(diǎn)值的更新
e.val = value;
break;
}
// 保存當(dāng)前結(jié)點(diǎn)
Node<K,V> pred = e;
if ((e = e.next) == null){ // 當(dāng)前結(jié)點(diǎn)的下一個結(jié)點(diǎn)為空，即為最后一個結(jié)點(diǎn)
// 新生一個結(jié)點(diǎn)并且賦值給next域
pred.next = new Node<K,V>(hash, key,
value, null);
// 退出循環(huán)
break;
}
}
}
else if (f instanceof TreeBin) { // 結(jié)點(diǎn)為紅黑樹結(jié)點(diǎn)類型
Node<K,V> p;
// binCount賦值為2
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) { // 將hash、key、value放入紅黑樹
// 保存結(jié)點(diǎn)的val
oldVal = p.val;
if (!onlyIfAbsent) // 判斷
// 賦值結(jié)點(diǎn)value值
p.val = value;
}
}
}
}
if (binCount != 0) { // binCount不為0
if (binCount >= TREEIFY_THRESHOLD) // 如果binCount大于等于轉(zhuǎn)化為紅黑樹的閾值
// 進(jìn)行轉(zhuǎn)化
treeifyBin(tab, i);
if (oldVal != null) // 舊值不為空
// 返回舊值
return oldVal;
break;
}
}
}
// 增加binCount的數(shù)量
addCount(1L, binCount);
return null;
}
說明：put函數(shù)底層調(diào)用了putVal進(jìn)行數(shù)據(jù)的插入，對于putVal函數(shù)的流程大體如下。
判斷存儲的key、value是否為空，若為空，則拋出異常，否則，進(jìn)入步驟②
計算key的hash值，隨后進(jìn)入無限循環(huán)，該無限循環(huán)可以確保成功插入數(shù)據(jù)，若table表為空或者長度為0，則初始化table表，否則，進(jìn)入步驟③
根據(jù)key的hash值取出table表中的結(jié)點(diǎn)元素，若取出的結(jié)點(diǎn)為空（該桶為空），則使用CAS將key、value、hash值生成的結(jié)點(diǎn)放入桶中。否則，進(jìn)入步驟④
若該結(jié)點(diǎn)的的hash值為MOVED，則對該桶中的結(jié)點(diǎn)進(jìn)行轉(zhuǎn)移，否則，進(jìn)入步驟⑤
對桶中的第一個結(jié)點(diǎn)（即table表中的結(jié)點(diǎn)）進(jìn)行加鎖，對該桶進(jìn)行遍歷，桶中的結(jié)點(diǎn)的hash值與key值與給定的hash值和key值相等，則根據(jù)標(biāo)識選擇是否進(jìn)行更新操作（用給定的value值替換該結(jié)點(diǎn)的value值），若遍歷完桶仍沒有找到hash值與key值和指定的hash值與key值相等的結(jié)點(diǎn)，則直接新生一個結(jié)點(diǎn)并賦值為之前最后一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)。進(jìn)入步驟⑥
若binCount值達(dá)到紅黑樹轉(zhuǎn)化的閾值，則將桶中的結(jié)構(gòu)轉(zhuǎn)化為紅黑樹存儲，最后，增加binCount的值。
在putVal函數(shù)中會涉及到如下幾個函數(shù)：initTable、tabAt、casTabAt、helpTransfer、putTreeVal、treeifyBin、addCount函數(shù)。下面對其中涉及到的函數(shù)進(jìn)行分析。
2.2 initTable()
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) { // 無限循環(huán)
if ((sc = sizeCtl) < 0) // sizeCtl小于0，則進(jìn)行線程讓步等待
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 比較sizeCtl的值與sc是否相等，相等則用-1替換
try {
if ((tab = table) == null || tab.length == 0) { // table表為空或者大小為0
// sc的值是否大于0，若是，則n為sc，否則，n為默認(rèn)初始容量
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// 新生結(jié)點(diǎn)數(shù)組
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 賦值給table
table = tab = nt;
// sc為n * 3/4
sc = n - (n >>> 2);
}
} finally {
// 設(shè)置sizeCtl的值
sizeCtl = sc;
}
break;
}
}
// 返回table表
return tab;
}
說明：對于table的大小，會根據(jù)sizeCtl的值進(jìn)行設(shè)置，如果沒有設(shè)置szieCtl的值，那么默認(rèn)生成的table大小為16，否則，會根據(jù)sizeCtl的大小設(shè)置table大小。
2.3 helpTransfer()
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) { // table表不為空并且結(jié)點(diǎn)類型使ForwardingNode類型，并且結(jié)點(diǎn)的nextTable不為空
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)) { // 比較并交換
// 將table的結(jié)點(diǎn)轉(zhuǎn)移到nextTab中
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
此函數(shù)用于在擴(kuò)容時將table表中的結(jié)點(diǎn)轉(zhuǎn)移到nextTable中。
2.4 putTreeVal()
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;
}
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
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);
}
TreeNode<K,V> xp = 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;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
lockRoot();
try {
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
說明：此函數(shù)用于將指定的hash、key、value值添加到紅黑樹中，若已經(jīng)添加了，則返回null，否則返回該結(jié)點(diǎn)。
2.5 treeifyBin()
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) { // 表不為空
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // table表的長度小于最小的長度
// 進(jìn)行擴(kuò)容，調(diào)整某個桶中結(jié)點(diǎn)數(shù)量過多的問題（由于某個桶中結(jié)點(diǎn)數(shù)量超出了閾值，則觸發(fā)treeifyBin）
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 桶中存在結(jié)點(diǎn)并且結(jié)點(diǎn)的hash值大于等于0
synchronized (b) { // 對桶中第一個結(jié)點(diǎn)進(jìn)行加鎖
if (tabAt(tab, index) == b) { // 第一個結(jié)點(diǎn)沒有變化
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) { // 遍歷桶中所有結(jié)點(diǎn)
// 新生一個TreeNode結(jié)點(diǎn)
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null) // 該結(jié)點(diǎn)前驅(qū)為空
// 設(shè)置p為頭結(jié)點(diǎn)
hd = p;
else
// 尾節(jié)點(diǎn)的next域賦值為p
tl.next = p;
// 尾節(jié)點(diǎn)賦值為p
tl = p;
}
// 設(shè)置table表中下標(biāo)為index的值為hd
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
說明：此函數(shù)用于將桶中的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化為紅黑樹，其中，值得注意的是，當(dāng)table的長度未達(dá)到閾值時，會進(jìn)行一次擴(kuò)容操作，該操作會使得觸發(fā)treeifyBin操作的某個桶中的所有元素進(jìn)行一
次重新分配，這樣可以避免某個桶中的結(jié)點(diǎn)數(shù)量太大。
2.6 addCount()
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // counterCells不為空或者比較交換失敗
CounterCell a; long v; int m;
// 無競爭標(biāo)識
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();
}
}
}
說明：此函數(shù)主要完成binCount的值加1的操作。
2.7 get()
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 計算key的hash值
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) { // 表不為空并且表的長度大于0并且key所在的桶不為空
if ((eh = e.hash) == h) { // 表中的元素的hash值與key的hash值相等
if ((ek = e.key) == key || (ek != null && key.equals(ek))) // 鍵相等
// 返回值
return e.val;
}
else if (eh < 0) // 結(jié)點(diǎn)hash值小于0
// 在桶（鏈表/紅黑樹）中查找
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) { // 對于結(jié)點(diǎn)hash值大于0的情況
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
說明：get()根據(jù)key的hash值來計算在哪個桶中，再遍歷桶，查找元素，若找到則返回該結(jié)點(diǎn)，否則，返回null。
