一、HashMap概述
1、HashMap概述
HashMap以key-value形式存儲資料，key允許為null，value也允許為null。
HashMap線程不安全，需要線程安全的HashMap可以使用ConcurrentHashMap。
HashMap底層是數組，又被稱為hash桶，每個桶中存放的是連結清單，連結清單中的節點存儲着集合中的元素。
JDK 1.8中當hash桶中連結清單長度達到 8 的時候會轉成紅黑樹。
當HashMap中的元素數量達到threshold門檻值的時候，會觸發擴容，hash桶的長度翻倍。
HashMap中hash桶的長度一定是 2 ^ n。
HashMap中對于key落在哪個桶上，不僅僅會計算hashCode，還會經過擾動函數擾動使得key的分布更加均勻。
今天下面所有的分析都是基于JDK 1.8 的HashMap。
2、HashMap計算key在hash桶中落點的算法
HashMap的get方法會根據key的hashCode值計算出這個key的落點在hash桶的那個位置上。
通常這種計算hash值落點算法可以使用取餘法，根據餘數選擇落點位置。
但是HashMap考慮到新能問題，利用了位運算的一個特性，将Hash桶的長度規定為 2 ^ n，然後利用tab[(tableSize - 1) & hash來得出不同hash值在hash桶中的落點位置。
3、hash()方法的擾動函數
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
hash()方法使用來擷取key的hash值的，我們知道是哈希函數映射的比較均勻的話，碰撞的機率會小一些。
我們可以看到hash()方法中對key的hashCode值還進行了異或運算，下面來分析一下這樣做的原因。
通過上面的分析我們知道計算key再hash桶中的落點采用了tab[(tableSize - 1) & hash算法，也就是取hash值的後幾位來作為判斷hash桶落點的依據。其實也就是對tableSize進行取餘。
而hashCode的取值範圍是Integer.MAX_VALUE，如果對tableSize進行取餘的話，會忽略掉高位的數，隻有低位的幾個數會參與運算。
是以采用了異或運算，将 hashCode ^ (hashCode >>> 16) 将會使得hashCode的每一位都參與到取餘運算中，這樣就會使得哈希函數映射更加的均勻，降低hash碰撞的機率。
JDK 1.7中的擾動函數：
final int hash(Object k) {
int h = hashSeed;
if ( != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
JDK 1.7中的擾動函數會對key進行四次擾動，可能考慮到過多次的擾動意義其實不大，是以JDK 1.8中将擾動函數修改為一次就好。
4、HashMap的構造方法
HashMap一共有四個構造方法：
public HashMap(){...}
public HashMap(int initialCapacity){...}
public HashMap(int initialCapacity, float loadFactor) {...}
public HashMap(Map<? extends K, ? extends V> m) {...}
其中前三個構造方法都是初始化一個空的HashMap，第四個構造方法會構造一個HashMap然後将參數中的 m 中的元素一一put到構造出來的HashMap中。
下面先來了解一下前三個構造方法：
要了解HashMap的構造方法需要先了解幾個常量個成員變量
//hash桶的預設長度
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
//預設加載因子
static final float DEFAULT_LOAD_FACTOR = f;
//HashMap中元素數量
transient int size;
//hash桶，用來存放連結清單和紅黑樹
transient Node<K,V>[] table;
//HashMap中元素的門檻值，當size > threshold時，将發生擴容
int threshold;
//加載因子
final float loadFactor;
其中table被transient修飾，是以HashMap在序列化的過程中不會序列化size屬性。
其中size被transient修飾，是以HashMap在序列化的過程中不會序列化size屬性。
其中loadFactor被final修飾，是以一個HashMap對象的loadFactor一旦在對象初始化的時候被設定，就不能再進行修改。
第一個構造方法其實就是HashMap(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR)
第二個方法其實就是HashMap(initialCapacity, DEFAULT_LOAD_FACTOR)
第三個構造方法這兩個變量都由HashMap對象建立的時候傳入。
我們可以發現在初始化構造HashMap的時候并沒有給table數組指派，是以初始化HashMap的時候hash桶的size是 0，需要在第一次put操作的時候才會給hash桶指派。這段指派代碼在resize方法中，下面講到resize方法的時候再一起講。
這裡我們針對第三個構造方法拿出來講一下：
public HashMap(int initialCapacity, float loadFactor) {
//initialCapacity合法性校驗
if (initialCapacity < )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//initialCapacity最大值校驗
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactor合法性校驗
if (loadFactor <= || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//設定HaspMap對象的loafFactor
this.loadFactor = loadFactor;
//設定HaspMap對象的threshold
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ;
}
tableSizeFor這個方法使用了位運算的技巧，将傳回第一個大于cap并且滿足2 ^ n的數。
調用這個方法是為了将threshold設定為滿足 2 ^ n 的數，之後在第一個put操作的時候會将這個threshold作為hash桶的size。
這樣我們就成功的控制了hash桶的size滿足 2 ^ n。
5、連結清單節點Node
下面我們來看一下連結清單中的節點Node，至于紅黑樹中的節點TreeNode這裡不做介紹：
static class Node<K,V> implements Map.Entry<K,V> {
//存放元素key的hash值
final int hash;
//存放元素的key
final K key;
//存放元素的value
V value;
//指向連結清單中下一個Node
Node<K,V> next;
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; }
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 = value;
value = newValue;
return oldValue;
}
//重寫equals方法，隻有當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;
}
}
其中Node節點中存放一個hash字段來記錄hash值而不是每次使用的時候再計算是因為每個Node的hash值都需要經過擾動函數的擾動，并且擴容的時候需要計算每個Node的hash值，是以出于空間換時間的想法，在Node節點中加入了hash字段。
6、擴容方法
當table沒有初始化時進行put操作或者size > threshold的時候會進行擴容
final Node<K,V>[] resize() {
//目前hash桶
Node<K,V>[] oldTab = table;
//目前hash桶的大小
int oldCap = (oldTab == null) ? : oldTab.length;
//目前hashMap的門檻值
int oldThr = threshold;
//初始化新的hash桶的大小和hashMap門檻值
int newCap, newThr = ;
//如果目前hash桶的大小大于0
if (oldCap > ) {
//如果目前hash桶的大小到達最大值，不再進行擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果目前hash桶的大小未達到最大值，将新的hash桶大小翻倍
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果舊的hash桶大小 >= 16，那麼新的hashMap門檻值也翻倍
newThr = oldThr << ; // double threshold
}
//如果目前hash桶大小為 0，但是門檻值不為 0
//那麼表示初始化的HashMap對對象進行擴容
else if (oldThr > )
//将目前hashMap的門檻值指派給新hash桶的大小
//此時門檻值和hash桶大小一緻
newCap = oldThr;
//如果目前hash桶的大小和hashMap門檻值都是0
else {
//設定新hash桶大小為預設值 16
newCap = DEFAULT_INITIAL_CAPACITY;
//設定新hashMap門檻值為 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果目前hashMap的門檻值為 0
if (newThr == ) {
//根據目前hash桶的大小和加載因子計算新的門檻值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新門檻值
threshold = newThr;
//根據新hash桶的大小建構新的Node數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新建構的Node數組指派給table
table = newTab;
//省略部分是将目前hash桶中所有的節點轉移到新的hash桶中
...
return newTab;
}
上面這段代碼分析了擴容過程中關于hash桶的大小以及hashMap門檻值的變化，看完這段可以比較清晰的了解擴容時Node數組的變化。
二、HashMap擴容詳細分析
其中關于擴容過程集合中的元素從原hash桶中向新hash桶的轉移過程沒有介紹，下面來介紹一下擴容時元素的轉移過程。
1、JDK 1.7中HashMap擴容過程
是以這裡先簡單分析一下JDK 1.7中的擴容過程：
void resize(int newCapacity) {
//目前hash桶
Entry[] oldTable = table;
//目前hash桶大小
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
//如果目前hash桶大小達到上限，将門檻值設定為Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return;
}
//根據傳入的newCapacity建立新的hash桶數組
Entry[] newTable = new Entry[newCapacity];
//專業元素
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//将新建構的Node數組指派給table
table = newTable;
//更新門檻值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
}
//轉移元素方法
void transfer(Entry[] newTable, boolean rehash) {
//新hash桶大小
int newCapacity = newTable.length;
//周遊目前hash桶
for (Entry<K,V> e : table) {
//如果桶中元素不是空，進入循環
while(null != e) {
//使用next指針指向連結清單下一個節點
//防止下一個節點丢失
Entry<K,V> next = e.next;
//根據hashseed的值來判斷是否需要使用rehash來減少Hash碰撞
if (rehash) {
e.hash = null == e.key ? : hash(e.key);
}
//找出key需要存放在新hash桶中的位置
int i = indexFor(e.hash, newCapacity);
//将目前轉移的元素插入到新hash桶指定位置連結清單表頭
e.next = newTable[i];
newTable[i] = e;
//轉移目前轉移元素在舊hash桶中的下一個元素
e = next;
}
}
}
//使用 & 運算代替取餘算法計算需要配置設定的has桶位置
static int indexFor(int h, int length) {
return h & (length-);
}
上面這一段是JDK 1.7中對HashMap擴容使用的算法，簡單概括一下擴容流程：
- 計算新hash桶的大小和門檻值
- 根據新hash桶的大小生成新的hash桶數組
- 對目前hash桶中的元素進行轉移
- 周遊hash桶
- 周遊制定下标hash桶中的待轉移節點
- 根據節點hash值算出在新hash桶中的下标
- 使用頭插法将待轉移的節點插入到新hash桶中的單連結清單上
- 将新hash桶以及新hash桶的大小以及門檻值設定到目前HashMap對象
2、JDK 1.7中HashMap擴容可以優化的地方
下面講一下JDK 1.7中HashMap擴容過程中可以優化的地方，也就是JDK 1.8中優化的地方。
頭插法
下關于待轉移元素插入新hash桶時采用了頭插法，在之前的文章待轉移元素位置的選擇
我們假設一個key的hash值是 x，目前hash桶的大小是 n，這個key在目前hash桶中的位置 i = x / n（其實HashMap采用的是 x & (n-1)，這裡為了好了解采用取餘算法）;
擴容的時候新hash桶的大小将變成 2n，那麼這個key在新hash桶中的位置 j = x / 2n。
我們可以很輕易的得出 j = i 或者 j = i + n。
是以原hash桶中某個下标為 i 的連結清單中的節點在擴容後一定會落在新hash桶中下标為 i 或 i + n 的位置上。
那麼如果 x & n == 0 表示這個key會落在新hash桶中下标為 i 的位置，如果 x & n ！= 0 表示這個key會落在新hash桶中下标為 i + n 的位置。
連結清單太長，查詢效率會低
如果連結清單長度太長，那麼HashMap的查詢效率會降低，可以考慮樹結構。
3、JDK 1.8 HashMap擴容過程
final Node<K,V>[] resize() {
//目前hash桶
Node<K,V>[] oldTab = table;
//目前hash桶的大小
int oldCap = (oldTab == null) ? : oldTab.length;
//目前hashMap的門檻值
int oldThr = threshold;
//初始化新的hash桶的大小和hashMap門檻值
int newCap, newThr = ;
//如果目前hash桶的大小大于0
if (oldCap > ) {
//如果目前hash桶的大小到達最大值，不再進行擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果目前hash桶的大小未達到最大值，将新的hash桶大小翻倍
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果舊的hash桶大小 >= 16，那麼新的hashMap門檻值也翻倍
newThr = oldThr << ; // double threshold
}
//如果目前hash桶大小為 0，但是門檻值不為 0
//那麼表示初始化的HashMap對對象進行擴容
else if (oldThr > )
//将目前hashMap的門檻值指派給新hash桶的大小
//此時門檻值和hash桶大小一緻
newCap = oldThr;
//如果目前hash桶的大小和hashMap門檻值都是0
else {
//設定新hash桶大小為預設值 16
newCap = DEFAULT_INITIAL_CAPACITY;
//設定新hashMap門檻值為 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果目前hashMap的門檻值為 0
if (newThr == ) {
//根據目前hash桶的大小和加載因子計算新的門檻值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新門檻值
threshold = newThr;
//根據新hash桶的大小建構新的Node數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新建構的Node數組指派給table
table = newTab;
if (oldTab != null) {
//周遊目前hash桶
for (int j = ; j < oldCap; ++j) {
//定義節點e用來指向待轉移的節點
Node<K,V> e;
//如果目前下标為 j 的桶中沒有元素，直接結束
if ((e = oldTab[j]) != null) {
//将目前下标為 j 的桶釋放
oldTab[j] = null;
//如果目前桶的中隻有一個節點
//直接計算出該key在新hash桶中對應的位置
if (e.next == null)
//這裡又一次使用了 & 代替取餘算法
newTab[e.hash & (newCap - )] = e;
//如果目前節點存在于樹中而不是連結清單中
else if (e instanceof TreeNode)
//采用紅黑樹的轉移邏輯，這裡暫不做介紹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果目前節點存在于連結清單中而不是樹中
else {
//定義低位連結清單的頭尾節點
Node<K,V> loHead = null, loTail = null;
//定義高位連結清單的頭尾節點
//其中高位連結清單在hash桶中的下标比低位節點大oldCap
Node<K,V> hiHead = null, hiTail = null;
//定義臨時節點
Node<K,V> next;
do {
//使用next指針指向連結清單下一個節點
//防止下一個節點丢失
next = e.next;
//利用 & 運算得出key落在低位連結清單中
if ((e.hash & oldCap) == ) {
//如果低位連結清單為空
//直接将待轉移元素置為表頭
if (loTail == null)
loHead = e;
//低位連結清單不為空
//采用尾插法将待轉移元素插入到低位連結清單中
else
loTail.next = e;
//更新低位連結清單尾指針
loTail = e;
}
//利用 & 運算得出key落在高位連結清單中
else {
//執行邏輯和低位連結清單一緻，不再贅述
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
//循環直到目前hash桶對應下标中沒有元素為止
} while ((e = next) != null);
//如果低位連結清單不為空
//将低位連結清單指派給低位hash桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//如果高位連結清單不為空
//将低位連結清單指派給高位hash桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上面這一段是JDK 1.8中對HashMap擴容使用的算法，簡單概括一下擴容流程：
- 計算新hash桶的大小和門檻值
- 根據新hash桶的大小生成新的hash桶數組，如果目前hash桶為空，構造一個長度預設的hash桶（JDK 1.7中在擴容前會先檢查目前hash桶是否為空）
- 将新hash桶以及新hash桶的大小以及門檻值設定到目前HashMap對象
- 對目前hash桶中的元素進行轉移
- 周遊hash桶
- 周遊指定下标hash桶中的待轉移節點
- 如果指定下标hash桶中待轉移節點隻有一個，直接計算在新hash桶中的落點并轉移到新hash桶中
- 如果指定下标hash桶中存儲的是樹，按照樹的結構來轉移（暫不做介紹）
- 如果指定洗标hash桶中存的是連結清單
- 建立低位連結清單頭尾指針和高位連結清單頭尾指針
- 将待轉移元素按照尾插法插入到低位連結清單和高位連結清單中
- 将低位hash桶和高位hash桶分别指向低位連結清單和高位連結清單
- 傳回新的hash桶
4、JDK 1.7 和 JDK 1.8關于HashMap擴容的差別
- JDK 1.7在擴容前會判斷hash桶是否為空，如果為空會提前建立；JDK 1.8會在擴容時檢查hash桶是否為空
- JDK 1.7采用頭插法将待轉移元素插入到新hash桶連結清單中，多線程場景下會導緻死循環；JDK 1.8采用尾插法，規避了死循環的情況
- JDK 1.7擴容後連結清單中的元素會倒置；JDK 1.8擴容後連結清單中的元素不會倒置
- 由于JDK 1.8對于連結清單長度達到 8 時會轉成紅黑樹，是以擴容過程中考慮到了紅黑樹的情況
- JDK 1.8在連結清單轉移的時候引入了低位連結清單和高位連結清單進行轉移，效率更高
雖然JDK 1.8中規避了HashMap擴容過程中遇到的死循環問題，但是HashMap仍然是線程不安全的，JDK 1.8隻是對HashMap做了一些優化，但是多線程場景下還是不能使用HashMap的。
三、HashMap常用方法源碼
下面再來分析一下HashMap中常用的方法。
下面部分文章基于JDK 1.8，就不再介紹JDK 1.7中的方法了。
1、get()方法
public V get(Object key) {
//定義臨時節點用于傳回結果
Node<K,V> e;
//先調用hash(key)方法獲得key的hash值
//調用getNode方法找到Node節點
//如果Node節點不存在傳回null，存在的話傳回Node節點的value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//使用擾動函數使得hash值分布更加均勻
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
//根據hash和key查詢Node節點
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//tab[(n - 1) & hash]可以找到key對應在hash桶中的位置
//如果hash桶不為空并且key對應hash桶的位置上存在節點，進入周遊
if ((tab = table) != null && (n = tab.length) > &&
(first = tab[(n - ) & hash]) != null) {
//如果第一個節點的hash值和key值和目前查詢的key一緻，直接傳回第一個節點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//第一個節點的hash值或者key值和查詢的key不一緻
//并且存在下一個節點，執行下面方法
if ((e = first.next) != null) {
//如果目前節點在紅黑樹中
if (first instanceof TreeNode)
//調用getTreeNode方法獲得紅黑樹中對應的節點（暫時不做介紹）
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果目前節點不在紅黑樹中，也就是連結清單中，進入循環
do {
//如果循環中某個節點的hash值和key值一緻，傳回這個節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
//當不存在下一個節點的時候結束循環
} while ((e = e.next) != null);
}
}
//如果hash桶為空或者key對應hash桶的位置上不存在節點，傳回null
return null;
}
上面這一段是HashMap中get()方法的源碼，簡單概括一下擴容流程：
- 計算需要查詢的key的hash值
- 判斷hash桶是不是空以及該hash值對應在hash桶上是否存在節點，不存在直接傳回null
- 對比頭節點的hash值和key是否和需要查詢的key一緻，如果一緻直接傳回頭節點
- 判斷頭節點在紅黑樹中還是連結清單中
- 如果在紅黑樹中，則在紅黑樹中查找該節點
- 如果在連結清單中，則周遊連結清單查詢該節點
下面來分析幾個小細節：
細節一、先比較hash再比較key
我們發現判斷HashMap中節點是否是需要查詢的key的時候使用的判斷條件是
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
會先比較一下hash值是否一緻再比較key是否相等，這麼做是也是為了查詢效率。
因為通常key都會重寫equals方法，通過equals方法比較的效率明顯是比hash值比較要慢的。
是以再equals判斷之前先比較一次hash值可以提前規避很多不符合的節點，效率上會高一些。
細節二、先比較頭節點，再周遊連結清單（紅黑樹）
我們發現當取到key對應hash桶中的節點的時候，會先比較一下頭節點是否是我們需要查詢的節點，如果不符，再去周遊連結清單（紅黑樹）。
因為在hash算法足夠分散的情況下，很多hash桶的每一個桶中都隻會存在一個節點，是以先比較第一個節點再去周遊也能帶來效率上的提升。
2、put()方法
public V put(K key, V value) {
//先調用hash(key)方法獲得key的hash值
//調用putVal方法插入資料，并傳回結果
return 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;
//如果hash桶為空
if ((tab = table) == null || (n = tab.length) == )
//擴容并将擴容後hash桶的大小指派給n
n = (tab = resize()).length;
//如果key對應hash桶的位置上沒有節點
if ((p = tab[i = (n - ) & hash]) == null)
//将put進來的key，value生成一個Node節點
//并将該節點指派給hash桶指定下标上
tab[i] = newNode(hash, key, value, null);
//如果key對應hash桶的位置上有節點
else {
//定義臨時變量
Node<K,V> e; K k;
//如果頭節點的hash值和key和需要put的key一緻
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将頭節點指派給臨時變量p，用于下面傳回
e = p;
//如果頭節點的hash值和key和需要put的key不一緻
//并且頭節點在紅黑樹中
else if (p instanceof TreeNode)
//調用紅黑樹的putTreeVal方法将key，value設定到紅黑樹中
//并且如果紅黑樹中存在該key，将對應的value指派給e
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果頭節點的hash值和key和需要put的key不一緻
//并且頭節點在連結清單中
else {
//累計便利次數，用于在下面連結清單長度達到 8 的時候轉成紅黑樹
for (int binCount = ; ; ++binCount) {
//如果連結清單中不存在下一個節點
if ((e = p.next) == null) {
//将put進來的key，value生成一個Node節點
//并将該節點按照尾插法插入到連結清單尾部
p.next = newNode(hash, key, value, null);
//如果便利次數達到 7 次，那麼插入新節點後連結清單長度将達到 8
if (binCount >= TREEIFY_THRESHOLD - )
//将連結清單轉成紅黑樹
treeifyBin(tab, hash);
//跳出循環
break;
}
//如果連結清單中節點的hash值和key和需要put的key一緻
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//跳出循環
break;
//連結清單中對應節點指派給臨時節點p
p = e;
}
}
//如果e != null，表示連結清單（紅黑樹）中存在相同的key
if (e != null) { // existing mapping for key
//記錄舊值，用于傳回
V oldValue = e.value;
//如果onlyIfAbsent == false或者舊值為空（這裡下面再講）
if (!onlyIfAbsent || oldValue == null)
//使用調用put方法傳遞進來的value覆寫連結清單中節點中的value
e.value = value;
//這個方法是為LinkedHashMap留的後路
afterNodeAccess(e);
//傳回舊值
return oldValue;
}
}
//能走到這一步，在上面if (e != null)判斷中 e == null
//表示新增了元素而不是替換了元素
//modCount記錄了HashMap在節點數量上變化的次數，在這裡加一
++modCount;
//目前HashMap中元素加一，并且和門檻值比較
if (++size > threshold)
//如果目前HashMap中元素數量大于門檻值，進行擴容
resize();
//這個方法是為LinkedHashMap留的後路
afterNodeInsertion(evict);
//由于是新增節點，沒有覆寫舊節點的值，傳回null
return null;
}
上面這一段是HashMap中put()方法的源碼，簡單概括一下擴容流程：
- 計算需要put的key的hash值
- 判斷hash桶是不是空，為空先進行擴容
- 判斷該key值對應在hash桶上是否存在節點，不存在則直接在hash桶中建立節點
- 對比頭節點的hash值和key是否和需要查詢的key一緻，如果一緻直接覆寫頭節點
- 判斷頭節點在紅黑樹中還是連結清單中
- 如果在紅黑樹中，則在紅黑樹中查找該節點，如果在連結清單中，則周遊連結清單查詢該節點
- 如果在連結清單（紅黑樹）中存在節點的hash值和key和需要put的key一緻，進行覆寫操作
- 如果不存在，建立新的節點，添加到連結清單（紅黑樹）中
- 如果目前HashMap中元素數量超過門檻值，進行擴容
- 如果put()方法覆寫了某個節點，則傳回這個節點的value，否則傳回null
下面我們來分析一下這段代碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (!onlyIfAbsent || oldValue == null)
//使用調用put方法傳遞進來的value覆寫連結清單中節點中的value
e.value = value
...
}
通過這段代碼我們發現，如果put方法的key在HashMap中存在，put方法一定會使用新的值去覆寫舊的值；如果putVal方法的key在HashMap中存在，隻有在舊值為空的情況下putVal方法才會使用新的值去覆寫舊的值。
3、clear()方法
public void clear() {
//定義臨時變量
Node<K,V>[] tab;
//将HashMap節點變化次數加一（如果目前hash桶是空也會增加）
modCount++;
//如果目前hash桶不是空，則周遊hash桶，hash桶中所有的桶都置空
if ((tab = table) != null && size > ) {
size = ;
for (int i = ; i < tab.length; ++i)
tab[i] = null;
}
}
clear()方法很簡單，就不做介紹了。
4、總結
到這裡，關于HashMap的get()、put()、clear()方法的源碼也都看完了。
這篇文章把HashMap主要的源碼和實作方式介紹了一下，關于紅黑樹方面的内容都略過了，沒有做過多介紹，以後有時間再分享一下紅黑樹相關的源碼。
喜歡這篇文章的朋友，歡迎掃描下圖關注公衆号lebronchen，第一時間收到更新内容。
![Java集合2-HashMap詳解（含源碼分析）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)