? ? ? ? 學(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對(duì)象屬性

hash：key的哈希值

key：節(jié)點(diǎn)的key卸例，類型和定義HashMap時(shí)的key相同

value：節(jié)點(diǎn)的value，類型和定義HashMap時(shí)的value相同

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

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

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

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

put方法

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

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

????????因?yàn)閔ashmap是非線程安全的，如果多線程操作hashmap擴(kuò)容時(shí)可能會(huì)發(fā)生死鎖的問題确镊，假設(shè)我們有兩個(gè)線程A士骤、B，hashmap容量為2蕾域，A線程放入key T1拷肌、T2、T3旨巷、T4廓块、T5，同時(shí)T1契沫、T2和T3的hash值相同带猴，形成一個(gè)鏈表T1->T2->T3,而T4、T5hash值不相同懈万，于是這時(shí)候容量不足拴清，需要進(jìn)行擴(kuò)容（rehash）靶病，于是新建一個(gè)更大容量的hash表，將數(shù)據(jù)從老的hash表中進(jìn)行遷移口予，這時(shí)候B線程進(jìn)來了娄周，A線程掛起，這時(shí)候B線程發(fā)現(xiàn)容量不足也需要擴(kuò)容沪停，這時(shí)候線程B擴(kuò)容的之后的鏈表為T1->T2,然后B線程執(zhí)行完了煤辨，A線程繼續(xù)執(zhí)行，將鏈表變成了T2->T1,這時(shí)候形成了T1.next=T2木张，T2.next=T1,所以當(dāng)用戶對(duì)這個(gè)key進(jìn)行取值的時(shí)候?qū)?huì)陷入死循環(huán)卡在那沒有反應(yīng)众辨。

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