閱讀要求：具備一定的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識，例如：數(shù)組，鏈表，二叉樹的數(shù)據(jù)結(jié)構(gòu)以及特性
HashMap 的構(gòu)成
- 數(shù)組 + 鏈表 + 紅黑樹
transient Node<K,V>[] table;
- 默認容量：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 擴容閥值
int threshold;
- 加載因子：默認是 0.75，范圍：0-1
final float loadFactor;
-
HashMap 數(shù)據(jù)結(jié)構(gòu)原型圖
圖片來源于：一文讀懂HashMap 一個數(shù)據(jù)，是如何保存到數(shù)據(jù)的哪一個下標下呢？
index = (size - 1) & hash
哈希碰撞（哈希沖突）
哈希碰撞的定義：
不同的 key 值，通過哈希函數(shù)，計算出來的 hash 相同
舉個栗子：
哈希函數(shù)為： hash = key % 3
傳遞的 key 分別為：1 和 4，于是有： hash(1) = 1%3 = 1； hash(4) = 4%3 =1;
不同的 key, 計算出來的 hash 值相同，故產(chǎn)生了哈希碰撞
哈希函數(shù)
良好的哈希函數(shù)應盡可能的具備有以下幾種特性：
- 計算速度快
- 計算出來的結(jié)果離散，哈希碰撞的機會盡可能少
解決哈希碰撞的方法
鏈地址法： 將 hash 相同的，存儲在同一線性鏈表中（參考：上方數(shù)據(jù)結(jié)構(gòu)原型圖）。
其他方法：探針法，開放地址法，再哈希法等
HashMap 的擴容機制
擴容機制
- 擴容時機
size >= loadFactor * capacity
舉個栗子：loadFactor 為 0.75， capacity 為 16, 則觸發(fā)擴容的時機就是 12 時觸發(fā)。
- 擴容機制：容量翻倍
threshold = oldThr << 1
- 擴容的時機
擴容優(yōu)化：
為了避免頻繁的擴容，造成性能問題和內(nèi)存浪費，在確定容量的情況下，應使用 HashMap 兩個參數(shù)的構(gòu)造函數(shù)，指定容量以及擴容因子
public HashMap(int initialCapacity, float loadFactor) {
}
默認的擴容因子為什么是 0.75？
利用統(tǒng)計學的泊松分布概念計算得出，可參考文章 HashMap的loadFactor為什么是0.75？
HashMap 的存儲過程
存儲過程流程圖
存儲過程流程圖
源碼解析
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 獲取初始化數(shù)據(jù)
if ((tab = table) == null || (n = tab.length) == 0)
// 數(shù)據(jù)進行初始化，并且給會重新計算 threshold 大小為 0.75 * 容量
n = (tab = resize()).length;
// 計算得到要插入到數(shù)據(jù)的哪一個位置
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果當前數(shù)組位置為空，則直接將此節(jié)點插入
tab[i] = newNode(hash, key, value, null);
else {
// 代表數(shù)組位置不空，則：1. 相同 key 值則替換位置下的值 2. 如果是紅黑樹，則插入到紅黑樹中；如果不是紅黑樹，則插入到鏈表中
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 找到相同 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) {
// 鏈表節(jié)點指向下一個為空，代表找到了末尾，插入到鏈表末尾
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表數(shù)量達到 8 個，鏈表轉(zhuǎn)紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到相同 key 值
break;
// 當前鏈表，指向下一個
p = e;
}
}
// 代表找到相同的 key 值，將此節(jié)點中的值替換
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 當前容量 +1，滿足擴容條件，進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
其它鍵值存儲方式
HashMap 和 Hashtable 的區(qū)別
- HashMap 是線程不安全的， HashTable 是線程安全的，因為 Hashtable 提供的函數(shù)都加載了 synchronize 關(guān)鍵字，故 Hashtable 的效率低；
- HashMap 默認容量是 16，Hashtable 的默認容量是 11；
- 存儲結(jié)構(gòu)不同等。
HashMap 的其他替代方案
- SparseArray
- Hashtable
- ConcurrentHashMap
不吐不快
- threshold 在構(gòu)造函數(shù)的時，是代表容量值，在首次 putVal 中，對 table 進行初始化，重新將 threshold 的值變?yōu)?capacity * loadFactor，threshold 存在二異性，巨坑
- resize 函數(shù)邏輯寫得渣到掉土了
