concurrenthashmap的初步使用及場景
concurrenthashmap是j.u.c包裡面提供的一個線程安全并且高效的hashmap，是以concurrenthashmap在并發程式設計的場景中使用的頻率比較高，那麼這一節課我們就從concurrenthashmap的使用上以及源碼層面來分析concurrenthashmap到底是如何實作安全性的
concurrenthashmap是map的派生類，是以api基本和hashmap是類似，主要就是put、get這些方法，接下來基于concurrenthashmap的put和get這兩個方法作為切入點來分析concurrenthashmap的源碼實作
concurrenthashmap的源碼分析
先要做一個說明，這節課分析的concurrenthashmap是基于jdk1.8的版本。 jdk1.7和jdk1.8版本的變化 concurrenthashmap和hashmap的實作原理是差不多的，但是因為concurrenthashmap需要支援并發操作，是以在實作上要比hashmap稍微複雜一些。 在jdk1.7的實作上，conrruenthashmap由一個個segment組成，簡單來說，concurrenthashmap是一個segment數組，它通過繼承reentrantlock來進行加鎖，通過每次鎖住一個segment來保證每個segment内的操作的線程安全性進而實作全局線程安全。整個結構圖如下
當每個操作分布在不同的segment上的時候，預設情況下，理論上可以同時支援16個線程的并發寫入。 相比于1.7版本，它做了兩個改進
取消了segment分段設計，直接使用node數組來儲存資料，并且采用node數組元素作為鎖來實作每一行資料進行加鎖來進一步減少并發沖突的機率
将原本數組+單向連結清單的資料結構變更為了數組+單向連結清單+紅黑樹的結構。為什麼要引入紅黑樹呢？在正常情況下，key hash之後如果能夠很均勻的分散在數組中，那麼table數組中的每個隊列的長度主要為0或者1.但是實際情況下，還是會存在一些隊列長度過長的情況。如果還采用單向清單方式，那麼查詢某個節點的時間複雜度就變為o(n); 是以對于隊列長度超過8的清單，jdk1.8采用了紅黑樹的結構，那麼查詢的時間複雜度就會降低到o(logn),可以提升查找的性能；
這個結構和jdk1.8版本中的hashmap的實作結構基本一緻，但是為了保證線程安全性，concurrenthashmap的實作會稍微複雜一下。接下來我們從源碼層面來了解一下它的原理. 我們基于put和get方法來分析它的實作即可
假如在上面這段代碼中存在兩個線程，在不加鎖的情況下：線程a成功執行castabat操作後，随後的線程b可以通過tabat方法立刻看到table[i]的改變。原因如下：線程a的castabat操作，具有volatile讀寫相同的記憶體語義，根據volatile的happens-before規則：線程a的castabat操作，一定對線程b的tabat操作可見
數組初始化方法，這個方法比較簡單，就是初始化一個合适大小的數組 sizectl這個要單獨說一下，如果沒搞懂這個屬性的意義，可能會被搞暈 這個标志是在node數組初始化或者擴容的時候的一個控制位辨別，負數代表正在進行初始化或者擴容操作 -1 代表正在初始化 -n 代表有n-1有二個線程正在進行擴容操作，這裡不是簡單的了解成n個線程，sizectl就是-n,這塊後續在講擴容的時候會說明 0辨別node數組還沒有被初始化，正數代表初始化或者下一次擴容的大小
該方法擷取對象中offset偏移位址對應的對象field的值。實際上這段代碼的含義等價于tab[i], 但是為什麼不直接使用tab[i]來計算呢？ getobjectvolatile，一旦看到volatile關鍵字，就表示可見性。因為對volatile寫操作happen-before于volatile讀操作，是以其他線程對table的修改均對get讀取可見； 雖然table數組本身是增加了volatile屬性，但是“volatile的數組隻針對數組的引用具有volatile的語義，而不是它的元素”。 是以如果有其他線程對這個數組的元素進行寫操作，那麼目前線程來讀的時候不一定能讀到最新的值。 出于性能考慮，doug lea直接通過unsafe類來對table進行操作。
在putval方法執行完成以後，會通過addcount來增加concurrenthashmap中的元素個數，并且還會可能觸發擴容操作。這裡會有兩個非常經典的設計
高并發下的擴容
如何保證addcount的資料安全性以及性能
在putval最後調用addcount的時候，傳遞了兩個參數，分别是1和bincount(連結清單長度)，看看addcount方法裡面做了什麼操作 x表示這次需要在表中增加的元素個數，check參數表示是否需要進行擴容檢查，大于等于0都需要進行檢查
concurrenthashmap是采用countercell數組來記錄元素個數的，像一般的集合記錄集合大小，直接定義一個size的成員變量即可，當出現改變的時候隻要更新這個變量就行。為什麼concurrenthashmap要用這種形式來處理呢？ 問題還是處在并發上，concurrenthashmap是并發集合，如果用一個成員變量來統計元素個數的話，為了保證并發情況下共享變量的的難全興，勢必會需要通過加鎖或者自旋來實作，如果競争比較激烈的情況下，size的設定上會出現比較大的沖突反而影響了性能，是以在concurrenthashmap采用了分片的方法來記錄大小，具體什麼意思，我們來分析下
fulladdcount主要是用來初始化countercell，來記錄元素個數，裡面包含擴容，初始化等操作
初始化長度為2的數組，然後随機得到指定的一個數組下标，将需要新增的值加入到對應下标位置處
判斷是否需要擴容，也就是當更新後的鍵值對總數basecount >= 門檻值sizectl時，進行rehash，這裡面會有兩個邏輯。
如果目前正在處于擴容階段，則目前線程會加入并且協助擴容
如果目前沒有在擴容，則直接觸發擴容操作
這塊邏輯要了解起來，也有一點複雜。 resizestamp用來生成一個和擴容有關的擴容戳，具體有什麼作用呢？我們基于它的實作來做一個分析
擴容是concurrenthashmap的精華之一，擴容操作的核心在于資料的轉移，在單線程環境下資料的轉移很簡單，無非就是把舊數組中的資料遷移到新的數組。但是這在多線程環境下，在擴容的時候其他線程也可能正在添加元素，這時又觸發了擴容怎麼辦？可能大家想到的第一個解決方案是加互斥鎖，把轉移過程鎖住，雖然是可行的解決方案，但是會帶來較大的性能開銷。因為互斥鎖會導緻所有通路臨界區的線程陷入到阻塞狀态，持有鎖的線程耗時越長，其他競争線程就會一直被阻塞，導緻吞吐量較低。而且還可能導緻死鎖。 而concurrenthashmap并沒有直接加鎖，而是采用cas實作無鎖的并發同步政策，最精華的部分是它可以利用多線程來進行協同擴容 簡單來說，它把node數組當作多個線程之間共享的任務隊列，然後通過維護一個指針來劃分每個線程鎖負責的區間，每個線程通過區間逆向周遊來實作擴容，一個已經遷移完的bucket會被替換為一個forwardingnode節點，标記目前bucket已經被其他線程遷移完了。接下來分析一下它的源碼實作 1、fwd:這個類是個辨別類，用于指向新表用的，其他線程遇到這個類會主動跳過這個類，因為這個類要麼就是擴容遷移正在進行，要麼就是已經完成擴容遷移，也就是這個類要保證線程安全，再進行操作。 2、advance:這個變量是用于提示代碼是否進行推進處理，也就是目前桶處理完，處理下一個桶的辨別 3、finishing:這個變量用于提示擴容是否結束用的
concurrenthashmap支援并發擴容，實作方式是，把node數組進行拆分，讓每個線程處理自己的區域，假設table數組總長度是64，預設情況下，那麼每個線程可以分到16個bucket。 然後每個線程處理的範圍，按照倒序來做遷移 通過for自循環處理每個槽位中的連結清單元素，預設advace為真，通過cas設定transferindex屬性值，并初始化i和bound值，i指目前處理的槽位序号，bound指需要處理的槽位邊界，先處理槽位31的節點； （bound,i） =(16,31) 從31的位置往前推動。
假設這個時候threada在進行transfer，那麼邏輯圖表示如下
在目前假設條件下，槽位15中沒有節點，則通過cas插入在第二步中初始化的forwardingnode節點，用于告訴其它線程該槽位已經處理過了；
在擴容操作transfer的第2414行，代碼如下
concurrenthashmap在做連結清單遷移時，會用高低位來實作，這裡有兩個問題要分析一下
如何實作高低位連結清單的區分 假如我們有這樣一個隊列
第14個槽位插入新節點之後，連結清單元素個數已經達到了8，且數組長度為16，優先通過擴容來緩解連結清單過長的問題，擴容這塊的圖解稍後再分析，先分析高低位擴容的原理 假如目前線程正在處理槽位為14的節點，它是一個連結清單結構，在代碼中，首先定義兩個變量節點ln和hn，實際就是lownode和highnode，分别儲存hash值的第x位為0和不等于0的節點 通過fn&n可以把這個連結清單中的元素分為兩類，a類是hash值的第x位為0，b類是hash值的第x位為不等于0（至于為什麼要這麼區分，稍後分析），并且通過lastrun記錄最後要處理的節點。最終要達到的目的是，a類的連結清單保持位置不動，b類的連結清單為14+16(擴容增加的長度)=30 我們把14槽位的連結清單單獨伶出來，我們用藍色表示 fn&n=0的節點，假如連結清單的分類是這樣
接着，通過cas操作，把hn鍊放在i+n也就是14+16的位置，ln鍊保持原來的位置不動。并且設定目前節點為fwd，表示已經被目前線程遷移完了
遷移完成以後的資料分布如下
要想了解這麼設計的目的，我們需要從concurrenthashmap的根據下标擷取對象的算法來看，在putval方法中1018行
如果線程擴容結束，那麼需要退出，就會執行transfer方法的如下代碼
如果對應的節點存在，判斷這個節點的hash是不是等于moved(-1)，說明目前節點是forwardingnode節點， 意味着有其他線程正在進行擴容，那麼目前現在直接幫助它進行擴容，是以調用helptransfer方法
這個方法的主要作用是，如果被添加的節點的位置已經存在節點的時候，需要以連結清單的方式加入到節點中 如果目前節點已經是一顆紅黑樹，那麼就會按照紅黑樹的規則将目前節點加入到紅黑樹中
判斷連結清單的長度是否已經達到臨界值8. 如果達到了臨界值，這個時候會根據目前數組的長度來決定是擴容還是将連結清單轉化為紅黑樹。也就是說如果目前數組的長度小于64，就會先擴容。否則，會把目前連結清單轉化為紅黑樹
在putval的最後部分，有一個判斷，如果連結清單長度大于8，那麼就會觸發擴容或者紅黑樹的轉化操作。
trypresize裡面部分代碼和addcount的部分代碼類似，看起來會稍微簡單一些