昨天的博客我解釋了HASHMAP(JDK1.7)在PUT的時(shí)候會(huì)發(fā)生沖突，而解決沖突的方式就是使用鏈表，那么我們假設(shè)HASHMAP存儲(chǔ)結(jié)構(gòu)如下圖：
那么節(jié)點(diǎn)1和節(jié)點(diǎn)2組成了一個(gè)鏈表，那么現(xiàn)在如果再來(lái)PUT一個(gè)節(jié)點(diǎn)3，假設(shè)節(jié)點(diǎn)3也需要插在這個(gè)鏈表中，我們考慮鏈表的插入效率，將節(jié)點(diǎn)3插在鏈表的頭部是最快的，那么就會(huì)如下圖：
那么按照上圖這種插入辦法，會(huì)出現(xiàn)一個(gè)問(wèn)題：
當(dāng)我們需要get(節(jié)點(diǎn)2)時(shí)，我們先將節(jié)點(diǎn)2的key進(jìn)行哈希然后算出下標(biāo)，拿到下標(biāo)后可以定位到數(shù)組中的節(jié)點(diǎn)1，但是發(fā)現(xiàn)節(jié)點(diǎn)1不等于節(jié)點(diǎn)2，所以不是最終的結(jié)果，但是節(jié)點(diǎn)1存在下一個(gè)節(jié)點(diǎn)，所以可以順著向下的指針找到節(jié)點(diǎn)2。
那么當(dāng)我們需要get(節(jié)點(diǎn)3)時(shí)呢，我們發(fā)現(xiàn)是找不到節(jié)點(diǎn)3的，所以當(dāng)我們把節(jié)點(diǎn)簡(jiǎn)單的插在鏈表的頭部是不行的。
那HashMap是怎么實(shí)現(xiàn)的呢？HashMap確實(shí)是將節(jié)點(diǎn)插在鏈表的頭部，但是在插完之后HashMap會(huì)將整個(gè)鏈表向下移動(dòng)一位，移動(dòng)完之后就會(huì)變成：
那么現(xiàn)在PUT的時(shí)候插入一個(gè)元素的思路就是：將新節(jié)點(diǎn)插在鏈表的頭部，此時(shí)新節(jié)點(diǎn)就是當(dāng)前這個(gè)鏈表的頭節(jié)點(diǎn)，接下來(lái)把頭節(jié)點(diǎn)移動(dòng)到數(shù)組位置即可。
當(dāng)我們?cè)谑褂肏ashMap的時(shí)候，還可能會(huì)出現(xiàn)下面的使用方式:
HashMap<String,String>hashMap=newHashMap<>();
hashMap.put("1","2");
Stringvalue=hashMap.put("1","3");
System.out.println(value);
第三行代碼也是PUT，而這個(gè)時(shí)候在HashMap里會(huì)將value覆蓋，也就是key="1"對(duì)應(yīng)的value最終為"3"，而第三行代碼返回的value將會(huì)是2。
我們現(xiàn)在來(lái)考慮這個(gè)PUT它是如何實(shí)現(xiàn)的，其實(shí)很簡(jiǎn)單，第三行代碼的邏輯也是先對(duì)"1"計(jì)算哈希值以及對(duì)應(yīng)的數(shù)組下標(biāo)，有了數(shù)組下標(biāo)之后就可以找到對(duì)應(yīng)的位置的鏈表，而在將新節(jié)點(diǎn)插入到鏈表之前，還需要判斷一下當(dāng)前新節(jié)點(diǎn)的key值是不是已經(jīng)在這個(gè)鏈表上存在，所以需要先去遍歷當(dāng)前這個(gè)位置的鏈表，在遍歷的過(guò)程中如果找到了相同的key則會(huì)進(jìn)行value的覆蓋，并且返回oldvalue。
好，寫(xiě)到這里其實(shí)對(duì)于HashMap的PUT的主要邏輯也差不多了，總結(jié)一下：
PUT(key，value)
int hashcode = key.hashCode();
int index = hashcode & (數(shù)組長(zhǎng)度-1)
遍歷index位置的鏈表，如果存在相同的key，則進(jìn)行value覆蓋，并且返回之前的value值
將key，value封裝為節(jié)點(diǎn)對(duì)象（Entry）
將節(jié)點(diǎn)插在index位置上的鏈表的頭部
將鏈表頭節(jié)點(diǎn)移動(dòng)到數(shù)組上
這是最核心的7步，然后在這個(gè)過(guò)程中還有很重要的一步就是擴(kuò)容，而擴(kuò)容是發(fā)生在插入節(jié)點(diǎn)之前的，也就是步驟4和5之間的。
那么關(guān)于JDK1.7里HashMap的擴(kuò)容時(shí)會(huì)出現(xiàn)“死鎖”問(wèn)題的，我們下篇文章繼續(xù)。
