HashMap源碼解析
-
- 結構圖
- 常用變量
- 内部類
- 構造方法
- 常見方法
-
- 核心方法hash、resize、tableSizeFor等
- put
- get
- remove
- 總結
結構圖
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
}
常用變量
// 序列号 ，序列化使用
private static final long serialVersionUID = 362498820763181265L;
// 預設的初始容量 1<<4 帶符号左移 0001 ---> 10000 (2進制) = 16(10進制)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 加載因子 例如：數組容量為8 當元素數量為6(8*0.75)時，則會觸發擴容。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當某個桶節點(桶即為數組的每個格子)數量大于8時，會轉換為紅黑樹。
static final int TREEIFY_THRESHOLD = 8;
//當某個桶節點數量小于6時，會轉換為連結清單，前提是它目前是紅黑樹結構。
static final int UNTREEIFY_THRESHOLD = 6;
// 整個hashMap中元素數量大于64時，也會進行轉為紅黑樹結構
static final int MIN_TREEIFY_CAPACITY = 64;
// hashmap底層存儲資料結構 --數組 transient關鍵字表示該屬性不能被序列化
transient Node<K,V>[] table;
// 将資料轉換成set的另一種存儲形式
transient Set<Map.Entry<K,V>> entrySet;
// 元素數量
transient int size;
// 統計該map修改的次數
transient int modCount;
// 臨界值，也就是元素數量達到臨界值時，會進行擴容 (LOAD_FACTOR * INITIAL_CAPACITY)
int threshold;
// 同加載因子
final float loadFactor;
内部類
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
// 樹節點 注意繼承了 LinkedHashMap的Entry，LinkedHashMap的Entry繼承了HashMap的Node
// 說明樹節點本身也是一種雙向連結清單
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...// 省略樹的相關方法
}
構造方法
public HashMap() {
// 加載因子 = 預設加載因子 = 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 給定一個預設容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 自定義 容量 以及 加載因子
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;
// 注意：tableSizeFor 一個必問必知的方法,在下面核心方法中講解。
// 傳回給定容量的最大2次幂；例如 initialCapacity = 6 傳回 8(2的3次方)；initialCapacity = 12 傳回 16(2的4次方)
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 見下
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 擷取元素個數
int s = m.size();
if (s > 0) {
// 如果 hashmap 還未初始化
if (table == null) { // pre-size
// +1 是為了除不盡的情況
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
// 計算擴容門檻值
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
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);
}
}
}
常見方法
核心方法hash、resize、tableSizeFor等
// hash算法
static final int hash(Object key) {
int h;
// ^:異或運算; >>>:無符号右移
// 1^1=0; 1^0=1; 0^1=1; 0^0=0
// 這裡又是異或又是位運算，理由呢。可以參照這個大神的解答：https://www.zhihu.com/question/20733617
// 簡單來說：這段代碼叫“擾動函數”，目的就是為了混合原始hash的高位與低位，以此來增加低位的随機性；減少hash沖突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// ***** 計算擴容因子 *****
// >>>:無符号右移,a>>>b a向右移動b位，高位用0補，低位舍棄
// |:或運算 有1必為1。 |= ---> a=a|b
// 假設入參為6 6-1=5 轉換成2進制即為 0101
// 0101 >>> 1 ---> 0010
// 0101 | 0010 ---> 0111
// 0111 >>> 2 ---> 000111
// 0111 | 000111 ---> 000111
// 同理...
// 最後 n+1 = 0111 + 1 = 1000 (8)
static final int tableSizeFor(int cap) {
// 這裡-1就是為了防止 cap 本來就是2次幂。
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;
}
// ***** 擴容 *****
final Node<K,V>[] resize() {
// 底層數組
Node<K,V>[] oldTab = table;
// 底層數組的長度（不是元素數量）
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 擴容因子 threshold = capacity*loadFactor
int oldThr = threshold;
int newCap, newThr = 0;
// 如果長度不為0 也就是說 不是首次加載 hashmap在put時添加資料（懶加載）
if (oldCap > 0) {
// 如果數組長度大于等于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果 原長度*2 < 最大容量 且 原長度 >= 16 那麼就擴容兩倍且把擴容因子*2 注意點1
// newCap = oldCap * 2 新長度為舊長度的2倍 ***********
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// DEFAULT_INITIAL_CAPACITY = 1<<4 = 16
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 擴容因子 * 2
newThr = oldThr << 1;
}
// 如果oldCap<=0，且oldThr>0 說明已經初始化了，例如把元素删除完之後的情況，那麼它的臨界值肯定還存在;如果是首次初始化，它的臨界值則為0
// 如果不是首次初始化
else if (oldThr > 0)
// 這種情況下，數組容量=old擴容門檻值
newCap = oldThr;
else { // 如果是首次初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 這裡是對 注意點1 的完善，如果注意點1的條件不滿足 那麼newThr還是未指派的狀态。
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;
if (oldTab != null) {
// 周遊舊數組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 設為null 友善GC回收。
oldTab[j] = null;
if (e.next == null)
// 下标計算 e.hash & (newCap - 1)
// 如果下一個節點為null，重新計算新的節點位置 并把節點放入新的位置
// newCap為2次幂 是以-1 低位全是1 是以位置資訊由e.hash決定。
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //紅黑樹操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 連結清單 resize最重要的操作之一就是對連結清單的拆分；
// 可以去看看其他部落客寫的文章：https://blog.csdn.net/weixin_41565013/article/details/93190786
// 連結清單1
Node<K,V> loHead = null, loTail = null;
// 連結清單2
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 這裡注意：新的位置 = 【原位置】 或 【原位置 + 原數組長度】
do {
next = e.next;
// oldCap 為 2次幂 低位全為0 高位為1
// 是以 (e.hash & oldCap) 隻能等于 1 或 0，這裡把0,1分成了兩個連結清單
// 如果 等于 0
if ((e.hash & oldCap) == 0) {
// 如果尾節點為null
if (loTail == null)
loHead = e;
else
// 連結清單尾添加
loTail.next = e;
loTail = e;
}
else { // (e.hash & oldCap) = 1
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 把連結清單頭指向數組[j]
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 把連結清單頭指向 newTab[原下标+原數組長度]
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent：如果目前位置已存在一個值，是否替換，false是替換，true是不替換
// evict：表是否在建立模式，如果為false，則表是在建立模式。
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未初始化或為空 則擴容
if ((tab = table) == null || (n = tab.length) == 0)
// 擴容方法 resize(),詳情見上resize()解析
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // n-1 必為低位全為1
// 如果這個下标下沒有資料，那麼就指派。
tab[i] = newNode(hash, key, value, null);
else {
// 如果該下标 已有節點
Node<K,V> e; K k;
// 這裡分三種情況
// 1. 如果hash 且 key相等，則直接替換舊值
// 2. 如果是紅黑樹，則調用紅黑樹的put方法
// 3. 如果是連結清單，使用尾插法。接着判斷是否達到轉樹的條件，如果達到條件，那麼就轉成紅黑樹
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果hash 相等 key也相等 那麼就是同一個對象。
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);
//static final int TREEIFY_THRESHOLD =8; 當連結清單長度大于8則會轉成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)//-1 for 1st:-1是為了第一次循環
// 轉成紅黑樹結構
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;
}
// 轉成樹
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果數組長度<64 就去擴容；如果長度大于>=64；轉成紅黑樹
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
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);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
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.left = x.right = null;
// 如果根節點為null
if (root == null) {
x.parent = null; // 父節點為null
x.red = false; // 置為黑色
root = x; // 則把x（目前節點）設為根節點
} else { // 如果已存在根節點
K k = x.key; // 目前節點的key
int h = x.hash; // 目前節點的hash
Class<?> kc = null; // key的class
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 如果p(根節點)的hash值 > 目前節點的hash值
if ((ph = p.hash) > h)
// 放到左側的标記
dir = -1;
else if (ph < h)
// 否則放到右側
dir = 1;
// 如果hash值還是相等，那麼就需要其他方法進行比較
// 如果目前連結清單節點的key實作了comparable接口，并且目前樹節點和連結清單節點是相同Class的執行個體，那麼通過comparable的方式再比較兩者
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
/*
* 如果dir小于等于0 ：目前連結清單節點一定放置在目前樹節點的左側，但不一定是該樹節點的左孩子，也可能是左孩子的右孩子 或者 更深層次的節點。
* 如果dir大于0 ：目前連結清單節點一定放置在目前樹節點的右側，但不一定是該樹節點的右孩子，也可能是右孩子的左孩子 或者 更深層次的節點。
* 如果目前樹節點不是葉子節點，那麼最終會以目前樹節點的左孩子或者右孩子 為 起始節點 再進行下一個循環 重新尋找自己（目前連結清單節點）的位置
* 如果目前樹節點就是葉子節點，那麼根據dir的值，就可以把目前連結清單節點挂載到目前樹節點的左或者右側了。
* 挂載之後,還需要重新把樹進行平衡。平衡之後,就可以針對下一個連結清單節點進行處理了。
*/
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
get
public V get(Object key) {
Node<K,V> e;
// 核心是getNode方法
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;
if ((tab = table) != null // table不為null
&& (n = tab.length) > 0 // 長度>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;
// 如果第一個節點的next節點不為null
if ((e = first.next) != null) {
// 如果是紅黑樹結構
if (first instanceof TreeNode)
// 使用樹的方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// while 循環，如果key已經相等，就說明找到了；就傳回。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 擷取根節點調用 find() 方法
return ((parent != null) ? root() : this).find(h, k, null);
}
// 擷取紅黑樹的根節點
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
// 如果沒有父節點，那麼目前節點就是根節點。
if ((p = r.parent) == null)
return r;
r = p;
}
}
// 紅黑樹的查詢算法
// kc:k的Class對象，該Class應該是實作了Comparable<K>的，否則應該是null
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
// pl:左子樹節點；pr:右子樹節點
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 比較根節點的hash跟 需要查詢的節點的hash值
// 如果根節點的hash比需查詢節點的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))) // 如果hash相等且key相等，直接放回目前節點即可。
return p;
else if (pl == null) // 如果左子樹為null，那麼轉到右子樹
p = pr;
else if (pr == null) // 如果右子樹為null,那麼轉到左子樹
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; //dir小于0，p指向右孩子，否則指向右孩子。緊接着就是下一輪循環了
// 執行到這裡說明無法通過comparable比較 或者 比較之後還是相等
// 從右孩子節點遞歸循環查找，如果找到了比對的則傳回
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods.
*
* @param hash: hash for key (key的hash)
* @param key: the key
* @param value: the value to match if matchValue, else ignored 如果是matchValue，則比對值，否則忽略
* @param matchValue: if true only remove if value is equal 如果為true，隻在value相等時移除
* @param movable: if false do not move other nodes while removing 如果為false，則在移除時不要移動其他節點
* @return the node, or null if none
*/
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;
// 如果數組不為null 長度大于0 且根據key得到的數組下标中有值。
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;
// 如果key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // 如果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)))) {
// 如果key一緻，則跳出循環，并拿到node節點。
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) // 如果連結清單頭==需要删除的節點
// 那麼直接讓node節點的next節點指向數組目前位置
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
總結
HashMap中最重要的幾點：
- 底層結構 數組+連結清單+紅黑樹
- 幾個關鍵的數字：16(預設容量) 0.75f(預設擴容因子) 12(16*0.75 預設擴容門檻值) 6(當連結清單長度小于6時，轉成連結清單) 8(當連結清單長度大于8時，轉成紅黑樹) 64(當底層數組容量大于64時，轉成紅黑樹)
- 擴容方法resize()
- 擴容門檻值計算方法
- put方法
- remove方法
- 對于紅黑樹的了解(加分)
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)