? ? ? ? 學(xué)習(xí)了java這么久沒有看過hashmap源碼，近期才來了解hashmap的底層結(jié)構(gòu)，雖然網(wǎng)上有很多關(guān)于hashmap的文章但是我還是想學(xué)習(xí)總結(jié)一下。

? ? ? ? 在jdk1.8之前hashmap是數(shù)組+鏈表的形式，jdk1.8變成了數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)，核心都是為了提高查詢速度，現(xiàn)在聊下hashmap的數(shù)據(jù)結(jié)構(gòu)基于jdk1.8。

基礎(chǔ)結(jié)構(gòu)圖

node類

node對象屬性

hash：key的哈希值

key：節(jié)點的key，類型和定義HashMap時的key相同

value：節(jié)點的value，類型和定義HashMap時的value相同

next：該節(jié)點的下一節(jié)點

????????當(dāng)它第一次put時候，它才會進(jìn)行初始化擴(kuò)容默認(rèn)大小capacity是16第二次是32第三次是64就算設(shè)置初始化20，大小也是32，每次擴(kuò)容都是2的冪，之所以每次擴(kuò)容都為2的冪是為了符合Hash算法均勻分布的原則，防止取模運算后有些index結(jié)果的出現(xiàn)幾率會更大，而有些index結(jié)果永遠(yuǎn)不會出現(xiàn)，為了index分布的更加均勻，所以采取2的冪。可以參考hashmap

????????每次進(jìn)行put時，他會計算key的hash值，然后通過位運算進(jìn)行取模(n -1) & hash，然后求出放置到數(shù)組的i位置，如果tab[i]為空，將node放置到這個位置，同時node.next為null，如果tab[i]不為空將會進(jìn)行判斷這個key值是否相等(畢竟hashcode肯定是相同)，如果key值相等將會替換掉這個node，如果key值不相等將會在這個node插入在鏈表的最前端，next連著之前的node，就類似（HashMap會這樣做:B.next = A,table[0] = B,如果又進(jìn)來C,index也等于0,那么C.next = B,table[0] = C)。

? ? ? ?而且hashmap還有個負(fù)載因子loadFactor（默認(rèn)0.75）、capacity容量大小（默認(rèn)16）和threshold（loadFactor * capacity），這個負(fù)載因子主要是用來衡量HashMap滿的程度，它主要是設(shè)置一個界限，當(dāng)map的容量除以capacity總?cè)萘看笮?gt;=loadFactor，其實就是map當(dāng)前容量大于threshold將會進(jìn)行擴(kuò)容。

put方法

? ? ? ? 如果當(dāng)鏈表的節(jié)點的長度大于TREEIFY_THRESHOLD（默認(rèn)是8，雖然判斷是bincont>=7但是由于for循環(huán)是給p.next進(jìn)行賦值，所以當(dāng)bincont為7的時候他的鏈表長度已經(jīng)是8了）的時候?qū)D(zhuǎn)成紅黑樹，但是如果tab長度小于MIN_TREEIFY_CAPACITY（默認(rèn)值是64），它不會轉(zhuǎn)紅黑樹而是將進(jìn)行擴(kuò)容再次散列（(n -1) & hash取模，因為擴(kuò)容后長度變動，重新散列后node下標(biāo)會變動達(dá)到防止鏈表過長的目的）避免鏈表過長。

鏈表轉(zhuǎn)紅黑樹《

????????因為hashmap是非線程安全的，如果多線程操作hashmap擴(kuò)容時可能會發(fā)生死鎖的問題，假設(shè)我們有兩個線程A、B，hashmap容量為2，A線程放入key T1、T2、T3、T4、T5，同時T1、T2和T3的hash值相同，形成一個鏈表T1->T2->T3,而T4、T5hash值不相同，于是這時候容量不足，需要進(jìn)行擴(kuò)容（rehash），于是新建一個更大容量的hash表，將數(shù)據(jù)從老的hash表中進(jìn)行遷移，這時候B線程進(jìn)來了，A線程掛起，這時候B線程發(fā)現(xiàn)容量不足也需要擴(kuò)容，這時候線程B擴(kuò)容的之后的鏈表為T1->T2,然后B線程執(zhí)行完了，A線程繼續(xù)執(zhí)行，將鏈表變成了T2->T1,這時候形成了T1.next=T2，T2.next=T1,所以當(dāng)用戶對這個key進(jìn)行取值的時候?qū)萑胨姥h(huán)卡在那沒有反應(yīng)。

? ? ? ? 如果需要多線程操作hashmap可以使用ConcurrenHashmap進(jìn)行替代，ConcurrenHashmap是一個線程安全的hashtable，這時候就有人問為什么不直接使用hashtable，雖然hashtable也是線程安全的但是hashtable鎖定的是一整個hash表，效率較為低下，而ConcurrenHashmap可以做到讀取數(shù)據(jù)不進(jìn)行加鎖實現(xiàn)段鎖，因為其內(nèi)部結(jié)構(gòu)有個Segment的存在，使其進(jìn)行寫操作的時候可以將鎖的粒度保持盡量小。