HashMap簡介 HashMap是Java語言中的一種集合類，它實現了Map介面，用於存儲Key-Value對。它基於哈希表數據結構，通過計算Key的哈希值來快速定位Value的位置，從而實現高效的插入、刪除和查找操作。下麵我們對照著JAVA1.8中的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。
