死磕 java集合之HashMap源碼分析

簡介

HashMap採用key/value存儲結構，每個key對應唯一的value，查詢和修改的速度都很快，能達到O(1)的平均時間複雜度。它是非線程安全的，且不保證元素存儲的順序；

繼承體系

HashMap實現了Cloneable，可以被克隆。

HashMap實現了Serializable，可以被序列化。

HashMap繼承自AbstractMap，實現了Map接口，具有Map的所有功能。

存儲結構

在Java中，HashMap的實現採用了（數組 + 鏈表 + 紅黑樹）的複雜結構，數組的一個元素又稱作桶。

在添加元素時，會根據hash值算出元素在數組中的位置，如果該位置沒有元素，則直接把元素放置在此處，如果該位置有元素了，則把元素以鏈表的形式放置在鏈表的尾部。

當一個鏈表的元素個數達到一定的數量（且數組的長度達到一定的長度）後，則把鏈表轉化為紅黑樹，從而提高效率。

數組的查詢效率為O(1)，鏈表的查詢效率是O(k)，紅黑樹的查詢效率是O(log k)，k為桶中的元素個數，所以當元素數量非常多的時候，轉化為紅黑樹能極大地提高效率。

源碼解析

屬性

/**
 * 默認的初始容量為16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
 * 最大的容量為2的30次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
 * 默認的裝載因子 

 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 * 當一個桶中的元素個數大於等於8時進行樹化
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 當一個桶中的元素個數小於等於6時把樹轉化為鏈表
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 當桶的個數達到64的時候才進行樹化
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 * 數組，又叫作桶（bucket）
 */
transient Node[] table;
/**
 * 作為entrySet()的緩存
 */
transient Set<map.entry>> entrySet;
/**
 * 元素的數量
 */
transient int size;
/**
 * 修改次數，用於在迭代的時候執行快速失敗策略
 */
transient int modCount;
/**
 * 當桶的使用數量達到多少時進行擴容，threshold = capacity * loadFactor
 */
int threshold;
/**
 * 裝載因子
 */
final float loadFactor; 

/<map.entry>

（1）容量

容量為數組的長度，亦即桶的個數，默認為16，最大為2的30次方，當容量達到64時才可以樹化。

（2）裝載因子

裝載因子用來計算容量達到多少時才進行擴容，默認裝載因子為0.75。

（3）樹化

樹化，當容量達到64且鏈表的長度達到8時進行樹化，當鏈表的長度小於6時反樹化。

Node內部類

Node是一個典型的單鏈表節點，其中，hash用來存儲key計算得來的hash值。

static class Node implements Map.Entry {
 final int hash;
 final K key;
 V value;
 Node next;
}

TreeNode內部類

這是一個神奇的類，它繼承自LinkedHashMap中的Entry類，關於LInkedHashMap.Entry這個類我們後面再講。

TreeNode是一個典型的樹型節點，其中，prev是鏈表中的節點，用於在刪除元素的時候可以快速找到它的前置節點。

// 位於HashMap中
static final class TreeNode extends LinkedHashMap.Entry {
 TreeNode parent; // red-black tree links
 TreeNode left;
 TreeNode right;
 TreeNode prev; // needed to unlink next upon deletion
 boolean red;
}
// 位於LinkedHashMap中，典型的雙向鏈表節點
static class Entry extends HashMap.Node {
 Entry before, after;
 Entry(int hash, K key, V value, Node next) {
 super(hash, key, value, next);
 }
}

HashMap()構造方法

空參構造方法，全部使用默認值。

public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap(int initialCapacity)構造方法

調用HashMap(int initialCapacity, float loadFactor)構造方法，傳入默認裝載因子。

public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity)構造方法

判斷傳入的初始容量和裝載因子是否合法，並計算擴容門檻，擴容門檻為傳入的初始容量往上取最近的2的n次方。

public HashMap(int initialCapacity, float loadFactor) {
 // 檢查傳入的初始容量是否合法
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: " +
 initialCapacity);
 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);
}
static final int tableSizeFor(int cap) {
 // 擴容門檻為傳入的初始容量往上取最近的2的n次方
 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;
}

put(K key, V value)方法

添加元素的入口。

public V put(K key, V value) {
 // 調用hash(key)計算出key的hash值
 return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
 int h;
 // 如果key為null，則hash值為0，否則調用key的hashCode()方法
 // 並讓高16位與整個hash異或，這樣做是為了使計算出的hash更分散
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node[] tab;
 Node p;
 int n, i;
 // 如果桶的數量為0，則初始化
 if ((tab = table) == null || (n = tab.length) == 0)
 // 調用resize()初始化
 n = (tab = resize()).length;
 // (n - 1) & hash 計算元素在哪個桶中
 // 如果這個桶中還沒有元素，則把這個元素放在桶中的第一個位置
 if ((p = tab[i = (n - 1) & hash]) == null)
 // 新建一個節點放在桶中
 tab[i] = newNode(hash, key, value, null); 

 else {
 // 如果桶中已經有元素存在了
 Node e;
 K k;
 // 如果桶中第一個元素的key與待插入元素的key相同，保存到e中用於後續修改value值
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 else if (p instanceof TreeNode)
 // 如果第一個元素是樹節點，則調用樹節點的putTreeVal插入元素
 e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);
 else {
 // 遍歷這個桶對應的鏈表，binCount用於存儲鏈表中元素的個數
 for (int binCount = 0; ; ++binCount) {
 // 如果鏈表遍歷完了都沒有找到相同key的元素，說明該key對應的元素不存在，則在鏈表最後插入一個新節點
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 // 如果插入新節點後鏈表長度大於8，則判斷是否需要樹化，因為第一個元素沒有加到binCount中，所以這裡-1
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 // 如果待插入的key在鏈表中找到了，則退出循環
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 } 

 // 如果找到了對應key的元素
 if (e != null) { // existing mapping for key
 // 記錄下舊值
 V oldValue = e.value;
 // 判斷是否需要替換舊值
 if (!onlyIfAbsent || oldValue == null)
 // 替換舊值為新值
 e.value = value;
 // 在節點被訪問後做點什麼事，在LinkedHashMap中用到
 afterNodeAccess(e);
 // 返回舊值
 return oldValue;
 }
 }
 // 到這裡了說明沒有找到元素
 // 修改次數加1
 ++modCount;
 // 元素數量加1，判斷是否需要擴容
 if (++size > threshold)
 // 擴容
 resize();
 // 在節點插入後做點什麼事，在LinkedHashMap中用到
 afterNodeInsertion(evict);
 // 沒找到元素返回null
 return null;
}

（1）計算key的hash值；

（2）如果桶（數組）數量為0，則初始化桶；

（3）如果key所在的桶沒有元素，則直接插入；

（4）如果key所在的桶中的第一個元素的key與待插入的key相同，說明找到了元素，轉後續流程（9）處理；

（5）如果第一個元素是樹節點，則調用樹節點的putTreeVal()尋找元素或插入樹節點；

（6）如果不是以上三種情況，則遍歷桶對應的鏈表查找key是否存在於鏈表中；

（7）如果找到了對應key的元素，則轉後續流程（9）處理；

（8）如果沒找到對應key的元素，則在鏈表最後插入一個新節點並判斷是否需要樹化；

（9）如果找到了對應key的元素，則判斷是否需要替換舊值，並直接返回舊值；

（10）如果插入了元素，則數量加1並判斷是否需要擴容；

resize()方法

擴容方法。

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) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
 // 如果舊容量的兩倍小於最大容量並且舊容量大於默認初始容量（16），則容量擴大為兩部，擴容門檻也擴大為兩倍
 newThr = oldThr << 1; // double threshold
 } else if (oldThr > 0) // initial capacity was placed in threshold
 // 使用非默認構造方法創建的map，第一次插入元素會走到這裡
 // 如果舊容量為0且舊擴容門檻大於0，則把新容量賦值為舊門檻
 newCap = oldThr;
 else { // zero initial threshold signifies using defaults
 // 調用默認構造方法創建的map，第一次插入元素會走到這裡
 // 如果舊容量舊擴容門檻都是0，說明還未初始化過，則初始化容量為默認容量，擴容門檻為默認容量*默認裝載因子
 newCap = DEFAULT_INITIAL_CAPACITY;
 newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 if (newThr == 0) {
 // 如果新擴容門檻為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[] newTab = (Node[]) new Node[newCap];
 // 把桶賦值為新數組
 table = newTab;
 // 如果舊數組不為空，則搬移元素
 if (oldTab != null) {
 // 遍歷舊數組
 for (int j = 0; j < oldCap; ++j) {
 Node e;
 // 如果桶中第一個元素不為空，賦值給e
 if ((e = oldTab[j]) != null) {
 // 清空舊桶，便於GC回收 
 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
 // 如果這個鏈表不止一個元素且不是一顆樹
 // 則分化成兩個鏈表插入到新的桶中去
 // 比如，假如原來容量為4，3、7、11、15這四個元素都在三號桶中 

 // 現在擴容到8，則3和11還是在三號桶，7和15要搬移到七號桶中去
 // 也就是分化成了兩個鏈表
 Node loHead = null, loTail = null;
 Node hiHead = null, hiTail = null;
 Node next;
 do {
 next = e.next;
 // (e.hash & oldCap) == 0的元素放在低位鏈表中
 // 比如，3 & 4 == 0
 if ((e.hash & oldCap) == 0) {
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 } else {
 // (e.hash & oldCap) != 0的元素放在高位鏈表中
 // 比如，7 & 4 != 0
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
 // 遍歷完成分化成兩個鏈表了
 // 低位鏈表在新桶中的位置與舊桶一樣（即3和11還在三號桶中）
 if (loTail != null) {
 loTail.next = null;
 newTab[j] = loHead;
 }
 // 高位鏈表在新桶中的位置正好是原來的位置加上舊容量（即7和15搬移到七號桶了）
 if (hiTail != null) {
 hiTail.next = null; 

 newTab[j + oldCap] = hiHead;
 }
 }
 }
 }
 }
 return newTab;
}

（1）如果使用是默認構造方法，則第一次插入元素時初始化為默認值，容量為16，擴容門檻為12；

（2）如果使用的是非默認構造方法，則第一次插入元素時初始化容量等於擴容門檻，擴容門檻在構造方法裡等於傳入容量向上最近的2的n次方；

（3）如果舊容量大於0，則新容量等於舊容量的2倍，但不超過最大容量2的30次方，新擴容門檻為舊擴容門檻的2倍；

（4）創建一個新容量的桶；

（5）搬移元素，原鏈表分化成兩個鏈表，低位鏈表存儲在原來桶的位置，高位鏈表搬移到原來桶的位置加舊容量的位置；

TreeNode.putTreeVal(...)方法

插入元素到紅黑樹中的方法。

final TreeNode putTreeVal(HashMap map, Node[] tab,
 int h, K k, V v) {
 Class> kc = null;
 // 標記是否找到這個key的節點
 boolean searched = false;
 // 找到樹的根節點
 TreeNode root = (parent != null) ? root() : this;
 // 從樹的根節點開始遍歷
 for (TreeNode p = root; ; ) {
 // dir=direction，標記是在左邊還是右邊
 // ph=p.hash，當前節點的hash值
 int dir, ph;
 // pk=p.key，當前節點的key值
 K pk;
 if ((ph = p.hash) > h) {
 // 當前hash比目標hash大，說明在左邊
 dir = -1;
 }
 else if (ph < h)
 // 當前hash比目標hash小，說明在右邊
 dir = 1;
 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
 // 兩者hash相同且key相等，說明找到了節點，直接返回該節點
 // 回到putVal()中判斷是否需要修改其value值
 return p;
 else if ((kc == null &&
 // 如果k是Comparable的子類則返回其真實的類，否則返回null 

 (kc = comparableClassFor(k)) == null) ||
 // 如果k和pk不是同樣的類型則返回0，否則返回兩者比較的結果
 (dir = compareComparables(kc, k, pk)) == 0) {
 // 這個條件表示兩者hash相同但是其中一個不是Comparable類型或者兩者類型不同
 // 比如key是Object類型，這時可以傳String也可以傳Integer，兩者hash值可能相同
 // 在紅黑樹中把同樣hash值的元素存儲在同一顆子樹，這裡相當於找到了這顆子樹的頂點
 // 從這個頂點分別遍歷其左右子樹去尋找有沒有跟待插入的key相同的元素
 if (!searched) {
 TreeNode q, ch;
 searched = true;
 // 遍歷左右子樹找到了直接返回
 if (((ch = p.left) != null &&
 (q = ch.find(h, k, kc)) != null) ||
 ((ch = p.right) != null &&
 (q = ch.find(h, k, kc)) != null))
 return q;
 }
 // 如果兩者類型相同，再根據它們的內存地址計算hash值進行比較
 dir = tieBreakOrder(k, pk);
 }
 TreeNode xp = p;
 if ((p = (dir <= 0) ? p.left : p.right) == null) {
 // 如果最後確實沒找到對應key的元素，則新建一個節點
 Node xpn = xp.next;
 TreeNode x = map.newTreeNode(h, k, v, xpn);
 if (dir <= 0) 

 xp.left = x;
 else
 xp.right = x;
 xp.next = x;
 x.parent = x.prev = xp;
 if (xpn != null)
 ((TreeNode) xpn).prev = x;
 // 插入樹節點後平衡
 // 把root節點移動到鏈表的第一個節點
 moveRootToFront(tab, balanceInsertion(root, x));
 return null;
 }
 }
}

（1）尋找根節點；

（2）從根節點開始查找；

（3）比較hash值及key值，如果都相同，直接返回，在putVal()方法中決定是否要替換value值；

（4）根據hash值及key值確定在樹的左子樹還是右子樹查找，找到了直接返回；

（5）如果最後沒有找到則在樹的相應位置插入元素，並做平衡；

treeifyBin()方法

如果插入元素後鏈表的長度大於等於8則判斷是否需要樹化。

final void treeifyBin(Node[] tab, int hash) {
 int n, index;
 Node e;
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 // 如果桶數量小於64，直接擴容而不用樹化
 // 因為擴容之後，鏈表會分化成兩個鏈表，達到減少元素的作用
 // 當然也不一定，比如容量為4，裡面存的全是除以4餘數等於3的元素
 // 這樣即使擴容也無法減少鏈表的長度
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode hd = null, tl = null;
 // 把所有節點換成樹節點
 do {
 TreeNode 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);
 }
}
 

TreeNode.treeify()方法

真正樹化的方法。

final void treeify(Node[] tab) {
 TreeNode root = null;
 for (TreeNode x = this, next; x != null; x = next) {
 next = (TreeNode) x.next;
 x.left = x.right = null;
 // 第一個元素作為根節點且為黑節點，其它元素依次插入到樹中再做平衡
 if (root == null) {
 x.parent = null;
 x.red = false;
 root = x;
 } else {
 K k = x.key;
 int h = x.hash;
 Class> kc = null;
 // 從根節點查找元素插入的位置
 for (TreeNode p = root; ; ) {
 int dir, ph;
 K pk = p.key;
 if ((ph = p.hash) > h)
 dir = -1;
 else if (ph < h)
 dir = 1;
 else if ((kc == null &&
 (kc = comparableClassFor(k)) == null) ||
 (dir = compareComparables(kc, k, pk)) == 0)
 dir = tieBreakOrder(k, pk);
 // 如果最後沒找到元素，則插入
 TreeNode xp = p;
 if ((p = (dir <= 0) ? p.left : p.right) == null) { 

 x.parent = xp;
 if (dir <= 0)
 xp.left = x;
 else
 xp.right = x;
 // 插入後平衡，默認插入的是紅節點，在balanceInsertion()方法裡
 root = balanceInsertion(root, x);
 break;
 }
 }
 }
 }
 // 把根節點移動到鏈表的頭節點，因為經過平衡之後原來的第一個元素不一定是根節點了
 moveRootToFront(tab, root);
}

（1）從鏈表的第一個元素開始遍歷；

（2）將第一個元素作為根節點；

（3）其它元素依次插入到紅黑樹中，再做平衡；

（4）將根節點移到鏈表第一元素的位置（因為平衡的時候根節點會改變）；

get(Object key)方法

public V get(Object key) {
 Node e; 

 return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
 Node[] tab;
 Node first, e;
 int n;
 K k;
 // 如果桶的數量大於0並且待查找的key所在的桶的第一個元素不為空
 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) 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;
}

（1）計算key的hash值；

（2）找到key所在的桶及其第一個元素；

（3）如果第一個元素的key等於待查找的key，直接返回；

（4）如果第一個元素是樹節點就按樹的方式來查找，否則按鏈表方式查找；

TreeNode.getTreeNode(int h, Object k)方法

final TreeNode getTreeNode(int h, Object k) {
 // 從樹的根節點開始查找
 return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode find(int h, Object k, Class> kc) {
 TreeNode p = this;
 do {
 int ph, dir;
 K pk;
 TreeNode pl = p.left, pr = p.right, q;
 if ((ph = p.hash) > h)
 // 左子樹
 p = pl;
 else if (ph < h)
 // 右子樹
 p = pr;
 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
 // 找到了直接返回
 return p;
 else if (pl == null)
 // hash相同但key不同，左子樹為空查右子樹
 p = pr;
 else if (pr == null)
 // 右子樹為空查左子樹
 p = pl;
 else if ((kc != null || 

 (kc = comparableClassFor(k)) != null) &&
 (dir = compareComparables(kc, k, pk)) != 0)
 // 通過compare方法比較key值的大小決定使用左子樹還是右子樹
 p = (dir < 0) ? pl : pr;
 else if ((q = pr.find(h, k, kc)) != null)
 // 如果以上條件都不通過，則嘗試在右子樹查找
 return q;
 else
 // 都沒找到就在左子樹查找
 p = pl;
 } while (p != null);
 return null;
}

經典二叉查找樹的查找過程，先根據hash值比較，再根據key值比較決定是查左子樹還是右子樹。

remove(Object key)方法

public V remove(Object key) {
 Node e;
 return (e = removeNode(hash(key), key, null, false, true)) == null ?
 null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
 boolean matchValue, boolean movable) {
 Node[] tab;
 Node p;
 int n, index;
 // 如果桶的數量大於0且待刪除的元素所在的桶的第一個元素不為空 

 if ((tab = table) != null && (n = tab.length) > 0 &&
 (p = tab[index = (n - 1) & hash]) != null) {
 Node node = null, e;
 K k;
 V v;
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 // 如果第一個元素正好就是要找的元素，賦值給node變量後續刪除使用
 node = p;
 else if ((e = p.next) != null) {
 if (p instanceof TreeNode)
 // 如果第一個元素是樹節點，則以樹的方式查找節點
 node = ((TreeNode) 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);
 }
 }
 // 如果找到了元素，則看參數是否需要匹配value值，如果不需要匹配直接刪除，如果需要匹配則看value值是否與傳入的value相等
 if (node != null && (!matchValue || (v = node.value) == value ||
 (value != null && value.equals(v)))) {
 if (node instanceof TreeNode)
 // 如果是樹節點，調用樹的刪除方法（以node調用的，是刪除自己）
 ((TreeNode) node).removeTreeNode(this, tab, movable);
 else if (node == p)
 // 如果待刪除的元素是第一個元素，則把第二個元素移到第一的位置 

 tab[index] = node.next;
 else
 // 否則刪除node節點
 p.next = node.next;
 ++modCount;
 --size;
 // 刪除節點後置處理
 afterNodeRemoval(node);
 return node;
 }
 }
 return null;
}

（1）先查找元素所在的節點；

（2）如果找到的節點是樹節點，則按樹的移除節點處理；

（3）如果找到的節點是桶中的第一個節點，則把第二個節點移到第一的位置；

（4）否則按鏈表刪除節點處理；

（5）修改size，調用移除節點後置處理等；

TreeNode.removeTreeNode(...)方法

final void removeTreeNode(HashMap map, Node[] tab,
 boolean movable) {
 int n; 

 // 如果桶的數量為0直接返回
 if (tab == null || (n = tab.length) == 0)
 return;
 // 節點在桶中的索引
 int index = (n - 1) & hash;
 // 第一個節點，根節點，根左子節點
 TreeNode first = (TreeNode) tab[index], root = first, rl;
 // 後繼節點，前置節點
 TreeNode succ = (TreeNode) next, pred = prev;
 if (pred == null)
 // 如果前置節點為空，說明當前節點是根節點，則把後繼節點賦值到第一個節點的位置，相當於刪除了當前節點
 tab[index] = first = succ;
 else
 // 否則把前置節點的下個節點設置為當前節點的後繼節點，相當於刪除了當前節點
 pred.next = succ;
 // 如果後繼節點不為空，則讓後繼節點的前置節點指向當前節點的前置節點，相當於刪除了當前節點
 if (succ != null)
 succ.prev = pred;
 // 如果第一個節點為空，說明沒有後繼節點了，直接返回
 if (first == null)
 return;
 // 如果根節點的父節點不為空，則重新查找父節點
 if (root.parent != null)
 root = root.root();
 // 如果根節點為空，則需要反樹化（將樹轉化為鏈表） 

 // 如果需要移動節點且樹的高度比較小，則需要反樹化
 if (root == null
 || (movable
 && (root.right == null
 || (rl = root.left) == null
 || rl.left == null))) {
 tab[index] = first.untreeify(map); // too small
 return;
 }
 // 分割線，以上都是刪除鏈表中的節點，下面才是直接刪除紅黑樹的節點（因為TreeNode本身即是鏈表節點又是樹節點）
 // 刪除紅黑樹節點的大致過程是尋找右子樹中最小的節點放到刪除節點的位置，然後做平衡，此處不過多註釋
 TreeNode p = this, pl = left, pr = right, replacement;
 if (pl != null && pr != null) {
 TreeNode s = pr, sl;
 while ((sl = s.left) != null) // find successor
 s = sl;
 boolean c = s.red;
 s.red = p.red;
 p.red = c; // swap colors
 TreeNode sr = s.right;
 TreeNode pp = p.parent;
 if (s == pr) { // p was s's direct parent
 p.parent = s;
 s.right = p;
 } else {
 TreeNode sp = s.parent;
 if ((p.parent = sp) != null) {
 if (s == sp.left)
 sp.left = p;
 else
 sp.right = p;
 }
 if ((s.right = pr) != null)
 pr.parent = s; 

 }
 p.left = null;
 if ((p.right = sr) != null)
 sr.parent = p;
 if ((s.left = pl) != null)
 pl.parent = s;
 if ((s.parent = pp) == null)
 root = s;
 else if (p == pp.left)
 pp.left = s;
 else
 pp.right = s;
 if (sr != null)
 replacement = sr;
 else
 replacement = p;
 } else if (pl != null)
 replacement = pl;
 else if (pr != null)
 replacement = pr;
 else
 replacement = p;
 if (replacement != p) {
 TreeNode pp = replacement.parent = p.parent;
 if (pp == null)
 root = replacement;
 else if (p == pp.left)
 pp.left = replacement;
 else
 pp.right = replacement;
 p.left = p.right = p.parent = null;
 }
 TreeNode r = p.red ? root : balanceDeletion(root, replacement);
 if (replacement == p) { // detach
 TreeNode pp = p.parent;
 p.parent = null;
 if (pp != null) {
 if (p == pp.left)
 pp.left = null;
 else if (p == pp.right)
 pp.right = null;
 }
 }
 if (movable)
 moveRootToFront(tab, r);
}
 

（1）TreeNode本身既是鏈表節點也是紅黑樹節點；

（2）先刪除鏈表節點；

（3）再刪除紅黑樹節點並做平衡；

總結

（1）HashMap是一種散列表，採用（數組 + 鏈表 + 紅黑樹）的存儲結構；

（2）HashMap的默認初始容量為16（1<<4），默認裝載因子為0.75f，容量總是2的n次方；

（3）HashMap擴容時每次容量變為原來的兩倍；

（4）當桶的數量小於64時不會進行樹化，只會擴容；

（5）當桶的數量大於64且單個桶中元素的數量大於8時，進行樹化；

（6）當單個桶中元素數量小於6時，進行反樹化；

（7）HashMap是非線程安全的容器；

（8）HashMap查找添加元素的時間複雜度都為O(1)；

帶詳細註釋的源碼地址

帶詳細註釋的源碼地址

彩蛋

紅黑樹知多少？

紅黑樹具有以下5種性質：

（1）節點是紅色或黑色。

（2）根節點是黑色。

（3）每個葉節點（NIL節點，空節點）是黑色的。

（4）每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

（5）從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

紅黑樹的時間複雜度為O(log n)，與樹的高度成正比。

紅黑樹每次的插入、刪除操作都需要做平衡，平衡時有可能會改變根節點的位置，顏色轉換，左旋，右旋等。

閱讀更多 戚小柒說IT 的文章

關鍵字: 個數 元素 一個桶