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