并發(fā)讀寫數(shù)據(jù)一致性保證（Java并發(fā)容器）
寫在前
業(yè)務開發(fā)過程，其實就是用戶業(yè)務數(shù)據(jù)的處理過程，因而開發(fā)的核心任務就是維護數(shù)據(jù)一致不出錯?，F(xiàn)實場景中，多個用戶會并發(fā)讀寫同一份數(shù)據(jù)（如秒殺），不加控制會翻車、加了控制則降低并發(fā)度，影響性能和用戶體驗。
如何優(yōu)雅的進行并發(fā)數(shù)據(jù)控制呢？本質(zhì)上需要解決兩個問題：
讀-寫沖突
寫-寫沖突
讓我們看下Java經(jīng)典的并發(fā)容器CopyOnWriteList以及ConcurrentHashMap是如何協(xié)調(diào)這兩個問題的
CopyOnWriteList
讀寫策略
CopyOnWrite顧名思義即寫時復制策略
針對寫處理，首先加ReentrantLock鎖，然后復制出一份數(shù)據(jù)副本，對副本進行更改之后，再將數(shù)據(jù)引用替換為副本數(shù)據(jù)，完成后釋放鎖
針對讀處理，依賴volatile提供的語義保證，每次讀都能讀到最新的數(shù)組引用
讀-寫沖突
顯然，CopyOnWriteList采用讀寫分離的思想解決并發(fā)讀寫的沖突
當讀操作與寫操作同時發(fā)生時：
如果寫操作未完成引用替換，這時讀操作處理的是原數(shù)組而寫操作處理的數(shù)組副本，互不干擾
如果寫操作已完成引用替換，這時讀操作與寫操作處理的都是同一個數(shù)組引用
可見在讀寫分離的設計下，并發(fā)讀寫過程中，讀不一定能實時看到最新的數(shù)據(jù)，也就是所謂的弱一致性。
也正是由于犧牲了強一致性，可以讓讀操作無鎖化，支撐高并發(fā)讀
寫-寫沖突
當多個寫操作的同時發(fā)生時，先拿到鎖的先執(zhí)行，其他線程只能阻塞等到鎖的釋放
簡單粗暴又行之有效，但并發(fā)性能相對較差
ConcurrentHashMap（JDK7）
讀寫策略
主要采用分段鎖的思想，降低同時操作一份數(shù)據(jù)的概率
針對讀操作：
先在數(shù)組中定位Segment并利用UNSAFE.getObjectVolatile原子讀語義獲取Segment
接著在數(shù)組中定位HashEntry并利用UNSAFE.getObjectVolatile原子讀語義獲取HashEntry
然后依賴final不變的next指針遍歷鏈表
找到對應的volatile值
針對寫操作：
先在數(shù)組中定位Segment并利用UNSAFE.getObjectVolatile原子讀語義獲取Segment
然后嘗試加鎖ReentrantLock
接著在數(shù)組中定位HashEntry并利用UNSAFE.getObjectVolatile原子讀語義獲取HashEntry鏈表頭節(jié)點
遍歷鏈表，若找到已存在的key，則利用UNSAFE.putOrderedObject原子寫新值，若找不到，則創(chuàng)建一個新的節(jié)點，插入到鏈表頭，同時利用UNSAFE.putOrderedObject原子更新鏈表頭
完成操作后釋放鎖
讀-寫沖突
若并發(fā)讀寫的數(shù)據(jù)不位于同一個Segment，操作是相互獨立的
若位于同一個Segment，ConcurrentHashMap利用了很多Java特性來解決讀寫沖突，使得很多讀操作都無鎖化
當讀操作與寫操作同時發(fā)生時：
若PUT的KEY已存在，直接更新原有的value，此時讀操作在volatile的保證下可以讀到最新值，無需加鎖
若PUT的key不存在增加一個節(jié)點，或刪除一個節(jié)點時，會改變原有的鏈表結構，注意到HashEntry的每個next指針都是final的，因此得復制鏈表，在更新HashEntry數(shù)組元素（即鏈表頭節(jié)點）的時候又是通過UNSAFE提供的語義保證來完成更新的，若新鏈表更新前發(fā)生讀操作，此時還是獲取原有的鏈表，無需加鎖，但是數(shù)據(jù)不是最新的
可見，支持無鎖并發(fā)讀操作還是弱一致的
寫-寫沖突
若并發(fā)寫操作的數(shù)據(jù)不位于同一個Segment，操作是相互獨立的
若位于同一個Segment，多個線程還是由于加ReentrantLock鎖導致阻塞等待
ConcurrentHashMap（JDK8）
讀寫策略
與JDK7相比，少了Segment分段鎖這一層，直接操作Node數(shù)組（鏈表頭數(shù)組），后面稱為桶
針對讀操作，通過UNSAFE.getObjectVolatile原子讀語義獲取最新的value
針對寫操作，由于采用懶惰加載的方式，剛初始化時只確定桶的數(shù)量，并沒有初始默認值。當需要put值的時候先定位下標，然后該下標下桶的值是否為null，如果是，則通過UNSAFE.comepareAndSwapObject(CAS)賦值，如果不為null，則加Synchronized鎖，找到對應的鏈表/紅黑樹的節(jié)點value進行更改，后釋放鎖
讀-寫沖突
若并發(fā)讀寫的數(shù)據(jù)不位于同一個桶（Node數(shù)組），則相互獨立互不干擾
若位于同一個桶，與JDK7的版本相比，簡單了許多，但還是基于Java的特性使得許多讀操作無鎖化
當讀操作與寫操作同時發(fā)生時：
若PUT的key已經(jīng)存在，則直接更新值，此時讀操作在volatile的保證下可以獲取最新值
若PUT的key不存在，會新建一個節(jié)點 或 刪除一個節(jié)點的時候，會改變對原有的結構，這時next指針是volatile的，直接插入到鏈表尾（超過一定長度變成紅黑樹）等對結構的修改，此時讀操作也是可以獲取到最新的next
因此只要寫操作happens-before讀操作，volatile語義就可以保證讀的數(shù)據(jù)是最新的，可以說JDK8版本的ConcurrentHashMap是強一致的（此處只關注基本讀寫（GET/PUT），可能會有弱一致的場景遺漏，例如擴容操作，不過應該是全局加鎖的，如有錯誤煩請指出，共同學習）
寫-寫沖突
若并發(fā)讀寫的數(shù)據(jù)不位于同一個桶，則相互獨立互不干擾
若位于同一個桶，注意到寫操作在不同的場景下采取不同的策略，CAS或Synchronized
當多個寫操作同時發(fā)生時，若桶為null，則CAS應對并發(fā)寫，當?shù)谝粋€寫操作賦值成功后，后面的寫線程CAS失敗，轉(zhuǎn)為競爭Synchronized鎖，阻塞等待
小結
為什么這么設計（個人觀點）
對數(shù)據(jù)進行存儲必然涉及數(shù)據(jù)結構的設計，任何對數(shù)據(jù)的操作都得基于數(shù)據(jù)結構，常規(guī)思路是對整個數(shù)據(jù)結構加鎖，但是鎖的存在會大大影響性能，所以接下來的任務，就是找到哪些可以無鎖化的操作。
操作主要分為兩大類，讀和寫。
先看寫，因為涉及到原有數(shù)據(jù)的改動，不加控制肯定會翻車，怎么控制呢？寫操作也分兩種，一種會改變結構，一種不會：
對于會改變結構的寫，不管底層是數(shù)組還是鏈表，由于改動得基于原有的結構，必然得加鎖串行化保證原子操作，優(yōu)化的點就是鎖層面的優(yōu)化，例如最開始HashTable等synchronized鎖到ConcurrentHashMap1.7版本的ReentrantLock鎖，再到1.8版本的Synchronized改良鎖 ?；蛘邤?shù)據(jù)分散化，concurrnethashmap等基于hash的數(shù)據(jù)結構比CopyOnWriteList的數(shù)據(jù)結構就多了桶分散的優(yōu)勢。
對于不會改變結構的寫，或者改動的頻率不大（桶擴容頻率低），由于鎖的開銷實在是太大了，CAS是個不錯的思路。為什么CopyOnWriteList不用CAS來控制并發(fā)寫，我個人覺得主要原因還是因為結構變化頻繁，可以看下ActomicReferenceArray等基于CAS的數(shù)組容器，都是創(chuàng)建后就不允許結構發(fā)生變化的。
確保數(shù)據(jù)不會改錯之后，讀相對就好辦了，主要考慮是不是要實時讀最新的數(shù)據(jù)（等待寫操作完成），也就是強一致還是弱一致的問題：
強一致的話，讀就得等寫完成，讀寫競爭同一把鎖，這就相互影響了讀寫的效率。大多數(shù)場景下，讀的數(shù)據(jù)一致性要求沒有寫的要求高，可以讀錯，但是堅決不可以寫錯。要是在讀的這一刻，數(shù)據(jù)還沒改完，讀到舊數(shù)據(jù)也沒關系，只要最后寫完對讀可見即可。
還好JMM（Java內(nèi)存模型）有個volatile可見性的語義，可以保證不加鎖的情況下，讀也能看到寫更改的數(shù)據(jù)。此外還有UNSAFE包的各種內(nèi)存直接操作，也可相對高性能的完成可見性語義，
對讀操作而言，最好的數(shù)據(jù)，就是不變的數(shù)據(jù)，不用擔心被修改引發(fā)的各種問題。唯一的不變是變化，一些數(shù)據(jù)還是有變化的可能，如果要支持這種不變性，或者說盡量減少變化的頻率，變化的部分就得在別的地方處理，也就是所謂的讀寫分離
常見面試問題分析
1.ConcurrentHashMap 和 Hashtable 的區(qū)別？
ConcurrentHashMap與HashTable都可以用于多線程的環(huán)境（都是線程安全的容器），但是當Hashtable的大小增加到一定的時候，性能會急劇下降，因為迭代時需要被鎖定很長的時間。因為ConcurrentHashMap引入了分割(segmentation)，不論它變得多么大，僅僅需要鎖定map的某個部分，而其它的線程不需要等到迭代完成才能訪問map。簡而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定map的某個部分，而Hashtable則會鎖定整個map。
（1）底層數(shù)據(jù)結構：
- JDK1.7的ConcurrentHashMap 底層采用分段的數(shù)組+鏈表實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結構跟HashMap1.8的結構一樣，Node數(shù)組+鏈表/紅黑樹;
- Hashtable和JDK1.8之前的HashMap的底層數(shù)據(jù)結構類似都是采用數(shù)組+鏈表的形式，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的；
（2）實現(xiàn)線程安全的方式（重要）：
- 在JDK1.7的時候，ConcurrentHashMap（分段鎖，可重入鎖）對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數(shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭，提高并發(fā)訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結構來實現(xiàn)，并發(fā)控制使用synchronized和CAS來操作。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化）整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結構，但是已經(jīng)簡化了屬性，只是為了兼容舊版本；
- Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態(tài)。如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。
2.ConcurrentHashMap有哪些構造函數(shù)？
//無參構造函數(shù)
public ConcurrentHashMap() {
}
//可傳初始容器大小(initialCapacity)的構造函數(shù)
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
//可傳入map的構造函數(shù)
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
//可設置閾值(加載因子*容量)和初始容量
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
//可設置初始容量和閾值和并發(fā)級別（concurrencyLevel）
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
3.ConcurrentHashMap 底層具體實現(xiàn)知道嗎？實現(xiàn)原理是什么？（怎么保證線程安全的？）
JDK1.7
在JDK1.7中ConcurrentHashMap采用了數(shù)組+Segment+分段鎖的方式實現(xiàn)。
Segment(分段鎖)：ConcurrentHashMap中的分段鎖稱為Segment，它即類似于HashMap的結構，即內(nèi)部擁有一個Entry數(shù)組，數(shù)組中的每個元素又是一個鏈表,同時又是一個ReentrantLock（Segment繼承了ReentrantLock）。
內(nèi)部結構：ConcurrentHashMap使用分段鎖技術，將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。如下圖是ConcurrentHashMap的內(nèi)部結構圖：
從上面的結構我們可以了解到，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部。
JDK1.8
- ConcurrentHashMap取消了Segment分段鎖，采?CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結構跟HashMap1.8的結構類似，數(shù)組+鏈表/紅黑二叉樹。Java 8在鏈表?度超過一定閾值（8）時將鏈表（尋址時間復雜度為O(N)）轉(zhuǎn)換為紅?樹（尋址時間復雜度為O(log(N))）。
- 對于put操作，如果Key對應的數(shù)組元素為null，則通過CAS操作將其設置為當前值。如果Key對應的數(shù)組元素（也即鏈表表頭或者樹的根元素）不為null，則對該元素使用synchronized關鍵字申請鎖，然后進行操作。synchronized只鎖定當前鏈表或紅黑二叉樹的首節(jié)點，這樣只要hash不沖突，就不會產(chǎn)?并發(fā)，效率又提升N倍。
- ConcurrentHashMap的get方法不需要加鎖，get方法采用了unsafe方法，來保證線程安全。
ConcurrentHashMap用什么技術保證線程安全？
- jdk1.7：Segment分段鎖+HashEntry（存儲鍵值對數(shù)據(jù)）來進行實現(xiàn)的；
- jdk1.8：放棄了Segment臃腫的設計，采用Node+CAS+Synchronized來保證線程安全；
4.ConcurrentHashMap迭代器是強一致性還是弱一致性？HashMap呢？ConcurrentHashMap能完全替代HashTable嗎？
HashTable雖然性能上不如ConcurrentHashMap，但并不能完全被取代，兩者的迭代器的一致性不同的。
ConcurrentHashMap弱一致性：ConcurrentHashMap可以支持在迭代過程中，當iterator被創(chuàng)建后集合再發(fā)生改變就不再是拋出ConcurrentModificationException，取而代之的是在改變時new新的數(shù)據(jù)從而不影響原有的數(shù)據(jù)，iterator完成后再將頭指針替換為新的數(shù)據(jù)，這樣iterator線程可以使用原來老的數(shù)據(jù)，而寫線程（添加元素等）也可以并發(fā)的完成改變，更重要的，這保證了多個線程并發(fā)執(zhí)行的連續(xù)性和擴展性，是性能提升的關鍵。ConcurrentHashMap的get，clear，iterator 都是弱一致性的。
hashmap強一致性：HashMap則拋出了ConcurrentModificationException，因為HashMap包含一個修改計數(shù)器modCount，當你調(diào)用他的next()方法來獲取下一個元素時，迭代器將會用到這個計數(shù)器。
兩者應用具體分析：
- Hashtable的任何操作都會把整個map鎖住，是阻塞的。好處是總能獲取最實時的更新，比如說線程A調(diào)用putAll寫入大量數(shù)據(jù)，期間線程B調(diào)用get，線程B就會被阻塞，直到線程A完成putAll，因此線程B肯定能獲取到線程A寫入的完整數(shù)據(jù)。壞處是所有調(diào)用都要排隊，效率較低。
- ConcurrentHashMap 是設計為非阻塞的。在更新時會局部鎖住某部分數(shù)據(jù)，但不會把整個map都鎖住。同步讀取操作則是完全非阻塞的。好處是在保證合理的同步前提下，效率很高。壞處 是嚴格來說讀取操作不能保證反映最近的更新。例如線程A調(diào)用putAll寫入大量數(shù)據(jù)，期間線程B調(diào)用get，則只能get到目前為止已經(jīng)順利插入的部分 數(shù)據(jù)。
選擇哪一個，是在性能與數(shù)據(jù)一致性之間權衡。ConcurrentHashMap適用于追求性能的場景，大多數(shù)線程都只做insert/delete操作，對讀取數(shù)據(jù)的一致性要求較低。
5.ConcurrentHashMap如何發(fā)生ReHash？
ConcurrentLevel并發(fā)級別（ 實際上是Segment的實際數(shù)量 默認16） 一旦設定的話，就不會改變。ConcurrentHashMap當元素個數(shù)大于臨界值的時候，就會發(fā)生擴容。但是ConcurrentHashMap與其他的HashMap不同的是，它不會對Segment 數(shù)量增大，只會增加Segment 后面的鏈表容量的大小。即對每個Segment 的元素進行的ReHash操作。
巨人的肩膀：
