HashMap 1.8 put get過程：
HashMap? ConcurrentHashMap? 相信看完這篇沒人能難住你焚辅！
put:
1凄贩、判斷當(dāng)前桶是否為空，空的就需要初始化（resize 中會判斷是否進行初始化）袱讹。
2疲扎、根據(jù)當(dāng)前 key 的 hashcode 定位到具體的桶中并判斷是否為空，為空表明沒有 Hash 沖突就直接在當(dāng)前位置創(chuàng)建一個新桶即可捷雕。
3椒丧、如果當(dāng)前桶有值（ Hash 沖突），那么就要比較當(dāng)前桶中的 key救巷、key 的 hashcode 與寫入的 key 是否相等壶熏，相等就賦值給 e,在第 8 步的時候會統(tǒng)一進行賦值及返回。
4浦译、如果當(dāng)前桶為紅黑樹棒假，那就要按照紅黑樹的方式寫入數(shù)據(jù)。
5精盅、如果是個鏈表帽哑，就需要將當(dāng)前的 key、value 封裝成一個新節(jié)點寫入到當(dāng)前桶的后面（形成鏈表）叹俏。
6妻枕、接著判斷當(dāng)前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時就要轉(zhuǎn)換為紅黑樹。
7屡谐、如果在遍歷過程中找到 key 相同時直接退出遍歷述么。
8、如果 e != null 就相當(dāng)于存在相同的 key,那就需要將值覆蓋愕掏。
9度秘、最后判斷是否需要進行擴容。get:
1亭珍、首先將 key hash 之后取得所定位的桶敷钾。
2、如果桶為空則直接返回 null 肄梨。
3阻荒、否則判斷桶的第一個位置(有可能是鏈表、紅黑樹)的 key 是否為查詢的 key众羡，是就直接返回 value侨赡。
4、如果第一個不匹配粱侣，則判斷它的下一個是紅黑樹還是鏈表羊壹。
5、紅黑樹就按照樹的查找方式返回值齐婴。
6油猫、不然就按照鏈表的方式遍歷匹配返回值。
HashMap為啥線程不安全
為什么HashMap線程不安全 -- 很棒
1柠偶、 put的時候情妖，hash沖突會導(dǎo)致數(shù)據(jù)被覆蓋而丟失（一直存在）
2、 多線程Resize時可能會形成環(huán)形鏈表诱担，當(dāng)執(zhí)行 get 時毡证，當(dāng)key 正好被分到那個 table[i] 上時，遍歷鏈表就會產(chǎn)生循環(huán)蔫仙。（jdk1.8用紅黑樹修復(fù)）
JDK8的修復(fù)：
JDK8 將 HashMap 的結(jié)構(gòu)作了修改料睛，將原來的鏈表部分改為數(shù)據(jù)少時仍然鏈表，當(dāng)超過一定數(shù)量后變換為紅黑樹摇邦。
HashMap在jdk1.7中采用頭插入法恤煞，在擴容時會改變鏈表中元素原本的順序，以至于在并發(fā)場景下導(dǎo)致鏈表成環(huán)的問題施籍。而在jdk1.8中采用尾插入法阱州，在擴容時會保持鏈表元素原本的順序，就不會出現(xiàn)鏈表成環(huán)的問題了法梯。
HashMap 多線程下死循環(huán)分析及JDK8修復(fù)HashMap在1.7和1.8之間的變化：
1苔货、1.7采用數(shù)組+單鏈表犀概，1.8在單鏈表超過一定長度后改成紅黑樹存儲
2、1.7擴容時需要重新計算哈希值和索引位置夜惭，1.8并不重新計算哈希值姻灶，巧妙地采用和擴容后容量進行&操作來計算新的索引位置。
3诈茧、1.7插入元素到單鏈表中采用頭插入法产喉，1.8采用的是尾插入法。
ConcurrentHashMap原理
- JDK1.7分析：
ConcurrentHashMap采用分段鎖（Segment+ReentrantLock）的機制敢会，實現(xiàn)并發(fā)的更新操作曾沈，底層采用數(shù)組+鏈表的存儲結(jié)構(gòu)。
其包含兩個核心靜態(tài)內(nèi)部類 Segment和HashEntry鸥昏。
- Segment繼承ReentrantLock用來充當(dāng)鎖的角色塞俱，每個 Segment 對象守護每個散列映射表的若干個桶。
- HashEntry 用來封裝映射表的鍵 / 值對吏垮；
- 每個桶是由若干個 HashEntry 對象鏈接起來的鏈表障涯。
一個 ConcurrentHashMap 實例中包含由若干個 Segment 對象組成的數(shù)組，下面我們通過一個圖來演示一下 ConcurrentHashMap 的結(jié)構(gòu)：
- JDK1.8分析：
1.8的實現(xiàn)已經(jīng)拋棄了Segment分段鎖機制膳汪，利用CAS+Synchronized來保證并發(fā)更新的安全唯蝶，底層采用數(shù)組+鏈表+紅黑樹的存儲結(jié)構(gòu)。
Segment+ReentrantLock VS CAS+Synchronized
ConcurrentHashMap 1.8為什么要使用CAS+Synchronized取代Segment+ReentrantLock
1.7：
- 在初始化ConcurrentHashMap的時候,會初始化一個Segment數(shù)組,容量為16,而每個Segment呢,都繼承了ReentrantLock類,也就是說每個Segment類本身就是一個鎖,之后Segment內(nèi)部又有一個table數(shù)組,而每個table數(shù)組里的索引數(shù)據(jù)呢,又對應(yīng)著一個Node鏈表遗嗽。
- 使用put方法的時候,是對我們的key進行hash拿到一個整型,然后將整型對16取模,拿到對應(yīng)的Segment,之后調(diào)用Segment的put方法,然后上鎖,請注意,這里lock()的時候其實是this.lock(),也就是說,每個Segment的鎖是分開的粘我。
1.8：
Synchronized上鎖的對象,請記住,Synchronized是靠對象的對象頭和此對象對應(yīng)的monitor來保證上鎖的,也就是對象頭里的重量級鎖標(biāo)志指向了monitor,而monitor呢,內(nèi)部則保存了一個當(dāng)前線程,也就是搶到了鎖的線程.
那么這里的這個f是什么呢?f一定是鏈表的頭結(jié)點，即該元素在Node數(shù)組中征字。所以這里鎖住的是hash沖突那條鏈表。
它是Node鏈表里的每一個Node,也就是說,Synchronized是將每一個Node對象作為了一個鎖,這樣做的好處是什么呢?將鎖細(xì)化了,也就是說,除非兩個線程同時操作一個Node,注意,是一個Node而不是一個Node鏈表哦,那么才會爭搶同一把鎖晴音。
如果使用ReentrantLock其實也可以將鎖細(xì)化成這樣的,只要讓Node類繼承ReentrantLock就行了,這樣的話調(diào)用f.lock()就能做到和Synchronized(f)同樣的效果,但為什么不這樣做呢?
請大家試想一下,鎖已經(jīng)被細(xì)化到這種程度了,那么出現(xiàn)并發(fā)爭搶的可能性還高嗎?還有就是,哪怕出現(xiàn)爭搶了,只要線程可以在30到50次自旋里拿到鎖,那么Synchronized就不會升級為重量級鎖,而等待的線程也就不用被掛起,我們也就少了掛起和喚醒這個上下文切換的過程開銷.
但如果是ReentrantLock呢?它則只有在線程沒有搶到鎖,然后新建Node節(jié)點后再嘗試一次而已,不會自旋,而是直接被掛起,這樣一來,我們就很容易會多出線程上下文開銷的代價.當(dāng)然,你也可以使用tryLock(),但是這樣又出現(xiàn)了一個問題,你怎么知道tryLock的時間呢?在時間范圍里還好,假如超過了呢?
所以,在鎖被細(xì)化到如此程度上,使用Synchronized是最好的選擇了.這里再補充一句,Synchronized和ReentrantLock他們的開銷差距是在釋放鎖時喚醒線程的數(shù)量,Synchronized是喚醒鎖池里所有的線程+剛好來訪問的線程,而ReentrantLock則是當(dāng)前線程后進來的第一個線程+剛好來訪問的線程.
如果是線程并發(fā)量不大的情況下,那么Synchronized因為自旋鎖,偏向鎖,輕量級鎖的原因,不用將等待線程掛起,偏向鎖甚至不用自旋,所以在這種情況下要比ReentrantLock高效
集合類
JAVA集合類
Java提高篇（三四）-----fail-fast機制
函數(shù)式編程锤躁，stream用法，Lambda表達(dá)式
Java 8 函數(shù)式接口
JDK 8 函數(shù)式編程入門
Java 8 中的 Streams API 詳解
- “快速失敗”也就是fail-fast
- 它是Java集合的一種錯誤檢測機制梧乘。當(dāng)多個線程對集合進行結(jié)構(gòu)上的改變的操作時填渠，有可能會產(chǎn)生fail-fast機制氛什。記住是有可能，而不是一定饺饭。例如：假設(shè)存在兩個線程（線程1鹊杖、線程2），線程1通過Iterator在遍歷集合A中的元素登下，在某個時候線程2修改了集合A的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改畔濒，而不是簡單的修改集合元素的內(nèi)容），那么這個時候程序就會拋出 ConcurrentModificationException 異常妇菱，從而產(chǎn)生fail-fast機制房交。
- 這一策略在源碼中的實現(xiàn)是通過 modCount 域白群，modCount 顧名思義就是修改次數(shù)唯卖，對 HashMap 內(nèi)容（當(dāng)然不僅僅是 HashMap 才會有卵沉，其他例如 ArrayList 也會）的修改都將增加這個值（大家可以再回頭看一下其源碼，在很多操作中都有 modCount++ 這句）堪嫂，那么在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount偎箫。
- 解決方案
在上文中也提到木柬，fail-fast 機制皆串，是一種錯誤檢測機制。它只能被用來檢測錯誤眉枕，因為 JDK 并不保證 fail-fast 機制一定會發(fā)生恶复。若在多線程環(huán)境下使用 fail-fast 機制的集合怜森，建議使用“java.util.concurrent 包下的類”去取代“java.util 包下的類”。
-
java集合框架圖
Map:
LinkedHashMap 幾乎和 HashMap 一樣：從技術(shù)上來說谤牡，不同的是它定義了一個 Entry<K,V> header副硅，這個 header 不是放在 Table 里，它是額外獨立出來的翅萤。LinkedHashMap 通過繼承 hashMap 中的 Entry<K,V>,并添加兩個屬性 Entry<K,V> before,after,和 header 結(jié)合起來組成一個雙向鏈表恐疲，來實現(xiàn)按插入順序或訪問順序排序。
Hashtable 與 HashMap 的簡單比較
- 1套么、HashTable 基于 Dictionary 類培己，而 HashMap 是基于 AbstractMap。Dictionary 是任何可將鍵映射到相應(yīng)值的類的抽象父類胚泌，而 AbstractMap 是基于 Map 接口的實現(xiàn)省咨，它以最大限度地減少實現(xiàn)此接口所需的工作。
- 2玷室、HashMap 的 key 和 value 都允許為 null零蓉，而 Hashtable 的 key 和 value 都不允許為 null。HashMap 遇到 key 為 null 的時候穷缤，調(diào)用 putForNullKey 方法進行處理敌蜂，而對 value 沒有處理；Hashtable遇到 null绅项，直接返回 NullPointerException紊册。
- 3、Hashtable 方法是同步快耿，而HashMap則不是囊陡。我們可以看一下源碼，Hashtable 中的幾乎所有的 public 的方法都是 synchronized 的掀亥，而有些方法也是在內(nèi)部通過 synchronized 代碼塊來實現(xiàn)撞反。所以有人一般都建議如果是涉及到多線程同步時采用 HashTable，沒有涉及就采用 HashMap搪花，但是在 Collections 類中存在一個靜態(tài)方法：synchronizedMap()遏片，該方法創(chuàng)建了一個線程安全的 Map 對象，并把它作為一個封裝的對象來返回
主題：ConcurrentHashMap之實現(xiàn)細(xì)節(jié)
HashMap為什么線程不安全(hash碰撞與擴容導(dǎo)致)
圖解集合5：不正確地使用HashMap引發(fā)死循環(huán)及元素丟失
淺析HashMap與ConcurrentHashMap的線程安全性
-
map結(jié)構(gòu)圖
-
map比較
-
map比較1
List:
Arrays.asList使用指南
使用java.util.List.subList時最好小心點
-
List架構(gòu)
-
List比較
-
List比較1
Set:
HashSet撮竿，它是基于 HashMap 實現(xiàn)的吮便，底層采用 HashMap 來保存元素,對于 HashSet 中保存的對象，請注意正確重寫其 equals 和 hashCode 方法幢踏，以保證放入的對象的唯一性髓需。
LinkedHashSet 是 Set 的一個具體實現(xiàn)，其維護著一個運行于所有條目的雙重鏈接列表房蝉。此鏈接列表定義了迭代順序僚匆，該迭代順序可為插入順序或是訪問順序微渠。
Vector
Stack
