硬核！撥開 HashMap 底層真面目
一起讀源碼
在學習 java 過程中，學會看源碼是一門必修課。作爲一個有一些 Python 基礎但沒有學習過相關源碼的 Python 應用者，我將會在這個系列逐步更新 java 源碼的學習。本系列基於 JAVA8，IDE 使用 IDEA。
第二期，將會對在算法中常用的HashSet的添加元素和擴容機制源碼進行學習。HashSet底層調用HashMap實現，在HashSet中，不能有重複元素 / 對象，也不能保證元素有序。
- HashSet 添加元素
HashSet 添加元素的步驟大致如下：
-
先獲取元素的 hash 值（hash 值與 hashCode 相關，但不完全等同）
-
對哈希值進行運算，得到一個索引值。
-
找到存儲數據表 table，看這個索引值對應位置是否有存放的元素。如果沒有，則直接加入；如果有，則調用對象的
equals()方法進行比較，如果相同，就放棄添加，如果不相同，則以鏈表的方式添加。
從添加元素來看，HashSet底層實現了一個HashMap，並通過在 table 上掛載鏈表 / 紅黑樹（滿足樹化的情況下）進行元素的添加。下面我們一起來看看底層的源碼。
示例代碼如下：
package com.geekthomas.set_;
import java.util.HashSet;
import java.util.Set;
/**
* @className: HashSet_
* @Description: TODO
* @version:
* @author: GeekThomas
* @date: 2022/3/19 11:59
*/
public class HashSet_ {
public static void main(String[] args) {
Set hashSet = new HashSet();
hashSet.add("a");
hashSet.add("b");
hashSet.add("a");
System.out.println(hashSet);
}
}我們仍然按照之前的方法，下斷點進行 debug
1.1. 執行 HashMap
在對HashSet初始化時，調用其構造器，實際上就是 new 一個HashMap
1.2. 添加元素
當調用add()方法添加元素時，我們來逐步看看底層發生了什麼。
首先，我們可以看到實現了一個add()方法，這個方法調用了 map 的put()方法
再往裏 step into，可以看到執行了HashMap的 put 方法，key 對應的就是上一步的 e（"a"），而這個 value 其實是上一步的PRESENT（這是HashSet中的一個 Object 對象，用於佔位)，該方法會得到 key 對應的 hash 值
image-20220319134457366
接下來我們使用force step into進入hash(key)方法，看看 hash 值是如何生成的，可以看到 hash 值與我們傳入的 key 的 hashcode 有關，特別地，當 key 爲 null 的時候，分配給其的 hash 值爲 0。
明白了 hash 值如何生成，我們再回到put()方法，看看putVal()這一步到底發生了什麼。這裏代碼很長，我們就拿下代碼逐行分析。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;
}1.2.1. 變量說明
在putVal()方法中，定義了一個Node類型的數組tab，以及節點，而在之後用到的table，則是在HashMap中定義的一個Node類型的數組，如下所示。
1.2.2. 第一次添加元素
在第一次向HashSet中添加元素時，由於此時table爲null，因此會調用resize()方法，對table進行擴容。進入resize()方法，在初始化的時候，oldCap爲 0，因此會直接進入到 else 代碼塊，這時定義了 newCap以及newThr（這個接下來講擴容的時候會用到），可以看到newCap被賦值爲一個常量DEFAULT_INITIAL_CAPACITY，再看看上面的類圖，這個其實在HashMap底層已經有定義了，就是 16。
然後根據這個newCap 創建一個新數組，賦值給table
可以看到，這時的table已經是長度爲 16 的數組了。
再回到putVal方法，此時 n=16，通過計算(n-1)&hash得到對應索引的值，並把這個位置的對象賦值給 p，如果 p 爲空，就說明在表tab（其實就是table）中，對應索引沒有存放元素，那麼就創建一個節點加入到表中。
此時可以看到，在table中索引爲 1 的位置上已經有元素了，元素就是 "a"。
最後，我們可以看到返回null，此時在add()方法中，返回的就是true，表示添加元素成功。
image-20220319144812570
在HashSet中確實已經加入了該元素。
繼續添加元素 "b"，發現對應索引爲 2（這裏重新 debug 了一下，所以 value 對象有變化，但實際上都是一個空的 Object 對象）
image-20220319145333681
1.2.3. 插入重複元素
當我們再插入 "a" 時，會發生什麼呢？
此時再次進入putVal方法，因爲此時 tab 已經不爲空了，所以第一個 if 並不會執行，而且因爲 "a" 對應的哈希值映射後的索引位置上已經有值（"a"），所以第二個 if 也不會進入。我們關注 else 這個代碼塊
在 else 代碼塊中，其實進行了一步判斷，判斷對應索引位置對應的鏈表的第一個元素與要插入的對象是否爲同一對象，需要同時滿足以下條件：
-
兩個對象的 hash 值相同
-
兩個對象的 key 是同一個對象或者 p 指向的 Node 節點的 key 的 equals() 方法和準備加入的 key 比較後相同
如果兩個條件同時滿足，則不能繼續加入。
如果上面的條件不滿足，那麼就判斷 p 是不是一棵紅黑樹，如果是紅黑樹，那麼就調用紅黑樹的putTreeVal進行添加。
如果均不滿足，則需要以鏈表的方式進行添加（這裏需要判斷鏈表的長度有沒有超過限度（其實就是 8），具體在下面的擴容中會詳細描述），對鏈表進行 for 循環，逐個比較鏈表中有無相同元素，如果準備加入的元素在鏈表中沒有相同元素，則加入到鏈表的最後，否則只要鏈表中有相同元素，就會跳出循環。
最後判斷 e 對象是否爲空，當加入相同對象時，e 肯定不爲空，此時返回對應的 value（其實就是上文的PRESENT）
在add()方法中，此時返回false。這樣就實現了HashSet不能有重複元素 / 對象的特性了。
- HashSet 擴容和轉成紅黑樹機制
2.1. table 數組擴容
我們用一段簡單代碼來研究
package com.geekthomas.set_;
import java.util.HashSet;
import java.util.Set;
/**
* @className: HashSet_
* @Description: TODO
* @version:
* @author: GeekThomas
* @date: 2022/3/19 11:59
*/
public class HashSet_ {
public static void main(String[] args) {
Set hashSet = new HashSet();
for (int i = 1; i < 100; i++) {
hashSet.add(i);
}
}
}仍然是下斷點 debug，在初始化時，table 爲空
當添加元素時，會自動擴容到 16
除此之外，我們還可以看到很多屬性信息，比如threshold=12，loadFactor=0.75，這其實就是我們在添加元素的時候進行的判斷，是否超出閾值。
接下來我們直接跳到加入十二個元素
再往後加，因爲數組已經達到臨界值，這時就會進行擴容，數組長度由 12->32，如下所示：
與此同時，我們可以看到數組的臨界值由 12->24
我們繼續添加元素，當加到第 25 個元素時，數組繼續擴容到 64
以此類推。
在源碼中，實際上就是實現了resize()方法，在第一次添加時，oldCap = table = null，此時newCap = DEFAULT_INITIAL_CAPACITY = 16，newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) = (int) (0.75 * 16) = 12。當到達臨界值時，newCap,newThr均會翻倍。
2.2. 紅黑樹
要觸發樹化機制，我們這裏就需要在添加元素的時候，使每個元素的 hash 值相同，這樣才能掛在 table 數組的同一索引位置。示例代碼如下：
package com.geekthomas.set_;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
* @className: HashSet_
* @Description: TODO
* @version:
* @author: GeekThomas
* @date: 2022/3/19 11:59
*/
public class HashSet_ {
public static void main(String[] args) {
Set hashSet = new HashSet();
for (int i = 1; i < 12; i++) {
hashSet.add(new A(i));
}
System.out.println("hashset=" + hashSet);
}
}
class A {
private int n;
public A(int n) {
this.n = n;
}
@Override
public int hashCode() {
return 100;
}
@Override
public String toString() {
return "A{" +
"n=" + n +
'}';
}
}繼續斷點調試，發現第一個元素插入到表中索引爲 4 的位置處。
我們再來看看下一個元素。沒有問題，第二個元素加入到索引爲 4 的鏈表中了
我們繼續往後加，一直到加入 8 個元素。
繼續添加，神奇的事情發生了，此時並沒有樹化，而是數組擴容到了 32。
繼續往下走，數組繼續擴容到 64，還沒有樹化。
再往下走，數組不會繼續擴容，而是樹化，從圖中可以看出，在表中索引爲 36 的位置處，掛載了一棵樹（此時是 TreeNode 節點而不再是 Node 節點）
在源碼中也能夠看到，當表的長度小於MIN_TREEIFY_CAPACITY=64時，會繼續擴容。
接下來還有一個問題，臨界值是否包括其他鏈表上的元素個數呢？
我們先通過實際代碼驗證
package com.geekthomas.set_;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
* @className: HashSet_
* @Description: TODO
* @version:
* @author: GeekThomas
* @date: 2022/3/19 11:59
*/
public class HashSet_ {
public static void main(String[] args) {
Set hashSet = new HashSet();
for (int i = 1; i < 8; i++) {//在table的某一條鏈表上添加了7個A對象
hashSet.add(new A(i));
}
for (int i = 1; i < 8; i++) {//在table的另一條鏈表上添加了7個B對象
hashSet.add(new B(i));
}
System.out.println("hashset=" + hashSet);
}
}
class A {
private int n;
public A(int n) {
this.n = n;
}
@Override
public int hashCode() {
return 100;
}
@Override
public String toString() {
return "A{" +
"n=" + n +
'}';
}
}
class B {
private int n;
public B(int n) {
this.n = n;
}
@Override
public int hashCode() {
return 200;
}
@Override
public String toString() {
return "B{" +
"n=" + n +
'}';
}
}我們這裏通過重寫hashCode方法，確保兩次添加的元素在不同鏈表上。接下來就是 debug 時間。第一次添加後，在table數組的索引爲 4 的位置上加入了 7 個元素。
繼續添加 B 對象，在索引爲 8 的位置處添加對象。
當加入 6 個 B 對象，也就是當前共加入 13 個對象時，數組擴容成 32。也就是說，臨界值是包括其他鏈表上的元素個數的。
image-20220319164915282
在源碼中也有所體現：在執行putVal()方法時，每次執行都會導致 size+1，因此每次插入一個新對象，就會導致 size 的修改。也就是說，臨界值是包括table數組中所有鏈表上的元素的。
- 一個簡單應用
package com.geekthomas.set_;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
* @className: HashSet_
* @Description: TODO
* @version:
* @author: GeekThomas
* @date: 2022/3/19 11:59
*/
public class HashSet_ {
/*
* @title main
* @description 定義一個Employee類，該類包含name, age屬性
* 創建三個Employee，放入到HashSet中，當age和name相同時，則認爲是相同員工，不能添加
* @author GeekThomas
* @param: args
* @updateTime 2022/3/19 16:53
* @throws
*/
public static void main(String[] args) {
Set hashSet = new HashSet();
hashSet.add(new Employee(24, "jack"));
hashSet.add(new Employee(22, "rose"));
hashSet.add(new Employee(24, "jack"));
System.out.println("hashSet=" + hashSet);
}
}
class Employee {
private int age;
private String name;
public Employee(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return age == employee.age &&
Objects.equals(name, employee.name);
}
@Override
public int hashCode() {
return Objects.hash(age, name);
}
@Override
public String toString() {
return "Employee{" +
"age=" + age +
", + name + '\'' +
'}';
}
}- 總結
我們再來梳理一下，
①在HashSet初始化時，會調用HashMap()底層實現，先初始化一個空table，在第一次添加元素時，會將table擴容到 16（這與 ArrayList 調用無參構造器擴容到 10 需要區分），然後進行添加操作，臨界值（threshold）爲 16 * 加載因子（loadFactor）0.75=12。
②在HashMap中，因爲需要傳入 key-value，因此在HashSet中添加元素時，會分配給元素一個 value（final static Object）。HashMap會統計計算對象的 hash 值來決定元素在表中的索引，並且進行判斷，如果表中對應索引處沒有值，那麼就將根據傳入的元素創建新的 Node 節點，插入到對應的索引位置。
③繼續添加元素，仍然會計算該元素對應的 hash 值，如果在表中對應索引處沒有元素存在，則加入；如果對應索引處有元素 p 存在，則需要分情況：
-
插入的對象與 p 相同（hash 值相同，或者說調用 equals 方法後一致），那麼就不再加入
-
插入的對象與 p 不同，而且 p 此時是一顆紅黑樹。這時候就需要將該對象加入到 p 的樹中
-
插入的對象既不與 p 相同，且 p 不是紅黑樹，那麼就以鏈表的方式添加到 p 所在索引位置的鏈表中。在添加前，需要判斷在鏈表中有無相同對象，如果鏈表中無相同對象，則將該對象加入到鏈表最後，否則只要有一個對象相同，都不執行添加操作。
④如果table數組長度到達臨界值 12，那麼就會擴容到 16 * 2=32，新的臨界值就是 24，以此類推
⑤在 JAVA8 中，如果一條鏈表的元素個數到達TREEIFY_THRESHOLD（默認是 8），並且 table 的大小大於等於MIN_TREEIFY_CAPACITY（默認是 64），就會進行樹化（紅黑樹），否則仍然採用數組擴容機制。
更多詳細內容可以參考 B 站韓順平 JAVA 系列課程 [1]
多肉羅羅 有溫度，有想法，有趣
參考資料
[1]
B 站韓順平 JAVA 系列課程: https://www.bilibili.com/video/BV1fh411y7R8?p=522
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jF2jb7VrY1f21ZIP3ty4VQ