1.7

數(shù)據(jù)結(jié)構(gòu)： 內(nèi)部主要是一個(gè)Segment數(shù)組，而數(shù)組的每一項(xiàng)又是一個(gè)HashEntry數(shù)組，元素都存在HashEntry數(shù)組里。因?yàn)槊看捂i定的是Segment對(duì)象，也就是整個(gè)HashEntry數(shù)組，所以又叫分段鎖。

image.png

1.8

數(shù)據(jù)結(jié)構(gòu)： 與HashMap一樣采用：數(shù)組+鏈表+紅黑樹

image.png

底層原理則是采用鎖鏈表或者紅黑樹頭結(jié)點(diǎn)，相比于HashTable的方法鎖，力度更細(xì)，是對(duì)數(shù)組（table）中的桶（鏈表或者紅黑樹）的頭結(jié)點(diǎn)進(jìn)行鎖定，這樣鎖定，只會(huì)影響數(shù)組（table）當(dāng)前下標(biāo)的數(shù)據(jù)，不會(huì)影響其他下標(biāo)節(jié)點(diǎn)的操作，可以提高讀寫效率。 putVal執(zhí)行流程：

1. 判斷存儲(chǔ)的key、value是否為空，若為空，則拋出異常

2. 計(jì)算key的hash值，隨后死循環(huán)（該循環(huán)可以確保成功插入，當(dāng)滿足適當(dāng)條件時(shí)，會(huì)主動(dòng)終止），判斷table表為空或者長度為0，則初始化table表

3. 根據(jù)hash值獲取table中該下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)，如果該節(jié)點(diǎn)為空，則根據(jù)參數(shù)生成新的節(jié)點(diǎn)，并以CAS的方式進(jìn)行更新，并終止死循環(huán)。

4. 如果該節(jié)點(diǎn)的hash值是MOVED(-1)，表示正在擴(kuò)容，則輔助對(duì)該節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移。

5. 對(duì)數(shù)組（table）中的節(jié)點(diǎn)，即桶的頭結(jié)點(diǎn)進(jìn)行鎖定，如果該節(jié)點(diǎn)的hash大于等于0，表示此桶是鏈表，然后對(duì)該桶進(jìn)行遍歷（死循環(huán)），尋找鏈表中與put的key的hash值相等，并且key相等的元素，然后進(jìn)行值的替換，如果到鏈表尾部都沒有符合條件的，就新建一個(gè)node，然后插入到該桶的尾部，并終止該循環(huán)遍歷。

6. 如果該節(jié)點(diǎn)的hash小于0，并且節(jié)點(diǎn)類型是TreeBin，則走紅黑樹的插入方式。

7. 判斷是否達(dá)到轉(zhuǎn)化紅黑樹的閾值，如果達(dá)到閾值，則鏈表轉(zhuǎn)化為紅黑樹。

image.png

推薦閱讀：職業(yè)規(guī)劃：《985、211、一本、二本、三本》2022年完整版進(jìn)大廠拿高薪方案！