1.7與1.8區(qū)別
1.7采用分段鎖的概念糕韧，如下圖所示葱跋，每段包含多個節(jié)點页滚，并且都是加悲觀鎖
1.8同樣是采用分段鎖的思想烁竭，只是這次將分段鎖的粒度降低到節(jié)點級別菲茬，并且采用了部分CAS樂觀鎖的操作，大大提升了并發(fā)性能
數(shù)據(jù)結構沿用了與它同時期的HashMap版本的思想，底層依然由數(shù)組+鏈表+紅黑樹的方式思想生均。
有一個最重要的不同點就是ConcurrentHashMap不允許key或value為null值
重點變量
/**
* 盛裝Node元素的數(shù)組 它的大小是2的整數(shù)次冪
* Size is always a power of two. Accessed directly by iterators.
*/
transient volatile Node<K,V>[] table;
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
hash表初始化或擴容時的一個控制位標識量听想。
負數(shù)代表正在進行初始化或擴容操作
-1代表正在初始化
-N 表示有N-1個線程正在進行擴容操作
正數(shù)或0代表hash表還沒有被初始化，這個數(shù)值表示初始化或下一次進行擴容的大小
*/
private transient volatile int sizeCtl;
Node
Node是ConcurrentHashMap最核心的內部類马胧，每個Node可以理解為數(shù)組中的一個節(jié)點
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;//帶有同步鎖的value
volatile Node<K,V> next;//帶有同步鎖的next指針
get
因為Node的val值域是volatile的汉买，所以無需加鎖就可以得到節(jié)點的最新值
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//計算hash值
int h = spread(key.hashCode());
//根據(jù)hash值確定節(jié)點位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//如果搜索到的節(jié)點key與傳入的key相同且不為null,直接返回這個節(jié)點
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果eh<0 說明這個節(jié)點在樹上 直接尋找
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//否則遍歷鏈表 找到對應的值并返回
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
put
簡潔說明：
- 根據(jù)給定的key的hash值找到其在table中的位置index
- 找到位置index后，根據(jù)以下情況進行存儲或者幫助擴容后存儲
- 如果當前正在擴容佩脊，則優(yōu)先幫助擴容
- 如果table[index]位置沒有元素蛙粘，則直接通過CAS存儲
- 如果table[i]存儲的是一個鏈表：如果鏈表不存在key則直接加入到鏈表尾部；如果存在key則更新其對應的value威彰；如果存入后鏈表元素>8出牧，還需要將鏈表轉換為紅黑樹
- 如果table[i]存儲的是一個紅黑樹，則按照紅黑樹方式插入
其中3跟4需要synchronized對頭節(jié)點進行加鎖
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) {
//不允許 key或value為null
if (key == null || value == null) throw new NullPointerException();
//計算hash值
int hash = spread(key.hashCode());
int binCount = 0;
//死循環(huán) 何時插入成功 何時跳出
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果table為空的話歇盼，初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//根據(jù)hash值計算出在table里面的位置
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果這個位置沒有值 舔痕，直接放進去，不需要加鎖
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)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//結點上鎖 這里的結點可以理解為hash值相同組成的鏈表的頭結點
synchronized (f) {
if (tabAt(tab, i) == f) {
//fh〉0 說明這個節(jié)點是一個鏈表的節(jié)點 不是樹的節(jié)點
if (fh >= 0) {
binCount = 1;
//在這里遍歷鏈表所有的結點
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果hash值和key值相同 則修改對應結點的value值
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;
//如果遍歷到了最后一個結點伯复，那么就證明新的節(jié)點需要插入 就把它插入在鏈表尾部
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果這個節(jié)點是樹節(jié)點，就按照樹的方式插入值
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//如果鏈表長度已經(jīng)達到臨界值8 就需要把鏈表轉換為樹結構
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//將當前ConcurrentHashMap的元素數(shù)量+1
addCount(1L, binCount);
return null;
}
size
ConcurrentHashMap 中鍵值對的個數(shù)通過求 baseCount 與 counterCells 非空元素的和得到
/**
* Base counter value, used mainly when there is no contention,
* but also as a fallback during table initialization
* races. Updated via CAS.
* 當沒有爭用時邢笙，使用這個變量計數(shù)啸如。
*/
private transient volatile long baseCount;
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
一個 volatile 的變量，在 addCount 方法中會使用它氮惯，而 addCount 方法在 put 結束后會調用叮雳。在 addCount 方法中，會對這個變量做 CAS 加法
但是如果并發(fā)導致 CAS 失敗了妇汗，使用 counterCells
如果使用 counterCells CAS 失敗了帘不，在 fullAddCount 方法中，會繼續(xù)死循環(huán)操作杨箭，直到成功
這種方式目的是降低更新size時的沖突厌均，提升性能
擴容
整個擴容操作分為兩個部分
第一部分是構建一個nextTable,它的容量是原來的兩倍，這個操作是單線程完成的告唆。這個單線程的保證是通過RESIZE_STAMP_SHIFT這個常量經(jīng)過一次運算來保證的
第二個部分就是將原來table中的元素復制到nextTable中棺弊，這里允許多線程進行操作。
先來看一下單線程是如何完成的：
它的大體思想就是遍歷擒悬、復制的過程模她。首先根據(jù)運算得到需要遍歷的次數(shù)i，然后利用tabAt方法獲得i位置的元素：
如果這個位置為空懂牧，就在原table中的i位置放入forwardNode節(jié)點侈净，這個也是觸發(fā)并發(fā)擴容的關鍵點尊勿；
如果這個位置是Node節(jié)點（fh>=0），如果它是一個鏈表的頭節(jié)點畜侦，就構造一個反序鏈表元扔，把他們分別放在nextTable的i和i+n的位置上，然后在原table中的i位置放入forwardNode節(jié)點
如果這個位置是TreeBin節(jié)點（fh<0）旋膳，也做一個反序處理澎语，并且判斷是否需要untreeify，把處理的結果分別放在nextTable的i和i+n的位置上验懊，然后在原table中的i位置放入forwardNode節(jié)點
遍歷過所有的節(jié)點以后就完成了復制工作擅羞，這時讓nextTable作為新的table，并且更新sizeCtl為新容量的0.75倍 义图，完成擴容减俏。
再看一下多線程是如何完成的：
多線程遍歷節(jié)點，處理了一個節(jié)點碱工，就把對應點的值set為forward娃承，另一個線程看到ForwardingNode節(jié)點，就向后遍歷怕篷。
Key和Value不允許null值
ConcurrentHashmap和Hashtable都是支持并發(fā)的草慧，這樣會有一個問題，當你通過get(k)獲取對應的value時匙头，如果獲取到的是null時，你無法判斷仔雷，它是put（k,v）的時候value為null蹂析，還是這個key從來沒有做過映射。
HashMap是非并發(fā)的碟婆，可以通過contains(key)來做這個判斷电抚。
而ConcurrentHashMap在調用m.containsKey(key)和m.get(key)，這兩個方法都是沒有加鎖的竖共，調用時候m可能被其他線程改變了蝙叛。
假如一個線程m.containsKey(k)為真，在還沒執(zhí)行m.get(k)的時候公给，k被另外一個線程給刪除了借帘，那么m.get(k)會返回null。如果允許null值的話淌铐，就會錯誤的判斷為k還存在肺然；因此不允許null值的話就可以正常的表示出當前的k是不存在的。所以在ConcurrentHashMap不應該有如下的寫法腿准，Key和Value不允許null值际起。
其實Value不允許null值就可以，Key為null似乎沒什么影響，作者一起排除null我也不知道什么原因街望。
if (m.containsKey(k)) {
return m.get(k);
} else {
throw new KeyNotPresentException();
}
總結
- Node級別分段鎖
- 讀不加鎖
- 寫不一定需要加鎖
- 可多線程擴容
- size計算方式特殊
