前言
今天潭千，我將通過(guò)源碼分析HashMap 1.8 ，從而講解HashMap 1.8 相對(duì)于 HashMap 1.7 的更新內(nèi)容，希望你們會(huì)喜歡。
示意圖.png
1. 簡(jiǎn)介
- 類定義
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
-
主要簡(jiǎn)介
示意圖.png - HashMap 的實(shí)現(xiàn)在 JDK 1.7 和 JDK 1.8 差別較大
- 今天丈甸，我將對(duì)照 JDK 1.7的源碼，在此基礎(chǔ)上講解 JDK 1.8 中 HashMap 的源碼解析
2. 數(shù)據(jù)結(jié)構(gòu)：引入了 紅黑樹
2.1 主要介紹
示意圖
關(guān)于 紅黑樹 的簡(jiǎn)介
示意圖
更加具體的了解，請(qǐng)：點(diǎn)擊閱讀文章
2.2 存儲(chǔ)流程
為了讓大家有個(gè)感性的認(rèn)識(shí)，只是簡(jiǎn)單的畫出存儲(chǔ)流程蒿褂，更加詳細(xì) & 具體的存儲(chǔ)流程會(huì)在下面源碼分析中給出
示意圖
2.3 數(shù)組元素 & 鏈表節(jié)點(diǎn)的 實(shí)現(xiàn)類
- HashMap中的數(shù)組元素 & 鏈表節(jié)點(diǎn) 采用 Node類 實(shí)現(xiàn)
與 JDK 1.7 的對(duì)比（Entry類），僅僅只是換了名字
- 該類的源碼分析如下
/**
* Node = HashMap的內(nèi)部類卒暂，實(shí)現(xiàn)了Map.Entry接口啄栓，本質(zhì)是 = 一個(gè)映射(鍵值對(duì))
* 實(shí)現(xiàn)了getKey()、getValue()也祠、equals(Object o)和hashCode()等方法
**/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值昙楚，HashMap根據(jù)該值確定記錄的位置
final K key; // key
V value; // value
Node<K,V> next;// 鏈表下一個(gè)節(jié)點(diǎn)
// 構(gòu)造方法
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; } // 返回 與 此項(xiàng) 對(duì)應(yīng)的鍵
public final V getValue() { return value; } // 返回 與 此項(xiàng) 對(duì)應(yīng)的值
public final String toString() { return key + "=" + value; }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* hashCode（）
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* equals（）
* 作用：判斷2個(gè)Entry是否相等，必須key和value都相等诈嘿，才返回true
*/
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.4 紅黑樹節(jié)點(diǎn) 實(shí)現(xiàn)類
HashMap中的紅黑樹節(jié)點(diǎn) 采用 TreeNode 類 實(shí)現(xiàn)
/**
* 紅黑樹節(jié)點(diǎn) 實(shí)現(xiàn)類：繼承自LinkedHashMap.Entry<K,V>類
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 屬性 = 父節(jié)點(diǎn)堪旧、左子樹、右子樹永淌、刪除輔助節(jié)點(diǎn) + 顏色
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
// 構(gòu)造函數(shù)
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
3. 具體使用
3.1 主要使用API（方法崎场、函數(shù)）
V get(Object key); // 獲得指定鍵的值
V put(K key, V value); // 添加鍵值對(duì)
void putAll(Map<? extends K, ? extends V> m); // 將指定Map中的鍵值對(duì) 復(fù)制到 此Map中
V remove(Object key); // 刪除該鍵值對(duì)
boolean containsKey(Object key); // 判斷是否存在該鍵的鍵值對(duì)佩耳；是 則返回true
boolean containsValue(Object value); // 判斷是否存在該值的鍵值對(duì)遂蛀；是 則返回true
Set<K> keySet(); // 單獨(dú)抽取key序列，將所有key生成一個(gè)Set
Collection<V> values(); // 單獨(dú)value序列干厚，將所有value生成一個(gè)Collection
void clear(); // 清除哈希表中的所有鍵值對(duì)
int size(); // 返回哈希表中所有 鍵值對(duì)的數(shù)量 = 數(shù)組中的鍵值對(duì) + 鏈表中的鍵值對(duì)
boolean isEmpty(); // 判斷HashMap是否為空李滴；size == 0時(shí) 表示為 空
3.2 使用流程
在具體使用時(shí)，主要流程是：
- 聲明1個(gè) HashMap的對(duì)象
- 向 HashMap 添加數(shù)據(jù)（成對(duì) 放入 鍵 - 值對(duì)）
- 獲取 HashMap 的某個(gè)數(shù)據(jù)
- 獲取 HashMap 的全部數(shù)據(jù)：遍歷HashMap
示例代碼
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
/**
* 1. 聲明1個(gè) HashMap的對(duì)象
*/
Map<String, Integer> map = new HashMap<String, Integer>();
/**
* 2. 向HashMap添加數(shù)據(jù)（成對(duì) 放入 鍵 - 值對(duì)）
*/
map.put("Android", 1);
map.put("Java", 2);
map.put("iOS", 3);
map.put("數(shù)據(jù)挖掘", 4);
map.put("產(chǎn)品經(jīng)理", 5);
/**
* 3. 獲取 HashMap 的某個(gè)數(shù)據(jù)
*/
System.out.println("key = 產(chǎn)品經(jīng)理時(shí)的值為：" + map.get("產(chǎn)品經(jīng)理"));
/**
* 4. 獲取 HashMap 的全部數(shù)據(jù)：遍歷HashMap
* 核心思想：
* 步驟1：獲得key-value對(duì)（Entry） 或 key 或 value的Set集合
* 步驟2：遍歷上述Set集合(使用for循環(huán) 蛮瞄、 迭代器（Iterator）均可)
* 方法共有3種：分別針對(duì) key-value對(duì)（Entry） 或 key 或 value
*/
// 方法1：獲得key-value的Set集合 再遍歷
System.out.println("方法1");
// 1. 獲得key-value對(duì)（Entry）的Set集合
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
// 2. 遍歷Set集合所坯，從而獲取key-value
// 2.1 通過(guò)for循環(huán)
for(Map.Entry<String, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}
System.out.println("----------");
// 2.2 通過(guò)迭代器：先獲得key-value對(duì)（Entry）的Iterator，再循環(huán)遍歷
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
// 遍歷時(shí)挂捅，需先獲取entry芹助，再分別獲取key、value
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print((String) entry.getKey());
System.out.println((Integer) entry.getValue());
}
// 方法2：獲得key的Set集合 再遍歷
System.out.println("方法2");
// 1. 獲得key的Set集合
Set<String> keySet = map.keySet();
// 2. 遍歷Set集合，從而獲取key状土，再獲取value
// 2.1 通過(guò)for循環(huán)
for(String key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}
System.out.println("----------");
// 2.2 通過(guò)迭代器：先獲得key的Iterator无蜂，再循環(huán)遍歷
Iterator iter2 = keySet.iterator();
String key = null;
while (iter2.hasNext()) {
key = (String)iter2.next();
System.out.print(key);
System.out.println(map.get(key));
}
// 方法3：獲得value的Set集合 再遍歷
System.out.println("方法3");
// 1. 獲得value的Set集合
Collection valueSet = map.values();
// 2. 遍歷Set集合，從而獲取value
// 2.1 獲得values 的Iterator
Iterator iter3 = valueSet.iterator();
// 2.2 通過(guò)遍歷蒙谓，直接獲取value
while (iter3.hasNext()) {
System.out.println(iter3.next());
}
}
}
// 注：對(duì)于遍歷方式斥季，推薦使用針對(duì) key-value對(duì)（Entry）的方式：效率高
// 原因：
// 1. 對(duì)于 遍歷keySet 、valueSet累驮，實(shí)質(zhì)上 = 遍歷了2次：1 = 轉(zhuǎn)為 iterator 迭代器遍歷酣倾、2 = 從 HashMap 中取出 key 的 value 操作（通過(guò) key 值 hashCode 和 equals 索引）
// 2. 對(duì)于 遍歷 entrySet ，實(shí)質(zhì) = 遍歷了1次 = 獲取存儲(chǔ)實(shí)體Entry（存儲(chǔ)了key 和 value ）
運(yùn)行結(jié)果
方法1
Java2
iOS3
數(shù)據(jù)挖掘4
Android1
產(chǎn)品經(jīng)理5
----------
Java2
iOS3
數(shù)據(jù)挖掘4
Android1
產(chǎn)品經(jīng)理5
方法2
Java2
iOS3
數(shù)據(jù)挖掘4
Android1
產(chǎn)品經(jīng)理5
----------
Java2
iOS3
數(shù)據(jù)挖掘4
Android1
產(chǎn)品經(jīng)理5
方法3
2
3
4
1
5
下面谤专，我們按照上述的使用過(guò)程躁锡，對(duì)一個(gè)個(gè)步驟進(jìn)行源碼解析
4. 基礎(chǔ)知識(shí)：HashMap中的重要參數(shù)（變量）
- 在進(jìn)行真正的源碼分析前，先講解HashMap中的重要參數(shù)（變量）
- HashMap中的主要參數(shù) 同 JDK 1.7 毒租，即：容量稚铣、加載因子、擴(kuò)容閾值
- 但由于數(shù)據(jù)結(jié)構(gòu)中引入了 紅黑樹墅垮，故加入了 與紅黑樹相關(guān)的參數(shù)惕医。具體介紹如下：
此處 再次詳細(xì)說(shuō)明 加載因子(同 JDK 1.7，但由于其重要性算色，故此處再次說(shuō)明)
示意圖
總結(jié) 數(shù)據(jù)結(jié)構(gòu) & 參數(shù)方面與 JDK 1.7的區(qū)別
示意圖.jpg
5. 源碼分析
- 本次的源碼分析主要是根據(jù) 使用步驟 進(jìn)行相關(guān)函數(shù)的詳細(xì)分析
-
主要分析內(nèi)容如下：
下面抬伺，我將對(duì)每個(gè)步驟內(nèi)容的主要方法進(jìn)行詳細(xì)分析
步驟1：聲明1個(gè) HashMap的對(duì)象
此處主要分析的構(gòu)造函數(shù) 類似 JDK 1.7
/**
* 函數(shù)使用原型
*/
Map<String,Integer> map = new HashMap<String,Integer>();
/**
* 源碼分析：主要是HashMap的構(gòu)造函數(shù) = 4個(gè)
* 僅貼出關(guān)于HashMap構(gòu)造函數(shù)的源碼
*/
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
// 省略上節(jié)闡述的參數(shù)
/**
* 構(gòu)造函數(shù)1：默認(rèn)構(gòu)造函數(shù)（無(wú)參）
* 加載因子 & 容量 = 默認(rèn) = 0.75、16
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 構(gòu)造函數(shù)2：指定“容量大小”的構(gòu)造函數(shù)
* 加載因子 = 默認(rèn) = 0.75 灾梦、容量 = 指定大小
*/
public HashMap(int initialCapacity) {
// 實(shí)際上是調(diào)用指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
// 只是在傳入的加載因子參數(shù) = 默認(rèn)加載因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 構(gòu)造函數(shù)3：指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
* 加載因子 & 容量 = 自己指定
*/
public HashMap(int initialCapacity, float loadFactor) {
// 指定初始容量必須非負(fù)峡钓，否則報(bào)錯(cuò)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕傳入的 > 最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充比必須為正
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 設(shè)置 加載因子
this.loadFactor = loadFactor;
// 設(shè)置 擴(kuò)容閾值
// 注：此處不是真正的閾值若河，僅僅只是將傳入的容量大小轉(zhuǎn)化為：>傳入容量大小的最小的2的冪能岩，該閾值后面會(huì)重新計(jì)算
// 下面會(huì)詳細(xì)講解 ->> 分析1
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 構(gòu)造函數(shù)4：包含“子Map”的構(gòu)造函數(shù)
* 即 構(gòu)造出來(lái)的HashMap包含傳入Map的映射關(guān)系
* 加載因子 & 容量 = 默認(rèn)
*/
public HashMap(Map<? extends K, ? extends V> m) {
// 設(shè)置容量大小 & 加載因子 = 默認(rèn)
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 將傳入的子Map中的全部元素逐個(gè)添加到HashMap中
putMapEntries(m, false);
}
}
/**
* 分析1：tableSizeFor(initialCapacity)
* 作用：將傳入的容量大小轉(zhuǎn)化為：>傳入容量大小的最小的2的冪
* 與JDK 1.7對(duì)比：類似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2(toSize)
*/
static final int tableSizeFor(int cap) {
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;
}
注：（同JDK 1.7類似）
此處僅用于接收初始容量大小（capacity）萧福、加載因子(Load factor)拉鹃，但仍無(wú)真正初始化哈希表，即初始化存儲(chǔ)數(shù)組table
此處先給出結(jié)論：真正初始化哈希表（初始化存儲(chǔ)數(shù)組table）是在第1次添加鍵值對(duì)時(shí)鲫忍，即第1次調(diào)用put（）時(shí)膏燕。下面會(huì)詳細(xì)說(shuō)明
至此，關(guān)于HashMap的構(gòu)造函數(shù)講解完畢悟民。
步驟2：向HashMap添加數(shù)據(jù)（成對(duì) 放入 鍵 - 值對(duì)）
在該步驟中坝辫，與JDK 1.7的差別較大：
示意圖.png
添加數(shù)據(jù)的流程如下
注：為了讓大家有個(gè)感性的認(rèn)識(shí)，只是簡(jiǎn)單的畫出存儲(chǔ)流程射亏，更加詳細(xì) & 具體的存儲(chǔ)流程會(huì)在下面源碼分析中給出
示意圖.png
源碼分析
/**
* 函數(shù)使用原型
*/
map.put("Android", 1);
map.put("Java", 2);
map.put("iOS", 3);
map.put("數(shù)據(jù)挖掘", 4);
map.put("產(chǎn)品經(jīng)理", 5);
/**
* 源碼分析：主要分析HashMap的put函數(shù)
*/
public V put(K key, V value) {
// 1. 對(duì)傳入數(shù)組的鍵Key計(jì)算Hash值 ->>分析1
// 2. 再調(diào)用putVal（）添加數(shù)據(jù)進(jìn)去 ->>分析2
return putVal(hash(key), key, value, false, true);
}
下面近忙，將詳細(xì)講解 上面的2個(gè)主要分析點(diǎn)
分析1：hash（key）
/**
* 分析1：hash(key)
* 作用：計(jì)算傳入數(shù)據(jù)的哈希碼（哈希值竭业、Hash值）
* 該函數(shù)在JDK 1.7 和 1.8 中的實(shí)現(xiàn)不同，但原理一樣 = 擾動(dòng)函數(shù) = 使得根據(jù)key生成的哈希碼（hash值）分布更加均勻及舍、更具備隨機(jī)性永品，避免出現(xiàn)hash值沖突（即指不同key但生成同1個(gè)hash值）
* JDK 1.7 做了9次擾動(dòng)處理 = 4次位運(yùn)算 + 5次異或運(yùn)算
* JDK 1.8 簡(jiǎn)化了擾動(dòng)函數(shù) = 只做了2次擾動(dòng) = 1次位運(yùn)算 + 1次異或運(yùn)算
*/
// JDK 1.7實(shí)現(xiàn)：將 鍵key 轉(zhuǎn)換成 哈希碼（hash值）操作 = 使用hashCode() + 4次位運(yùn)算 + 5次異或運(yùn)算（9次擾動(dòng)）
static final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// JDK 1.8實(shí)現(xiàn)：將 鍵key 轉(zhuǎn)換成 哈希碼（hash值）操作 = 使用hashCode() + 1次位運(yùn)算 + 1次異或運(yùn)算（2次擾動(dòng)）
// 1. 取hashCode值： h = key.hashCode()
// 2. 高位參與低位的運(yùn)算：h ^ (h >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// a. 當(dāng)key = null時(shí)，hash值 = 0击纬，所以HashMap的key 可為null
// 注：對(duì)比HashTable鼎姐，HashTable對(duì)key直接hashCode（），若key為null時(shí)更振，會(huì)拋出異常炕桨，所以HashTable的key不可為null
// b. 當(dāng)key ≠ null時(shí)，則通過(guò)先計(jì)算出 key的 hashCode()（記為h）肯腕，然后 對(duì)哈希碼進(jìn)行 擾動(dòng)處理： 按位 異或（^） 哈希碼自身右移16位后的二進(jìn)制
}
/**
* 計(jì)算存儲(chǔ)位置的函數(shù)分析：indexFor(hash, table.length)
* 注：該函數(shù)僅存在于JDK 1.7 献宫，JDK 1.8中實(shí)際上無(wú)該函數(shù)（直接用1條語(yǔ)句判斷寫出），但原理相同
* 為了方便講解实撒，故提前到此講解
*/
static int indexFor(int h, int length) {
return h & (length-1);
// 將對(duì)哈希碼擾動(dòng)處理后的結(jié)果 與運(yùn)算(&) （數(shù)組長(zhǎng)度-1）姊途，最終得到存儲(chǔ)在數(shù)組table的位置（即數(shù)組下標(biāo)、索引）
}
總結(jié) 計(jì)算存放在數(shù)組 table 中的位置（即數(shù)組下標(biāo)知态、索引）的過(guò)程
- 此處與 JDK 1.7的區(qū)別在于：hash值的求解過(guò)程中 哈希碼的二次處理方式（擾動(dòng)處理）
- 步驟1捷兰、2 = hash值的求解過(guò)程
示意圖.png
示意圖.png
在了解 如何計(jì)算存放數(shù)組table 中的位置 后，所謂 知其然 而 需知其所以然负敏，下面我將講解為什么要這樣計(jì)算贡茅，即主要解答以下3個(gè)問(wèn)題：
- 1.為什么不直接采用經(jīng)過(guò)hashCode（）處理的哈希碼 作為 存儲(chǔ)數(shù)組table的下標(biāo)位置？
- 2.為什么采用 哈希碼 與運(yùn)算(&) （數(shù)組長(zhǎng)度-1） 計(jì)算數(shù)組下標(biāo)其做？
- 3.為什么在計(jì)算數(shù)組下標(biāo)前顶考，需對(duì)哈希碼進(jìn)行二次處理：擾動(dòng)處理？
在回答這3個(gè)問(wèn)題前妖泄，請(qǐng)大家記住一個(gè)核心思想：
所有處理的根本目的驹沿，都是為了提高 存儲(chǔ)key-value的數(shù)組下標(biāo)位置 的隨機(jī)性 & 分布均勻性，盡量避免出現(xiàn)hash值沖突蹈胡。即：對(duì)于不同key渊季，存儲(chǔ)的數(shù)組下標(biāo)位置要盡可能不一樣
問(wèn)題1：為什么不直接采用經(jīng)過(guò)hashCode（）處理的哈希碼 作為 存儲(chǔ)數(shù)組table的下標(biāo)位置？
- 結(jié)論：容易出現(xiàn) 哈希碼 與 數(shù)組大小范圍不匹配的情況审残，即 計(jì)算出來(lái)的哈希碼可能 不在數(shù)組大小范圍內(nèi)梭域，從而導(dǎo)致無(wú)法匹配存儲(chǔ)位置
-
原因描述
示意圖.png
問(wèn)題2：為什么采用 哈希碼 與運(yùn)算(&) （數(shù)組長(zhǎng)度-1） 計(jì)算數(shù)組下標(biāo)斑举？
- 結(jié)論：根據(jù)HashMap的容量大薪两巍（數(shù)組長(zhǎng)度），按需取 哈希碼一定數(shù)量的低位 作為存儲(chǔ)的數(shù)組下標(biāo)位置富玷，從而 解決 “哈希碼與數(shù)組大小范圍不匹配” 的問(wèn)題
- 具體解決方案描述
示意圖.png
問(wèn)題3：為什么在計(jì)算數(shù)組下標(biāo)前璧坟，需對(duì)哈希碼進(jìn)行二次處理：擾動(dòng)處理既穆？
- 結(jié)論：加大哈希碼低位的隨機(jī)性，使得分布更均勻雀鹃，從而提高對(duì)應(yīng)數(shù)組存儲(chǔ)下標(biāo)位置的隨機(jī)性 & 均勻性幻工，最終減少Hash沖突
分析2：putVal(hash(key), key, value, false, true);
此處有2個(gè)主要講解點(diǎn)：
- 計(jì)算完存儲(chǔ)位置后，具體該如何 存放數(shù)據(jù) 到哈希表中
- 具體如何擴(kuò)容黎茎，即 擴(kuò)容機(jī)制
主要講解點(diǎn)1：計(jì)算完存儲(chǔ)位置后囊颅，具體該如何存放數(shù)據(jù)到哈希表中
由于數(shù)據(jù)結(jié)構(gòu)中加入了紅黑樹，所以在存放數(shù)據(jù)到哈希表中時(shí)傅瞻，需進(jìn)行多次數(shù)據(jù)結(jié)構(gòu)的判斷：數(shù)組踢代、紅黑樹、鏈表
與 JDK 1.7的區(qū)別： JDK 1.7只需判斷 數(shù)組 & 鏈表
/**
* 分析2：putVal(hash(key), key, value, false, true)
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 若哈希表的數(shù)組tab為空嗅骄，則 通過(guò)resize() 創(chuàng)建
// 所以胳挎，初始化哈希表的時(shí)機(jī) = 第1次調(diào)用put函數(shù)時(shí)，即調(diào)用resize() 初始化創(chuàng)建
// 關(guān)于resize（）的源碼分析將在下面講解擴(kuò)容時(shí)詳細(xì)分析溺森，此處先跳過(guò)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 計(jì)算插入存儲(chǔ)的數(shù)組索引i：根據(jù)鍵值key計(jì)算的hash值 得到
// 此處的數(shù)組下標(biāo)計(jì)算方式 = i = (n - 1) & hash慕爬，同JDK 1.7中的indexFor（），上面已詳細(xì)描述
// 3. 插入時(shí)屏积，需判斷是否存在Hash沖突：
// 若不存在（即當(dāng)前table[i] == null）医窿，則直接在該數(shù)組位置新建節(jié)點(diǎn)，插入完畢
// 否則炊林，代表存在Hash沖突留搔，即當(dāng)前存儲(chǔ)位置已存在節(jié)點(diǎn)，則依次往下判斷：a. 當(dāng)前位置的key是否與需插入的key相同铛铁、b. 判斷需插入的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹 or 鏈表
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // newNode(hash, key, value, null)的源碼 = new Node<>(hash, key, value, next)
else {
Node<K,V> e; K k;
// a. 判斷 table[i]的元素的key是否與 需插入的key一樣隔显，若相同則 直接用新value 覆蓋 舊value
// 判斷原則：equals（）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b. 繼續(xù)判斷：需插入的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹 or 鏈表
// 若是紅黑樹，則直接在樹中插入 or 更新鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ->>分析3
// 若是鏈表,則在鏈表中插入 or 更新鍵值對(duì)
// i. 遍歷table[i]饵逐，判斷Key是否已存在：采用equals（） 對(duì)比當(dāng)前遍歷節(jié)點(diǎn)的key 與 需插入數(shù)據(jù)的key：若已存在括眠，則直接用新value 覆蓋 舊value
// ii. 遍歷完畢后仍無(wú)發(fā)現(xiàn)上述情況，則直接在鏈表尾部插入數(shù)據(jù)
// 注：新增節(jié)點(diǎn)后倍权，需判斷鏈表長(zhǎng)度是否>8（8 = 桶的樹化閾值）：若是掷豺，則把鏈表轉(zhuǎn)換為紅黑樹
else {
for (int binCount = 0; ; ++binCount) {
// 對(duì)于ii：若數(shù)組的下1個(gè)位置，表示已到表尾也沒(méi)有找到key值相同節(jié)點(diǎn)薄声，則新建節(jié)點(diǎn) = 插入節(jié)點(diǎn)
// 注：此處是從鏈表尾插入当船，與JDK 1.7不同（從鏈表頭插入，即永遠(yuǎn)都是添加到數(shù)組的位置默辨，原來(lái)數(shù)組位置的數(shù)據(jù)則往后移）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 插入節(jié)點(diǎn)后德频，若鏈表節(jié)點(diǎn)>數(shù)閾值，則將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 樹化操作
break;
}
// 對(duì)于i
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 更新p指向下一個(gè)節(jié)點(diǎn)缩幸，繼續(xù)遍歷
p = e;
}
}
// 對(duì)i情況的后續(xù)操作：發(fā)現(xiàn)key已存在壹置，直接用新value 覆蓋 舊value & 返回舊value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 替換舊值時(shí)會(huì)調(diào)用的方法（默認(rèn)實(shí)現(xiàn)為空）
return oldValue;
}
}
++modCount;
// 插入成功后竞思，判斷實(shí)際存在的鍵值對(duì)數(shù)量size > 最大容量threshold
// 若 > ，則進(jìn)行擴(kuò)容 ->>分析4（但單獨(dú)講解钞护，請(qǐng)直接跳出該代碼塊）
if (++size > threshold)
resize();
afterNodeInsertion(evict);// 插入成功時(shí)會(huì)調(diào)用的方法（默認(rèn)實(shí)現(xiàn)為空）
return null;
}
/**
* 分析3：putTreeVal(this, tab, hash, key, value)
* 作用：向紅黑樹插入 or 更新數(shù)據(jù)（鍵值對(duì)）
* 過(guò)程：遍歷紅黑樹判斷該節(jié)點(diǎn)的key是否與需插入的key 相同：
* a. 若相同盖喷，則新value覆蓋舊value
* b. 若不相同，則插入
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
主要講解點(diǎn)2：擴(kuò)容機(jī)制（即 resize（）函數(shù)方法）
-
擴(kuò)容流程如下
- 源碼分析
/**
* 分析4：resize（）
* 該函數(shù)有2種使用情況：1.初始化哈希表 2.當(dāng)前數(shù)組容量過(guò)小难咕，需擴(kuò)容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 擴(kuò)容前的數(shù)組（當(dāng)前數(shù)組）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 擴(kuò)容前的數(shù)組的容量 = 長(zhǎng)度
int oldThr = threshold;// 擴(kuò)容前的數(shù)組的閾值
int newCap, newThr = 0;
// 針對(duì)情況2：若擴(kuò)容前的數(shù)組容量超過(guò)最大值课梳，則不再擴(kuò)充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 針對(duì)情況2：若無(wú)超過(guò)最大值，就擴(kuò)充為原來(lái)的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通過(guò)右移擴(kuò)充2倍
}
// 針對(duì)情況1：初始化哈希表（采用指定 or 默認(rèn)值）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
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) {
// 把每個(gè)bucket都移動(dòng)到新的buckets中
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 { // 鏈表優(yōu)化重hash的代碼塊
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
擴(kuò)容流程（含 與 JDK 1.7 的對(duì)比）
此處主要講解： JDK 1.8擴(kuò)容時(shí)余佃，數(shù)據(jù)存儲(chǔ)位置重新計(jì)算的方式
-
計(jì)算結(jié)論 & 原因解析
9A379F8B0471F604A3FB7E264EC5003B.png
-
數(shù)組位置轉(zhuǎn)換的示意圖
33F3518F9083AE9FA76037C48B3374B3.png
JDK 1.8根據(jù)此結(jié)論作出的新元素存儲(chǔ)位置計(jì)算規(guī)則 非常簡(jiǎn)單惦界，提高了擴(kuò)容效率.
這與 JDK 1.7在計(jì)算新元素的存儲(chǔ)位置有很大區(qū)別：JDK 1.7在擴(kuò)容后，都需按照原來(lái)方法重新計(jì)算咙冗，即
hashCode（）->> 擾動(dòng)處理 ->>（h & length-1））
總結(jié)
-
添加數(shù)據(jù)的流程
-
與 JDK 1.7的區(qū)別
至此沾歪，關(guān)于 HashMap的添加數(shù)據(jù)源碼分析 分析完畢。
步驟3：從HashMap中獲取數(shù)據(jù)
- 假如理解了上述put（）函數(shù)的原理雾消，那么get（）函數(shù)非常好理解灾搏，因?yàn)槎叩倪^(guò)程原理幾乎相同
-
get（）函數(shù)的流程如下：
- 源碼分析
/**
* 函數(shù)原型
* 作用：根據(jù)鍵key，向HashMap獲取對(duì)應(yīng)的值
*/
map.get(key)立润；
/**
* 源碼分析
*/
public V get(Object key) {
Node<K,V> e;
// 1. 計(jì)算需獲取數(shù)據(jù)的hash值
// 2. 通過(guò)getNode（）獲取所查詢的數(shù)據(jù) ->>分析1
// 3. 獲取后狂窑，判斷數(shù)據(jù)是否為空
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 分析1：getNode(hash(key), key))
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 計(jì)算存放在數(shù)組table中的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 4. 通過(guò)該函數(shù)，依次在數(shù)組桑腮、紅黑樹泉哈、鏈表中查找（通過(guò)equals（）判斷）
// a. 先在數(shù)組中找，若存在破讨，則直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// b. 若數(shù)組中沒(méi)有丛晦，則到紅黑樹中尋找
if ((e = first.next) != null) {
// 在樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// c. 若紅黑樹中也沒(méi)有，則通過(guò)遍歷提陶，到鏈表中尋找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
至此烫沙，關(guān)于 “向 HashMap 獲取數(shù)據(jù) “講解完畢。
步驟4：對(duì)HashMap的其他操作
即 對(duì)其余使用API（函數(shù)隙笆、方法）的源碼分析
- HashMap除了核心的put（）锌蓄、get（）函數(shù)，還有以下主要使用的函數(shù)方法
void clear(); // 清除哈希表中的所有鍵值對(duì)
int size(); // 返回哈希表中所有 鍵值對(duì)的數(shù)量 = 數(shù)組中的鍵值對(duì) + 鏈表中的鍵值對(duì)
boolean isEmpty(); // 判斷HashMap是否為空撑柔；size == 0時(shí) 表示為 空
void putAll(Map<? extends K, ? extends V> m); // 將指定Map中的鍵值對(duì) 復(fù)制到 此Map中
V remove(Object key); // 刪除該鍵值對(duì)
boolean containsKey(Object key); // 判斷是否存在該鍵的鍵值對(duì)瘸爽；是 則返回true
boolean containsValue(Object value); // 判斷是否存在該值的鍵值對(duì)；是 則返回true
- 關(guān)于上述方法的源碼的原理 同 JDK 1.7铅忿，此處不作過(guò)多描述
至此剪决，關(guān)于 HashMap的底層原理 & 主要使用API（函數(shù)、方法）講解完畢。
6. 源碼總結(jié)
下面昼捍，用3個(gè)圖總結(jié)整個(gè)源碼內(nèi)容：
總結(jié)內(nèi)容 = 數(shù)據(jù)結(jié)構(gòu)、主要參數(shù)肢扯、添加 & 查詢數(shù)據(jù)流程妒茬、擴(kuò)容機(jī)制
-
數(shù)據(jù)結(jié)構(gòu) & 主要參數(shù)
-
添加 & 查詢數(shù)據(jù)流程
-
擴(kuò)容機(jī)制
