HashMap 原理及原始碼分析
1. 存盤結構
HashMap 內部是由 Node 型別的陣列實作的，Node 包含著鍵值對，內部有四個欄位，從 next 欄位我們可以看出，Node 是一個鏈表，即陣列的每一個位置被當作一個桶，每個桶存盤一個鏈表，HashMap 使用拉鏈法來解決沖突，同一個桶中存放 hashcode 與陣列長度取模運算結果相同的 Node，
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 = https://www.cnblogs.com/Code-CHAN/p/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 = https://www.cnblogs.com/Code-CHAN/p/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;
}
}
2. 索引計算
在 HashMap 中，node 在陣列中的索引根據 key 的哈希值與陣列長度取模運算得到，
如下為 HashMap 中 putVal 方法（put方法的實際執行程序），
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// ...
}
可以看到第6行中
i = (n - 1) & hash
其中 i 即為根據 key 計算得到的索引，n 為陣列的大小，
這是因為在 HashMap 中, 陣列的大小為 \(2^n\), 則其二進制形式具有如下特點：
令 x = 1 << 4，即 x 為 2 的 4 次方
x : 0001 0000
x-1 : 0000 1111
令一個數 y 與 x - 1 取與
y : 1101 1011
x-1 : 0000 1111
y&(x-1) : 0000 1011
這個性質和 y 對 x 取模效果是一樣的
y : 1101 1011
x : 0001 0000
y%x : 0000 1011
我們知道，位運算的代價比求模運算小的多，因此使用這種計算時用位運算能夠帶來更高的性能，
3. put 操作
HashMap 中 put 方法實際執行的是 putVal 方法，
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
下面為 putVal 方法的實作，為了更好的理解 put 操作，原始碼中有關紅黑樹及擴容的部分，先使用省略號代替，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// map 剛構造并且未添加元素時，陣列為 null，需要進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算索引，若索引位置的桶為空，則將其放入桶中
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（e 為需要更新的節點）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ...
else {
// 遍歷桶中的鏈表
for (int binCount = 0; ; ++binCount) {
// 如果到達鏈表尾部，即 map 中不存在該 key 的節點，則將其添加到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// ...
break;
}
// 如果在遍歷程序中存在 key，則將其賦給 e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e 不為空，說明 map 中存在該 key，更新其 value
if (e != null) {
V oldValue = https://www.cnblogs.com/Code-CHAN/p/e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//...
}
總結
put 操作主要步驟為：
- 根據 key 計算 node 在陣列中的索引
- 若索引位置為空，則將 node 放入該索引位置
- 若不為空
- 遍歷該索引位置的桶中元素，比較桶中元素 key 是否與該 key 相同，若相同則更新其 value
- 若桶中不存在該 key，則新建一個 node 放入桶中
4. 擴容
設 HashMap 中陣列的長度為 n, 存盤的鍵值對數量為 m, 在哈希函式滿足均勻性的前提下，每個鏈表長度為 m / n，因此查找的時間復雜度為 O(m / n)，
為了減小查找效率，即減小 m / n, 則應該增大 n，即陣列的長度，HashMap 使用動態擴容的方式來根據當前鍵值對的數量，來調整陣列的大小，是得空間和時間效率都能得到保證，
和擴容相關的引數主要有：capatity、size、threshold 和 loadFactor
| 引數 | 含義 |
|---|---|
| capacity | table 陣列的大小，默認為 16 |
| size | 鍵值對數量 |
| threshold | size 的臨界值，當 size 大于 threshold 時就必須進行擴容操作 |
| loadFactor | 裝載因子，默認為 0.75，table 能夠使用的比例 threshold = (int) (capacity * loadFactor) |
擴容操作在 putVal 中，有兩種情況會觸發
- map 初始時，陣列大小為 0，需要擴容
- 當鍵值對數量超過臨界值時，觸發擴容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; /* 陣列為 null，需要擴容 */
// ...
if (++size > threshold)
resize(); /* size 超過臨界值，觸發擴容 */
// ...
}
擴容主要分為兩步
- 對陣列容量進行擴容
- 擴容后需要原來陣列的所有鍵插入到新的陣列中
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 1. 進行擴容
if (oldCap > 0) {
// 若容量大于等于最大容量，則無法擴容，將臨界值改為 int 的最大值，并回傳（因為沒有擴容無需重新插入鍵）
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量擴大到原來的兩倍，并將臨界值修改到原來的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0) // 若陣列大小為 0，臨界值不為 0，則陣列初始大小為臨界值（tableSizeFor 方法保證 oldThr 為 2 的 n 次方，下一節介紹）
newCap = oldThr;
else { // 若陣列大小為 0，臨界值為 0，則初始大小為 16，初始臨界值 = 0.75 * 16 = 12
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;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 2. 重新插入鍵
if (oldTab != null) {
// 遍歷舊的陣列
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 桶中含有元素，則遍歷桶中元素
if ((e = oldTab[j]) != null) {
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 { // 遍歷鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/**
* 舉個例子
* oldCap : 0001 0000
* newCap : 0010 0000
* newCap-1: 0001 1111
* 若哈希與舊陣列大小與運算為 0，則說明
* 哈希與 newCap-1 運算時，與最高位1運算
* 的結果為 0，則索引位置位于 [0,oldCap)
* 若運算結果不為 0，則索引位置為 [oldCap, newCap)
* 又同一個桶中，與 oldCap-1 運算結果相同，
* 即同一個桶中的元素，計算的新索引要么為舊索引值，
* 要么為舊索引值+oldCap（與最高位1相與不為0）
* 則 loHead 為舊索引位置的頭節點，hiHead 為
* 新索引位置的頭節點
*/
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;
}
5. 保證陣列容量為 \(2^n\)
HashMap 的建構式允許用戶傳入初始容量，并且可以不是 \(2^n\)，但是 HashMap 可以將其轉為 \(2^n\) ，
先考慮如何求一個數的掩碼，對于 1000 0000，它的掩碼為 1111 1111，可以使用以下方法得到：
mask |= mask >> 1 1100 0000
mask |= mask >> 2 1111 0000
mask |= mask >> 4 1111 1111
則 mask + 1 是大于原始數字的最小的 2 的 n 次方
HashMap 通過 tableSizeFor 來保證陣列容量為 2 的 n 次方
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412974.html
標籤：其他
上一篇：藍橋杯ALGO-1003