hashmap實現原理源碼

A. HashMap實現原理

HashMap在實際開發中用到的頻率非常高，面試中也是熱點。所以決定寫一篇文章進行分析，希望對想看源碼的人起到一些幫助，看之前需要對鏈表比較熟悉。
以下都是我自己的理解，歡迎討論，寫的不好輕噴。

HashMap中的數據結構為散列表，又名哈希表。在這里我會對散列表進行一個簡單的介紹，在此之前我們需要先回顧一下 數組 、 鏈表 的優缺點。

數組和鏈表的優缺點取決於他們各自在內存中存儲的模式，也就是直接使用 順序存儲 或 鏈式存儲 導致的。無論是數組還是鏈表，都有明顯的缺點。而在實際業務中，我們想要的往往是定址、刪除、插入性能都很好的數據結構，散列表就是這樣一種結構，它巧妙的結合了數組與鏈表的優點，並將其缺點弱化（並不是完全消除）

散列表的做法是將key映射到數組的某個下標，存取的時候通過key獲取到下標（index）然後通過下標直接存取。速度極快，而將key映射到下標需要使用 散列函數 ，又名 哈希函數 。說到哈希函數可能有人已經想到了，如何將key映射到數組的下標。

圖中計算下標使用到了以下兩個函數：

值得注意的是，下標並不是通過hash函數直接得到的，計算下標還要對hash值做index()處理。
Ps：在散列表中，數組的格子叫做 桶 ，下標叫做 桶號 ，桶可以包含一個key-value對，為了方便理解，後文不會使用這兩個名詞。

以下是哈希碰撞相關的說明：

以下是下標沖突相關的說明：

很多人認為哈希值的碰撞和下標沖突是同一個東西，其實不是的，它們的正確關系是這樣的， hashCode發生碰撞，則下標一定沖突；而下標沖突，hashCode並不一定碰撞

上文提到，在jdk1.8以前HashMap的實現是 散列表 = 數組 + 鏈表 ，但是到目前為止我們還沒有看到鏈表起到的作用。事實上，HashMap引入鏈表的用意就是解決下標沖突。

下圖是引入鏈表後的散列表：

如上圖所示，左邊的豎條，是一個大小為16的數組，其中存儲的是鏈表的頭結點，我們知道，擁有鏈表的頭結點即可訪問整個鏈表，所以認為這個數組中的每個下標都存儲著一個鏈表。其具體做法是，如果發現下標沖突，則 後插入的節點以鏈表的形式追加到前一個節點的後面 。

這種使用鏈表解決沖突的方法叫做： 拉鏈法 （又叫鏈地址法）。HashMap使用的就是拉鏈法，拉鏈法是沖突發生以後的解決方案。

Q：有了拉鏈法，就不用擔心發生沖突嗎？
A：並不是！由於沖突的節點會不停的在鏈表上追加，大量的沖突會導致單個鏈表過長，使查詢性能降低。所以一個好的散列表的實現應該從源頭上減少沖突發生的可能性，沖突發生的概率和哈希函數返回值的均勻程度有直接關系，得到的哈希值越均勻，沖突發生的可能性越小。為了使哈希值更均勻，HashMap內部單獨實現了hash()方法。

以上是散列表的存儲結構，但是在被運用到HashMap中時還有其他需要注意的地方，這里會詳細說明。

現在我們清楚了散列表的存儲結構，細心的人應該已經發現了一個問題：java中數組的長度是固定的， 無論哈希函數是否均勻，隨著插入到散列表中數據的增多，在數組長度不變的情況下，鏈表的長度會不斷增加 。這會導致鏈表查詢性能不佳的缺點出現在散列表上，從而使散列表失去原本的意義。為了解決這個問題，HashMap引入了擴容與負載因子。

以下是和擴容相關的一些概念和解釋：

Ps： 擴容要重新計算下標 ， 擴容要重新計算下標 ， 擴容要重新計算下標 ，因為下標的計算和數組長度有關，長度改變，下標也應當重新計算。

在1.8及其以上的jdk版本中，HashMap又引入了紅黑樹。

紅黑樹的引入被用於替換鏈表，上文說到，如果沖突過多，會導致鏈表過長，降低查詢性能，均勻的hash函數能有效的緩解沖突過多，但是並不能完全避免。所以HashMap加入了另一種解決方案，在往鏈表後追加節點時，如果發現鏈表長度達到8，就會將鏈表轉為紅黑樹，以此提升查詢的性能。

B. hashmap底層實現原理

hashmap底層實現原理是SortedMap介面能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的。

如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現Comparable介面或者在構造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。

Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，並且是線程安全的，任一時間只有一個線程能寫Hashtable

從結構實現來講，HashMap是：數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的。

(2)hashmap實現原理源碼擴展閱讀

從源碼可知，HashMap類中有一個非常重要的欄位，就是 Node[] table，即哈希桶數組。Node是HashMap的一個內部類，實現了Map.Entry介面，本質是就是一個映射(鍵值對)，除了K，V，還包含hash和next。

HashMap就是使用哈希表來存儲的。哈希表為解決沖突，採用鏈地址法來解決問題，鏈地址法，簡單來說，就是數組加鏈表的結合。在每個數組元素上都一個鏈表結構，當數據被Hash後，得到數組下標，把數據放在對應下標元素的鏈表上。

如果哈希桶數組很大，即使較差的Hash演算法也會比較分散，如果哈希桶數組數組很小，即使好的Hash演算法也會出現較多碰撞，所以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況確定哈希桶數組的大小，並在此基礎上設計好的hash演算法減少Hash碰撞。