Java刷題知識點之HashMap的實作原理、HashMap的存儲結構、HashMap在JDK1.6、JDK1.7、JDK1.8之間的差異以及帶來的性能影響HashMap的實作原理HashMap的存儲結構牛客網Java刷題知識點之數組、連結清單、哈希表、 紅黑二叉樹HashMap在JDK1.6中的實作方式HashMap在JDK1.7中的實作HashMap在JDK1.8中的實作HashMap的不足以及産生原因總結

　　HashMap是基于java.util.map接口的實作，該實作提供了所有的對Map的可選操作，同時也允許null類型的key以及value （HashTable與此大緻相同，隻是HashTable是同步的，不過HashTable一般被認為是已經過時的，很少有人再去用了）。

　　HashMap不保證Map中的順序，特别是不能保證資料在一段時間内的順序性。

　　如果散列函數（Hash函數）在正确的在桶中分散元素，HashMap的實作提供了對基本的操作（put與get）時間性能為常數。

　　集合視圖的疊代需要的時間與HashMap執行個體的容量capacity值（桶數）和大小（鍵值對個數）成正比，是以如果對疊代器的性能比較關注， 那麼不要把初始化的容量capacity值設的太高或不要将裝填因子load factor設的太小就非常重要。

　　HashMap的執行個體總有兩個非常重要的影響性能的參數：初始容量大小（initial capacity）與裝填因子（load factor）。

       在HashMap中，capacity就是buckets的數量，初始容量大小就是在HashMap建立的時候指定的capacity。

　　裝填因子指的是HashMap在多滿的時候就需要提前自動擴容了（如初始化容量16，裝填因子0.75，一旦元素個數 超過16*0.75=12個的時候，就需要對容量進行擴充，翻倍） 擴容需要rehash，也就是說HashMap内部結構會被重新建構。

　　通常來講，預設的裝填因子0.75提供了一個基于時間與空間代價比較好的平衡。桶中裝的更滿意味着空間開銷更低， 但是查找開銷變大（反映到HashMap中就是包含get與put在内各種操作開銷變大，時間變長）。

　　當設定初始容量大小時，應該考慮HashMap中預期的數量以及裝填因子，這樣才能讓rehash執行的次數最少， 如果初始化大小的值比實際資料的條數乘以裝填因子的積還要大，那麼就不會發生rehash。

　　如果有非常多的記錄存在HashMap中，那麼在初始化這個HashMap的時候将容量capacity設定的足夠大，比自動rehash 擴容效率更高。

　　注意如果很多key有了相同的hashCode值，那麼會對性能造成很大的影響（産生聚集問題，rehash次數變多，性能下降），為了改善這種情況 當key可以進行比較（繼承了Comparable接口之類的），HashMap會采用對key進行比較排序。

　　注意：HashMap不是線程同步的。

　　如果多線程并發通路一個HashMap，同時至少有一個線程修改了HashMap的結構，那麼該HashMap必須要在外部進行同步 （結構的改變指的是添加或删除一個映射關系-鍵值對，隻是根據key修改了value的值不會對HashMap造成結構上的影響） 這種同步操作通常在封裝有HashMap的Object中實作；如果沒有這樣的對象實作，那麼HashMap需要采用Collections.synchronizedMap 來保證多線程并發環境下的資料同步問題，這個操作最好在建立HashMap的時候就去做。 Map m = Collections.synchronizedMap(new HashMap(…));

　　如果HashMap産生的疊代器建立後，HashMap資料結構又發生了變化，則除了remove方法外，疊代器iterator會抛出一個 ConcurrentModificationException異常，這就是疊代器的快速失敗（fail-fast）。 是以面對并發修改，疊代器采用快速而幹淨的失敗來取代在未來的某一個不确定的時間産生不确定的後果。

　　注意：疊代器的快速失敗行為是無法保證的，通常來講，在非同步并發修改的情況下這種硬性保證都沒法給出，快速失敗也隻能盡量抛出 ConcurrentModificationException異常，是以不能寫一段代碼去基于該異常做出義務邏輯處理，最好快速失敗進行BUG探測。

　　HashMap的存儲，本質上是構造了一個table，根據計算的hashCode将對應的KV存儲到該table中，一旦發生hashCode沖突，那麼就會将該KV放到對應的已有元素的後面， 此時，形成了一個連結清單式的存儲結構，即：HashMap 就是一個table數組  +   連結清單實作的存儲結構（在JDK1.8之前的存儲結構），如下圖所示：

　　

　　 從上圖中，我們可以發現哈希表是由數組  +   連結清單組成的，一個長度為16的數組中，每個元素存儲的是一個連結清單的頭結點。那麼這些元素是按照什麼樣的規則存儲到數組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。是以12、28、108以及140都存儲在數組下标為12的位置。它的内部其實是用一個Entity數組來實作的，屬性有key、value、next。

　　當構造出一個HashMap後，每次put一個元素時，會執行addEntry操作，addEntry中會執行建立一個Entry實體存儲目前的KV，如果有Hash沖突， 那麼就會将目前的entry指向最後一個沖突的entry，同時将目前的entry放到連結清單中，執行完目前操作後，判斷是否需要resize，如果需要，則構造出一個新的entry數組（比之前大一倍）， 并将原有的數組中的entry連結清單（或entry）拷貝到新的數組中。

 　　在JDK1.8中有了一些變化，當連結清單的存儲的資料個數大于等于8的時候，不再采用連結清單存儲，而采用了紅黑樹存儲結構。如下圖所示：

　　 這麼做主要是查詢的時間複雜度上，連結清單為O(n)，而紅黑樹一直是O(logn)，一般來講，沖突（即為相同的hash值存儲的元素個數） 超過8個，紅黑樹的性能高于連結清單的查找性能。

　　put方法：

　　put方法完成資料的基本寫入操作，同時會驗證資料的有效性，如key是否為空的處理，計算hash值，hash值 的查找，并根據hash值找出所有的資料，判斷是否重複，如果重複，則替換，并傳回舊值，如果不重複，則寫入資料（addEntry）。

　　對應的addEntry方法： addEntry方法實作了資料的寫入以及判斷是否需要對HashMap進行擴容。

　　resize方法： resize方法主要是對Map進行擴容的實際操作：構造存儲結構，并調用資料轉移方法transfer進行資料轉移

　　transfer 方法： 完成資料轉移，注意，轉移的過程就是兩個數組進行資料拷貝的過程，資料産生了倒置，新元素其實是插入到了第一個位置。

　　 Entry的構造： 鍊式存儲結構。

　　JDK1.7中的實作與JDK1.6中的實作總體來說，基本沒有改進，差別不大。

　　put 方法：

　　addEntry方法：

　　resize方法：

　　transfer方法：

　　createEntry方法：

　　put方法： put方法中與JDK1.6/1.7相比，新增了判斷是否是TreeNode的邏輯，TreeNode即為紅黑樹， 同時添加了沖突的元素個數是否大于等于7的判斷（因為第一個是-1，是以還是8個元素），如果沖突的元素個數超過8個，則構造紅黑樹（treeifyBin方法），否則還是按照連結清單方式存儲。

　　treeifyBin方法： treeifyBin方法主要是将鍊式存儲的沖突的資料轉換成樹狀存儲結構

　　resize方法： 注意：JDK1.8中resize方法擴容時對連結清單保持了原有的順序。

　　在多線程并發環境下會有如下一種情況：

　　兩個線程同時操作時同時遇到HashMap需要擴容，且映射到相同的位址（key計算得到的HashCode相同），此時在擴容時可能發生一種情況， 兩個線程同時對HashMap進行擴容，擴容時做第一次循環時一個線程阻塞，另一個完成擴容，前一個繼續，那麼就可能發生連結清單資料的互相指向問題， 造成get資料時周遊的死循環

　　測試代碼如下：

　　注意：我參考了大量的網上的一些部落格，他們基本都是基于JDK1.6進行的分析，即：先寫入資料，再擴容：

　　由此，很容易産生上述問題，而在JDK1.7中發生了變化，先擴容，再進行資料寫入：

　　此時，先擴容，再寫入資料，就不會産生這種問題，但是會産生另一中問題，即： HashMap中有A元素，thread1 寫入B元素（碰撞），thread2寫入C元素（碰撞） 線程thread1先擴容，在寫入資料，同時線程thread2也進行該操作那麼，最終互不影響， thread1得到：B->A連結清單，thread2得到：C->A連結清單，那麼，在thread1中取資料，能否取到C元素？ 多線程并發問題依舊存在。

　　在JDK1.8中，HashMap的這塊兒做了大量改進，死循環問題已經解決了：

　　但是JDK1.8 中通過測試發現依然存在JDK1.7中的資料丢失情況。

　　同時在并發情況下會出現如下新的問題： Hash碰撞情況下：前一個線程判斷是連結清單存儲，準備寫入資料，但是寫入時阻塞，其他線程也準備寫入，發現資料連結清單為8，此時構造紅黑樹，然後完成資料轉移 前一個線程此後寫入資料時，就會出現類型錯誤：

相關測試代碼（可能需要多執行幾次）：

HashMap的JDK1.6、JDK1.7、JDK1.8中的實作各不相同，尤其以JDK1.8變化最大，注意區分

本文轉自大資料躺過的坑部落格園部落格，原文連結：http://www.cnblogs.com/zlslch/p/7622756.html，如需轉載請自行聯系原作者