ConcurrentHashMap源碼分析

1. hashmap實現(xiàn)線程安全的方式介紹

2. 并發(fā)容器是如何實現(xiàn)線程安全的（底層的介紹）

3. hashmap和concurrenthashmap進(jìn)行對比

1. hashtable

2. colletions.synchronizedMap()方法

3. ConcurrentHashMap

private?final Node[] initTable() {
????????Node[] tab; int?sc;
????????while?((tab = table) == null?|| tab.length == 0) {
????????????if?((sc = sizeCtl) < 0)
????????????????Thread.yield(); // lost initialization race; just spin
????????????else?if?(U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
????????????????try?{
????????????????????if?((tab = table) == null?|| tab.length == 0) {
????????????????????????int?n = (sc > 0) ? sc : DEFAULT_CAPACITY;
????????????????????????@SuppressWarnings("unchecked")
????????????????????????Node[] nt = (Node[])new?Node[n];
????????????????????????table = tab = nt;
????????????????????????sc = n - (n >>> 2);
????????????????????}
????????????????} finally?{
????????????????????sizeCtl = sc;
????????????????}
????????????????break;
????????????}
????????}
????????return?tab;
????}

1. 首先計算hash值，定位到該table索引位置，如果是首節(jié)點(diǎn)符合就返回

2. 如果遇到擴(kuò)容的時候，會調(diào)用標(biāo)志正在擴(kuò)容節(jié)點(diǎn)ForwardingNode的find方法，查找該節(jié)點(diǎn)，匹配就返回

3. 以上都不符合的話，就往下遍歷節(jié)點(diǎn)，匹配就返回，否則最后就返回null

//會發(fā)現(xiàn)源碼中沒有一處加了鎖
public?V get(Object key) {
????Node[] tab; Node e, p; int?n, eh; K ek;
????int?h = spread(key.hashCode()); //計算hash
????if?((tab = table) != null?&& (n = tab.length) > 0?&&
????????(e = tabAt(tab, (n - 1) & h)) != null) {//讀取首節(jié)點(diǎn)的Node元素
????????if?((eh = e.hash) == h) { //如果該節(jié)點(diǎn)就是首節(jié)點(diǎn)就返回
????????????if?((ek = e.key) == key || (ek != null?&& key.equals(ek)))
????????????????return?e.val;
????????}
????????//hash值為負(fù)值表示正在擴(kuò)容，這個時候查的是ForwardingNode的find方法來定位到nextTable來
????????//eh=-1，說明該節(jié)點(diǎn)是一個ForwardingNode，正在遷移，此時調(diào)用ForwardingNode的find方法去nextTable里找。
????????//eh=-2，說明該節(jié)點(diǎn)是一個TreeBin，此時調(diào)用TreeBin的find方法遍歷紅黑樹，由于紅黑樹有可能正在旋轉(zhuǎn)變色，所以find里會有讀寫鎖。
????????//eh>=0，說明該節(jié)點(diǎn)下掛的是一個鏈表，直接遍歷該鏈表即可。
????????else?if?(eh < 0)
????????????return?(p = e.find(h, key)) != null?? p.val : null;
????????while?((e = e.next) != null) {//既不是首節(jié)點(diǎn)也不是ForwardingNode，那就往下遍歷
????????????if?(e.hash == h &&
????????????????((ek = e.key) == key || (ek != null?&& key.equals(ek))))
????????????????return?e.val;
????????}
????}
????return?null;
}

• volatile關(guān)鍵字對于基本類型的修改可以在隨后對多個線程的讀保持一致，但是對于引用類型如數(shù)組，實體bean，僅僅保證引用的可見性，但并不保證引用內(nèi)容的可見性。

• 禁止進(jìn)行指令重排序。

• 如果對聲明了volatile的變量進(jìn)行寫操作，JVM就會向處理器發(fā)送一條指令，將這個變量所在緩存行的數(shù)據(jù)寫回到系統(tǒng)內(nèi)存。但是，就算寫回到內(nèi)存，如果其他處理器緩存的值還是舊的，再執(zhí)行計算操作就會有問題。

• 在多處理器下，為了保證各個處理器的緩存是一致的，就會實現(xiàn)緩存一致性協(xié)議，當(dāng)某個CPU在寫數(shù)據(jù)時，如果發(fā)現(xiàn)操作的變量是共享變量，則會通知其他CPU告知該變量的緩存行是無效的，因此其他CPU在讀取該變量時，發(fā)現(xiàn)其無效會重新從主存中加載數(shù)據(jù)。

  
  

  

  
  

  總結(jié)下來：

  
  

• 第一：使用volatile關(guān)鍵字會強(qiáng)制將修改的值立即寫入主存；

• 第二：使用volatile關(guān)鍵字的話，當(dāng)線程2進(jìn)行修改時，會導(dǎo)致線程1的工作內(nèi)存中緩存變量的緩存行無效（反映到硬件層的話，就是CPU的L1或者L2緩存中對應(yīng)的緩存行無效）；

• 第三：由于線程1的工作內(nèi)存中緩存變量的緩存行無效，所以線程1再次讀取變量的值時會去主存讀取。

/**
?????* The array of bins. Lazily initialized upon first insertion.
?????* Size is always a power of two. Accessed directly by iterators.
?????*/
????transient volatile Node[]?table;

static?class?Node<K,V> implements?Map.Entry<K,V> {
????final?int?hash;
????final?K key;
????//可以看到這些都用了volatile修飾
????volatile?V val;
????volatile?Node next;

????Node(int?hash, K key, V val, Node next) {
????????this.hash = hash;
????????this.key = key;
????????this.val = val;
????????this.next = next;
????}

????public?final?K getKey()???????{ return?key; }
????public?final?V getValue()?????{ return?val; }
????public?final?int?hashCode()???{ return?key.hashCode() ^ val.hashCode(); }
????public?final?String toString(){ return?key + "="?+ val; }
????public?final?V setValue(V value)?{
????????throw?new?UnsupportedOperationException();
????}

????public?final?boolean?equals(Object o)?{
????????Object k, v, u; Map.Entry e;
????????return?((o instanceof?Map.Entry) &&
????????????????(k = (e = (Map.Entry)o).getKey()) != null?&&
????????????????(v = e.getValue()) != null?&&
????????????????(k == key || k.equals(key)) &&
????????????????(v == (u = val) || v.equals(u)));
????}

????/**
?????* Virtualized support for map.get(); overridden in subclasses.
?????*/
????Node find(int?h, Object k)?{
????????Node e = this;
????????if?(k != null) {
????????????do?{
????????????????K ek;
????????????????if?(e.hash == h &&
????????????????????((ek = e.key) == k || (ek != null?&& k.equals(ek))))
????????????????????return?e;
????????????} while?((e = e.next) != null);
????????}
????????return?null;
????}
}

1. 若插入位置元素為null 則通過cas進(jìn)行插入元素

2. 若插入元素不為空則對頭節(jié)點(diǎn)元素進(jìn)行加鎖操作，進(jìn)行插入元素操作

3. 第二步需要判斷頭結(jié)點(diǎn)類型若為鏈表使用鏈表方式進(jìn)行插入否則使用樹節(jié)點(diǎn)形式進(jìn)行插入

1. 初始化時counterCells為空，在并發(fā)量很高時，如果存在兩個線程同時執(zhí)行CAS修改baseCount值，則失敗的線程會繼續(xù)執(zhí)行方法體中的邏輯，使用CounterCell記錄元素個數(shù)的變化；

2. 如果CounterCell數(shù)組counterCells為空，調(diào)用fullAddCount()方法進(jìn)行初始化，并插入對應(yīng)的記錄數(shù)，通過CAS設(shè)置cellsBusy字段，只有設(shè)置成功的線程才能初始化CounterCell數(shù)組。

3. 如果通過CAS設(shè)置cellsBusy字段失敗的話，則繼續(xù)嘗試通過CAS修改baseCount字段，如果修改baseCount字段成功的話，就退出循環(huán)，否則繼續(xù)循環(huán)插入CounterCell對象；