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

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

基礎結構圖

node類

node對象屬性

hash：key的哈希值

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

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

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

????????當它第一次put時候，它才會進行初始化擴容默認大小capacity是16第二次是32第三次是64就算設置初始化20，大小也是32，每次擴容都是2的冪，之所以每次擴容都為2的冪是為了符合Hash算法均勻分布的原則，防止取模運算后有些index結果的出現(xiàn)幾率會更大，而有些index結果永遠不會出現(xiàn)，為了index分布的更加均勻，所以采取2的冪?？梢詤⒖?a target="_blank">hashmap

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

? ? ? ?而且hashmap還有個負載因子loadFactor（默認0.75）、capacity容量大小（默認16）和threshold（loadFactor * capacity），這個負載因子主要是用來衡量HashMap滿的程度，它主要是設置一個界限，當map的容量除以capacity總容量大小>=loadFactor，其實就是map當前容量大于threshold將會進行擴容。

put方法

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

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

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

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