jdk1.7 分段鎖
1、HashTable容器在競爭激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因，是因為所有訪問HashTable的線程都必須競爭同一把鎖
2、假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數(shù)據(jù)，那么當多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時，線程間就不會存在鎖競爭，從而可以有效的提高并發(fā)訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)
a、首先將數(shù)據(jù)分成一段一段的存儲
b、然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問
c、有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖。這里“按順序”是很重要的，否則極有可能出現(xiàn)死鎖
d、在ConcurrentHashMap內(nèi)部，段數(shù)組是final的，并且其成員變量實際上也是final的，但是，僅僅是將數(shù)組聲明為final的并不保證數(shù)組成員也是final的，這需要實現(xiàn)上的保證。這可以確保不會出現(xiàn)死鎖，因為獲得鎖的順序是固定的。
3、ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成
4、Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色
5、HashEntry則用于存儲鍵值對數(shù)據(jù)
6、一個ConcurrentHashMap里包含一個Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)
7、一個Segment里包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結(jié)構(gòu)的元素， 每個Segment守護者一個HashEntry數(shù)組里的元素,當對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應(yīng)的Segment鎖。
jdk1.8 concurrentHashMap原理分析
1.8版本的ConcurrentHashMap的實現(xiàn)與1.7版本有很大的差別，放棄了段鎖的概念，借鑒了HashMap的數(shù)據(jù)結(jié)構(gòu)：數(shù)組＋鏈表＋紅黑樹
-
ConcurrentHashMap不接受nullkey和nullvalue
-
數(shù)據(jù)結(jié)構(gòu)：數(shù)組＋鏈表＋紅黑樹
-
并發(fā)原理：cas樂觀鎖+synchronized鎖
-
加鎖對象：數(shù)組每個位置的頭節(jié)點
concurrentHashMap數(shù)據(jù)結(jié)構(gòu)
ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)（數(shù)組+鏈表+紅黑樹），桶中的結(jié)構(gòu)可能是鏈表，也可能是紅黑樹，紅黑樹是為了提高查找效率
構(gòu)造函數(shù)
1、對于構(gòu)造函數(shù)而言，會根據(jù)輸入的initialCapacity的大小來確定一個最小的且大于等于initialCapacity大小的2的n次冪，如initialCapacity為15，則sizeCtl為16，若initialCapacity為16，則sizeCtl為16
2、若initialCapacity大小超過了允許的最大值，則sizeCtl為最大值
3、值得注意的是，構(gòu)造函數(shù)中的concurrencyLevel參數(shù)已經(jīng)在JDK1.8中的意義發(fā)生了很大的變化，其并不代表所允許的并發(fā)數(shù) 只是用來確定sizeCtl大小
4、在JDK1.8中的并發(fā)控制都是針對具體的桶而言，即有多少個桶就可以允許多少個并發(fā)數(shù)。
- ConcurrentHashMap()
該構(gòu)造函數(shù)用于創(chuàng)建一個帶有默認初始容量 (16)、加載因子 (0.75) 和 concurrencyLevel (16) 的新的空映射
- ConcurrentHashMap(int)
該構(gòu)造函數(shù)用于創(chuàng)建一個帶有指定初始容量、默認加載因子 (0.75) 和 concurrencyLevel (16) 的新的空映射
- ConcurrentHashMap(Map<? extends K, ? extends V>)
該構(gòu)造函數(shù)用于構(gòu)造一個與給定映射具有相同映射關(guān)系的新映射
?public?ConcurrentHashMap(Map<??extends?K,???extends?V>?m)?{
????????this.sizeCtl?=?DEFAULT_CAPACITY;
????????//?將集合m的元素全部放入
????????putAll(m);
????}- ConcurrentHashMap(int, float)
public?ConcurrentHashMap(int?initialCapacity,?float?loadFactor)?{
????????this(initialCapacity,?loadFactor,?1);
????}- ConcurrentHashMap(int, float, int)
putVal函數(shù)
V putVal(K key, V value, boolean onlyIfAbsent)
put函數(shù)底層調(diào)用了putVal進行數(shù)據(jù)的插入，對于putVal函數(shù)的流程大體如下。
① 判斷存儲的key、value是否為空，若為空，則拋出異常，否則，進入步驟②
② 計算key的hash值，隨后進入無限循環(huán)，該無限循環(huán)可以確保成功插入數(shù)據(jù)，若table表為空或者長度為0，則初始化table表，否則，進入步驟③
③ 根據(jù)key的hash值取出table表中的結(jié)點元素，若取出的結(jié)點為空（該桶為空），則使用CAS將key、value、hash值生成的結(jié)點放入桶中。否則，進入步驟④
④ 若該結(jié)點的的hash值為MOVED，則對該桶中的結(jié)點進行轉(zhuǎn)移，否則，進入步驟⑤
⑤ 對桶中的第一個結(jié)點（即table表中的結(jié)點）進行加鎖，對該桶進行遍歷，桶中的結(jié)點的hash值與key值與給定的hash值和key值相等，則根據(jù)標識選擇是否進行更新操作（用給定的value值替換該結(jié)點的value值），若遍歷完桶仍沒有找到hash值與key值和指定的hash值與key值相等的結(jié)點，則直接新生一個結(jié)點并賦值為之前最后一個結(jié)點的下一個結(jié)點。進入步驟⑥
⑥ 若binCount值達到紅黑樹轉(zhuǎn)化的閾值，則將桶中的結(jié)構(gòu)轉(zhuǎn)化為紅黑樹存儲，最后，增加binCount的值
初始化table
Node<K,V>[] initTable()
對于table的大小，會根據(jù)sizeCtl的值進行設(shè)置，如果沒有設(shè)置szieCtl的值，那么默認生成的table大小為16，否則，會根據(jù)sizeCtl的大小設(shè)置table大小
獲取table指定元素
static?final?<K,V>?Node<K,V>?tabAt(Node<K,V>[]?tab,?int?i)?{
????????return?(Node<K,V>)U.getObjectVolatile(tab,?((long)i?<<?ASHIFT)?+?ABASE);
}此函數(shù)返回table數(shù)組中下標為i的結(jié)點，可以看到是通過Unsafe對象通過反射獲取的，getObjectVolatile的第二項參數(shù)為下標為i的偏移地址
比較并交換
static?final?<K,V>?boolean?casTabAt(Node<K,V>[]?tab,?int?i,Node<K,V>?c,?Node<K,V>?v)?{
???return?U.compareAndSwapObject(tab,?((long)i?<<?ASHIFT)?+?ABASE,?c,?v);
}此函數(shù)用于比較table數(shù)組下標為i的結(jié)點是否為c，若為c，則用v交換操作。否則，不進行交換操作。
協(xié)助轉(zhuǎn)移
Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f)
此函數(shù)用于在擴容時將table表中的結(jié)點轉(zhuǎn)移到nextTable中
添加節(jié)點到紅黑樹
TreeNode<K,V> putTreeVal(int h, K k, V v)
此函數(shù)用于將指定的hash、key、value值添加到紅黑樹中，若已經(jīng)添加了，則返回null，否則返回該結(jié)點
轉(zhuǎn)換成紅黑樹
void treeifyBin(Node<K,V>[] tab, int index)
此函數(shù)用于將桶中的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化為紅黑樹，其中，值得注意的是，當table的長度未達到閾值時，會進行一次擴容操作，該操作會使得觸發(fā)treeifyBin操作的某個桶中的所有元素進行一次重新分配，這樣可以避免某個桶中的結(jié)點數(shù)量太大。
查詢
V get(Object key)
get函數(shù)根據(jù)key的hash值來計算在哪個桶中，再遍歷桶，查找元素，若找到則返回該結(jié)點，否則，返回null
刪除
replaceNode
此函數(shù)對remove函數(shù)提供支持，remove函數(shù)底層是調(diào)用的replaceNode函數(shù)實現(xiàn)結(jié)點的刪除
1、計算hash值
2、進入無限循環(huán) 確保刪除成功
3、若table表為空或者表長度為0或者key所對應(yīng)的桶為空 跳出循環(huán)
4、若桶中第一個結(jié)點的hash值為MOVED 則轉(zhuǎn)移數(shù)據(jù)
5、刪除操作
準備對桶中的第一個節(jié)點進行枷鎖處理 但看看是否滿足前提條件
a、判斷桶中的第一個節(jié)點是否沒有變化
a-1、節(jié)點hash值是否大于0
a-2、無限循環(huán)鏈表
a-3、判斷 結(jié)點的hash值與指定的hash值相等，并且key也相等
a-4、進行替換或刪除
b、判斷是否為紅黑樹
b-1、 轉(zhuǎn)換為treeNode結(jié)構(gòu)
b-2、根節(jié)點不為空并且存在與指定hash和key相等的結(jié)點
b-3、進行替換或刪除
