JDK容器三大將
任何一項(xiàng)新的技術(shù)轰豆、一種新的語(yǔ)言本質(zhì)上都是算法+數(shù)據(jù)結(jié)構(gòu)我注。任何技術(shù)的選型本質(zhì)上都是在基于業(yè)務(wù)和硬件條件的充分理解呀洲，采用合適的數(shù)據(jù)結(jié)構(gòu)审胸、適當(dāng)?shù)乃惴ㄒ赃_(dá)到資源和效率的最優(yōu)解尼变。Java開(kāi)發(fā)亦是如此利凑，工欲善其事，必先利其器嫌术，想要使用Java這種語(yǔ)言開(kāi)發(fā)好程序哀澈，就必須選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行開(kāi)發(fā)。JDK容器則是所有Java應(yīng)用開(kāi)發(fā)的基礎(chǔ)度气，不論是業(yè)務(wù)代碼割按，還是各種知名的Java開(kāi)源項(xiàng)目（如異步網(wǎng)絡(luò)框架netty、容器管理框架Spring磷籍、分布式計(jì)算框架Hadoop适荣、搜索引擎框架Elastic Search），全都是大量在JDK容器的基礎(chǔ)上進(jìn)行開(kāi)發(fā)院领。而JDK容器作為這些優(yōu)秀開(kāi)源項(xiàng)目的默認(rèn)選擇弛矛，必然有其優(yōu)勢(shì)，本文將分析下JDK容器三大將之哈希表比然。
JDK容器三大將：List强法、Set万俗、Map
HashMap介紹
所有編程語(yǔ)言都躲不開(kāi)數(shù)據(jù)結(jié)構(gòu)原理中的幾種經(jīng)典結(jié)構(gòu)，鏈表饮怯、線性表闰歪、哈希表等。哈希表以其O(1) 的查找耗時(shí)在查找速度方面傲視群雄硕淑，Java中哈希表的實(shí)現(xiàn)即HashMap類课竣。
（原JDK中還有一個(gè)Hashtable類，由于put和get操作都加了synchronized鎖導(dǎo)致單線程性能差置媳，多線程又有基于分段鎖的ConcurrentHashMap作為更好的選擇于樟，官方已經(jīng)聲明不在維護(hù)）
先來(lái)看下HashMap的繼承關(guān)系圖如下
- Map接口為實(shí)現(xiàn)類暴露了一系列方法，AbstractMap抽象類為Map的一些基礎(chǔ)功能提供了簡(jiǎn)單實(shí)現(xiàn)
- Cloneable表示該類支持通過(guò)
java.lang.Object#clone()方法克隆拇囊，clone方法相關(guān)的細(xì)節(jié)（淺拷貝迂曲、深拷貝）讀者可以搜索相關(guān)關(guān)鍵字閱讀 - Serializable接口表示該類支持Java自帶序列化功能進(jìn)行序列化
HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap的數(shù)據(jù)結(jié)構(gòu)如下圖
下面分別來(lái)介紹下圖中的幾個(gè)概念：
- size，存著HashMap當(dāng)前的大小寥袭，執(zhí)行hashMap.size()時(shí)直接在O(1)的時(shí)間返回哈希表的大小路捧，如圖有著三個(gè)鍵值對(duì)关霸，所以size=3
- modCount，記錄哈希表結(jié)構(gòu)變更的次數(shù)杰扫，用于在HashMap結(jié)構(gòu)變更時(shí)能夠快速失敗队寇，后面會(huì)詳細(xì)介紹
- table，是一個(gè)Node數(shù)組（默認(rèn)大小16）章姓，Node是HashMap的內(nèi)部定義類佳遣，結(jié)構(gòu)如圖，保存著一對(duì)鍵值對(duì)凡伊。當(dāng)執(zhí)行
map.put(k, v)命令時(shí)會(huì)根據(jù)k的哈希值映射到Node數(shù)組的某個(gè)位置零渐，并且通過(guò)拉鏈法處理哈希沖突 - loadFactor、threshold系忙，分別為裝載因子（默認(rèn)0.75）和閾值（Node.length * 裝載因子）诵盼，當(dāng)HashMap的容量（即size）超過(guò)閾值時(shí)會(huì)觸發(fā)rehash，對(duì)Node數(shù)組進(jìn)行擴(kuò)容
HashMap的put/get操作執(zhí)行過(guò)程
put()
HashMap的put操作的執(zhí)行過(guò)程偽代碼如下
void put(key, value) {
index = hash(key);
if(table[index] == null)
table[index] = newNode(key, value); // 節(jié)點(diǎn)沒(méi)有hash沖突時(shí)將該kv錄入節(jié)點(diǎn)
else
insertIntoLastNode(table[index], key, value); // 節(jié)點(diǎn)hash沖突時(shí)寫(xiě)入拉鏈的最后
}
- 當(dāng)hash沖突寫(xiě)入拉鏈時(shí)银还，HashMap有著一個(gè)常量
TREEIFY_THRESHOLD=8风宁，當(dāng)拉鏈長(zhǎng)度超過(guò)閾值后鏈表會(huì)升級(jí)為紅黑樹(shù) - 上文提到過(guò)的參數(shù)
threshold = Node.length * 裝載因子，當(dāng)put完的哈希表節(jié)點(diǎn)總數(shù)達(dá)到Node數(shù)組容量的0.75時(shí)會(huì)觸發(fā)擴(kuò)容
get()
HashMap的get操作執(zhí)行過(guò)程的偽代碼如下见剩，都是經(jīng)典的拉鏈法哈希查找的步驟
V get(key) {
index = hash(key);
if(table[index].key.hash == key.hash && table[index] == key)
return table[index].value; // 如上圖中Node[2]定位到的第一個(gè)Node杀糯，如果對(duì)比相等，則返回value
else
return findNodeOrNullFromList(key); // 從拉鏈中查找該key的值
}
查找時(shí)同樣也會(huì)需要根據(jù)當(dāng)前是鏈表還是紅黑樹(shù)走不同的查詢邏輯
HashMap的擴(kuò)容過(guò)程
接下來(lái)重點(diǎn)看下HashMap的擴(kuò)容過(guò)程苍苞，上文提到固翰，HashMap在put的時(shí)候，如果put完的哈希表節(jié)點(diǎn)總數(shù)達(dá)到threshold羹呵，則會(huì)進(jìn)行HashMap的擴(kuò)容骂际，擴(kuò)容的操作過(guò)程如下圖：
resize的展開(kāi)過(guò)程如下：
- 開(kāi)辟一個(gè)新的table數(shù)組，大小是原來(lái)的2倍冈欢，即
table[32] - 如果當(dāng)前節(jié)點(diǎn)沒(méi)有哈希沖突歉铝，則直接重新計(jì)算該節(jié)點(diǎn)的
table[]數(shù)組下標(biāo)位置并且放入 - 如果當(dāng)前節(jié)點(diǎn)是紅黑樹(shù)，則執(zhí)行紅黑樹(shù)的split操作將紅黑樹(shù)拆成兩半凑耻，如果拆分后的大小小于了
TREEIFY_THRESHOLD閾值的話太示，降級(jí)為鏈表 - 如果當(dāng)前節(jié)點(diǎn)是鏈表，則根據(jù)
當(dāng)前節(jié)點(diǎn)的hash & oldTable.size（如本例中為16）香浩，根據(jù)結(jié)果為0（low鏈表）或1（high鏈表）拆分為兩個(gè)鏈表类缤，也就是根據(jù)16的二進(jìn)制位（1_0000）從右往左數(shù)第5位
- low鏈表，即
節(jié)點(diǎn).hash & 16 == 0邻吭，即節(jié)點(diǎn).hash第5位為0的節(jié)點(diǎn)保持原下標(biāo) - high鏈表餐弱，即
節(jié)點(diǎn).hash & 16 == 1，即節(jié)點(diǎn).hash第5位為1的節(jié)點(diǎn)下標(biāo)=原下標(biāo)+16
下圖展示了擴(kuò)容時(shí)鏈表的大致拆分過(guò)程
HashMap的modCount以及使用注意
如前文所述，HashMap內(nèi)部維護(hù)著一個(gè)成員變量modCount膏蚓，在HashMap每次進(jìn)行可能影響HashMap結(jié)構(gòu)的操作時(shí)都會(huì)導(dǎo)致modCount++（例如put瓢谢、remove）
這樣做是因?yàn)镠ashMap是不支持線程安全的，如果你的代碼在遍歷HashMap的同時(shí)又在修改影響著HashMap的內(nèi)容驮瞧，必然會(huì)導(dǎo)致遍歷出的結(jié)果不正確氓扛，與其拿到不正確結(jié)果導(dǎo)致后續(xù)基于這個(gè)錯(cuò)誤結(jié)果的一系列錯(cuò)誤，不如快速掀桌子拋出異常ConcurrentModificationException結(jié)束這次遍歷剧董，這個(gè)就是快速失敶鄙小（FailFast），其它相關(guān)的異常容錯(cuò)機(jī)制還有failover（失效轉(zhuǎn)移）翅楼、failback（失效自動(dòng)回復(fù)）等，感興趣的讀者可以自行搜索真慢。
通過(guò)上文可以知道毅臊，modCount主要是遍歷請(qǐng)求受到影響時(shí)的處理方式，但是我們的代碼中經(jīng)常會(huì)遇到一種經(jīng)典的執(zhí)行情況铸史，如下
for(K key : map.keySet()) {
if(key == xxx)
map.remove(key); // 執(zhí)行完后下一輪for循環(huán)拋出ConcurrentModificationException
}
這種時(shí)候我們是在一個(gè)單線程中换淆，我們的目的是刪掉符合判斷條件的節(jié)點(diǎn)然后繼續(xù)遍歷Map袁翁，但是這樣會(huì)導(dǎo)致代碼拋出ConcurrentModificationException異常，就是因?yàn)樵趫?zhí)行了map.remove(key)之后modCount++蚯撩，進(jìn)而導(dǎo)致遍歷開(kāi)始前記錄的 expectModCount != modCount，從而拋出異常
解決的辦法是通過(guò)iterator.remove()刪除節(jié)點(diǎn)
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Entry entry = iter.next();
if(entry.key == xxx)
iter.remove();
}
HashMap的keySet和entrySet
在我們?nèi)粘ｉ_(kāi)發(fā)中經(jīng)常需要對(duì)HashMap進(jìn)行遍歷烛占，常用遍歷方式有兩種：keySet()和entrySet()胎挎。
這兩種遍歷方式返回的Set集合本質(zhì)上都是HashMap的一個(gè)視圖，這個(gè)Set本身是不存儲(chǔ)數(shù)據(jù)的忆家，只是它覆寫(xiě)了相關(guān)的iterator犹菇、contains等方法，這些方法又會(huì)去對(duì)HashMap中的table數(shù)組進(jìn)行相關(guān)的查詢等操作芽卿。
當(dāng)我們對(duì)keySet()和entrySet()返回的Set集合進(jìn)行add操作時(shí)會(huì)拋出UnsupportedOperationException揭芍。
高性能的并發(fā)哈希表--ConcurrentHashMap
以上討論的HashMap是JDK在Hashtable的改進(jìn)上實(shí)現(xiàn)了高性能的單線程版的哈希實(shí)現(xiàn)，這在我們?nèi)粘Ｆ鋵?shí)已經(jīng)能夠處理很多場(chǎng)景卸例，甚至于當(dāng)你所需的HashMap需要實(shí)現(xiàn)線程隔離的時(shí)候也可以通過(guò)ThreadLocal來(lái)實(shí)現(xiàn)（詳見(jiàn) 圖解分析ThreadLocal的原理與應(yīng)用場(chǎng)景）
但是某些場(chǎng)景的哈希表不得不在多個(gè)線程之間共享称杨，這些線程有可能同時(shí)讀某一個(gè)key，同時(shí)改某一個(gè)key筷转，一個(gè)在讀某個(gè)key的時(shí)候另一個(gè)卻在改這個(gè)key姑原，面對(duì)這種情況HashMap只能掀桌子了，但是我們總還是需要一種支持多線程的高效的哈希數(shù)據(jù)結(jié)構(gòu)旦装，
ConcurrentHashMap：“沒(méi)錯(cuò)页衙，正式在下”。
關(guān)于ConcurrentHashMap的高并發(fā)哈希實(shí)現(xiàn)原理會(huì)在下篇文章分析。
reference
[1] JDK8源碼
[2] 《算法導(dǎo)論》
本文的分析都是基于JDK8
