昨天的博客我解釋了HASHMAP(JDK1.7)在PUT的時候會發(fā)生沖突，而解決沖突的方式就是使用鏈表，那么我們假設HASHMAP存儲結構如下圖：

那么節(jié)點1和節(jié)點2組成了一個鏈表，那么現(xiàn)在如果再來PUT一個節(jié)點3，假設節(jié)點3也需要插在這個鏈表中，我們考慮鏈表的插入效率，將節(jié)點3插在鏈表的頭部是最快的，那么就會如下圖：

那么按照上圖這種插入辦法，會出現(xiàn)一個問題：

當我們需要get(節(jié)點2)時，我們先將節(jié)點2的key進行哈希然后算出下標，拿到下標后可以定位到數(shù)組中的節(jié)點1，但是發(fā)現(xiàn)節(jié)點1不等于節(jié)點2，所以不是最終的結果，但是節(jié)點1存在下一個節(jié)點，所以可以順著向下的指針找到節(jié)點2。

那么當我們需要get(節(jié)點3)時呢，我們發(fā)現(xiàn)是找不到節(jié)點3的，所以當我們把節(jié)點簡單的插在鏈表的頭部是不行的。

那HashMap是怎么實現(xiàn)的呢？HashMap確實是將節(jié)點插在鏈表的頭部，但是在插完之后HashMap會將整個鏈表向下移動一位，移動完之后就會變成：

那么現(xiàn)在PUT的時候插入一個元素的思路就是：將新節(jié)點插在鏈表的頭部，此時新節(jié)點就是當前這個鏈表的頭節(jié)點，接下來把頭節(jié)點移動到數(shù)組位置即可。

當我們在使用HashMap的時候，還可能會出現(xiàn)下面的使用方式:

HashMap<String,String>hashMap=newHashMap<>();
hashMap.put("1","2");
Stringvalue=hashMap.put("1","3");
System.out.println(value);

第三行代碼也是PUT，而這個時候在HashMap里會將value覆蓋，也就是key="1"對應的value最終為"3"，而第三行代碼返回的value將會是2。

我們現(xiàn)在來考慮這個PUT它是如何實現(xiàn)的，其實很簡單，第三行代碼的邏輯也是先對"1"計算哈希值以及對應的數(shù)組下標，有了數(shù)組下標之后就可以找到對應的位置的鏈表，而在將新節(jié)點插入到鏈表之前，還需要判斷一下當前新節(jié)點的key值是不是已經(jīng)在這個鏈表上存在，所以需要先去遍歷當前這個位置的鏈表，在遍歷的過程中如果找到了相同的key則會進行value的覆蓋，并且返回oldvalue。

好，寫到這里其實對于HashMap的PUT的主要邏輯也差不多了，總結一下：

PUT(key，value)

int hashcode = key.hashCode();

int index = hashcode & (數(shù)組長度-1)

遍歷index位置的鏈表，如果存在相同的key，則進行value覆蓋，并且返回之前的value值

將key，value封裝為節(jié)點對象（Entry）

將節(jié)點插在index位置上的鏈表的頭部

將鏈表頭節(jié)點移動到數(shù)組上

這是最核心的7步，然后在這個過程中還有很重要的一步就是擴容，而擴容是發(fā)生在插入節(jié)點之前的，也就是步驟4和5之間的。

那么關于JDK1.7里HashMap的擴容時會出現(xiàn)“死鎖”問題的，我們下篇文章繼續(xù)。