ConcurrentHashMap也是一種Map，也可以用來存放key-value，但它是線程安全的Map，在高并發(fā)的情況下，不會像HashMap那樣出現(xiàn)添加數(shù)據(jù)丟失，擴展形成死鏈的情況。HashTable也是線程安全的，但是相比HashTable直接加鎖的做法，1.8里面的ConcurrentHashMap采用lock-free顯得更加高效。
Map體系圖
由圖可知，ConcurrentHashMap和HashMap一樣，也是繼承AbstractMap，而AbstractMap實現(xiàn)了Map接口。
ConcurrentHashMap源碼大概了解（1.8）
ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)
/**
* concurrentHashMap存放單個key-value的地方，有TreeBin，TreeNode，F(xiàn)orwardingNode，ReservationNode四個子類
*/
static class Node<K,V> implements Map.Entry<K,V> {
/**
* 計算key的得到的哈希值
* int hash = spread(key.hashCode());
* static final int spread(int h) {
* return (h ^ (h >>> 16)) & HASH_BITS;
* }
* static final int HASH_BITS = 0x7fffffff;
*/
final int hash;
final K key;
volatile V val;
//節(jié)點所在的連接中指向的下一個元素
volatile Node<K,V> next;
}
/**
* 跟HashMap一樣，table是存放所有key-value的地方，默認為null，當(dāng)插入元素時會初始化，初始化大小為16，每次擴容為原來的兩倍
*/
transient volatile Node<K,V>[] table;
/**
* 擴容時新生成的數(shù)組，大小為table的兩倍
*/
private transient volatile Node<K,V>[] nextTable;
/**
* 重要屬性，用來控制table的初始化和擴容，
* 0： 默認值，表示初始化table或擴容用默認值16和2倍
* > 0 : 使用sizeCtl的大小來擴容
* -1 ： 表示正在初始化
* -n : 表示有（n - 1）個線程正在擴容
*/
private transient volatile int sizeCtl;
/**
* Node鏈表轉(zhuǎn)成紅黑樹會先判斷當(dāng)前整個map的size是否大于MIN_TREEIFY_CAPACITY并且當(dāng)前鏈表大小大于TREEIFY_THRESHOLD
*/
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
ConcurrentHashMap添加元素
put()源碼
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key 和 value 為null都報空指針異常
if (key == null || value == null) throw new NullPointerException();
//計算hash值
int hash = spread(key.hashCode());
//元素的數(shù)量
int binCount = 0;
//一個死循環(huán)
for (ConcurrentHashMap.Node<K,V>[] tab = table;;) {
ConcurrentHashMap.Node<K,V> f; int n, i, fh;
//如果table為null，說明是第一次插數(shù)據(jù)，要初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//(n - 1) & hash)為元素在table中的位置，tabAt是用來獲取tab的第i個元素是否為空
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//用CAS把節(jié)點置上去，如果節(jié)點不為null返回false
if (casTabAt(tab, i, null,
new ConcurrentHashMap.Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//moved為 -1 ，如果一個節(jié)點的hash值為 -1，表示他是擴容轉(zhuǎn)發(fā)節(jié)點
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//當(dāng)table不為空，并且tab上第i個元素也不為空的時候執(zhí)行這里，說明要形成鏈表了
else {
V oldVal = null;
//加鎖，為什么要加鎖？
synchronized (f) {
//為什么還要再次比較呢？
if (tabAt(tab, i) == f) {
//fh是首節(jié)點的哈希值，大于0說明不是紅黑樹，而是鏈表
if (fh >= 0) {
//鏈表的元素數(shù)量
binCount = 1;
//遍歷鏈表并且插入
for (ConcurrentHashMap.Node<K,V> e = f;; ++binCount) {
K ek;
//如果是已經(jīng)有的元素，替換它的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
ConcurrentHashMap.Node<K,V> pred = e;
//如果已經(jīng)是最后一個元素，把新進來的元素添加進去，否則遍歷鏈表
if ((e = e.next) == null) {
pred.next = new ConcurrentHashMap.Node<K,V>(hash, key,
value, null);
break;
}
}
}
//紅黑樹做紅黑樹的處理
else if (f instanceof ConcurrentHashMap.TreeBin) {
ConcurrentHashMap.Node<K,V> p;
binCount = 2;
if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//如果鏈表元素大于TREEIFY_THRESHOLD 轉(zhuǎn)成紅黑樹
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//返回元素
if (oldVal != null)
return oldVal;
break;
}
}
}
//擴容
addCount(1L, binCount);
return null;
}
initTable()源碼
private final ConcurrentHashMap.Node<K,V>[] initTable() {
ConcurrentHashMap.Node<K,V>[] tab; int sc;
//只有當(dāng)table不為空的時候，才跳出循環(huán)
while ((tab = table) == null || tab.length == 0) {
//sizeCtl< 0 說明有其它線程正在初始化table，線程讓出CPU
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//SIZECTL對應(yīng)的偏移量正式sizeCtl，CAS將sc置為 -1，表示正在初始化，如果返回false，說明傳進去的sc和sizeCtl不一致
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//再次判斷table是否為空
if ((tab = table) == null || tab.length == 0) {
//擴容大小，如果sc>0，則用sizeCtl的值，否則用默認值16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
//初始化table數(shù)據(jù)
@SuppressWarnings("unchecked")
ConcurrentHashMap.Node<K,V>[] nt = (ConcurrentHashMap.Node<K,V>[])new ConcurrentHashMap.Node<?,?>[n];
table = tab = nt;
//這個地方看不懂
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
get()源碼
public V get(Object key) {
ConcurrentHashMap.Node<K,V>[] tab; ConcurrentHashMap.Node<K,V> e, p; int n, eh; K ek;
//計算哈希值
int h = spread(key.hashCode());
//如果table不為空，并且長度大于0，還有對應(yīng)鏈表首節(jié)點不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//如果鏈表首節(jié)點和key的hash值一樣，并且key也一致
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//這個好像是擴容時候的轉(zhuǎn)發(fā)節(jié)點
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//遍歷鏈表直到找到key也一樣的節(jié)點
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap（1.7）也了解一下
1.7中的ConcurrentHashMap采用了分段鎖的機制，底層是一個Segment數(shù)組，而每個Segment可以理解為指向一個HashMap。當(dāng)ConcurrentHashMap進行讀寫操作的時候，首先會計算對應(yīng)Segment數(shù)組的哪個位置，然后計算在segment指向的HashMap的哪個位置。當(dāng)進行寫操作時，會對對應(yīng)的segment進行加鎖，不同的segment并發(fā)操作時不會互相影響。
