為什么學習 HashMap 源碼？

作為一名 java 開發，基本上最常用的數據結構就是 HashMap 和 List，jdk 的 HashMap 設計還是非常值得深入學習的。

無論是在面試還是工作中，知道原理都對會我們有很大的幫助。

本篇的內容較長，建議先收藏，再細細品味。

不同于網上簡單的源碼分析，更多的是實現背后的設計思想。

涉及的內容比較廣泛，從統計學中的泊松分布，到計算機基礎的位運算，經典的紅黑樹、鏈表、數組等數據結構，也談到了 Hash 函數的相關介紹，文末也引入了美團對于 HashMap 的源碼分析，所以整體深度和廣度都比較大。

思維導圖如下：

思維導圖

本文是兩年前整理的，文中不免有疏漏過時的地方，歡迎大家提出寶貴的意見。

之所以這里拿出來，有以下幾個目的：

(1)讓讀者理解 HashMap 的設計思想，知道 rehash 的過程。下一節我們將自己實現一個 HashMap

(2)為什么要自己實現 HashMap?

最近在手寫 redis 框架，都說 redis 是一個特性更加強大的 Map，自然 HashMap 就是入門基礎。Redis 高性能中一個過人之處的設計就是漸進式 rehash，和大家一起實現一個漸進式 rehash 的 map，更能體會和理解作者設計的巧妙。

想把常見的數據結構獨立為一個開源工具，便于后期使用。比如這次手寫 redis，循環鏈表，LRU map 等都是從零開始寫的，不利于復用，還容易有 BUG。

好了，下面就讓我們一起開始 HashMap 的源碼之旅吧~

HashMap 源碼

HashMap 是平時使用到非常多的一個集合類，感覺有必要深入學習一下。

首先嘗試自己閱讀一遍源碼。

java 版本

$?java?-version
java?version?"1.8.0_91"
Java(TM)?SE?Runtime?Environment?(build?1.8.0_91-b14)
Java?HotSpot(TM)?64-Bit?Server?VM?(build?25.91-b14,?mixed?mode)

數據結構

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

對于當前類的官方說明

基于哈希表實現的映射接口。這個實現提供了所有可選的映射操作，并允許空值和空鍵。(HashMap類大致相當于Hashtable，但它是非同步的，并且允許為空。)

這個類不保證映射的順序;特別地，它不能保證順序會隨時間保持不變。

這個實現為基本操作(get和put)提供了恒定時間的性能，假設哈希函數將元素適當地分散在各個桶中。對集合視圖的迭代需要與HashMap實例的“容量”(桶數)及其大小(鍵-值映射數)成比例的時間。因此，如果迭代性能很重要，那么不要將初始容量設置得太高(或者負載系數太低)，這是非常重要的。

HashMap實例有兩個影響其性能的參數: 初始容量和負載因子。

容量是哈希表中的桶數，初始容量只是創建哈希表時的容量。負載因子是在哈希表的容量自動增加之前，哈希表被允許達到的最大容量的度量。當哈希表中的條目數量超過負載因子和當前容量的乘積時，哈希表就會被重新哈希(也就是說，重新構建內部數據結構)，這樣哈希表的桶數大約是原來的兩倍。

一般來說，默認的負載因子(0.75)在時間和空間成本之間提供了很好的權衡。

較高的值減少了空間開銷，但增加了查找成本(反映在HashMap類的大多數操作中，包括get和put)。在設置映射的初始容量時，應該考慮映射中的期望條目數及其負載因子，以最小化重哈希操作的數量。如果初始容量大于條目的最大數量除以負載因子，就不會發生重哈希操作。

如果要將許多映射存儲在HashMap實例中，那么使用足夠大的容量創建映射將使映射存儲的效率更高，而不是讓它根據需要執行自動重哈希以增長表。

注意，使用具有相同hashCode()的多個鍵確實可以降低任何散列表的性能。為了改善影響，當鍵具有可比性時，這個類可以使用鍵之間的比較順序來幫助斷開連接。

注意，這個實現不是同步的。如果多個線程并發地訪問散列映射，并且至少有一個線程在結構上修改了映射，那么它必須在外部同步。(結構修改是添加或刪除一個或多個映射的任何操作;僅更改與實例已經包含的鍵關聯的值并不是結構修改。這通常是通過對自然封裝映射的對象進行同步來完成的。

如果不存在這樣的對象，則應該使用集合“包裝” Collections.synchronizedMap 方法。這最好在創建時完成，以防止意外的對映射的非同步訪問:

Map?m?=?Collections.synchronizedMap(new?HashMap(...));

這個類的所有“集合視圖方法”返回的迭代器都是快速失敗的:如果在創建迭代器之后的任何時候對映射進行結構上的修改，除了通過迭代器自己的remove方法，迭代器將拋出ConcurrentModificationException。因此，在并發修改的情況下，迭代器會快速而干凈地失敗，而不是在未來的不確定時間內冒著任意的、不確定的行為的風險。

注意，迭代器的快速故障行為不能得到保證，因為一般來說，在存在非同步并發修改的情況下，不可能做出任何硬性保證。快速失敗迭代器以最佳的方式拋出ConcurrentModificationException。因此，編寫依賴于此異常的程序來保證其正確性是錯誤的:迭代器的快速故障行為應該僅用于檢測錯誤。

其他基礎信息

這個類是Java集合框架的成員。

@since 1.2

java.util 包下

源碼初探

接口

public?class?HashMap<K,V>?extends?AbstractMap<K,V>implements?Map<K,V>,?Cloneable,?Serializable?{}

當前類實現了三個接口，我們主要關心 Map 接口即可。

繼承了一個抽象類 AbstractMap，這個暫時放在本節后面學習。

常量定義

默認初始化容量

/**
?*?The?default?initial?capacity?-?MUST?be?a?power?of?two.
?*/
static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<4;?//?aka?16

• 為什么不直接使用 16？

看了下 statckoverflow，感覺比較靠譜的解釋是：

為了避免使用魔法數字，使得常量定義本身就具有自我解釋的含義。

強調這個數必須是 2 的冪。

• 為什么要是 2 的冪？

它是這樣設計的，因為它允許使用快速位和操作將每個鍵的哈希代碼包裝到表的容量范圍內，正如您在訪問表的方法中看到的:

final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?first,?e;?int?n;?K?k;if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{?///?
????????...

最大容量

隱式指定較高值時使用的最大容量。

由任何帶有參數的構造函數。

必須是2的冪且小于 1<<30。

/**
*?The?maximum?capacity,?used?if?a?higher?value?is?implicitly?specified
*?by?either?of?the?constructors?with?arguments.
*?MUST?be?a?power?of?two?<=?1<<30.
*/
static?final?int?MAXIMUM_CAPACITY?=?1?<30;

• 為什么是 1 << 30？

當然了 interger 的最大容量為 2^31-1

除此之外，2**31是20億，每個哈希條目需要一個對象作為條目本身，一個對象作為鍵，一個對象作為值。

在為應用程序中的其他內容分配空間之前，最小對象大小通常為24字節左右，因此這將是1440億字節。

可以肯定地說，最大容量限制只是理論上的。

感覺實際內存也沒這么大！

負載因子

當負載因子較大時，去給table數組擴容的可能性就會少，所以相對占用內存較少(空間上較少)，但是每條entry鏈上的元素會相對較多，查詢的時間也會增長(時間上較多)。

反之就是，負載因子較少的時候，給table數組擴容的可能性就高，那么內存空間占用就多，但是entry鏈上的元素就會相對較少，查出的時間也會減少。

所以才有了負載因子是時間和空間上的一種折中的說法。

所以設置負載因子的時候要考慮自己追求的是時間還是空間上的少。

/**
?*?The?load?factor?used?when?none?specified?in?constructor.
?*/
static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;

• 為什么是 0.75，不是 0.8 或者 0.6

其實 hashmap 源碼中有解釋。

Because?TreeNodes?are?about?twice?the?size?of?regular?nodes,?we
use?them?only?when?bins?contain?enough?nodes?to?warrant?use
(see?TREEIFY_THRESHOLD).?And?when?they?become?too?small?(due?to
removal?or?resizing)?they?are?converted?back?to?plain?bins.??In
usages?with?well-distributed?user?hashCodes,?tree?bins?are
rarely?used.??Ideally,?under?random?hashCodes,?the?frequency?of
nodes?in?bins?follows?a?Poisson?distribution
(http://en.wikipedia.org/wiki/Poisson_distribution)?with?a
parameter?of?about?0.5?on?average?for?the?default?resizing
threshold?of?0.75,?although?with?a?large?variance?because?of
resizing?granularity.?Ignoring?variance,?the?expected
occurrences?of?list?size?k?are?(exp(-0.5)?*?pow(0.5,?k)?/
factorial(k)).?The?first?values?are:

0:????0.60653066
1:????0.30326533
2:????0.07581633
3:????0.01263606
4:????0.00157952
5:????0.00015795
6:????0.00001316
7:????0.00000094
8:????0.00000006
more:?less?than?1?in?ten?million

簡單翻譯一下就是在理想情況下,使用隨機哈希碼,節點出現的頻率在hash桶中遵循泊松分布，同時給出了桶中元素個數和概率的對照表。

從上面的表中可以看到當桶中元素到達8個的時候，概率已經變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的鏈表長度超過８個是幾乎不可能的。

Poisson distribution —— 泊松分布

閾值

/**
?*?The?bin?count?threshold?for?using?a?tree?rather?than?list?for?a
?*?bin.??Bins?are?converted?to?trees?when?adding?an?element?to?a
?*?bin?with?at?least?this?many?nodes.?The?value?must?be?greater
?*?than?2?and?should?be?at?least?8?to?mesh?with?assumptions?in
?*?tree?removal?about?conversion?back?to?plain?bins?upon
?*?shrinkage.
?*/
static?final?int?TREEIFY_THRESHOLD?=?8;

/**
?*?The?bin?count?threshold?for?untreeifying?a?(split)?bin?during?a
?*?resize?operation.?Should?be?less?than?TREEIFY_THRESHOLD,?and?at
?*?most?6?to?mesh?with?shrinkage?detection?under?removal.
?*/
static?final?int?UNTREEIFY_THRESHOLD?=?6;

/**
?*?The?smallest?table?capacity?for?which?bins?may?be?treeified.
?*?(Otherwise?the?table?is?resized?if?too?many?nodes?in?a?bin.)
?*?Should?be?at?least?4?*?TREEIFY_THRESHOLD?to?avoid?conflicts
?*?between?resizing?and?treeification?thresholds.
?*/
static?final?int?MIN_TREEIFY_CAPACITY?=?64;

TREEIFY_THRESHOLD

使用紅黑樹而不是列表的bin count閾值。

當向具有至少這么多節點的bin中添加元素時，bin被轉換為樹。這個值必須大于2，并且應該至少為8，以便與樹刪除中關于收縮后轉換回普通容器的假設相匹配。

UNTREEIFY_THRESHOLD

在調整大小操作期間取消(分割)存儲庫的存儲計數閾值。

應小于TREEIFY_THRESHOLD，并最多6個網格與收縮檢測下去除。

MIN_TREEIFY_CAPACITY

最小的表容量，可為容器進行樹狀排列。(否則，如果在一個bin中有太多節點，表將被調整大小。)

至少為 4 * TREEIFY_THRESHOLD，以避免調整大小和樹化閾值之間的沖突。

Node

源碼

• Node.java

基礎 hash 結點定義。

/**
?*?Basic?hash?bin?node,?used?for?most?entries.??(See?below?for
?*?TreeNode?subclass,?and?in?LinkedHashMap?for?its?Entry?subclass.)
?*/
static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;
????final?K?key;
????V?value;
????Node?next;
????Node(int?hash,?K?key,?V?value,?Node?next)?{this.hash?=?hash;this.key?=?key;this.value?=?value;this.next?=?next;
????}public?final?K?getKey()????????{?return?key;?}public?final?V?getValue()??????{?return?value;?}public?final?String?toString()?{?return?key?+?"="?+?value;?}public?final?int?hashCode()?{return?Objects.hashCode(key)?^?Objects.hashCode(value);
????}public?final?V?setValue(V?newValue)?{
????????V?oldValue?=?value;
????????value?=?newValue;return?oldValue;
????}public?final?boolean?equals(Object?o)?{//?快速判斷if?(o?==?this)return?true;//?類型判斷????if?(o?instanceof?Map.Entry)?{
????????????Map.Entry,?>?e?=?(Map.Entry,?>)o;if?(Objects.equals(key,?e.getKey())?&&
????????????????Objects.equals(value,?e.getValue()))return?true;
????????}return?false;
????}
}

個人理解

四個核心元素：

final?int?hash;?//?hash?值
final?K?key;????//?key
V?value;????//?value?值
Node?next;?//?下一個元素結點

hash 值的算法

hash 算法如下。

直接 key/value 的異或(^)。

Objects.hashCode(key)?^?Objects.hashCode(value);

其中 hashCode() 方法如下：

public?static?int?hashCode(Object?o)?{
????return?o?!=?null???o.hashCode()?:?0;
}

最后還是會調用對象本身的 hashCode() 算法。一般我們自己會定義。

靜態工具類

hash

static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}

為什么這么設計？

• jdk8 自帶解釋

計算key.hashCode()，并將(XORs)的高比特位分散到低比特位。

因為表使用的是power-of-two掩蔽，所以只在當前掩碼上方以位為單位變化的哈希總是會發生沖突。

(已知的例子中有一組浮點鍵，它們在小表中保存連續的整數。)

因此，我們應用了一種轉換，將高比特的影響向下傳播。

比特傳播的速度、效用和質量之間存在權衡。

因為許多常見的散列集已經合理分布(所以不要受益于傳播),因為我們用樹來處理大型的碰撞在垃圾箱,我們只是XOR一些改變以最便宜的方式來減少系統lossage,以及將最高位的影響,否則永遠不會因為指數計算中使用的表。

• 知乎的解釋

這段代碼叫擾動函數。

HashMap擴容之前的數組初始大小才16。所以這個散列值是不能直接拿來用的。

用之前還要先做對數組的長度取模運算，得到的余數才能用來訪問數組下標。

putVal 函數源碼

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,boolean?evict)?{
????????Node[]?tab;?Node?p;?int?n,?i;if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????????n?=?(tab?=?resize()).length;if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????????tab[i]?=?newNode(hash,?key,?value,?null);//...????
}

其中這一句 tab[i = (n - 1) & hash])

這一步就是在尋找桶的過程，就是上圖總數組，根據容量取如果容量是16 對hash值取低16位，那么下標范圍就在容量大小范圍內了。

這里也就解釋了為什么 hashmap 的大小需要為 2 的正整數冪，因為這樣(數組長度-1)正好相當于一個“低位掩碼”。

比如大小 16，則 (16-1) = 15 = 00000000 00000000 00001111(二進制);

????10100101?11000100?00100101
&?00000000?00000000?00001111
-------------------------------
????00000000?00000000?00000101????//高位全部歸零，只保留末四位

但是問題是，散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴重。

擾動函數的價值如下：

擾動函數的價值

右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。

而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。

優化哈希的原理介紹

comparable class

• comparableClassFor()

獲取對象 x 的類，如果這個類實現了 class C implements Comparable 接口。

ps: 這個方法很有借鑒意義，可以做簡單的拓展。我們可以獲取任意接口泛型中的類型。

static?Class>?comparableClassFor(Object?x)?{
????if?(x?instanceof?Comparable)?{
????????Class>?c;?Type[]?ts,?as;?Type?t;?ParameterizedType?p;
????????if?((c?=?x.getClass())?==?String.class)?//?bypass?checksreturn?c;
????????if?((ts?=?c.getGenericInterfaces())?!=?null)?{
????????????for?(int?i?=?0;?i?????????????????if?(((t?=?ts[i])?instanceof?ParameterizedType)?&&
????????????????????((p?=?(ParameterizedType)t).getRawType()?==
?????????????????????Comparable.class)?&&
????????????????????(as?=?p.getActualTypeArguments())?!=?null?&&
????????????????????as.length?==?1?&&?as[0]?==?c)?//?type?arg?is?c
????????????????????return?c;
????????????}
????????}
????}
????return?null;
}

compareComparables()

獲取兩個可比較對象的比較結果。

@SuppressWarnings({"rawtypes","unchecked"})?//?for?cast?to?Comparable
static?int?compareComparables(Class>?kc,?Object?k,?Object?x)?{
????return?(x?==?null?||?x.getClass()?!=?kc???0?:
????????????((Comparable)k).compareTo(x));
}

tableSizeFor

獲取 2 的冪

static?final?int?tableSizeFor(int?cap)?{
????int?n?=?cap?-?1;
????n?|=?n?>>>?1;
????n?|=?n?>>>?2;
????n?|=?n?>>>?4;
????n?|=?n?>>>?8;
????n?|=?n?>>>?16;
????return?(n?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
}

• 被調用處

public?HashMap(int?initialCapacity,?float?loadFactor)?{
????//?check...
????this.loadFactor?=?loadFactor;
????this.threshold?=?tableSizeFor(initialCapacity);
}

• 感想

emmm....為什么要這么寫？性能嗎？

簡單分析

當在實例化HashMap實例時，如果給定了initialCapacity，由于HashMap的capacity都是2的冪，因此這個方法用于找到大于等于initialCapacity的最小的2的冪(initialCapacity如果就是2的冪，則返回的還是這個數)。

• 為什么要 -1

int n = cap - 1;

首先，為什么要對cap做減1操作。int n = cap - 1; 這是為了防止，cap已經是2的冪。如果cap已經是2的冪， 又沒有執行這個減1操作，則執行完后面的幾條無符號右移操作之后，返回的capacity將是這個cap的2倍。如果不懂，要看完后面的幾個無符號右移之后再回來看看。

下面看看這幾個無符號右移操作：

如果n這時為0了(經過了cap-1之后)，則經過后面的幾次無符號右移依然是0，最后返回的capacity是1(最后有個n+1的操作)。

這里只討論n不等于0的情況。

• 第一次位運算

n |= n >>> 1;

由于n不等于0，則n的二進制表示中總會有一bit為1，這時考慮最高位的1。

通過無符號右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進制表示中與最高位的1緊鄰的右邊一位也為1，如000011xxxxxx。

其他依次類推

實例

比如 initialCapacity = 10;

表達式???????????????????????二進制
------------------------------------------------------????

initialCapacity?=?10;
int?n?=?9;??????????????????0000?1001
------------------------------------------------------????


n?|=?n?>>>?1;???????????????0000?1001
????????????????????????????0000?0100???(右移1位)?或運算
??????????????????????????=?0000?1101
------------------------------------------------------????

n?|=?n?>>>?2;???????????????0000?1101
????????????????????????????0000?0011???(右移2位)?或運算
??????????????????????????=?0000?1111
------------------------------------------------------????

n?|=?n?>>>?4;???????????????0000?1111
????????????????????????????0000?0000???(右移4位)?或運算
??????????????????????????=?0000?1111
------------------------------------------------------??

n?|=?n?>>>?8;???????????????0000?1111
????????????????????????????0000?0000???(右移8位)?或運算
??????????????????????????=?0000?1111
------------------------------------------------------??

n?|=?n?>>>?16;??????????????0000?1111
????????????????????????????0000?0000???(右移16位)?或運算
??????????????????????????=?0000?1111
------------------------------------------------------??

n = n+1;????????????????????0001 0000????結果：2^4 = 16;??????

put() 解釋

下面的內容出自美團博客 Java 8系列之重新認識HashMap

由于寫的非常好，此處就直接復制過來了。

流程圖解

HashMap的put方法執行過程可以通過下圖來理解，自己有興趣可以去對比源碼更清楚地研究學習。

輸入圖片說明

①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可；

⑥.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

方法源碼

public?V?put(K?key,?V?value)?{
????return?putVal(hash(key),?key,?value,?false,?true);
}
/**
?*?Implements?Map.put?and?related?methods
?*
?*?@param?hash?hash?for?key
?*?@param?key?the?key
?*?@param?value?the?value?to?put
?*?@param?onlyIfAbsent?if?true,?don't?change?existing?value
?*?@param?evict?if?false,?the?table?is?in?creation?mode.
?*?@return?previous?value,?or?null?if?none
?*/
final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);else?{
????????Node?e;?K?k;if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);else?{for?(int?binCount?=?0;?;?++binCount)?{if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);break;
????????????????}if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))break;
????????????????p?=?e;
????????????}
????????}if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????afterNodeAccess(e);return?oldValue;
????????}
????}
????++modCount;if?(++size?>?threshold)
????????resize();
????afterNodeInsertion(evict);return?null;
}

擴容機制

簡介

擴容(resize)就是重新計算容量，向HashMap對象里不停的添加元素，而HashMap對象內部的數組無法裝載更多的元素時，對象就需要擴大數組的長度，以便能裝入更多的元素。

當然Java里的數組是無法自動擴容的，方法是使用一個新的數組代替已有的容量小的數組，就像我們用一個小桶裝水，如果想裝更多的水，就得換大水桶。

JDK7 源碼

我們分析下resize()的源碼，鑒于JDK1.8融入了紅黑樹，較復雜，為了便于理解我們仍然使用JDK1.7的代碼，好理解一些，本質上區別不大，具體區別后文再說。

void?resize(int?newCapacity)?{???//傳入新的容量
????Entry[]?oldTable?=?table;????//引用擴容前的Entry數組
????int?oldCapacity?=?oldTable.length;?????????
????if?(oldCapacity?==?MAXIMUM_CAPACITY)?{??//擴容前的數組大小如果已經達到最大(2^30)了
????????threshold?=?Integer.MAX_VALUE;?//修改閾值為int的最大值(2^31-1)，這樣以后就不會擴容了
????????return;
????}

????Entry[]?newTable?=?new?Entry[newCapacity];??//初始化一個新的Entry數組
????transfer(newTable);?????????????????????????//！！將數據轉移到新的Entry數組里
????table?=?newTable;???????????????????????????//HashMap的table屬性引用新的Entry數組
????threshold?=?(int)(newCapacity?*?loadFactor);//修改閾值
}

這里就是使用一個容量更大的數組來代替已有的容量小的數組，transfer() 方法將原有Entry數組的元素拷貝到新的Entry數組里。

void?transfer(Entry[]?newTable)?{
????Entry[]?src?=?table;???????????????????//src引用了舊的Entry數組
????int?newCapacity?=?newTable.length;
????for?(int?j?=?0;?j?//遍歷舊的Entry數組
????????Entry?e?=?src[j];?????????????//取得舊Entry數組的每個元素if?(e?!=?null)?{
????????????src[j]?=?null;//釋放舊Entry數組的對象引用(for循環后，舊的Entry數組不再引用任何對象)do?{
????????????????Entry?next?=?e.next;int?i?=?indexFor(e.hash,?newCapacity);?//！！重新計算每個元素在數組中的位置
????????????????e.next?=?newTable[i];?//標記[1]
????????????????newTable[i]?=?e;??????//將元素放在數組上
????????????????e?=?next;?????????????//訪問下一個Entry鏈上的元素
????????????}?while?(e?!=?null);
????????}
????}
}

newTable[i]的引用賦給了e.next，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置；

這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發生了hash沖突的話)，這一點和Jdk1.8有區別，下文詳解。

在舊數組中同一條Entry鏈上的元素，通過重新計算索引位置后，有可能被放到了新數組的不同位置上。

案例

下面舉個例子說明下擴容過程。假設了我們的hash算法就是簡單的用key mod 一下表的大小(也就是數組的長度)。

其中的哈希桶數組table的size=2， 所以key = 3、7、5，put順序依次為 5、7、3。

在mod 2以后都沖突在table[1]這里了。

這里假設負載因子 loadFactor=1，即當鍵值對的實際大小size 大于 table的實際大小時進行擴容。

接下來的三個步驟是哈希桶數組 resize成4，然后所有的Node重新rehash的過程。

輸入圖片說明

Jdk8 優化

經過觀測可以發現，我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。

看下圖可以明白這句話的意思，n為table的長度，圖(a)表示擴容前的key1和key2兩種key確定索引位置的示例，

圖(b)表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。

位運算

元素在重新計算hash之后，因為n變為2倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

index

因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：

rehash

這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。

這一塊就是JDK1.8新增的優化點。

有一點注意區別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。

JDK8 源碼

有興趣的同學可以研究下JDK1.8的resize源碼，寫的很贊:

/**
?*?Initializes?or?doubles?table?size.??If?null,?allocates?in
?*?accord?with?initial?capacity?target?held?in?field?threshold.
?*?Otherwise,?because?we?are?using?power-of-two?expansion,?the
?*?elements?from?each?bin?must?either?stay?at?same?index,?or?move
?*?with?a?power?of?two?offset?in?the?new?table.
?*
?*?@return?the?table
?*/
final?Node[]?resize()?{
????Node[]?oldTab?=?table;int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;int?oldThr?=?threshold;int?newCap,?newThr?=?0;if?(oldCap?>?0)?{if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;return?oldTab;
????????}else?if?((newCap?=?oldCap?<1)??????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????newThr?=?oldThr?<1;?//?double?threshold
????}else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????newCap?=?oldThr;else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????}if?(newThr?==?0)?{float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];
????table?=?newTab;if?(oldTab?!=?null)?{for?(int?j?=?0;?j?????????????Node?e;if?((e?=?oldTab[j])?!=?null)?{
????????????????oldTab[j]?=?null;if?(e.next?==?null)
????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;else?if?(e?instanceof?TreeNode)
????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?next;do?{
????????????????????????next?=?e.next;if?((e.hash?&?oldCap)?==?0)?{if?(loTail?==?null)
????????????????????????????????loHead?=?e;else
????????????????????????????????loTail.next?=?e;
????????????????????????????loTail?=?e;
????????????????????????}else?{if?(hiTail?==?null)
????????????????????????????????hiHead?=?e;else
????????????????????????????????hiTail.next?=?e;
????????????????????????????hiTail?=?e;
????????????????????????}
????????????????????}?while?((e?=?next)?!=?null);if?(loTail?!=?null)?{
????????????????????????loTail.next?=?null;
????????????????????????newTab[j]?=?loHead;
????????????????????}if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}return?newTab;
}

小結

如果你已經通讀全文，那么你已經非常厲害了。

其實第一遍沒有徹底理解也沒有關系，知道 HashMap 有一個 reHash 的過程就行，類似于 ArrayList 的 resize。

下一節我們將一起學習下自己手寫實現一個漸進式 rehash 的 HashMap，感興趣的可以關注一下，便于實時接收最新內容。

覺得本文對你有幫助的話，歡迎點贊評論收藏轉發一波。你的鼓勵，是我最大的動力~

不知道你有哪些收獲呢？或者有其他更多的想法，歡迎留言區和我一起討論，期待與你的思考相遇。

總結

以上是生活随笔為你收集整理的hashmap remove 没释放内存_java从零开始手写 redis（13）HashMap 源码原理详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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