資訊專欄INFORMATION COLUMN
摘要：最近準(zhǔn)備面試，一談到基礎(chǔ)，大部分面試官上來就數(shù)據(jù)結(jié)構(gòu)素質(zhì)三連與區(qū)別，底層數(shù)據(jù)結(jié)構(gòu)，為什么能保證線程安全。數(shù)組順序存儲，內(nèi)存連續(xù)，查詢快，插入刪除效率稍微低，不過現(xiàn)在略有改善。而在開始，是由和的方式去實現(xiàn)高并發(fā)下的線程安全。
最近準(zhǔn)備面試，一談到j(luò)ava基礎(chǔ)，大部分面試官上來就java數(shù)據(jù)結(jié)構(gòu)素質(zhì)三連：ArrayList與LinkedList區(qū)別，HashMap底層數(shù)據(jù)結(jié)構(gòu)，ConcurrentHashMap為什么能保證線程安全。
剛畢業(yè)的應(yīng)屆生，或者基礎(chǔ)不好程序員（比如：本尊，對沒錯就是我~），只了解皮毛，一稍微深入就gg思密達(dá)。面試官：嗯...回頭等通知吧~ 基本一首《涼涼》送我到門外了。
不好意思，扯遠(yuǎn)了！ 前兩個問題很簡單，一個數(shù)組一個鏈表。
數(shù)組順序存儲，內(nèi)存連續(xù)，查詢快，插入刪除效率稍微低（System.copyArray），不過現(xiàn)在略有改善。
鏈表插入刪除快速高效，查詢效率差了點意思，存儲不連續(xù)。
總之，各有利弊吧，根據(jù)業(yè)務(wù)場景選擇適合自己的存儲結(jié)構(gòu)，不過現(xiàn)在也出現(xiàn)很多類似的改進(jìn)版本，暫時不談了（其實我也沒了解過，啊哈哈哈~有點尷尬）
HashMap JDK1.8以前基本都是數(shù)組＋鏈表實現(xiàn)，JDK1.8開始改為數(shù)組+列表，當(dāng)列表長度大于某個值（具體忘了），鏈表轉(zhuǎn)化為一個X爆了的數(shù)據(jù)結(jié)構(gòu)————紅黑樹（我都嚇尿了反正，看了幾百遍沒記住這玩意各種算法）
其實今天主要是想聊一下這個叫做ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)，看過網(wǎng)上幾篇文章實在是看的蛋疼，一來寫的一般，對于源碼的復(fù)制粘貼，最為我看起來吃力；二來紅黑樹太難，看著難受的一比。是在無法理解這個數(shù)據(jù)結(jié)構(gòu)的精髓所在，故而想自己寫篇文章來記錄自己學(xué)習(xí)的過程，就好比孫悟空去了一趟五指山下，做個標(biāo)記！
廢話少說直接先上jb：
如圖所示，相比傳統(tǒng)HashMap，jdk1.8之前 ConcurrentHashMap 在傳統(tǒng)HashEntry之前增加了一個segment數(shù)組。Segment數(shù)組的意義就是將一個大的table分割成多個小的table來進(jìn)行加鎖，Segment數(shù)組中每一個元素就是一把鎖，每一個Segment元素存儲的是HashEntry數(shù)組+鏈表。而在jdk1.8開始，ConcurrentHashMap是由CAS和Synchronized的方式去實現(xiàn)高并發(fā)下的線程安全。
我們主要從的get，put等方法來學(xué)習(xí)ConcurrentHashMap，是如何插入和獲取元素，以及如何保證線程安全。
先看下get方法源碼：
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
我看上面的代碼好多中間變量，很影響我這種菜鳥分析邏輯，于是我按照自己的編碼風(fēng)格，重寫了一下：
public V get(Object key) {
int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1
Node[] tab = table;
// 一般對哈希表的散列很自然地會想到用hash值對length取模（即除法散列法）
// Hashtable中也是這樣實現(xiàn)的，這種方法基本能保證元素在哈希表中散列的比較均勻，
// 但取模會用到除法運算，效率很低，HashMap中則通過h&(length-1)的方法來代替取模，
// 同樣實現(xiàn)了均勻的散列，但效率要高很多，這也是HashMap對Hashtable的一個改進(jìn)。
Node e = tabAt(tab, (tab.length - 1) & h);
if (tab == null || tab.length <= 0 ||e == null) {
return null;
}
if (e.hash == h) {
if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey()))){
return e.getValue();
}
} else if (e.hash < 0) {
Node p = e.find(h, key);
return p!= null ? p.getValue() : null;
}
e = e.next;
while (e != null) {
if (e.hash != h) {
return null;
}
if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey())))
return e.getValue();
}
return null;
}
int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1
代碼的意思————通過哈希值二進(jìn)制異或該哈希值二進(jìn)制右移動16位 是為了計算哈希值 再和 上面那玩意進(jìn)行與運算并不知道是什么鬼。如下圖：
計算出Hash值之后要通過hash值找到對應(yīng)數(shù)組的下標(biāo)進(jìn)而找到數(shù)組元素：
