簡(jiǎn)介
HashMap是線程不安全的股冗，所以 Java 還提供了 ConcurrentHashMap 類來解決高并發(fā)下的安全問題州袒。
Java8 中，ConcurrentHashMap 相對(duì)于 Java7 來說纺非， 它是通過 CAS 操作和 synchronized 來實(shí)現(xiàn)線程安全的须蜗， 而 Java7 是使用分段鎖來實(shí)現(xiàn)線程安全的，并且Java7是對(duì)數(shù)組分段同步蓉坎，而 Java8 是對(duì)數(shù)組元素同步澳眷。
這里大致看下的它的源碼，ConcurrentHashMap 相對(duì)于 HashMap 來說蛉艾，因?yàn)樗幚淼牟l(fā)的情況钳踊，所以源碼會(huì)復(fù)雜不少，這里做個(gè)大致了解與 HashMap 做個(gè)對(duì)比勿侯。
依然從 put 開始了解 ConcurrentHashMap 是如何實(shí)現(xiàn)線程安全的拓瞪。
源碼分析 Java8
put 方法
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
//這里可以直接發(fā)現(xiàn)一個(gè)和 HashMap 不同的地方， ConcurrentHashMap 不支持含 null 的鍵值對(duì)
if (key == null || value == null) throw new NullPointerException();
//計(jì)算哈希值
int hash = spread(key.hashCode());
//這個(gè)值將用來記錄鏈表或者紅黑樹長(zhǎng)度
int binCount = 0;
//此處開始自旋
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//如果數(shù)組不存在或者長(zhǎng)度為 0,則初始化數(shù)組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果計(jì)算出來的位置在數(shù)組中還沒有存放對(duì)象助琐，那么通過 CAS 來放入
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
//由于可能在高并發(fā)的情況下祭埂， 所以正在擴(kuò)容的時(shí)候也要考慮，這里會(huì)幫助擴(kuò)容
tab = helpTransfer(tab, f);
else {
//如果該位置不為空兵钮，則可能有鏈表或者紅黑樹
V oldVal = null;
//使用 synchronized 同步該位置下對(duì)應(yīng)的數(shù)組里的對(duì)象
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//如果存在鏈表
binCount = 1;
//遍歷鏈表
for (Node<K,V> e = f;; ++binCount) {
//接來下的邏輯和 HashMap 一樣蛆橡，在鏈表尾部插入新對(duì)象
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!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) {
//如果當(dāng)前塊里是紅黑樹
Node<K,V> p;
binCount = 2;
//此處遍歷紅黑樹
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
//如果 key 相同， 那么根據(jù) onlyIfAbsent 判斷是否需要替換
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
// 鏈表節(jié)點(diǎn)大于8 轉(zhuǎn)成紅黑樹
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//擴(kuò)容的邏輯也在這里面
addCount(1L, binCount);
return null;
}
ConcurrentHashMap 的 put 方法掘譬，首先自旋泰演，如果存放對(duì)象的塊中為 null 時(shí)，將通過 CAS 來放入新鍵值對(duì)葱轩，如果已經(jīng)存在對(duì)象的話睦焕，則使用 synchronized 給插入操作上鎖藐握。
如果發(fā)現(xiàn)正在擴(kuò)容，那么將會(huì)利用并發(fā)的特性垃喊，來幫助擴(kuò)容猾普。
補(bǔ)上初始化數(shù)組的方法 initTable。
initTable 方法
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//不斷循環(huán)直到數(shù)組建立
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
//如果 sizeCtl 小于 0,則說明有其他地方先初始化數(shù)組本谜，所以放棄執(zhí)行權(quán)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
//不然就通過 CAS 來修改 sizeCtl 值為 -1 初家，告訴其它線程數(shù)組正在初始化
try {
//接下來就是創(chuàng)建一個(gè)數(shù)組
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
//創(chuàng)建完數(shù)組后就將 sizeCtl 修改
sizeCtl = sc;
}
break;
}
}
//返回創(chuàng)建好的數(shù)組
return tab;
}
可以看出 ConcurrentHashMap 初始化數(shù)組的核心是 sizeCtl 這個(gè)值，這個(gè)值是 volatile 修飾的耕突，保證了它的可見性笤成，通過判斷這個(gè)值是不是小于 0，來決定是否需要執(zhí)行數(shù)組的初始化眷茁。
最后
從這兩段源碼可以看出 ConcurrentHashMap 是怎么樣實(shí)現(xiàn)一個(gè)線程安全的 HashMap 了。
這里引出一下 HashTable 為什么被棄用的問題纵诞。
HashTable 與 HashMap 的不同
- 不支持 null 鍵值對(duì)上祈，HashMap 可以。
- 線程安全浙芙，是對(duì)修改過程同步實(shí)現(xiàn)的登刺，這樣效率會(huì)很低。而 HashMap 不是線程安全嗡呼。
- 初始容量是 11纸俭， 擴(kuò)容是 2 * oldCap + 1, HashMap 為 16，2 * oldCap南窗。
- 初始容量即擴(kuò)容大小不一樣揍很，所以計(jì)算 index 的值方法也不一樣。
為什么棄用 HashTable
原因主要出在上面第二點(diǎn)万伤，它的修改是對(duì)整個(gè)方法同步實(shí)現(xiàn)的窒悔，效率會(huì)低非常多，同時(shí)它與 HashMap 還是有許多不同的地方敌买， ConcurrentHashMap 在容量以及擴(kuò)容規(guī)則等都延續(xù)了 HashMap简珠。
