JDK1.7版本中的HashMap

以下講解基于JDK1.7

<a href="https://s5.51cto.com/oss/201711/21/16e2d5411abebb9936a0a8ca46147371.png" target="_blank"></a>

HashMap底層是一個數組，哈希值相同的元素放在數組中的相同的位置，多個相同哈希值的元素形成一個連結清單。也就是說，元素的組織形式是單向連結清單。

下面從put、get、remove這三個方法分析一下源代碼，看看HashMap增删查改是怎麼做的。

<a href="https://s2.51cto.com/oss/201711/21/c1457a37a1263785263c4f295139c194.png" target="_blank"></a>

<a href="https://s2.51cto.com/oss/201711/21/52c70c6639570c637115c51fce0b9edc.png" target="_blank"></a>

<a href="https://s2.51cto.com/oss/201711/21/31ae5bd82dd27e186909af6f3e7f0824.png" target="_blank"></a>

構造HashMap對象的時候做了初始化，指定預設的初始容量（數組長度）和增長因子

接下來，從put開始分析

<a href="https://s1.51cto.com/oss/201711/21/4266c06f740f92a3670abe063b774944.png" target="_blank"></a>

<a href="https://s1.51cto.com/oss/201711/21/422ebfef9499513522b028f870209cf4.png" target="_blank"></a>

<a href="https://s1.51cto.com/oss/201711/21/8549e057a56656e2bab37e2f90b13c13.png" target="_blank"></a>

從上面三段代碼可以看出添加一個元素的基本流程：

（1）HashMap的key值允許為null，而且key為null的元素放在數組中下标為0的位置

（2）根據待插入元素的key值計算出一個哈希值，然後根據這個哈希值和數組的長度計算該元素将要放置的位置（PS：下标）。如果這個位置為空，那麼直接插入。否則，周遊該位置上的連結清單，依次比較他們的key值是否相同，如果相同，則将用新值替換舊值，然後傳回就值。

（3）正常插入，将待插入的元素放置在連結清單的頭部，然後将其指向原先的連結清單頭部（即：原先放置在待插入位置的元素）。也就是說，新插入的元素是放在頭部的，我覺得這樣做的好處可能是根據LRU的原則減少周遊的次數。

<a href="https://s3.51cto.com/oss/201711/21/4aaa1f8dfd8c2aa5524e77b383f1d413.png" target="_blank"></a>

(4)有一種特殊情況是，擴容。

<a href="https://s1.51cto.com/oss/201711/22/e353474a8dabc72e43738c338e3cda84.png" target="_blank"></a>

<a href="https://s5.51cto.com/oss/201711/22/c22e2dfcf011e6bd26b17492f1fd5cae.png" target="_blank"></a>

<a href="https://s5.51cto.com/oss/201711/22/9a6f0038999803732fd6a601ba1c3dc2.png" target="_blank"></a>

擴容就是，将原數組中的每個位置的元素都遷移到新數組中，在遷移到新數組的過程中同樣先計算哈希值，然後得出将要放置在新數組中那個位置上。連結清單的遷移過程相當于将原先的連結清單倒置，先将頭部的元素遷移過去，然後将下一個元素遷移過去，令next元素的next指向新數組位置上的元素，最終呈現出來的效果就是連結清單倒置。

接下來看get操作

<a href="https://s2.51cto.com/oss/201711/22/a3ba157a678f086b90172ede47e6ee72.png" target="_blank"></a>

<a href="https://s4.51cto.com/oss/201711/22/7f1b13557cabd806e2451490868996a9.png" target="_blank"></a>

get操作比較簡單：

（1）根據key算哈希值，進而得出元素可能的位置，然後周遊該位置上的連結清單，比較key值是否相同，相同則傳回，否則傳回null

最後是remove

删除也相對比較簡單：

（1）删除元素所在位置，周遊連結清單，比較key值，找到待删除元素以後，如果目前隻有一個元素，直接删除，此位置置位NULL，否則将前面元素的next指向後面元素。

HashMap在并發情況下存在的問題（并發就是沒法保證順序）

（1）插入的元素可能被覆寫

<a href="https://s2.51cto.com/oss/201711/22/75421e9d2f9efb86b0993eacc39674dc.png" target="_blank"></a>

假設有兩個線程都執行到這裡，線程1它的key=A，value=aaa，線程2它的key=B，value=bbb。

假設i=1，那麼線程1執行的時候table[1]=new Entry&lt;&gt;(1234, "A", "aaa", null);

等到線程2執行的時候table[1]=new Entry&lt;&gt;(1234, "B", "bbb", null);

于是乎，線程1插入的資料就丢失了（或者說是被覆寫了）

（2）put的時候，連結清單可能形成環形資料結構，導緻如果查找一個不存在的元素時死循環

那麼環狀是怎麼形成的呢？發生在擴容的時候。請看圖

<a href="https://s4.51cto.com/oss/201711/22/fe7de554410a6b5077ada724afc4b907.png" target="_blank"></a>

假設有兩個元素A和B，它們的關系是A.next=B，B.next=null

大概就是下面這個樣子

<a href="https://s2.51cto.com/oss/201711/22/3848a9c0cc5f7fe380da2d7a1605b807.png" target="_blank"></a>

假設有兩個線程，線程-1和線程-2，它們在執行插入的時候都發現需要擴容，于是乎都開始擴容。

當然，擴容是在它們自己的記憶體中進行的。假設線程-1完成對A元素的遷移後準備對B進行遷移并執行到Entry&lt;K,V&gt; next = e.next;時還沒執行時線程被挂起了。執行到線程-2先執行完擴容，于是擴容後的指向關系變成了這個樣子：B.next=A，A.next=null

<a href="https://s4.51cto.com/oss/201711/22/c07b8da039ca7de381673f0b09bcba76.png" target="_blank"></a>

特别注意，看圖上畫的好像是元素直接放到數組的某個位置，但我們要知道，其它放的是元素的位址，也就是說元素本身的位置不變，修改的隻是指針指向。盡管線程-2構造的新數組對線程-1而言是不可見的，但是不可否認，線程-2在擴容過程中已經将A和B的指向關系修改了，也就是說，此時，B是指向A的，這一點對線程-1而言是可見的。

接下來，線程-1醒來，繼續執行

while(null != e) {

此時，對照代碼應該是這樣的

<a href="https://s5.51cto.com/oss/201711/22/e5d8c692c771bfecb2bde936bee2164a.png" target="_blank"></a>

經過這一遍，現在在新數組中的指向關系變成：B--&gt;A--&gt;NULL

緊接着，因為e已經是A了，是以null != e，于是再執行一遍

<a href="https://s4.51cto.com/oss/201711/22/ecc603045ca1f804f44cce7d805a47a5.png" target="_blank"></a>

然後就變成這樣了

<a href="https://s5.51cto.com/oss/201711/22/15c1dd235ec478750eab54e90b07bf39.png" target="_blank"></a>

接下來，麻煩來了。

查找C，經過計算C應該與A、B在數組的同一個位置，于是周遊連結清單

<a href="https://s5.51cto.com/oss/201711/22/ea09508843b2647c5dccd5874aaebc8c.png" target="_blank"></a>

于是，通過A找到B，通過B又找到A，通過A又找到B，通過B又找到A，如此反複，永遠都不為null，死循環

終于講明白了

最後，再提一點，就是hash方法，字元串和非字元串算哈希值的方法是不一樣的

<a href="https://s5.51cto.com/oss/201711/22/cbb2f3f52dcfd68e2d21a2e1327ee8c9.png" target="_blank"></a>

參考：

http://blog.csdn.net/zhuqiuhui/article/details/51849692

https://www.cnblogs.com/binyue/p/3726403.html

本文轉自   手不要亂摸  51CTO部落格，原文連結:http://blog.51cto.com/5880861/1984059