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