以下源碼均為jdk1.7

HashMap概述

HashMap是基于哈希表的Map接口的非同步實現. 提供所有可選的映射操作, 并允許使用null值和null健. 此類不保證映射的順序.

需要注意的是: HashMap不是同步的.

哈希表

哈希表定義: 哈希表是一種根據關鍵碼去尋找值的數據映射結構, 該結構通過把關鍵碼映射的位置去尋找存放值的地方.

舉個例子, 最典型的例子就是字典, 如果想要在字典中查找"按"字, 通常會根據拼音 an 去查找拼音索引(當然也可以是偏旁索引), 然后找到 ti 在字典中的位置, 得到第一個拼音為 an 的字 "安". 這個過程就是鍵碼映射, 即 通過 key 查找 f(key). 其中 key為關鍵字, f()是哈希函數, 哈希函數的結果就是哈希值.

哈希沖突:?那么問題來了, 我們要查找的是"按",而不是"安", 但他們的拼音都是一樣的. 通過關鍵字 an "按"和"安"可以映射到一樣的字典頁碼4的位置, 這就是哈希沖突(也叫哈希碰撞), 在公式上表達就是 key1 != key2, 但f(key1)=f(key2).

key 為值, f(key)計算得出數組中存儲地址, 這樣就會出現兩個元素的地址相同的情況. 這時, 哈希函數的設計就至關重要了, 好的哈希函數會盡可能的保證 計算簡單和散列地址分布均勻, 但是, 數組是一個連續的固定長度的內存空間, 再好的哈希函數也不能保證得到的存儲地址絕不發生沖突.

哈希沖突的解決方案有多種: 開放定址法(發生沖突, 尋找下一個), 再散列函數法, 鏈地址法.

HashMap就是采用了鏈地址發, 也就是 數組+鏈表 的方式.

HashMap的實現原理

最基本的數據結構有兩種: 數組和指針, HashMap就是通過這兩個數據結構實現的, 是數組和鏈表的結合體.

?

從圖中可以看出, HashMap底層是一個數組結構, 數組中的每一項是一個鏈表. 當新建HashMap時, 會初始化一個數組.

HashMap的主干是一個Entry數組.

?

Entry是一個靜態內部類, 包含 key-value.

?

HashMap存儲的整體結構如下:

?

簡單說, HashMap有數組+鏈表組成, 數組是HashMap的主體, 鏈表是為了解決哈希沖突而存在的, 如果定位到數組位置不含鏈表(當前entry的next指向null), 那么對于查找,添加等操作很快, 僅需一次尋址即可; 如果定位到的數組包含鏈表, 那么添加操作就要遍歷鏈表, 然后通過key的equals方法進行逐一對比, 存在即覆蓋, 不存在則新增, 而查找操作也需遍歷鏈表.

所以, 性能考慮, HashMap中的鏈表出現越少, 性能越好.

HasmMap幾個重要的字段:

?

?

?

?

?

HashMap的構造函數:

?

從上面代碼中可以看出, 在常規構造器中, 沒有為數組 table 分配內存空間(有個參數為map的構造器除外), 而是在執行 put操作時才真正構建table數組

?

再來看 inflateTable()方法源碼:

?

重量級角色, 哈希函數出場:

?

indexFor()函數實現如下:

?

h&(length - 1)保證獲取的index一定在數組的范圍內, 例如: 容量為16, length-1=15, h=18, 進行計算為:

?

得出index=2.

故而, 最終存儲位置的確定為如下流程:

?

最后看下 addEntry 的實現:

?

通過 addEntry 的代碼可以看出, 當發生哈希沖突并且size大于閾值時, 需要進行數組擴容, 擴容時, 需要新建一個長度為之前2倍的新數組, 最后將當前的Entry數組中元素全部傳過去, 擴容后的新數組長度為之前的2倍, 所以擴容相對來說是一個耗資源的操作.

下面看get方法就簡單得多了:

?

然后是getEntry()源碼:

?

可以看出, get方法的實現相當簡單, 流程為: key(hashcode)-->hash-->indexFor-->最終索引位置, 找到對應位置table[i], 在查看是否有鏈表, 遍歷鏈表, 通過key的equals方法比對查找對應的記錄.

在getEntry方法中, 定位到數組位置之后遍歷鏈表的時候, e.hash==hash這個判斷是否有必要. 試想如下場景, 如果傳入的key對象重寫了equals方法卻沒有重寫hashCode, 而恰巧此對象定位到這個數組位置, 如果僅僅用equals判斷可能是相等的, 但其hashCode和當前對象不一致, 這種情況, 根據Object的hashCode的約定, 不能返回當前對象, 而應該返回null.

重寫equals方法要同時重寫hashCode方法

為什么重寫equals時也要同時重寫hashCode? 下面舉個小例子:

?

實際輸出結果:

結果: null

現在我們已經對HashMap的原理有了一定了解, 這個結果就不難理解了. 盡管我們在進行get和put操作的時候, 使用的key從邏輯上講是等值的, 但由于沒有重寫hashCode方法, 在進行put操作時: key(hashcod1)-->hash-->indexFor-->最終索引位置; 而通過key去除value時: key(hashcode2)-->hash-->indexFor-->最終索引位置, 由于hashcode1和hashcode2不相等, 最終得出的數組索引頁不一樣而返回null(也可能碰巧定位到了一個數組位置, 但是也會判斷其entry的hash值是否相等, 上面get方法中有提到)

所以, 在重寫equals方法時, 必須注意重寫hashCode方法, 同時還要保證equals判斷相等的兩個對象, 調用hashCode方法要返回同樣的整數值, 而equals判斷不相等的兩個對象, 其hashCode可以相同, 只是會發生哈希沖突, 應該盡量避免.

HashMap的遍歷

?

總結

HashMap底層將key-value當成一個整體處理, 這個整體就是Entry對象. HashMap底層采用一個Entry[]數組來保存所有的key-value對, 當需要存儲一個Entry對象時, 會根據hash算法來決定其在數組中的位置, 再根據equals方法決定其在該數組位置上的鏈表中的存儲位置; 當需要取出一個Entry時, 也會根據hash算法找到其在數組中的存儲位置, 再根據equals方法從該位置上的鏈表中取出該Entry.

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Java集合之HashMap源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。