HashMap原始碼詳解
HashMap簡介
HashMap是Java語言中的一種集合類，它實現了Map介面，用於儲存Key-Value對。它基於雜湊表資料結構，通過計算Key的雜湊值來快速定位Value的位置，從而實現高效的插入、刪除和查詢操作。下面我們對照著JAVA1.8中的HashMap原始碼來分析一下它的內部實現邏輯
基本的結構
在開始分析HashMap的實現邏輯之前，我們需要先了解一下基礎的組成和內部的成員變數都有哪些，分別代表什麼意思。
1、Node<K,V>
首先我們看一下HashMap其中一個子類:Node<K,V>，這個子類用於儲存基本的元素，即Key-Value對、Key的Hash值以及指向下一個節點的Node<K,V>變數。在HashMap內部，由Node<K,V>型別組成的陣列用來儲存所有的元素。 Node<K,V>實現自Map.Entry<K,V>介面，並且實現了介面中規定的多個基本方法:
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
...
}
同時，在Node<K,V>類中，定義了4個成員變數：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable {
....
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
...
}
其中hash是key的hash值，key和value儲存鍵和值，next變數指向連結串列中的下一個元素。
2、HashMap的成員變數
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
table：儲存所有元素的陣列。
entrySet：一個用於遍歷所有資料節點的集合。
size：記錄HashMap中元素的總數量。
modCount：用來判斷在對HashMap資料項進行遍歷時，其中的資料項是否有修改過，如刪除或者新增一項。
threshold：控制擴容時機，當資料項數量大於threshold時進行擴容，新的容量大小是老的兩倍。
loadFactor：預設值0.75，載入因子決定threshold大小，計算公式是threshold=table.length*loadFactor。
我們先大致瞭解一下HashMap成員變數及基礎的Key-Value承載的結構，之後隨著介紹的進度我們再介紹新的型別。下面我們開始正式分析HashMap的邏輯。
初始化方法
HashMap有4個初始化方法，分別是：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// MAXIMUM_CAPACITY = 1 << 30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
第一個初始化方法有兩個引數:initialCapacity和loadFactor，看引數名initialCapacity好像是控制初始化時HashMap容量大小的，實際上它不直接控制大小，而是通過tableSizeFor方法計算出threshold的值，此時threshold為大於等於傳入的initialCapacity的2的次冪最小值。比如傳入3，那麼threshold=\(2^2\)=4，如果傳入9，則threshold=\(2^4\)=16。loadFactor初始化HashMap的成員變數loadFactor。
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
而實際控制容量大小的邏輯在新增第一個元素時確定，現在先放一邊不管，等到介紹新增邏輯時再分析。
第二個建構函式很簡單，直接呼叫了第一個建構函式，傳入initialCapacity和預設的載入因子DEFAULT_LOAD_FACTOR，預設載入因子是0.75。
第三個是無參的建構函式，沒有設定threshold，只設定了預設的載入因子0.75。
第四個建構函式則是使用一個現有的Map物件進行初始化操作，首先設定好預設的載入因子，然後利用putMapEntries方法初始化資料項。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//若傳入的Map為空，則不進行初始化操作
if (s > 0) {
//初始化時，HashMap中還沒有任何元素，所以table為null，此時根據傳入的map大小計算出threshold。
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//非初始化（例如呼叫putAll方法）時，如果傳入的map大小大於threshold，則進行resize擴容操作。
else if (s > threshold)
resize();
//遍歷傳入的map,依次呼叫putVal方法將所有資料加到當前HashMap物件中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
這個方法中所呼叫的resize和putVal方法在其他地方也有呼叫，我們在put方法的實現中再詳細分析，此處只需要知道這個建構函式是通過其他Map物件構造HashMap物件的。
現在已經瞭解了它的基本結構和所有的建構函式，我們用一張圖先直觀的看一下HashMap是什麼樣的。
在這個HashMap物件中，變數table長度等於8，size等於3，threshold等於6。當元素個數大於6時，table將被擴容到16個，threshold也會變為12。
操作
1、put操作
put操作的實現邏輯是呼叫一個內部不可重寫的方法putVal實現，這個方法有5個入參，分別是Key的Hash值、Key、Value、onlyIfAbsent、evict。onlyIfAbsent表示是否覆蓋相同Key的Value值，為true時，只有原來的Value值為null時才會覆蓋，否則不覆蓋。為false時直接覆蓋原值。下來我們直接看原始碼並逐行分析。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/**
* 將物件成員變數table賦值給區域性變數tab並判斷是否為null，如果為null，或者不為null則將長度賦給區域性變數n，並判斷長度是否0。
* 條件成立的話呼叫resize()方法對table進行初始化，並將初始化後的table長度重新賦值給n。
* 注意：除了呼叫第四個構造方法使用其他Map物件進行初始化，其餘三個構造方法構造HashMap物件時，
* table預設是null,所以在第一次往HashMap裡新增資料時就需要初始化table物件。
* resize()方法是HashMap內部的一個通用方法，初始化table、擴容縮容都要用到它，後續還會出現很多次，所以一定要眼熟他。
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 長度與key的hash值做按位元與運算，得到的結果一定小於長度值。然後將得到的值賦給i，
* 並從tab中對應槽位取值並賦值給p。如果取到的是null，則表明當前位置沒有存其他元素，
* 可以直接將新元素新增到tab中。若非null，表示key重複或者Key的hash值計算槽位衝突，則進行其他操作。
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接建立新節點並賦值給tab[i]
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/**
* 若新元素的hash值和剛才取到的p的hash值相同，並且p的key和新元素的key相同，
* 那就表示當前要儲存的新key值是已存在的，不必新增，所以將p賦值給e以備後面操作。
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/**
* 否則就是Key的槽位衝突，HashMap中如果發生Hash值計算後的槽位衝突，有兩種結構進行儲存，第一個是連結串列，第二個是紅黑樹。
* 下面的程式碼會判斷p節點是否為TreeNode型別，如果是則將p轉為TreeNode，並呼叫它的putTreeVal方法，將新元素儲存到樹中。
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
/**
* 如果不是TreeNode型別就是上面剛開始介紹的普通Node，它裡面的next變數可以指向一個Node物件，從而形成連結串列。
* 迴圈遍歷p的next是否為null並且複製給e，如果為null，表示已經迴圈到了連結串列尾部，接下來建立一個Node節點並賦給p.next，
* 即連結串列尾部增加元素。如果不為null表示還沒回圈到連結串列尾部，判斷是否存在重複元素，和上面判斷邏輯相同。如果相同，
* 則在接下來處理e，如果不相同則進入下一輪迴圈判斷，直到連結串列尾部。
* 要注意一點是每新增一個元素到連結串列尾部時，要判斷一下當前連結串列長度是否大於等於TREEIFY_THRESHOLD，是的話會嘗試將當前連結串列轉換為紅黑樹。
* TREEIFY_THRESHOLD是用來判斷連結串列是否需要轉換紅黑樹的閾值，它的值為8，即連結串列長度大於等於8時嘗試轉換為紅黑樹。
*/
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;
}
}
/**
* 經過上面的計算後，區域性變數e如果不為null，則表示當前需要新增的key值以存在，此時就判斷onlyIfAbsent值，
* 若為false，或者已存在的key值對應的value值是null，則直接覆蓋舊值。
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
/**
* 每進行一次操作（新增，刪除等），modCount就加1。每新增一個元素size就加1，
* 然後判斷當前tab中元素數量是否大於threshold，大於則呼叫resize函數進行擴容。
*/
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面put方法總體邏輯概括下來是，Key的hash值是否與陣列中已有元素槽位衝突，若未衝突則直接在對應槽位新增元素。否則需要判斷Key是否一致，不一致，則將新元素加到連結串列尾部或者紅黑樹中，若連結串列長度超過閾值還需要將連結串列轉換為紅黑樹。若一致，則需要判斷是否覆蓋舊值。最後再判斷是否要擴容。
reseize()方法在HashMap內部承擔著非常重要的任務，包括初始化table，控制table的大小，控制擴容閾值threshold和擴容操作等。接下來我們看看resize()的實現邏輯。
final Node<K,V>[] resize() {
/**
* 首先將當前table，capacity，threshold全部暫存到old開頭的變數中。
* 定義新的capacity，threshold變數。定義newCap,newThr變數表示擴容後的table容量和擴容閾值。
*/
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/**
* 1、當前容量如果大於0，新的容量將翻倍，並且當前容量如果大於預設的初始化容量（16），那麼擴容閾值也翻倍，否則擴容閾值使用載入因子進行計算。
* 2、當前容量如果等於0，並且當前擴容閾值大於0，那麼當前擴容閾值就作為新的容量大小，用於初始化table，並且重新計算擴容閾值。（無參建構函式初始化HashMap,並且第一次新增元素時的情況）
* 3、當前容量和擴容閾值都為0時，使用預設的初始化容量（16）並計算擴容閾值（12）
*/
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
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 < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//擴容完畢後，如果舊的table陣列不為null，就將舊的陣列元素遷移到擴容後新的table陣列中。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//不為null說明舊陣列中的這個槽位有元素，將資料賦值給變數e,並開始遷移。
if ((e = oldTab[j]) != null) {
//舊陣列裡這個槽位置為null，等待記憶體回收
oldTab[j] = null;
//next等於null說明當前槽位不存在hash衝突的元素，重新計算槽位後放到新陣列中。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//否則說明存在衝突，並判斷當前槽位中的元素是否是TreeNode型別，如果是的話說明已經轉為紅黑樹了，所以遷移邏輯由紅黑樹邏輯實現。
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
/**
* 不是TreeNode型別，那必然是Node型別了，也就是連結串列，此時就遷移連結串列。但也不是單純的把連結串列原樣遷移過去，而是會進行計算，
* 因為存在這種情況，如果table的長度不長，但是有大量的key發生hash衝突，那麼就會出現某個槽位的連結串列很長有很多資料，
* 但其他槽位基本上沒資料的情況，這時就需要將這個長連結串列拆分成兩個長度相對較短的連結串列，儲存在新table的不同槽位上，增加查詢效率。
*/
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/**
* 利用元素的hash值和舊連結串列長度做按位元與運算，將長連結串列拆分成兩個連結串列，一個連結串列放在和舊table相同位置的新table槽位中，
* 另一個連結串列的槽位距離第一個槽位隔了一箇舊table的長度。
*/
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;
}
上面說過在新增元素的時候，如果某個槽位的連結串列長度超過8個就會將連結串列轉換為紅黑樹，嚴格來說並非只看連結串列長度來決定是否進行轉換，我們來分析一下treeifyBin方法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果當前table陣列長度小於轉換數規定的最小容量即64時，不轉紅黑樹，只進行擴容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
/**
* 進行轉換紅黑樹前的準備工作，將當前槽位的連結串列元素由Node型別轉換為TreeNode型別，然後使用TreeNode型別的prev和next屬性將所有節點連線起來，
* 構成TreeNode型別連結串列。最後才呼叫連結串列頭節點的treeify方法進行紅黑樹轉換。
*/
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
通過上面的treeifyBin方法，我們知道如果陣列長度如果小於64時，即使某個槽位的連結串列長度超過8也不會轉紅黑樹，而是首先將陣列長度擴容到超過64，同時resize方法也會在遷移資料時根據條件將連結串列長度超過原陣列長度的連結串列拆分成兩個連結串列儲存到不同的槽位。同時我們也知道了不光是元素個數超過threshold才會擴容，當某個槽位的連結串列長度超過8並且陣列長度小於64也會觸發陣列擴容。而紅黑樹的原理和具體操作本文不做詳細介紹，有興趣的可以看看網上這篇文章或者自行搜尋。
現在我們已經分析了新增元素的原始碼邏輯了，接下來我們結合幾個例子和圖來進一步加深理解。為了模擬Hash衝突的情況，我們先定義一個類Student，並且重寫它的hashCode和equals方法，hashCode方法只計算name，equals方法計算name和age，確保Student類作為Key儲存到HashMap中時發生Hash衝突，使程式按照我們預想的方向執行。
package com.xxx.demo;
import java.util.Objects;
public class Student {
private Integer age;
private String name;
public Student(Integer age, String name) {
this.age = age;
this.name = name;
}
public Integer getAge() {
return age;
}
public String getName() {
return name;
}
@Override
public boolean equals(Object o) {
if (Objects.isNull(o)) {
return false;
}
if (!(o instanceof Student)) {
return false;
}
Student target = (Student) o;
return age.equals(target.getAge()) && name.equals(target.getName());
}
@Override
public int hashCode() {
return name.hashCode();
}
}
接下來我們建立一個HashMap，並往其中新增若干元素，然後分析一下這個HashMap內部是如何執行的。
public static void main(String[] args){
Map<Student,String> map = new HashMap<>(4);
map.put(new Student(18,"張三"),"value1");
map.put(new Student(18,"李四"),"value2");
map.put(new Student(19,"王五"),"value3");
map.put(new Student(18,"張三"),"value4");
map.put(new Student(19,"張三"),"value5");
map.put(new Student(20,"張三"),"value6");
map.put(new Student(21,"張三"),"value7");
map.put(new Student(22,"張三"),"value8");
map.put(new Student(23,"張三"),"value9");
map.put(new Student(24,"張三"),"value10");
map.put(new Student(25,"張三"),"value11");
map.put(new Student(16,"張麻子"),"value12");
map.put(new Student(26, "張三"), "value13");
}
首先初始化HashMap時傳入了initialCapacity=4，根據我們上面分析的初始化邏輯，此時map物件中的loadFactor=0.75（預設），threshold=4（大於等於4的2的最小次冪值），table=null，size=0，modCount=0。
然後新增第一個Key-Value對後，size=1，modCount=1，table初始化長度為4的Node<Student,String>陣列，threshold變為3（4*0.75）
新增第二個Key-Value對後，size=2,modCount=2。
新增第三個Key-Value對後，size=3，modCount=3。
新增第四個Key-Value對時，因為Student物件和第一次新增的相等，所以預設會覆蓋掉第一次新增的value值，此時size=3，modCount=3。
從第五個開始到第11個Key-Value對，都會發生hash衝突但Key不相同，所以接下來第五個Key-Value元素會在table[2]的位置上搭建連結串列，table[2]上的Node物件的next會指向新的元素。但是當value5被新增進去後，size=4，大於擴容的數量閾值3，此時進行擴容，從table[4]變為table[8]，threshold=6，並對已有的元素重新計算hash值後遷移到新table中。此時元素的分佈如下：
然後陸續新增元素一直到第8個時，再次擴容，table[8]變為table[16]，threshold=12，再重計算hashcode並重排元素在陣列中的位置。
當新增完value13後，table[2]上的元素已經超過TREEIFY_THRESHOLD了，此時就會呼叫treeifyBin方法，嘗試對槽位2上的連結串列進行紅黑樹的轉換，不過現在陣列的長度還不夠64位元，不進行轉換，而是擴容並遷移各個槽位上的資料。當前table長度為32，threshold為24。
value14新增到hashMap後，同樣會再次擴容，table長度到64，threshold為48，並且各個元素重新計算槽位。等到value15被加入到HashMap後，槽位34(新增value14後槽位2的元素重新計算槽位到34)上才會真正轉換為紅黑樹。
紅黑樹相較於連結串列，在查詢方面的時間複雜度為O(log n)，是一種自平衡的二叉查詢樹。而連結串列的查詢操作需要遍歷整個連結串列，時間複雜度為O(n)。因此紅黑樹在查詢方面具有明顯的優勢。
除了put方法外，還有一個putAll方法，此方法實際上是呼叫putMapEntries方法，將一個Map型別引數迴圈新增到HashMap中，putMapEntries方法的邏輯上面我們已經介紹過了。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
2、刪除元素操作
我們首先看一下刪除方法原始碼
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
remove方法內部呼叫removeNode方法，將指定Key的元素刪除，並在刪除成功後返回對應Key的value值。下面是removeNode的原始碼。
/**
* hash:Key的hashcode
* matchValue: 是否匹配value，true的話表示不光匹配Key，還需要匹配value才可以對元素進行移除操作
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//陣列不為空並且對應槽位有值，則將對應槽位元素賦值給p
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
/**
* p的hash值和要刪除的hash值一樣，並且Key本身相等，說明p就是要刪除的值，則將p賦值給node；
* 否則說明存在hash相同，但值不相同的key，即hash衝突。此時判斷p.next是否有值，
* 有值代表連結串列或紅黑樹存在，可以在連結串列或紅黑樹上進一步檢索Key，如果找到了則賦值給node。
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
/**
* 若node有值，並且不匹配value值，或者value值匹配成功，即開始刪除操作。
* 如果node是TreeNode型別，則呼叫紅黑樹的移除操作對元素進行移除。否則是Node型別；
* node==p說明直接在槽位上匹配到元素了，沒有進行hash衝突判斷，所以直接將node的next賦值給槽位，
* node物件在當前方法執行完後就失去了參照，可以被GC。
* 若node不等於p，則說明進行了hash衝突判斷，也是同樣的道理，把node的next複製給p.next，
* node失去參照等待被GC。最後返回匹配到的node即可。
*/
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
上面的刪除方法我們分析了刪除的相關邏輯，當然除了紅黑樹的刪除方法，本文不具體介紹紅黑樹。不過HashMap中有個邏輯還得說一下。在新增元素的方法中，我們知道連結串列轉紅黑樹的條件是：陣列長度大於等於64，連結串列長度超過8，那麼就會被轉換成紅黑樹。如果刪除紅黑樹裡的元素，達到什麼條件時，紅黑樹才退化成連結串列？這塊的邏輯在removeTreeNode方法和split中
final void removeTreeNode(HashMap<K,V> map,Node<K,V>[] tab, boolean movable){
......
//樹根節點為null，或者不為null的情況下，跟節點的右節點是空的，或者左節點是空的，或者右節點的左節點是空的，此時執行退化操作
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
......
}
final void split(HashMap<K,V> map,Node<K,V>[] tab,int index, int bit){
......
//lc\hc為樹上的元素個數，如果元素個數少於等於UNTREEIFY_THRESHOLD時，則將樹退化到連結串列，UNTREEIFY_THRESHOLD的值為6.
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
......
}
在我們分析完新增元素的邏輯和原始碼後，再看上面移除元素的邏輯就很簡單了，其中匹配元素的邏輯在putVal方法中也出現過，老眼熟了。下面我們簡單的圖示一下移除的步驟。
圖1表示陣列和連結串列的原始狀態，圖2表示刪除指定槽位連結串列頭元素後的情況，即tab[index] = node.next這行程式碼。圖3表示hash計算槽位衝突後檢索連結串列，刪除連結串列中某個元素的情況，即p.next = node.next這行程式碼。
HashMap還提供了一個clear方法，用於清除陣列中所有槽位元素，邏輯也非常簡單，即迴圈陣列將所有槽位設定為null，並將size設定為0。
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
3、查詢元素
在介紹查詢元素方法之前，我們先看一下HashMap中集合相關的原始碼和邏輯。HashMap中有三個獲取集合的方法：keySet(),values(),entrySet()，分別返回Key的集合，value的集合及鍵值對集合，三個方法的實現都依賴內部類KeySet,EntrySet,Values。其中KeySet和EntrySet繼承自AbstractSet抽象類，Values繼承自AbstractCollection抽象類，下面我們只分析EntrySet集合的原始碼和邏輯，KeySet和Values集合邏輯類似，有興趣的可以自行檢視。
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
//多數方法的核心實現邏輯都是依賴HashMap中的邏輯實現。
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
/**
* 遍歷方法對所有元素進行遍歷時，會判斷modCount是否有變化，如果有變，說明在遍歷途中，有其他執行緒對元素進行了增加或者刪除，
* 有執行緒安全問題所以丟擲異常。或者在遍歷方法內對集合元素進行了增加或刪除操作。
*/
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
通過上面的forEach方法，我們總算知道了modCount到底是幹嗎用的了，modCount就是為了保證，在任何時候遍歷該鍵值對的集合時確保集合內的值不會變化，導致發生「明明我都遍歷所有元素統一處理了，為什麼還有好幾個元素不生效」這種事情。
接下來我們正式看看查詢相關程式碼邏輯。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
/**
* 根據Key的hash值，計算出所在槽位。並去除對應槽位的值賦值給first變數。
* first變數hash值和方法入參的hash值相等，並且first.key與入參key相等，表示找到節點資料，並返回。
* hash值相等，但first.key與入參key不相等，說明有hash衝突。若first是TreeNode型別說明當前槽位已經是紅黑樹，則使用紅黑樹的方法進行元素查詢。否則是連結串列，遍歷連結串列的next屬性進行查詢
* 將找到的元素返回，未找到則返回null
*/
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
查詢元素的方法邏輯非常清晰和容易理解，getNode方法作為內部的方法被許多方法呼叫，是一個公共的查詢元素方法。
其他方法
除了基本新增元素、刪除元素、查詢元素等方法，還有其他的方法提供給我們，以支援更多的功能。
/**
* 替換Value，查到對應Key的元素節點後，判斷Value值是否等於給定的oldValue，相等則將newValue值替換至元素節點，不相等則不替換。
*/
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
/**
* 查詢到對應Key元素節點後，直接對Value值進行替換，不進行其他邏輯判斷。
*/
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
/**
* 通過給定的Key查詢元素，將查到的元素Key、Value值傳入入參的回撥函數，並通過回撥函數接受一個返回值，
* 若返回值不為null，用返回值替換舊的value值，否則刪除查到的元素。
*/
public V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node<K,V> e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
removeNode(hash, key, null, false, true);
}
return null;
}
除了上面介紹的幾類方法，還有邏輯相似或者作用相似的幾個方法，包括合併方法，替換元素方法，遍歷方法等等，就不一一介紹了，有興趣的話各位可以自己看看。
另外在我們上面分析的眾多的原始碼邏輯中，可以看到出現了很多次的afterNodeAccess,afterNodeInsertion,afterNodeRemoval的方法呼叫，這些方法在HashMap內部沒有實現是個空方法，實際上的實現是在LinkedHashMap類中，而LinkedHashMap則是繼承自HashMap的，所以LinkedHashMap範例在呼叫父類別方法，也就是HashMap中的相關邏輯時，這幾個方法才有實質的作用。
總結
HashMap是建立在Hash演演算法和陣列之上，擁有對陣列進行隨機存取能力的Key-Value結構，同時在處理Hash衝突時使用了不同的策略即連結串列和紅黑樹，得益於此，HashMap擁有比較高的效能，各類開源中介軟體中也有大量的應用，日常程式設計中也會非常頻繁的使用到HashMap。但HashMap是非執行緒安全的，多個執行緒同時對它進行操作會出現執行緒安全問題，如果要在多執行緒環境中使用Key-Value結構的資料結構容器，可以使用ConcurrentHashMap。