HashMap 詳解一

本文代碼來自JDK8

實作原理

1. 建立一個數組
2. 根據元素哈希值計算數組索引, 儲存到數組
3. 索引号相同的元素通過連結清單儲存
4. 連結清單長度超過範圍轉紅黑樹儲存

預設常量

• 初始長度大小: DEFAULT_INITIAL_CAPACITY = 1 << 4, 為了區分容量和元素數目, 這裡就用長度表示容量
• 最大長度大小: MAXIMUM_CAPACITY = 1 << 30
• 預設加載因子: DEFAULT_LOAD_FACTOR = 0.75f
• 連結清單轉紅黑樹的門檻值: TREEIFY_THRESHOLD = 8
• 紅黑樹轉連結清單的門檻值: UNTREEIFY_THRESHOLD = 6
• 轉換紅黑樹要求最小數組長度: MIN_TREEIFY_CAPACITY = 64

變量

• transient Node[] table: 儲存元素的數組
• transient int size: 元素個數, 不是數組長度
• int threshold: 對數組擴容的門檻值, 容量*加載因子
• final float loadFactor: 加載因子, 越大填充的資料就越多, 沖突也會越多; 越小填充的資料就越少, 沖突也會減少, 為什麼取 0.75 預設值就不深入讨論了

哈希值計算

// key為空, 對應哈希值為 0
// 否則将 key 的哈希值進行擾動: 高 16 位與低 16 位進行異或
// 這樣做的原因是當哈希值與數組長度減一進行與運算得出索引時, 
// 對于數組長度比較小的情況, 如果沒有擾動, 哈希值的高位将不參與運算, 最後的索引值很有可能會重複
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}           

關于 tableSizeFor 方法留到下一 part 再講.