HashMap源碼分析(一)(超級詳細(xì))

寧靜致遠(yuǎn)8q9vr1 2019-07-19

展開全文

HashMap1.8和1.8之前的源碼差別很大

1.HashMap簡介

HashMap基于哈希表的Map接口實現(xiàn)，是以key-value存儲形式存在。（除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。)

HashMap 的實現(xiàn)不是同步的，這意味著它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。在 JDK1.8 中，HashMap 是由數(shù)組+鏈表+紅黑樹構(gòu)成，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)變得復(fù)雜了，但是效率也變的更高效。

1.2 HashMap數(shù)據(jù)結(jié)構(gòu)

在 JDK1.8 中，HashMap 是由數(shù)組+鏈表+紅黑樹構(gòu)成，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)變得復(fù)雜了，但是效率也變的更高效。當(dāng)一個值中要存儲到Map的時候會根據(jù)Key的值來計算出他的

hash，通過哈希來確認(rèn)到數(shù)組的位置，如果發(fā)生哈希碰撞就以鏈表的形式存儲在Object源碼分析中解釋過，但是這樣如果鏈表過長來的話，HashMap會把這個鏈表轉(zhuǎn)換成紅黑樹來存儲。

來看一下HashMap的存儲結(jié)構(gòu)

HashMap源碼分析(一)(超級詳細(xì))

但是這樣的話問題來了，HashMap為什么要使用紅黑樹呢，這樣結(jié)構(gòu)的話不是更麻煩了嗎？？

這個問題我也沒有想過，其實很多在看的時候只會在乎紅黑樹的實現(xiàn)而忽略到了為什么要使用的這個問題，我也是在寫本文的時候突發(fā)疑惑。參考了網(wǎng)上的例子，同時也解釋了為什么閥值為8：

因為Map中桶的元素初始化是鏈表保存的，其查找性能是O(n)，而樹結(jié)構(gòu)能將查找性能提升到O(log(n))。當(dāng)鏈表長度很小的時候，即使遍歷，速度也非?？?，但是當(dāng)鏈表長度不斷變長，肯定會對查詢性能有一定的影響，所以才需要轉(zhuǎn)成樹。至于為什么閾值是8，我想，去源碼中找尋答案應(yīng)該是最可靠的途徑。
參考地址：https:///nPFXmXwJ

2.類結(jié)構(gòu)

我們來看一下類結(jié)構(gòu)

HashMap源碼分析(一)(超級詳細(xì))

在閱讀源碼的時候一直有個問題很困惑就是HashMap已經(jīng)繼承了AbstractMap而AbstractMap類實現(xiàn)了Map接口，那為什么HashMap還要在實現(xiàn)Map接口呢？同樣在ArrayList中LinkedList中都是這種結(jié)構(gòu)。

據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述，這樣的寫法是一個失誤。在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時候，他認(rèn)為這樣寫，在某些地方可能是有價值的，直到他意識到錯了。顯然的，JDK的維護者，后來不認(rèn)為這個小小的失誤值得去修改，所以就這樣存在下來了。

HashMap源碼分析(一)(超級詳細(xì))

Cloneable 空接口，表示可以克隆
Serializable 序列化
AbstractMap 提供Map實現(xiàn)接口

3.屬性

初始化容量(必須是二的n次冪)

HashMap源碼分析(一)(超級詳細(xì))

集合最大容量(必須是二的冪)

HashMap源碼分析(一)(超級詳細(xì))

負(fù)載因子，默認(rèn)的0.75

HashMap源碼分析(一)(超級詳細(xì))

當(dāng)鏈表的值超過8則會轉(zhuǎn)紅黑樹(1.8新增)

HashMap源碼分析(一)(超級詳細(xì))

當(dāng)鏈表的值小于6則會從紅黑樹轉(zhuǎn)回鏈表

HashMap源碼分析(一)(超級詳細(xì))

當(dāng)Map里面的數(shù)量超過這個值時，表中的桶才能進行樹形化，否則桶內(nèi)元素太多時會擴容，而不是樹形化為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD

HashMap源碼分析(一)(超級詳細(xì))

table用來初始化(必須是二的n次冪)

HashMap源碼分析(一)(超級詳細(xì))

用來存放緩存

HashMap源碼分析(一)(超級詳細(xì))

HashMap中存儲的數(shù)量

HashMap源碼分析(一)(超級詳細(xì))

用來記錄HashMap的修改次數(shù)

HashMap源碼分析(一)(超級詳細(xì))

用來調(diào)整大小下一個容量的值計算方式為(容量*負(fù)載因子)

HashMap源碼分析(一)(超級詳細(xì))

哈希表的加載因子

HashMap源碼分析(一)(超級詳細(xì))

重點屬性

table在JDK1.8中我們了解到HashMap是由數(shù)組加鏈表加紅黑樹來組成的結(jié)構(gòu)其中table就是HashMap中的數(shù)組
size為HashMap中K-V的實時數(shù)量
loadFactor加載因子，是用來衡量 HashMap 滿的程度，計算HashMap的實時加載因子的方法為：size/capacity，而不是占用桶的數(shù)量去除以capacity。capacity 是桶的數(shù)量，也就是 table 的長度length。
threshold計算公式：capacity * loadFactor。這個值是當(dāng)前已占用數(shù)組長度的最大值。過這個數(shù)目就重新resize(擴容)，擴容后的 HashMap 容量是之前容量的兩倍

4.構(gòu)造方法

開始看構(gòu)造方法。

4.1 HashMap()

構(gòu)造一個空的 HashMap ，默認(rèn)初始容量（16）和默認(rèn)負(fù)載因子（0.75）。

HashMap源碼分析(一)(超級詳細(xì))

4.2 HashMap(int initialCapacity)

構(gòu)造一個空的 HashMap具有指定的初始容量和默認(rèn)負(fù)載因子（0.75）。

HashMap源碼分析(一)(超級詳細(xì))

4.3 HashMap(int initialCapacity, float loadFactor)

構(gòu)造一個空的 HashMap具有指定的初始容量和負(fù)載因子。我們來分析一下。

HashMap源碼分析(一)(超級詳細(xì))

最后調(diào)用了tableSizeFor，來看一下方法實現(xiàn)：

HashMap源碼分析(一)(超級詳細(xì))

5.增加

現(xiàn)在我們開始分析put()方法

HashMap源碼分析(一)(超級詳細(xì))

我們可以看到put調(diào)用的是putVal來進行數(shù)據(jù)插入，但是要注意到key在這里執(zhí)行了一下hash()方法,來看一下Hash方法是如何實現(xiàn)的。

HashMap源碼分析(一)(超級詳細(xì))

從上面可以得知HashMap是支持Key為空的，而HashTable是直接用過Key來獲取HashCode所以key為空會拋異常其實上面就已經(jīng)解釋了為什么HashMap的長度為什么要是2的冪因為HashMap 使用的方法很巧妙，它通過 hash & (table.length -1)來得到該對象的保存位，前面說過 HashMap 底層數(shù)組的長度總是2的n次方，這是HashMap在速度上的優(yōu)化。當(dāng) length 總是2的n次方時，hash & (length-1)運算等價于對 length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。

現(xiàn)在看putVal()方法，看看它到底做了什么。

主要參數(shù)：