在這里說一下茶敏，線程安全和線程不安全的容器類惊搏。請(qǐng)帶著質(zhì)疑的角度看待這篇文章恬惯，感恩。
前提
什么是線程安全浓恳？
通俗的說奖蔓，在多線程中吆鹤，在執(zhí)行一段代碼上洲守，仍然按照我們?cè)仍O(shè)想的邏輯運(yùn)行梗醇，產(chǎn)生我們意向到的結(jié)果叙谨。
學(xué)術(shù)的說，在一個(gè)線程調(diào)用共享資源的時(shí)候涤垫，什么時(shí)候讓其他線程蝠猬，或者怎么樣讓其他線程看到這個(gè)資源的變化榆芦。
java內(nèi)存模型如何應(yīng)對(duì)上述問題匆绣？
happend-before ，數(shù)據(jù)依賴性 旺入，as-if-serial ,? 內(nèi)存屏障，----這些都是禁止某些指令重排
happend-before 咐鹤，數(shù)據(jù)依賴性 圣絮，as-if-serial 這三個(gè)都是說扮匠，禁止某些重排序棒搜，按照前趨圖力麸，執(zhí)行。就是寫了才能讀闺鲸，開始了才能結(jié)束摸恍，有一個(gè)邏輯上的先后關(guān)系立镶。當(dāng)然happend-before有個(gè)更重要的一點(diǎn)
A hb B
B hb C
結(jié)果 ： A hb C
內(nèi)存屏障：禁止某些重排序 + 緩存和主存之間數(shù)據(jù)的一致性問題谜慌。
如何保證線程安全莺奔，
鎖（synchronized / lock ) 变泄， CAS? 妨蛹， 寫時(shí)復(fù)制蛙卤，
正題
關(guān)于數(shù)據(jù)結(jié)構(gòu)颤难，分為邏輯上的和真實(shí)存儲(chǔ)在計(jì)算機(jī)中的數(shù)據(jù)的結(jié)構(gòu)行嗤。也可以分為真實(shí)的結(jié)構(gòu)（數(shù)組垛耳，鏈表）和具體的程序員實(shí)現(xiàn)的抽象結(jié)構(gòu)（棧堂鲜，隊(duì)列 缔莲，堆酌予，圖抛虫，樹建椰，散列表）.
java中常見的，我下面要說的數(shù)據(jù)結(jié)構(gòu)：list , set , map
1.關(guān)于list :
有序（存儲(chǔ)的/插入的順序）屠列，意思就是排隊(duì)的內(nèi)個(gè)意思笛洛，每個(gè)人都拿著愛的號(hào)碼牌苛让，
可以重復(fù)
刪除狱杰，查找的時(shí)候要比較仿畸，數(shù)據(jù)類型為引用數(shù)據(jù)類型時(shí) 错沽， 類要重寫equals()方法。
單線程：
ArrayList和LinkedList的差別？
看過源碼都知道：ArrayList 用數(shù)組實(shí)現(xiàn)，查詢效率高吴侦，插入刪除效率低备韧， LinkedList是用雙向鏈表實(shí)現(xiàn)的痪枫，插入刪除效率高 织堂，查詢效率低。
這些單線程的都是強(qiáng)一致性奶陈，有一個(gè)字段modCount （對(duì)象被修改次數(shù)）這個(gè)字段作用：在用迭代器的遍歷中易阳，這個(gè)時(shí)候其他線程修改了數(shù)據(jù)的結(jié)構(gòu)（增/刪），就會(huì)報(bào)ConcurrentModificationException異常吃粒。
多線程安全：
1.Vector.Class? 潦俺， 在每個(gè)方法上加synchronized關(guān)鍵字，加鎖實(shí)現(xiàn)線程安全徐勃。
2.Collections.synchronizedList(....) ,也是通過加synchronized鎖來實(shí)現(xiàn)線程安全
3.juc包下CopyOnWriteArrayList.Class ，數(shù)組實(shí)現(xiàn)僻肖，適用在讀多肖爵，寫少的場(chǎng)合中。
- 使用 ReentrantLock 和 volatile? 和 寫時(shí)復(fù)制 臀脏，三個(gè)方面解決線程安全問題
- volatile : 解決數(shù)組的內(nèi)存可見性
-RentrantLock 劝堪，鎖住的是：修改容器內(nèi)的數(shù)據(jù)的時(shí)候的只允許一個(gè)線程修改冀自。
-寫時(shí)復(fù)制：保證如果有線程正在修改容器內(nèi)的數(shù)據(jù)，這個(gè)時(shí)候有線程想讀幅聘，讀取容器內(nèi)的數(shù)據(jù)凡纳，修改的是復(fù)制的版本，修改之后把數(shù)據(jù)在刷新在容器內(nèi)帝蒿，因?yàn)檫@個(gè)容器內(nèi)的數(shù)據(jù)是volatile荐糜， 保證多線程中的內(nèi)存可見性。
2.關(guān)于Map
這里先說Map葛超，因?yàn)榇蟛糠諷et中數(shù)據(jù)的存儲(chǔ)在對(duì)應(yīng)Map中的Key中暴氏。
容器內(nèi)的數(shù)據(jù)類型，如果是引用數(shù)據(jù)類型绣张，要重寫hashCode(）方法和equals()方法答渔，因?yàn)樘砑訉?duì)象步驟如下;
首先調(diào)用hashCode()方法，（此計(jì)算的對(duì)象哈希值決定了Set中的存儲(chǔ)位置）：若此位置之前沒有對(duì)象存儲(chǔ)侥涵，則這個(gè)對(duì)象沼撕，直接存儲(chǔ)到此位置上;若有存儲(chǔ)對(duì)象，通過equals方法芜飘，比較這兩個(gè)對(duì)象是否相同务豺，如果相同，后一個(gè)對(duì)象就不能再添加嗦明，萬一返回false呢笼沥，則都存儲(chǔ)在"同一個(gè)位置"。
單線程：
1.HashMap （數(shù)組 + 鏈表+紅黑樹 娶牌，null ok）
問題：HashMap? get() / put()的工作原理奔浅？
存儲(chǔ)過程：
0.hash(key.hashCode())? 充分使用key的hashCode值的前16位和后16位 “&”操作 得到一個(gè) int? hash值
1.判斷table是否為null,是就擴(kuò)容
2.這個(gè)hash值 & (數(shù)組Size -1 ) , 得出找到要放在桶上的索引，如果這個(gè)位置上沒值诗良，就保存key -value汹桦，
3.如果索引位置上有值，再equalse(）判斷是否相等累榜，如果相等营勤，就覆蓋old value
4. 如果索引位置上的值和插入的值不相等，就檢查這個(gè)節(jié)點(diǎn)是不是treeNode壹罚，如果是就紅黑樹插入key-value 葛作，這里依然要equals(），如果相等就 覆蓋 old value
5. 如果不是紅黑樹猖凛，那么遍歷他的鏈表赂蠢，遍歷的過程中做兩件事? 1.檢查是否遍歷到了鏈表的尾端，如果是就插入到尾端檢查這個(gè)時(shí)候鏈表的長(zhǎng)度是否是8辨泳，是的話 虱岂，(判斷數(shù)組的length如果大于64玖院，就把鏈表轉(zhuǎn)化為紅黑樹，小于64就擴(kuò)容)? ? 2.equals()于當(dāng)前鏈上結(jié)點(diǎn)是否相等第岖，相等就跳出遍歷难菌，覆蓋old valueB
6.覆蓋了old value會(huì)返回old value ， 沒有覆蓋就modCount +1 ,檢查是否需要擴(kuò)容
get() 過程：
1. hash(key.hashCode()) & (table.length -1) 找到索引蔑滓，桶的位置
2.索引上沒有值郊酒，返回null , 桶上有值equals() 相等，返回;
3.不等就看這個(gè)節(jié)點(diǎn)是不是treeNode键袱，是就查找equals()燎窘，true返回值，false 就返回null
4.不是treeNode 蹄咖， 就查看這個(gè)有沒有next個(gè)節(jié)點(diǎn)鏈褐健，遍歷，equals()澜汤，同上蚜迅。
問題：HashMap中解決碰撞的方法？
首先知道幾個(gè)數(shù)字 ：
16 ： capacity 默認(rèn)數(shù)組的長(zhǎng)度 , 不默認(rèn)就2的冪次方俊抵，減少碰撞慢叨。
8：當(dāng)值插入值后鏈表長(zhǎng)度變成 8 就把鏈表變?yōu)榧t黑樹,或者擴(kuò)容
擴(kuò)容相關(guān)參數(shù)
0.75：final? loadFactor 負(fù)載因子，當(dāng)添加key-value之后 务蝠， 檢查當(dāng)前的容量 size 是否達(dá)到了threshold（capacity*loadFactor）閾值，達(dá)到了就擴(kuò)容烛缔。至于為什么是0.75呢馏段？javadoc上說，0.75滿足泊松分布践瓷。
64: final院喜，最小轉(zhuǎn)變?yōu)榧t黑樹的這個(gè)一個(gè)閾值： 在鏈表轉(zhuǎn)紅黑樹中 ， 如果map中table 的長(zhǎng)度沒有達(dá)到這個(gè)值晕翠，就會(huì)通過擴(kuò)容解決沖突喷舀，并不會(huì)鏈表轉(zhuǎn)紅黑樹
總結(jié)：這個(gè)如何解決沖突，就是在桶后面加了一個(gè)鏈表淋肾，為了解決鏈表過長(zhǎng)查找效率變?yōu)镺(n）,鏈表過長(zhǎng)變?yōu)榧t黑樹查找效率變?yōu)镺(logN)
問題：HashMap的擴(kuò)容硫麻？
擴(kuò)容就是變成原來table.length的兩倍，這樣的好處樊卓，關(guān)于整體結(jié)構(gòu)上的動(dòng)蕩拿愧，這個(gè)值，要不就在 原來的索引上碌尔，要不就在原來的索引+原來table.length處浇辜。多線程擴(kuò)容會(huì)產(chǎn)生循環(huán)鏈表券敌，引起死鎖，讓Cpu的使用率變成100%
繼承HashMap的LinkedHashMap：
就是在HashMap的基礎(chǔ)上柳洋，加了雙向鏈表待诅，維護(hù)了一個(gè)順序，默認(rèn)是插入的順序熊镣，可以用過構(gòu)造方法指定accessOrder為true, 然后重寫LinkedHashMap中的removeEldestEntry方法? 這樣維護(hù)的是LRU（最近最久未使用淘汰）順序卑雁。
問題：如何維護(hù)順序問題？
LinkedHashMap 繼承HashMap之后重寫了三個(gè)鉤子方法轧钓，用著三個(gè)方法來維護(hù)一個(gè)順序問題
2.TreeMap（紅黑樹）
自定義key的排序? 序厉，在數(shù)量級(jí)很大的情況下使用TreeMap。關(guān)于key為null的問題 毕箍， 可以put存儲(chǔ),如果get讀的時(shí)候回報(bào)錯(cuò)NullPointerException異常弛房，但是可以遍歷，迭代器讀取
多線程安全：
1.Hashtable : （不允許key為 null）加synchronized 關(guān)鍵字實(shí)現(xiàn)同步方法 .
2.Collections.synchronizedMap() /synchronizedSortedMap()
3.ConcurrentHashMap ( 數(shù)據(jù)類型和HashMap一樣而柑，不能為null ) :?
volatile table? 文捶， CAS方法一些狀態(tài)值的維護(hù)或者插入? ， synchronized（node）媒咳，三個(gè)原子操作
問題：put() / get()的工作原理粹排？HashMap有什么不一樣呢 ？
put()
0.這里寫了循環(huán)涩澡，只有插入成功才會(huì)返回顽耳。
1.判斷當(dāng)桶上是不是有值 ，CAS插入值妙同，插入成功就返回射富，有值之后先判斷是否有其他線程是否在擴(kuò)容，是就幫助擴(kuò)容粥帚，沒有擴(kuò)容就接著插入胰耗。
2.加鎖的粒度不是整個(gè)這個(gè)方法，加鎖是在node結(jié)點(diǎn)上芒涡，這個(gè)時(shí)候synchronized(當(dāng)前這個(gè)桶)柴灯，下面和HashMap一樣，是鏈表就插在鏈表后面（這個(gè)之后要判斷鏈表長(zhǎng)度是否大于8费尽，當(dāng)前table.length是否大于64赠群，是就轉(zhuǎn)變?yōu)榧t黑樹），是紅黑樹就按照紅黑樹插入依啰。
3.插入之后判斷是否要擴(kuò)容
問題：關(guān)于擴(kuò)容的問題乎串？很難
在ConcurrentHashMap里，sizeCtl承擔(dān)map擴(kuò)容的問題，并增加了一點(diǎn)功能叹誉。
當(dāng)sizeCtl=-1鸯两，代表正在初始化。
當(dāng)sizeCtl=-N长豁，代表有N-1個(gè)線程在擴(kuò)容钧唐。
當(dāng)sizeCtl=0，代表需要初始化匠襟。
以上三個(gè)值钝侠，都是狀態(tài)位。
當(dāng)sizeCtl>0酸舍，即擴(kuò)容的閾值帅韧，也即總?cè)萘?* 0.75。
多線程擴(kuò)容啃勉，每個(gè)線程都擴(kuò)容自己分到的桶忽舟，擴(kuò)容完成后把node結(jié)點(diǎn)變?yōu)镕orwardingNode，通知其他線程這個(gè)桶已經(jīng)擴(kuò)容完畢淮阐，并且設(shè)置桶上hash值為 MOVED
問題：ConcurrentHashMap的弱一致性問題叮阅？
如果有線程遍歷，這個(gè)時(shí)候有線程做修改數(shù)據(jù)結(jié)構(gòu)的事情泣特？
在使用迭代器時(shí)浩姥，如果修改的部分發(fā)生在還沒有迭代的地方，就會(huì)顯示出來状您，如果迭代在已經(jīng)迭代的地方就不會(huì)顯示出來
問題：ConcurrentHashMap并行度勒叠？
讀完全并行。
寫部分并行膏孟，因?yàn)閟ynchronized的是桶上的node , 所以table的length有多少缴饭，并行度就是多少。
迭代器
3.ConcurrentSkipListMap :
ConcurrentHashMap是HashMap的 多線程版本骆莹，ConcurrentSkipListMap是TreeMap的多線程版本，對(duì)key有一個(gè)排序担猛。
無阻塞幕垦，所有的操作都是并行的 ， 跳表基于鏈表 傅联， 這個(gè)結(jié)構(gòu)查找類似二分查找先改。這個(gè)以后再寫
3.關(guān)于Set
1.無序（存儲(chǔ)位置 根據(jù)Hash值），他和list一樣都繼承Collection.Class
2.不可重復(fù)
單線程：
HashSet , TreeSet 這些類各自實(shí)現(xiàn) HashMap 蒸走， TreeMap仇奶，以其中的key保存自己的值，value是一個(gè)默認(rèn)的值比驻。
線程安全：
1.Collections.synchronizedSet
2.CopyOnWriteArraySet()
同CopyOnWriteArrayList一樣, 使用volatile 數(shù)組 + lock +寫時(shí)復(fù)制 该溯，實(shí)現(xiàn)線程安全岛抄。
