HashMap 是基于哈希表的Map 接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null 值和null 鍵(允許一個null鍵，HashTable不允許entry的鍵或者值為空)。此類不保證映射的順序，特别是它不保證該順序恒久不變。
JDK1.8 之前 HashMap 由
數組+連結清單
組成的，數組是 HashMap 的主體，連結清單則是主要為了解決哈希沖突而存在的（
“拉鍊法”解決沖突
）。JDK1.8 以後在解決哈希沖突時有了較大的變化，當
連結清單長度大于門檻值（預設為 8）時，且tab.length>64時，将連結清單轉化為紅黑樹
，以減少搜尋時間。
【1】底層資料結構分析
JDK1.8 之前 HashMap 底層是
數組和連結清單
結合在一起使用也就是
連結清單散列
。HashMap 通過
key 的 hashCode
經過
擾動函數
處理過後得到
hash 值
，然後通過
(n - 1) & hash值
判斷目前元素存放的位置（這裡的
n 指的是數組的長度
）。如果目前位置存在元素的話，就判斷該元素與要存入的元素的
hash 值以及 key
是否相同，如果相同的話，直接覆寫；不相同就通過拉鍊法解決沖突。
①
hash(Object key)
–擾動函數
所謂擾動函數指的就是
HashMap 的 hash
方法。使用 hash 方法也就是擾動函數是為了防止一些實作比較差的 hashCode() 方法造成的碰撞，換句話說使用擾動函數之後可以減少碰撞。
JDK 1.8 的
hash
方法 相比于 JDK 1.7
hash
方法更加簡化，但是原理不變。
static final int hash(Object key) {
int h;
// key.hashCode()：傳回散列值也就是hashcode
// ^ ：按位異或--相同為0 不同為1
// >>>:無符号右移，符号位随着移動，空位都以0補齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//保留h的高16位，低16位變為原高16位與低16位異或結果
} 對比一下 JDK1.7的 HashMap 的
hash
方法源碼。
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hash(int h)
方法根據
key 的hashCode
重新計算一次散列。此算法加入了高位計算，防止低位不變，高位變化時，造成的hash 沖突。
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次。我們可以看到在HashMap 中要找到某個元素，需要根據
key 的hash 值
來求得對應數組中的位置。如何計算這個位置就是hash 算法。
② 拉鍊法
所謂
“拉鍊法”
就是：将
連結清單和數組
相結合。也就是說建立一個
連結清單數組
，數組中
每一格就是一個連結清單
。若遇到哈希沖突，則将沖突的值加到連結清單中即可。
jdk1.7 HashMap資料結構：
從上圖中可以看出，HashMap 底層就是一個數組結構，數組中的每一項又是一個連結清單。當建立一個HashMap 的時候，就會初始化一個數組。
③ jdk1.8及以後
相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，
當連結清單長度大于門檻值（TREEIFY_THRESHOLD 預設為8）且tab.length>64時，将連結清單轉化為紅黑樹
，以減少搜尋時間。
【2】類的屬性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 預設的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設的填充因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當桶(bucket)上的結點數大于這個值時會轉成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 當桶(bucket)上的結點數小于這個值時樹轉連結清單
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中結構轉化為紅黑樹對應的數組 table的最小大小
//即，如果根據TREEIFY_THRESHOLD 判斷需要轉成紅黑樹時，還要判斷目前容量是否大于MIN_TREEIFY_CAPACITY
//如果小于MIN_TREEIFY_CAPACITY ，則resize；否則轉成紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
// 存儲元素的數組，總是2的幂次倍
transient Node<k,v>[] table;
// 存放具體元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的個數，注意這個不等于數組的長度(table.length)
transient int size;
// 每次擴容和更改map結構的計數器--快速失敗機制有關
transient int modCount;
//The next size value at which to resize (capacity * load factor).
// 臨界值， 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
//預設為16*0.75=12
int threshold;
// 填充因子-負載因子
final float loadFactor;
} - loadFactor加載因子
負載因子loadFactor 定義為：
散清單的實際元素數目(n)/ 散清單的容量(m)
。
loadFactor加載因子是控制數組存放資料的疏密程度，loadFactor越趨近于1，那麼 數組中存放的資料(entry)也就越多，也就越密，也就是會讓連結清單的長度增加;
load Factor
越小，也就是趨近于0,散清單的資料将過于稀疏，對空間造成嚴重浪費。
負載因子衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小。對于使用連結清單法的散清單來說，查找一個元素的平均時間是O(1+a)，是以如果負載因子越大，對空間的利用更充分，然而後果是查找效率的降低 ；如果負載因子太小，那麼散清單的資料将過于稀疏，對空間造成嚴重浪費。loadFactor太大導緻查找元素效率低，太小導緻數組的使用率低，存放的資料會很分散。loadFactor的預設值為
0.75f
是官方給出的一個比較好的臨界值。
給定的
預設容量為 16，負載因子為 0.75
。Map 在使用過程中不斷的往裡面存放資料，當size(數量)達到了
threshold-臨界值- 16 * 0.75 = 12 就需要将目前 16 的容量進行擴容
，而擴容這個過程涉及到 rehash、複制資料等操作，是以非常消耗性能。
- threshold
HashMap 的實作中，通過threshold 字段來判斷HashMap 的最大容量：
threshold = (int)(capacity * loadFactor); 結合負載因子的定義公式可知，
threshold 就是在此loadFactor 和capacity
對應下
允許的最大元素數目
，超過這個數目就重新resize，以降低實際的負載因子。預設的的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時，
resize後的HashMap容量是容量的兩倍
。
【3】Node節點類源碼
Node節點類源碼如下：
// 實作自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
// 哈希值，存放元素到hashmap中時用來與其他元素hash值比較
final int hash;
final K key;//鍵
V value;//值
// 指向下一個節點
Node<K,V> next;
//根據構造函數可知，Node節點包含hash值 key value以及指向下一個結點的引用
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; }
// 重寫hashCode()方法
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() 方法
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;
}
} Object的hashCode(Object o)方法：
public static int hashCode(Object o) {
return o != null ? o.hashCode() : 0;
} TreeNode節點類部分源碼如下：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父
TreeNode<K,V> left; // 左
TreeNode<K,V> right; // 右
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 判斷顔色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 傳回根節點
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
} 【4】HashMap源碼分析
① 構造函數
// 預設構造函數，使用預設加載因子和初始容量 -初始容量為 16，負載因子為 0.75
public More ...HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 包含另一個“Map”的構造函數
public More ...HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);//下面會分析到這個方法
}
// 指定“容量大小”的構造函數并使用預設負載因子0.75
public More ...HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 指定“容量大小”和“加載因子”的構造函數
//initialCapacity：HashMap 的最大容量，即為底層數組的長度。
public More ...HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//根據initialCapacity計算threshold
this.threshold = tableSizeFor(initialCapacity);
} ② putMapEntries方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判斷table是否已經初始化
if (table == null) { // pre-size
// 未初始化，s為m的實際元素個數
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 計算得到的t大于門檻值，則重新指派門檻值
if (t > threshold)
threshold = tableSizeFor(t);
}
// tab已初始化，并且m元素個數大于門檻值，進行擴容處理
else if (s > threshold)
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
} ③ JDK1.8中put方法
HashMap隻提供了put用于添加元素，putVal方法隻是給put方法調用的一個方法，并沒有提供給使用者使用。
對putVal方法添加元素的分析如下：
- ①如果定位到的數組位置沒有元素 就直接插入。
- ②如果定位到的數組位置有元素就和要插入的key比較，如果key相同就直接覆寫，如果key不相同，就判斷p是否是一個樹節點，如果是就調用
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
實作Map.put和相關方法
@param onlyIfAbsent 如果為true，不改變存在的值
@param evict 如果為false，則表處于建立模式
傳回舊值，不存在則傳回null
下面描述中的桶為數組中的節點和該節點後面的連結清單或紅黑樹結點組合體
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p;
int n, i;//n為tab數組長度
// table未初始化或者長度為0，進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// `(n - 1) & hash` 确定元素存放在哪個桶中，如果桶為空，新生成結點放入桶中
//(此時，這個結點是放在數組中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中該位置已經存在元素
else {
Node<K,V> e; K k;
// 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一個元素指派給e，用e來記錄
e = p;
// hash值不相等，即key不相等；判斷是否為紅黑樹結點
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) {
// 如果在尾部則在尾部插入新結點，jdk1.7是插入到連結清單頭部
p.next = newNode(hash, key, value, null);
// 結點數量達到門檻值，嘗試轉化為紅黑樹(沒說一定轉)，具體看下文該方法分析
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循環
break;
}
// 循環周遊過程中，判斷連結清單中結點的key值與插入的元素的key值是否相等，hash是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
p = e;
}//到這for循環結束
}
// 表示在桶中找到key值、hash值與插入元素相等的結點
//或者e是一個新結點
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 通路後回調
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 結構性修改
++modCount;
// 實際大小大于門檻值則擴容
//size 非tab.length
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
} ④ JDK1.7 put方法的代碼
對于put方法的分析如下：
- ①如果定位到的數組位置沒有元素 就直接插入。
- ②如果定位到的數組位置有元素，周遊以這個元素為頭結點的連結清單，依次和插入的key比較，如果key相同就直接覆寫，key不同就采用頭插法插入元素。
public V put(K key, V value)
//判斷是否為空表
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// HashMap 允許存放null 鍵和null 值。
// 當key 為null 時，調用putForNullKey 方法，将value 放置在數組第一個位置。
if (key == null)
return putForNullKey(value);
//擷取key的hash值
int hash = hash(key);
//搜尋指定hash 值在對應table 中的索引。
int i = indexFor(hash, table.length);
//如果 i 索引處的 Entry 不為 null，通過循環不斷周遊 e 元素的下一個元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 從table[i]先周遊
Object k;
//如果hash和key相同，則直接覆寫并傳回舊值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果i 索引處的Entry 為null，表明此處還沒有Entry。
//将key、value 添加到i 索引處。
addEntry(hash, key, value, i);
return null;
} 根據上面
(jdk1.7)put
方法的源代碼可以看出，當程式試圖将一個key-value 對放入HashMap中時，程式首先根據該 key 的 hash值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hash值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較傳回 true，新添加 Entry 的 value 将覆寫集合中原有 Entry 的 value，但key 不會覆寫。如果這兩個 Entry 的 key 通過 equals 比較傳回 false，新添加的 Entry 将與集合中原有 Entry 形成 Entry 鍊，而且
新添加的 Entry 位于 Entry 鍊的頭部
——具體說明繼續看 addEntry() 方法的說明。如果數組該位置上沒有元素，就直接将該元素放到此數組中的該位置上。
addEntry(hash, key, value, i)
方法根據計算出的hash 值，将key-value 對放在數組table的
i
索引處。addEntry 是 HashMap 提供的一個包通路權限的方法，代碼如下：
//JDK1.7中
void addEntry(int hash, K key, V value, int bucketIndex) {
// 擷取指定 bucketIndex 索引處的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新建立的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 如果 Map 中的 key-value 對的數量超過了門檻值
if (size++ >= threshold)
// 把 table 對象的長度擴充到原來的2 倍。
resize(2 * table.length);
} 當系統決定存儲HashMap 中的key-value 對時，完全沒有考慮Entry 中的value，僅僅隻是根據key 來計算并決定每個Entry 的存儲位置。我們完全可以把 Map 集合中的 value 當成 key 的附屬，當系統決定了 key 的存儲位置之後，value 随之儲存在那裡即可。
我們可以看到在HashMap 中要找到某個元素，需要根據key 的hash 值來求得對應數組中的位置。如何計算這個位置就是hash 算法。前面說過jdk1.7中HashMap 的資料結構是數組和連結清單的結合，是以我們當然希望這個HashMap 裡面的
元素位置盡量的分布均勻些
，盡量使得每個位置上的元素數量隻有一個。那麼當我們用hash 算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去周遊連結清單，這樣就大大優化了查詢的效率。
對于任意給定的對象，隻要它的 hashCode() 傳回值相同，那麼程式調用
hash(int h)
方法所計算得到的
hash 碼值
總是相同的。我們首先想到的就是把
hash 值對數組長度取模
運算，這樣一來，元素的分布相對來說是比較均勻的。但是，
“模”運算
的消耗還是比較大的，在HashMap 中是這樣做的：
(n - 1) & hash,n為tab.length
來計算該對象應該儲存在 table 數組的哪個索引處。這個方法非常巧妙，它通過
(n - 1) & hash
來得到該對象的儲存位，而HashMap
底層數組的長度
總是
2 的 n 次方
，這是HashMap 在速度上的優化。
為什麼說
(n-1)&hash
是速度上的優化？請看下面分析。
初始化時HashMap 的容量總是
2 的n
次方，即底層數組的長度總是為2的n 次方。當length 總是 2 的n 次方時，
(n - 1) & hash
運算等價于對length 取模，也就是
hash%n
，但是
&比%
具有更高的效率。
這看上去很簡單，其實比較有玄機的，我們舉個例子來說明。
假設數組長度分别為15 和16，優化後的hash 碼分别為8 和9，那麼&運算後的結果如下：
從上面的例子中可以看出：當它們和
15-1（1110）“與”
的時候，産生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就産生了碰撞，8 和9 會被放到數組中的同一個位置上形成連結清單，那麼查詢的時候就需要周遊這個鍊 表，得到8 或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15 的時候，hash 值會與
15-1（1110）進行“與”
，那麼 最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101 這幾個位置永遠都不能存放元素了，空間浪費相當大。更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味着進一步增加了碰撞的幾率，減慢了查詢的效率！
而當數組長度為16 時，即為2 的n 次方時，
2^n-1
得到的二進制數的每個位上的值都為1，這使得在
低位上&
時，得到的和原
hash 的低位
相同，加之
hash(int h)
方法對key 的hashCode的進一步優化，加入了高位計算，就使得隻有相同的
hash
值的兩個值才會被放到數組中的同一個位置上形成連結清單。是以說，當數組長度為2 的n 次幂的時候，不同的key 算得得index相同的幾率較小，那麼資料在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用周遊某個位置上的連結清單，這樣查詢效率也就較高了。
⑤ get方法
jdk1.8中get方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//根據key的hash值和key擷取一個Node-static class Node<K,V> implements Map.Entry<K,V>
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷第一個數組元素，key的hash值和key值相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 周遊下面節點，桶中不止一個節點
if ((e = first.next) != null) {
// 如果節點為樹結點，就在樹中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在連結清單中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} JDK1.7的get方法如下：
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
} 從HashMap 中get 元素時，首先計算key 的hash，找到數組中對應位置的某一進制素，然後通過key 的equals 方法在對應位置的連結清單中找到需要的元素。在1.7中有一個很明顯的地方是：當 Hash 沖突嚴重時，在桶上形成的連結清單會變的越來越長，這樣在查詢時的效率就會越來越低；時間複雜度為
O(N)
。
從這兩個核心方法（get/put）可以看出 1.8 中對
大連結清單
做了優化，修改為紅黑樹之後查詢效率直接提高到了
O(logn)
。
【5】HashMap 的resize（rehash）
當HashMap 中的元素越來越多的時候，hash 沖突的幾率也就越來越高，因為數組的長度是固定的。是以為了提高查詢的效率，就要對HashMap 的數組進行擴容，數組擴容這個操作也會出現在ArrayList 中，這是一個常用的操作。
而在HashMap 數組擴容之後，最消耗性能的點就出現了：原數組中的資料必須重新計算其在新數組中的位置，并放進去，這就是
resize
。
那麼HashMap 什麼時候進行擴容呢？當HashMap 中的元素個數超過
數組大小*loadFactor
時，就會進行數組擴容，loadFactor 的預設值為0.75，這是一個折中的取值。也就是說，預設情況下，數組大小為16，那麼當HashMap 中元素個數超過
16*0.75=12
的時候，就把數組的大小擴充為
2*16=32
，即擴大一倍，然後重新計算每個元素在數組中的位置。而這是一個非常消耗性能的操作，是以如果我們已經預知HashMap 中元素的個數，那麼預設元素的個數能夠有效的提高HashMap 的性能。
JDK1.8中resize方法如下：
final Node<K,V>[] resize() {
//舊的數組表
Node<K,V>[] oldTab = table;
//舊的tab length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//舊的門檻值
int oldThr = threshold;
int newCap, newThr = 0;
//第一種，舊的tab.length大于0
if (oldCap > 0) {
// 超過最大值就不再擴充了，就隻好随你碰撞去吧
//MAXIMUM_CAPACITY --1<<30
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就将tab.length和threshold擴充為原來的2倍
//DEFAULT_INITIAL_CAPACITY-- 1<<4
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//第二種，tab.length==0，這時 newCap = oldThr;即新的容量為舊的門檻值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//第三種，oldCap ==0 &&oldThr ==0 使用預設值
else {
signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
//重新指派threshold 為newThr
threshold = newThr;
//到這裡，新的容量和新的門檻值都重新指派完畢
//根據新的容量建立新的tab
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //重新指派table 為newTab
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//将其置為null 友善GC
oldTab[j] = null;
//判斷是否有下一個節點
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//根據(n-1)&hash擷取數組下标位置
//判斷是否樹節點
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //連結清單
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;
} 【6】TreeNode的相關方法
① putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)
在putVal方法中判斷目前節點
(p = tab[i = (n - 1) & hash])
是否為TreeNode，如果是，則調用putTreeVal方法。
源碼如下：
//根據hash key 擷取一個Node<K,V> e
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;//pk為根結點的key
//根結點的hash值與将要被放入的元素的hash值比較
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果根結點hash值和key都等于将要被放入元素的hash值和key，則傳回根結點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//如果hash值相等但是key不等，則嘗試周遊左右分支
//判斷kc是否為可比較類，如果是；
//則判斷if pk matches kc，如果是傳回k.compareTo(pk)，否則傳回0。
else if ((kc == null && (kc = comparableClassFor(k)) == null)
||
(dir = compareComparables(kc, k, pk)) == 0) {
//如果沒有搜尋過
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//周遊左右分支，根據h k kc找到一個結點
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;
}
}
} ② getTreeNode(int h, Object k)
在get方法中擷取一個結點時，如果該結點為樹結點，就會調用getTreeNode(int h, Object k)方法。
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
//這裡kc為null
}
/**
* 根據hash和key從root查找一個node
* 當第一次使用comparing keys，kc緩存comparableClassFor(key)
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果ph>h,則p=p.left
if ((ph = p.hash) > h)
p = pl;
//如果ph<h,則p=p.right
else if (ph < h)
p = pr;
//如果hash和key都相等，直接傳回p
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//如果hash相等，key不等，判斷pl是否為null ，如果pl為null，就p=p.right
else if (pl == null)
p = pr;
//如果hash相等，key不等，判斷pr是否為null ，如果pr為null，就p=p.left
else if (pr == null)
p = pl;
//如果hash相等，key不等，且pl pr均不為null，判斷kc
//就根據dir 判斷給p指派pl還是pr
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//從右邊開始查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
} ③ treeifyBin(Node<K,V>[] tab, int hash)
替換給定index處(使用hash确定)“桶”的連接配接節點，在put中
if (binCount >= TREEIFY_THRESHOLD - 1)
就會調用
treeifyBin(Node<K,V>[] tab, int hash)
方法，嘗試轉為紅黑樹。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//首先判斷tab.length，不合适就擴容；
//tab.length大于等于MIN_TREEIFY_CAPACITY時才進行紅黑樹轉換
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//拿到數組中index處的元素
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//循環周遊，把每個e替換為TreeNode
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
//傳回一個新的TreeNode
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
} ④ split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)
在resize中，如果結點為TreeNode，則調用該方法：
/*Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
* */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
} 【7】Fail-Fast 機制
我們知道java.util.HashMap 不是線程安全的，是以如果在使用疊代器的過程中有其他線程修改了map，那麼将抛出ConcurrentModificationException，這就是所謂fail-fast 政策。
這一政策在源碼中的實作是通過modCount 域，modCount 顧名思義就是修改次數，對HashMap 内容的修改都将增加這個值，那麼在疊代器初始化過程中會将這個值賦給疊代器的expectedModCount。
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
} 在疊代過程中，判斷modCount 跟expectedModCount 是否相等，如果不相等就表示已經有其他線程修改了Map。
在HashMap 的API 中指出，由所有HashMap 類的“collection 視圖方法”所傳回的疊代器都是快速失敗的：在疊代器建立之後，如果從結構上對映射進行修改，除非通過疊代器本身的 remove 方法，其他任何時間任何方式的修改，疊代器都将抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不冒在将來不确定的時間發生任意不确定行為的風險。
注意，疊代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發修改時，不可能作出任何堅決的保證。快速失敗疊代器盡最大努力抛出 ConcurrentModificationException。是以，編寫依賴于此異常的程式的做法是錯誤的，正确做法是：疊代器的快速失敗行為應該僅用于檢測程式錯誤。
【8】HashMap的一些問題
① 在并發場景下使用時容易出現死循環
如下圖所示，使用1000個線程并發往map中放資料：
因為在HashMap擴容的時候會調用resize（）方法，就是這裡的并發操作容易在一個桶上形成環形連結清單。這樣當擷取一個不存在的 key 時，計算出的 index 正好是環形連結清單的下标就會出現死循環。如圖：
② HashMap的并發問題
hashmap在插入新的階段的時候，多個線程同時插入，會把除了最後的那個線程的其它線程插入的結點丢失。
對于修改的時候，多個線程修改，會隻保留最後的一個線程的修改結果。
擴容的時候，會隻保留最後一個線程的擴容後的那個數組。