HashMap源碼閱讀筆記
@
目錄
本文基於jdk1.8
HashMap採用 key/value 存儲結構，每個key對應唯一的value。
在jdk1.7之前，HashMap 的內部存儲結構是數組+鏈表。
在jdk1.8中 HashMap的存儲結構是 數組+鏈表+紅黑樹，提高了效率。
一、紅黑樹
在閱讀HashMap源碼之前，有必要對紅黑樹進行一些了解。
1、紅黑樹的性質
紅黑樹是一種自平衡二叉查找樹。
紅黑樹具有如下特性：
- 1、 任何一個節點都有顏色，黑色或者紅色
- 2、根節點是黑色的
- 3、 父子節點之間不能出現兩個連續的紅節點
- 4、任何一個節點向下遍歷到其子孫的葉子節點，所經過的黑節點個數必須相等
- 5、空節點被認為是黑色的
2、 紅黑樹平衡操作
紅黑樹是一種平衡樹，讓紅黑樹保持平衡狀態主要有兩種方式：旋轉（左旋、右旋）和變色。
左旋和右旋的示意圖如下：
變色即改變節點的顏色來保持平衡，如下圖：
3、HashMap中的紅黑樹
HashMap採用了混合式的存儲結構——數組+鏈表+紅黑樹。
在添加元素時，會根據hash值算出元素在數組中的位置，如果該位置沒有元素，則直接把元素放置在此處，如果該位置有元素了，則把元素以鏈表的形式放置在鏈表的尾部。
當一個鏈表的元素個數達到一定的數量（且數組的長度達到一定的長度）後，則把鏈錶轉化為紅黑樹，從而提高效率。
二、散列(Hash)
1、 散列表(Hash Table)
HashMap是一種基於散列表(Hash Table) 的Map，散列表是一種通用的數據結構，大部分程式語言都原生支援。
散列表的概念：key經過hash函數運算後得到一個槽（buckets或slots）的索引（index），槽中保存著要取的值。
如下圖：
2、散列函數(Hash函數)
索引是通過散列函數計算出來的，那麼不同的key可能經過散列函數計算得到相同的索引，這就產生了哈希碰撞
所以必須設計一個優秀的散列函數來降低哈希碰撞的概率。
發生哈希碰撞後也要合適地處理。
簡單看一下HashMap中的hash方法：
static final int hash(Object key) {
int h;
//key.hashCode()為哈希演算法，返回初始哈希值
//再做一次16位右位移異或混合
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
字元串的hashCode是一個int類型值，那可以直接作為數組下標了，且不會出現碰撞。但是這個hashCode的取值範圍是[-2147483648, 2147483647]，有將近40億的長度，所以肯定是不能作為數組下標的，記憶體也放不下。
默認初始化的Map大小是16個長度 DEFAULT_INITIAL_CAPACITY = 1 << 4，所以獲取的Hash值並不能直接作為下標使用，需要與數組長度進行取模運算得到一個下標值。
所說義，hashMap源碼這裡不只是直接獲取哈希值，還進行了一次擾動計算，(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移16位，也就正好是自己長度的一半，之後與原哈希值做異或運算，這樣就混合了原哈希值中的高位和低位，增大了隨機性。
三、HashMap源碼
1、HashMap繼承關係
還是從HashMap的繼承關係看起，HashMap類圖如下：
- 實現了Cloneable，可以被克隆
- 實現了Serializable，可以被序列化
- 繼承自AbstractMap，實現了Map介面，具有Map的所有功能
2、HashMap屬性
/**
* 默認容量，必須是2的冪
**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //aka16
/**
* 最大的容量為2的30次方
**/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認負載因子，值為0.75，當容量超過3/4時擴容
**/
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<K,V>[] table;
/**
* 作為entrySet()的快取
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 元素的數量
*/
transient int size;
/**
* 修改次數，用於在迭代的時候執行快速失敗策略
*/
transient int modCount;
/**
* 當桶的使用數量達到多少時進行擴容，threshold = capacity * loadFactor
*/
int threshold;
/**
* 裝載因子
*/
final float loadFactor;
-
容量
容量為數組的長度，亦即桶的個數，默認為16，最大為2的30次方，當容量達到64時會進行樹化。 -
負載因子
負載因子用來計算容量達到多少時才進行擴容，默認負載因子為0.75。當容量超過3/4時擴容。 -
樹化
樹化，當容量達到64且鏈表的長度達到8時進行樹化，當鏈表的長度小於6時反樹化。
3、Node內部類
Node是一個典型的單鏈表節點，其中，hash用來存儲key計算得來的hash值。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
4、紅黑樹相關
上面了解了紅黑樹的一些性質和操作，接下來看看具體的實現。
4.1、TreeNode內部類
Node是紅黑樹的節點類。它繼承自LinkedHashMap中的Entry類。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父節點
TreeNode<K,V> left; //左孩子
TreeNode<K,V> right; //右孩子
TreeNode<K,V> prev; // 前置節點
boolean red; //紅黑樹的顏色
/**
* 構造函數
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回根節點
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
//……
}
4.2、左旋
/**
* 紅黑樹左旋操作
**/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//p不為null且p的右子樹不為null
if (p != null && (r = p.right) != null) {
//將r(p的右子樹)的左子樹編程p的右子樹
if ((rl = p.right = r.left) != null)
//修改父節點引用，rl是r(p的右子樹)的左子樹
rl.parent = p;
// 將r(p的右子樹)的父節點變成p的父節點（左旋過程，將右子樹變成自己的父節點）
if ((pp = r.parent = p.parent) == null)
//如果p節點的父節點為null，證明p是根節點（子樹的根節點）
//將r變成根節點（子樹的根節點），並變成黑色（平衡）
(root = r).red = false;
//如果存在父節點且p是該節點的左子樹
else if (pp.left == p)
//將r(p的右子樹)變成該節點的左子樹
pp.left = r;
//如果存在父節點且p節點是該節點的右子樹
else
//將r(p的右子樹)變成該節點的右子樹
pp.right = r;
//將r(p的左子樹)變成p（左旋中，將左子樹變成自己的父節點）
r.left = p;
//r變成p的父節點
p.parent = r;
}
return root;
}
看一下圖示。
-
p沒有父節點
-
p有父節點
4.3、右旋
/**
* 紅黑樹右旋
**/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//p不為null且p的左子樹不為null
if (p != null && (l = p.left) != null) {
//將l(p的左子樹)的右子樹變成p的左子樹
if ((lr = p.left = l.right) != null)
lr.parent = p;
//將l(p的右子樹)的父節點變成p的父節點（右旋過程，將左子樹變成自己的父節點）
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
//如果存在父節點且p是該節點的右子樹
else if (pp.right == p)
pp.right = l;
//如果存在父節點且p是該節點的左子樹
else
pp.left = l;
//將l(p的右子樹)變成p（右旋中，將右子樹變成自己的父節點）
l.right = p;
p.parent = l;
}
return root;
}
圖示如下：
- p沒有父節點（可以理解為p是根節點）
- p有父節點
4.3、樹化
treeify，意即樹化。
前面提到了，當哈希桶中的鏈表長度超過閾值（默認8）的時候，就會對鏈表進行樹化。
/**
* 紅黑樹化
* @return 樹的根節點
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//循環整理
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//取出下一個鏈表節點
next = (TreeNode<K,V>)x.next;
//將x節點的左右節點設置為null
x.left = x.right = null;
//判斷當前紅黑樹是否有根節點
if (root == null) {
//如果沒有根節點
//當前節點的父節點設置為null
x.parent = null;
//設置顏色為黑色（根節點為黑色）
x.red = false;
//將x節點設置為根節點
root = x;
}
//當前紅黑樹存在根節點
else {
//獲取x節點的key
K k = x.key;
//獲取x節點的hash
int h = x.hash;
//key的class
Class<?> kc = null;
//從根節點遍歷，將x節點插入到紅黑樹中
for (TreeNode<K,V> p = root;;) {
//定義dir(方向),ph(節點hash)
int dir, ph;
//取出p節點的key
K pk = p.key;
//當p節點的hash大於x節點的hash時
if ((ph = p.hash) > h)
//左側
dir = -1;
else if (ph < h)
//右側
dir = 1;
//如果上面的if分支沒走，則證明兩個節點key的hash值相等，需要通過其他方式進行比較
//如果當前節點(x)的key的類實現了comparable介面，且當前循環節點(p)是相同Class的實例
//那麼就通過comparable進行比較
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//若還是相等，就通過tieBreakOrder比較
dir = tieBreakOrder(k, pk);
//先快取p節點
TreeNode<K,V> xp = p;
//根據dir方向，來選擇在左側還是右側插入
//並判斷是否為null
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//選擇的左/右子樹為null
//將原來的p節點(現xp)設置為x的父節點
x.parent = xp;
//如果dir 小於等於0
//將x節點放置在原p(現xp)節點的左側
if (dir <= 0)
xp.left = x;
//如果dir 大於0
//將x節點放置在原p(現xp)節點的右側
xp.right = x;
//調用balanceInsertion進行插入平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
//確保哈希桶指定位置存儲的節點是紅黑樹的根節點
moveRootToFront(tab, root);
}
/**
* 確保哈希桶指定位置存儲的節點是紅黑樹的根節點
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//索引位置
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果不是紅黑樹的根節點
if (root != first) {
Node<K,V> rn;
//指向紅黑樹的根節點
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//整理節點順序
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//遞歸做一個恆定校驗
assert checkInvariants(root);
}
}
圖例如下：
4.4、插入平衡
紅黑樹插入節點後，需要保持平衡。
balanceInsertion就是在保持紅黑樹插入節點後的平衡。
保持平衡的方式是旋轉和變色。
/**
* 插入平衡
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//將x節點設為紅色（新插入節點一開始為紅色）
x.red = true;
//一個沒有邊界的循環(需要內部跳出)
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//取出x的父節點並判斷是否為null
if ((xp = x.parent) == null) {
//x沒有父節點
x.red = false;//變色(黑色)
return x;//x為根節點發那會
}
//如果x存在父節點且x的父節點為黑色或x的父父節點不存在
else if (!xp.red || (xpp = xp.parent) == null)
//返回root
return root;
//如果x的父節點是父父節點的左孩子
if (xp == (xppl = xpp.left)) {
//父父節點的右孩子不為null且為紅色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//變色(黑)
xp.red = false;//變色(黑)
xpp.red = true;//變色(紅)
x = xpp;
}
else {
//x是父節點的右孩子
if (x == xp.right) {
//左旋
root = rotateLeft(root, x = xp);
//處理x的父父節點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//x的父節點存在
if (xp != null) {
xp.red = false;//變色
//x的父父節點存在
if (xpp != null) {
xpp.red = true;//變色
//右旋
root = rotateRight(root, xpp);
}
}
}
}
//如果x的父節點是父父節點的右孩子
else {
//x的父父節點的左孩子存在且為紅色
if (xppl != null && xppl.red) {
xppl.red = false;//變色(黑)
xp.red = false;//變色(黑)
xpp.red = true;//變色(紅)
x = xpp;
}
else {
//如果x是父節點的左孩子
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
//處理x的父父節點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果x的父節點存在
if (xp != null) {
xp.red = false;//變色(黑)
//如果x的父父節點存在
if (xpp != null) {
xpp.red = true;//變色(紅)
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
圖例如下：
- 假如有如下一個鏈表，裡面的數字代表hash值（先不考慮hash分布）
- 然後按照鏈表順序取出節點進行紅黑樹插入，以及插入後平衡操作（左旋右旋/變色）
4.5、反樹化
當鏈表的長度小於6時反樹化，即紅黑樹退化成鏈表。
/**
* 紅黑樹鏈表化
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//循環，將紅黑樹轉成鏈表
for (Node<K,V> q = this; q != null; q = q.next) {
//構造一個普通鏈表節點
Node<K,V> p = map.replacementNode(q, null);
//維護順序
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
4.6、查找
對應鏈表的節點查找，在鏈表樹化後，節點的查找就是紅黑樹實現的。查找的邏輯還是比較清晰的，因為紅黑樹是自平衡二叉查找樹，節點左子樹都比自己小，右子樹都比自己大，所以根據給定的hash，可以確定從左子樹還是右子樹查找，然後進行循環。
/**
* 紅黑樹節點查找的入口方法
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* 根據給定的hash和key，從紅黑樹的根節點開始進行查找
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//取出左子樹和右子樹，根據hash和key進行查找
TreeNode<K,V> pl = p.left, pr = p.right, q;
//根據hash大小決定取左子樹還是右子樹
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)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
4.7、刪除節點
刪除節點的操作還是比較麻煩，因為刪除之後需要平衡紅黑樹。
/**
* 移除給定節點, 調用該方法時要確保節點存在.
* 因為無法交換存在葉子節點的內部節點內容，所以這會比典型的紅黑樹節點刪除來得複雜
* 遍歷過程中"next"指針指向的繼任節點是可訪問的，所以我們交換了樹的連接.
* 如果當前樹節點太少，則將二叉樹替換成簡單形式
* (2-6節點測試觸發，取決於樹的結構)
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//判斷哈希桶
if (tab == null || (n = tab.length) == 0)
return;
//下標
int index = (n - 1) & hash;
//取出指定下標的根節點
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//繼任節點和前置節點
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//前置節點不存在，則證明要移除的節點是根節點
if (pred == null)
//將繼任節點往前移
tab[index] = first = succ;
else
//前置節點存在，則將繼任節點連接到前置節點（移除本節點）
pred.next = succ;
//判斷繼任節點是否存在
if (succ != null)
//存在的話，修改前置引用
succ.prev = pred;
//這個時候first為null，則表示哈希桶指定位置可能只有一個節點
if (first == null)
//返回
return;
//獲取根節點
if (root.parent != null)
root = root.root();
//根節點不存在或者根節點的左子樹/右子樹不存在或者左左子樹不存在
//該判斷是作為鏈表化的閾值
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
//紅黑樹太小，進行鏈表化
tab[index] = first.untreeify(map); // too small
return;
}
//取得要移除的節點，左子樹，右子樹
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//左右子樹同時存在
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//循環查找繼任節點
while ((sl = s.left) != null) // find successor
s = sl;
//交換p和s的顏色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//相等則證明p是s的直接父節點（只有一個層級）
if (s == pr) { // p was s's direct parent
//交換位置
p.parent = s;
s.right = p;
}
//如果是多個層級
else {
//取出s的父節點
TreeNode<K,V> sp = s.parent;
//下面操作仍然是交換p和s的位置
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的右子樹引用
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<K,V> 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;
}
//判斷p的顏色
//如果p是紅色節點，則將根節點賦值給r
//如果p是黑色節點，則進行刪除平衡(類似於插入平衡)
//這裡的r要存儲紅黑樹的根節點
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果替換節點是自身的話
if (replacement == p) { // detach
//進行分離操作
TreeNode<K,V> 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);
}
5、HashMap構造方法
- 無參構造方法：
/**
* 所有參數使用默認值
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- HashMap(int initialCapacity)：指定默認裝載因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- HashMap(int initialCapacity, float loadFactor)：判斷傳入的初始容量和裝載因子是否合法，並計算擴容門檻，擴容門檻為傳入的初始容量往上取最近的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;
}
6、插入
HashMap插入的流程圖如下：
public V put(K key, V value) {
//調用hash(key)計算出key的hash值
return putVal(hash(key), key, value, false, 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，table 被延遲到插入新數據時再進行初始化
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<K,V> 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<K,V>)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;
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 到這裡了說明沒有找到元素
// 修改次數加1
++modCount;
// 元素數量加1，判斷是否需要擴容
if (++size > threshold)
// 擴容
resize();
afterNodeInsertion(evict);
return null;
}
插入：
- 1、首先進行哈希值的擾動，獲取一個新的哈希值。
- 2、判斷tab是否位空或者長度為0，如果是則進行擴容操作
- 3、根據哈希值計算下標，如果對應小標正好沒有存放數據，則直接插入即可，否則需要覆蓋。
- 4、判斷tab[i]是否為樹節點，否則向鏈表中插入數據，是則向樹中插入節點。
- 5、如果鏈表中插入節點的時候，鏈表長度大於等於8，則需要把鏈錶轉換為紅黑樹。
- 6、最後所有元素處理完成後，判斷是否超過閾值；threshold，超過則擴容。
- 7、treeifyBin,是一個鏈錶轉樹的方法，但不是所有的鏈表長度為8後都會轉成樹，還需要判斷存放key值的數組桶長度是否小於64 （MIN_TREEIFY_CAPACITY）。如果小於則需要擴容，擴容後鏈表上的數據會被拆分散列的相應的桶節點上，也就把鏈表長度縮短了。
7、擴容
HashMap是基於數組+鏈表和紅黑樹實現的，但用於存放key值得的數組桶的長度是固定的，由初始化決定。
那麼，隨著數據的插入數量增加以及負載因子的作用下，就需要擴容來存放更多的數據。
final Node<K, V>[] resize() {
// 舊數組
Node<K, V>[] 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<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
// 把桶賦值為新數組
table = newTab;
// 如果舊數組不為空，則搬移元素
if (oldTab != null) {
// 遍歷舊數組
for (int j = 0; j < oldCap; ++j) {
Node<K, V> 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<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
// 如果這個鏈表不止一個元素且不是一顆樹
// 則分化成兩個鏈表插入到新的桶中去
// 比如，假如原來容量為4，3、7、11、15這四個元素都在三號桶中
// 現在擴容到8，則3和11還是在三號桶，7和15要搬移到七號桶中去
// 也就是分化成了兩個鏈表
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> 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）搬移元素，原鏈表分化成兩個鏈表，低位鏈表存儲在原來桶的位置，高位鏈表搬移到原來桶的位置加舊容量的位置
8、查找
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;
// 如果桶的數量大於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<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;
}
查找：
-
（1）計算key的hash值；
-
（2）找到key所在的桶及其第一個元素；
-
（3）如果第一個元素的key等於待查找的key，直接返回；
-
（4）如果第一個元素是樹節點就按樹的方式來查找，否則按鏈表方式查找；
8、刪除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.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;
// 定位桶數組中的下標位置，index = (n - 1) & hash
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;
// 如果鍵的值與鏈表第一個節點相等，則將 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);
}
}
// 刪除節點，以及紅黑樹需要修復，因為刪除後會破壞平衡性。鏈表的刪除更加簡單。
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是一種散列表，採用（數組 + 鏈表 + 紅黑樹）的存儲結構
- HashMap的默認初始容量為16（1<<4），默認裝載因子為0.75f，容量總是2的n次方
- HashMap擴容時每次容量變為原來的兩倍
- 當桶的數量小於64時不會進行樹化，只會擴容
- 當桶的數量大於64且單個桶中元素的數量大於8時，進行樹化
- 當單個桶中元素數量小於6時，進行反樹化
- HashMap是非執行緒安全的
- HashMap查找添加元素的時間複雜度都為O(1)
本文為學習筆記，參考資料如下！
參考：
【1】：【死磕 Java 集合】— HashMap源碼分析
【2】：HashMap源碼閱讀
【3】：面經手冊 · 第3篇《HashMap核心知識，擾動函數、負載因子、擴容鏈表拆分，深度學習》
【4】：面經手冊 · 第4篇《HashMap數據插入、查找、刪除、遍歷，源碼分析》
【5】：面經手冊 · 第5篇《看圖說話，講解2-3平衡樹「紅黑樹的前身」》
【6】：面經手冊 · 第6篇《帶著面試題學習紅黑樹操作原理，解析什麼時候染色、怎麼進行旋轉、與2-3樹有什麼關聯》
【7】：Java源碼閱讀之紅黑樹在HashMap中的應用 – JDK1.8
【8】：Java HashMap 源碼解析
【9】：重學數據結構（六、樹和二叉樹）
【10】：紅黑樹深入剖析及Java實現
【11】：哈希碰撞與生日攻擊
