簡介
HashMap是線程不安全的，所以 Java 還提供了 ConcurrentHashMap 類來解決高并發(fā)下的安全問題。
Java8 中，ConcurrentHashMap 相對于 Java7 來說， 它是通過 CAS 操作和 synchronized 來實現(xiàn)線程安全的， 而 Java7 是使用分段鎖來實現(xiàn)線程安全的，并且Java7是對數(shù)組分段同步，而 Java8 是對數(shù)組元素同步。
這里大致看下的它的源碼，ConcurrentHashMap 相對于 HashMap 來說，因為它處理的并發(fā)的情況，所以源碼會復(fù)雜不少，這里做個大致了解與 HashMap 做個對比。
依然從 put 開始了解 ConcurrentHashMap 是如何實現(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)一個和 HashMap 不同的地方， ConcurrentHashMap 不支持含 null 的鍵值對
if (key == null || value == null) throw new NullPointerException();
//計算哈希值
int hash = spread(key.hashCode());
//這個值將用來記錄鏈表或者紅黑樹長度
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ù)組不存在或者長度為 0,則初始化數(shù)組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果計算出來的位置在數(shù)組中還沒有存放對象，那么通過 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ā)的情況下， 所以正在擴容的時候也要考慮，這里會幫助擴容
tab = helpTransfer(tab, f);
else {
//如果該位置不為空，則可能有鏈表或者紅黑樹
V oldVal = null;
//使用 synchronized 同步該位置下對應(yīng)的數(shù)組里的對象
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//如果存在鏈表
binCount = 1;
//遍歷鏈表
for (Node<K,V> e = f;; ++binCount) {
//接來下的邏輯和 HashMap 一樣，在鏈表尾部插入新對象
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é)點大于8 轉(zhuǎn)成紅黑樹
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//擴容的邏輯也在這里面
addCount(1L, binCount);
return null;
}
ConcurrentHashMap 的 put 方法，首先自旋，如果存放對象的塊中為 null 時，將通過 CAS 來放入新鍵值對，如果已經(jīng)存在對象的話，則使用 synchronized 給插入操作上鎖。
如果發(fā)現(xiàn)正在擴容，那么將會利用并發(fā)的特性，來幫助擴容。
補上初始化數(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)建一個數(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 這個值，這個值是 volatile 修飾的，保證了它的可見性，通過判斷這個值是不是小于 0，來決定是否需要執(zhí)行數(shù)組的初始化。
最后
從這兩段源碼可以看出 ConcurrentHashMap 是怎么樣實現(xiàn)一個線程安全的 HashMap 了。
這里引出一下 HashTable 為什么被棄用的問題。
HashTable 與 HashMap 的不同
- 不支持 null 鍵值對，HashMap 可以。
- 線程安全，是對修改過程同步實現(xiàn)的，這樣效率會很低。而 HashMap 不是線程安全。
- 初始容量是 11， 擴容是 2 * oldCap + 1, HashMap 為 16，2 * oldCap。
- 初始容量即擴容大小不一樣，所以計算 index 的值方法也不一樣。
為什么棄用 HashTable
原因主要出在上面第二點，它的修改是對整個方法同步實現(xiàn)的，效率會低非常多，同時它與 HashMap 還是有許多不同的地方， ConcurrentHashMap 在容量以及擴容規(guī)則等都延續(xù)了 HashMap。
