并發(fā)讀寫數(shù)據(jù)一致性保證（Java并發(fā)容器）
寫在前
業(yè)務(wù)開發(fā)過程，其實就是用戶業(yè)務(wù)數(shù)據(jù)的處理過程玄捕，因而開發(fā)的核心任務(wù)就是維護數(shù)據(jù)一致不出錯。現(xiàn)實場景中飘蚯，多個用戶會并發(fā)讀寫同一份數(shù)據(jù)（如秒殺）局骤，不加控制會翻車峦甩、加了控制則降低并發(fā)度凯傲，影響性能和用戶體驗冰单。
如何優(yōu)雅的進行并發(fā)數(shù)據(jù)控制呢诫欠？本質(zhì)上需要解決兩個問題：
讀-寫沖突
寫-寫沖突
讓我們看下Java經(jīng)典的并發(fā)容器CopyOnWriteList以及ConcurrentHashMap是如何協(xié)調(diào)這兩個問題的
CopyOnWriteList
讀寫策略
CopyOnWrite顧名思義即寫時復(fù)制策略
針對寫處理轿偎，首先加ReentrantLock鎖坏晦，然后復(fù)制出一份數(shù)據(jù)副本英遭，對副本進行更改之后挖诸，再將數(shù)據(jù)引用替換為副本數(shù)據(jù)多律，完成后釋放鎖
針對讀處理狼荞，依賴volatile提供的語義保證相味，每次讀都能讀到最新的數(shù)組引用
讀-寫沖突
顯然丰涉，CopyOnWriteList采用讀寫分離的思想解決并發(fā)讀寫的沖突
當讀操作與寫操作同時發(fā)生時：
如果寫操作未完成引用替換一死，這時讀操作處理的是原數(shù)組而寫操作處理的數(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指針遍歷鏈表
找到對應(yīng)的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é)點時，會改變原有的鏈表結(jié)構(gòu)续膳，注意到HashEntry的每個next指針都是final的怒见，因此得復(fù)制鏈表，在更新HashEntry數(shù)組元素（即鏈表頭節(jié)點）的時候又是通過UNSAFE提供的語義保證來完成更新的姑宽，若新鏈表更新前發(fā)生讀操作，此時還是獲取原有的鏈表闺阱，無需加鎖炮车，但是數(shù)據(jù)不是最新的
可見，支持無鎖并發(fā)讀操作還是弱一致的
寫-寫沖突
若并發(fā)寫操作的數(shù)據(jù)不位于同一個Segment，操作是相互獨立的
若位于同一個Segment瘦穆，多個線程還是由于加ReentrantLock鎖導(dǎo)致阻塞等待
ConcurrentHashMap（JDK8）
讀寫策略
與JDK7相比纪隙，少了Segment分段鎖這一層，直接操作Node數(shù)組（鏈表頭數(shù)組）扛或，后面稱為桶
針對讀操作绵咱，通過UNSAFE.getObjectVolatile原子讀語義獲取最新的value
針對寫操作，由于采用懶惰加載的方式熙兔，剛初始化時只確定桶的數(shù)量悲伶，并沒有初始默認值。當需要put值的時候先定位下標住涉，然后該下標下桶的值是否為null麸锉，如果是，則通過UNSAFE.comepareAndSwapObject(CAS)賦值舆声，如果不為null花沉，則加Synchronized鎖，找到對應(yīng)的鏈表/紅黑樹的節(jié)點value進行更改媳握，后釋放鎖
讀-寫沖突
若并發(fā)讀寫的數(shù)據(jù)不位于同一個桶（Node數(shù)組）碱屁，則相互獨立互不干擾
若位于同一個桶，與JDK7的版本相比蛾找，簡單了許多娩脾，但還是基于Java的特性使得許多讀操作無鎖化
當讀操作與寫操作同時發(fā)生時：
若PUT的key已經(jīng)存在，則直接更新值腋粥，此時讀操作在volatile的保證下可以獲取最新值
若PUT的key不存在晦雨，會新建一個節(jié)點 或 刪除一個節(jié)點的時候，會改變對原有的結(jié)構(gòu)隘冲，這時next指針是volatile的闹瞧，直接插入到鏈表尾（超過一定長度變成紅黑樹）等對結(jié)構(gòu)的修改，此時讀操作也是可以獲取到最新的next
因此只要寫操作happens-before讀操作展辞，volatile語義就可以保證讀的數(shù)據(jù)是最新的奥邮，可以說JDK8版本的ConcurrentHashMap是強一致的（此處只關(guān)注基本讀寫（GET/PUT），可能會有弱一致的場景遺漏罗珍，例如擴容操作洽腺，不過應(yīng)該是全局加鎖的，如有錯誤煩請指出覆旱，共同學(xué)習(xí)）
寫-寫沖突
若并發(fā)讀寫的數(shù)據(jù)不位于同一個桶蘸朋，則相互獨立互不干擾
若位于同一個桶，注意到寫操作在不同的場景下采取不同的策略扣唱，CAS或Synchronized
當多個寫操作同時發(fā)生時藕坯，若桶為null团南，則CAS應(yīng)對并發(fā)寫，當?shù)谝粋€寫操作賦值成功后炼彪，后面的寫線程CAS失敗吐根，轉(zhuǎn)為競爭Synchronized鎖，阻塞等待
小結(jié)
為什么這么設(shè)計（個人觀點）
對數(shù)據(jù)進行存儲必然涉及數(shù)據(jù)結(jié)構(gòu)的設(shè)計辐马，任何對數(shù)據(jù)的操作都得基于數(shù)據(jù)結(jié)構(gòu)拷橘，常規(guī)思路是對整個數(shù)據(jù)結(jié)構(gòu)加鎖，但是鎖的存在會大大影響性能喜爷，所以接下來的任務(wù)冗疮，就是找到哪些可以無鎖化的操作。
操作主要分為兩大類贞奋，讀和寫赌厅。
先看寫，因為涉及到原有數(shù)據(jù)的改動轿塔，不加控制肯定會翻車特愿，怎么控制呢？寫操作也分兩種勾缭，一種會改變結(jié)構(gòu)揍障，一種不會：
對于會改變結(jié)構(gòu)的寫检眯，不管底層是數(shù)組還是鏈表风皿，由于改動得基于原有的結(jié)構(gòu)敌卓，必然得加鎖串行化保證原子操作仆百，優(yōu)化的點就是鎖層面的優(yōu)化，例如最開始HashTable等synchronized鎖到ConcurrentHashMap1.7版本的ReentrantLock鎖幔虏，再到1.8版本的Synchronized改良鎖 梧油】皆螅或者數(shù)據(jù)分散化碘梢，concurrnethashmap等基于hash的數(shù)據(jù)結(jié)構(gòu)比CopyOnWriteList的數(shù)據(jù)結(jié)構(gòu)就多了桶分散的優(yōu)勢咬摇。
對于不會改變結(jié)構(gòu)的寫，或者改動的頻率不大（桶擴容頻率低）煞躬，由于鎖的開銷實在是太大了肛鹏，CAS是個不錯的思路。為什么CopyOnWriteList不用CAS來控制并發(fā)寫恩沛，我個人覺得主要原因還是因為結(jié)構(gòu)變化頻繁在扰，可以看下ActomicReferenceArray等基于CAS的數(shù)組容器，都是創(chuàng)建后就不允許結(jié)構(gòu)發(fā)生變化的雷客。
確保數(shù)據(jù)不會改錯之后芒珠，讀相對就好辦了，主要考慮是不是要實時讀最新的數(shù)據(jù)（等待寫操作完成）搅裙，也就是強一致還是弱一致的問題：
強一致的話妓局，讀就得等寫完成总放，讀寫競爭同一把鎖，這就相互影響了讀寫的效率好爬。大多數(shù)場景下，讀的數(shù)據(jù)一致性要求沒有寫的要求高甥啄，可以讀錯存炮，但是堅決不可以寫錯。要是在讀的這一刻蜈漓，數(shù)據(jù)還沒改完穆桂，讀到舊數(shù)據(jù)也沒關(guān)系，只要最后寫完對讀可見即可融虽。
還好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ù)結(jié)構(gòu)：
- JDK1.7的ConcurrentHashMap 底層采用分段的數(shù)組+鏈表實現(xiàn)个束，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣慕购，Node數(shù)組+鏈表/紅黑樹;
- Hashtable和JDK1.8之前的HashMap的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用數(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ù)結(jié)構(gòu)來實現(xiàn)糠悯，并發(fā)控制使用synchronized和CAS來操作帮坚。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化）整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結(jié)構(gòu)逢防，但是已經(jīng)簡化了屬性叶沛，只是為了兼容舊版本；
- Hashtable(同一把鎖) :使用 synchronized 來保證線程安全忘朝，效率非常低下灰署。當一個線程訪問同步方法時，其他線程也訪問同步方法局嘁，可能會進入阻塞或輪詢狀態(tài)溉箕。如使用 put 添加元素，另一個線程不能使用 put 添加元素悦昵，也不能使用 get肴茄，競爭會越來越激烈效率越低。
2.ConcurrentHashMap有哪些構(gòu)造函數(shù)但指？
//無參構(gòu)造函數(shù)
public ConcurrentHashMap() {
}
//可傳初始容器大小(initialCapacity)的構(gòu)造函數(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的構(gòu)造函數(shù)
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
//可設(shè)置閾值(加載因子*容量)和初始容量
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
//可設(shè)置初始容量和閾值和并發(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的結(jié)構(gòu)剩岳，即內(nèi)部擁有一個Entry數(shù)組贞滨，數(shù)組中的每個元素又是一個鏈表,同時又是一個ReentrantLock（Segment繼承了ReentrantLock）。
內(nèi)部結(jié)構(gòu)：ConcurrentHashMap使用分段鎖技術(shù)拍棕，將數(shù)據(jù)分成一段一段的存儲晓铆，然后給每一段數(shù)據(jù)配一把鎖勺良，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問骄噪，能夠?qū)崿F(xiàn)真正的并發(fā)訪問尚困。如下圖是ConcurrentHashMap的內(nèi)部結(jié)構(gòu)圖：
從上面的結(jié)構(gòu)我們可以了解到，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作链蕊。第一次Hash定位到Segment尾组，第二次Hash定位到元素所在的鏈表的頭部。
JDK1.8
- ConcurrentHashMap取消了Segment分段鎖示弓，采?CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似呵萨，數(shù)組+鏈表/紅黑二叉樹奏属。Java 8在鏈表?度超過一定閾值（8）時將鏈表（尋址時間復(fù)雜度為O(N)）轉(zhuǎn)換為紅?樹（尋址時間復(fù)雜度為O(log(N))）。
- 對于put操作潮峦，如果Key對應(yīng)的數(shù)組元素為null囱皿，則通過CAS操作將其設(shè)置為當前值。如果Key對應(yīng)的數(shù)組元素（也即鏈表表頭或者樹的根元素）不為null忱嘹，則對該元素使用synchronized關(guān)鍵字申請鎖嘱腥，然后進行操作。synchronized只鎖定當前鏈表或紅黑二叉樹的首節(jié)點拘悦，這樣只要hash不沖突齿兔，就不會產(chǎn)?并發(fā)，效率又提升N倍础米。
- ConcurrentHashMap的get方法不需要加鎖分苇，get方法采用了unsafe方法，來保證線程安全屁桑。
ConcurrentHashMap用什么技術(shù)保證線程安全医寿？
- jdk1.7：Segment分段鎖+HashEntry（存儲鍵值對數(shù)據(jù)）來進行實現(xiàn)的；
- jdk1.8：放棄了Segment臃腫的設(shè)計蘑斧，采用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ù)性和擴展性，是性能提升的關(guān)鍵涵亏。ConcurrentHashMap的get宰睡，clear，iterator 都是弱一致性的气筋。
hashmap強一致性：HashMap則拋出了ConcurrentModificationException拆内，因為HashMap包含一個修改計數(shù)器modCount，當你調(diào)用他的next()方法來獲取下一個元素時宠默，迭代器將會用到這個計數(shù)器麸恍。
兩者應(yīng)用具體分析：
- Hashtable的任何操作都會把整個map鎖住，是阻塞的搀矫。好處是總能獲取最實時的更新抹沪，比如說線程A調(diào)用putAll寫入大量數(shù)據(jù)，期間線程B調(diào)用get瓤球，線程B就會被阻塞融欧，直到線程A完成putAll，因此線程B肯定能獲取到線程A寫入的完整數(shù)據(jù)卦羡。壞處是所有調(diào)用都要排隊噪馏，效率較低。
- ConcurrentHashMap 是設(shè)計為非阻塞的虹茶。在更新時會局部鎖住某部分數(shù)據(jù)逝薪，但不會把整個map都鎖住。同步讀取操作則是完全非阻塞的蝴罪。好處是在保證合理的同步前提下董济，效率很高。壞處 是嚴格來說讀取操作不能保證反映最近的更新要门。例如線程A調(diào)用putAll寫入大量數(shù)據(jù)虏肾，期間線程B調(diào)用get，則只能get到目前為止已經(jīng)順利插入的部分 數(shù)據(jù)欢搜。
選擇哪一個封豪，是在性能與數(shù)據(jù)一致性之間權(quán)衡。ConcurrentHashMap適用于追求性能的場景炒瘟，大多數(shù)線程都只做insert/delete操作吹埠，對讀取數(shù)據(jù)的一致性要求較低。
5.ConcurrentHashMap如何發(fā)生ReHash？
ConcurrentLevel并發(fā)級別（ 實際上是Segment的實際數(shù)量 默認16） 一旦設(shè)定的話缘琅，就不會改變粘都。ConcurrentHashMap當元素個數(shù)大于臨界值的時候，就會發(fā)生擴容刷袍。但是ConcurrentHashMap與其他的HashMap不同的是翩隧，它不會對Segment 數(shù)量增大，只會增加Segment 后面的鏈表容量的大小呻纹。即對每個Segment 的元素進行的ReHash操作堆生。
巨人的肩膀：
