本篇結構：
- 前言
- HashMap的資料結構
- 常用方法及周遊選擇
- HashMap中的重要參數
- 源碼分析
- 疑問解答
一、前言
HashMap在日常軟體開發中用得很多，它很友善，使用也簡單，這樣一個經常陪在我們身邊的容器對象，當然應該好好研究一下啦，畢竟了解了本質，才能更好的相處。這和日常處朋友是一樣的。
二、HashMap的資料結構
2.1、基本資料結構
資料結構的知識是薄弱環節，這裡就隻簡單介紹下HashMap的結構。
在JDK1.8之前，HashMap的實作是基于數組+連結清單的形式，當往一個HashMap中放資料時，根據key計算得到hashCode，經過進一步處理得到數組（Hash表）的下标，然後存放資料。
如果存在兩個key，計算出相同的數組下标，即出現hash沖突，這時就通過一個連結清單來維持這個關系，後put的值放在連結清單的尾部。
大緻是這樣的結構：
為解決哈希碰撞後出現連結清單過程導緻索引效率變慢的問題，JDK1.8之後引入了紅黑樹（連結清單的時間複雜度是O(n)，紅黑樹為O(logn)），當連結清單長度大于8後，連結清單轉為紅黑樹。
ps:漫畫算法：什麼是紅黑樹？
2.2、HashMap數組元素和連結清單的節點
HashMap中存的是Key-Valve鍵值對。
1.數組元素和連結清單節點是采用Node類實作
Node類是HashMap中的一個靜态内部類，實作了Map.Entry接口（在JDK1.8之前，是采用Entry類實作）。
可以看看Node類的源碼：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值，HashMap根據該值确定記錄的位置
final K key; // key
V value; // value
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;
}
// 判斷2個Node是否相等的依據是Key和Value都相等
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.紅黑樹節點是采用TreeNode類實作
TreeNode也是HashMap的靜态内部類，繼承LinkedHashMap.Entry，簡單列下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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
...
}
三、常用方法及周遊選擇
V get(Object key); // 獲得指定鍵的值
V put(K key, V value); // 添加鍵值對
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的鍵值對 複制到此Map中
V remove(Object key); // 删除該鍵值對
boolean containsKey(Object key); // 判斷是否存在該鍵的鍵值對；是 則傳回true boolean
containsValue(Object value); // 判斷是否存在該值的鍵值對；是 則傳回true
Set keySet(); // 單獨抽取key序列，将所有key生成一個Set
Collection values(); // 單獨value序列，将所有value生成一個Collection
void clear(); // 清除哈希表中的所有鍵值對
int size(); // 傳回哈希表中所有鍵值對的數量 = 數組中的鍵值對 + 連結清單中的鍵值對
boolean isEmpty(); // 判斷HashMap是否為空；size == 0時 表示為空
public class HashMapTest {
public static void main(String[] args) {
// 1. new
Map<String, Integer> map = new HashMap<String, Integer>();
// 2. put
map.put("Android", 1);
map.put("Java", 2);
map.put("iOS", 3);
// 3. get
System.out.println("key = Java：" + map.get("Java"));
// 4. 周遊HashMap ------------ start
// 核心思想：
// 步驟1：獲得key-value對（Entry） 或 key 或 value的Set集合
// 步驟2：周遊上述Set集合(使用for循環 、 疊代器（Iterator）均可)
// 方法共有3種：分别針對 key-value對（Entry） 或 key 或 value
// 4.1：獲得key-value的Set集合，再周遊
iterate1(map);
// 4.2：獲得key的Set集合，再周遊
iterator2(map);
// 方法3：獲得value的Set集合，再周遊
iterator3(map);
// 4. 周遊HashMap ------------ end
}
/**
* 獲得key-value的Set集合，再周遊
* @param map
*/
static void iterate1(Map<String, Integer> map){
System.out.println("method 1: iterate Set<Entry<K, V>> start..........");
// 1.獲得key-value對（Entry）的Set集合
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
// 2.周遊Set集合，進而擷取key-value
// 3.for循環
for(Map.Entry<String, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}
System.out.println("method 1: iterate Set<Entry<K, V>> end..........");
}
/**
* 獲得key的Set集合，再周遊
* @param map
*/
static void iterator2(Map<String, Integer> map){
System.out.println("method 2: iterate Set<Key> start..........");
// 1.獲得key的Set集合
Set<String> keySet = map.keySet();
// 2.周遊Set集合，進而擷取key，再擷取value
// 3.for循環
for(String key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}
System.out.println("method 2: iterate Set<Key> end..........");
}
/**
* 獲得value的Set集合，再周遊
* @param map
*/
static void iterator3(Map<String, Integer> map){
System.out.println("method 3: iterate Set<Value> start..........");
// 1. 獲得value的Set集合
Collection valueSet = map.values();
// 2. 周遊Set集合，進而擷取value
// 2.1 獲得values 的Iterator
Iterator iter = valueSet.iterator();
// 2.2 通過周遊，直接擷取value
while (iter.hasNext()) {
System.out.println(iter.next());
}
System.out.println("method 3: iterate Set<Value> end..........");
}
}
對于周遊方式，具體的情況有不同的選擇：
- 如果隻是周遊key，使用keySet是最好的選擇，周遊Map.Entry效率相差不大；
- 如果隻周遊Value，周遊Map.Entry和valueSet都可，而通過keySet的方式效率會稍差，因為要通過get(key)的方式擷取value（get的時間複雜度取決于for循環的次數），會多出一部分消耗；
- 如果既要Key，又要Value，周遊Map.Entry。
四、HashMap中的重要參數
// 預設容量16（1<<4 = 00001中的1向左移4位 = 10000 = 十進制的2^4=16）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 = 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 實際加載因子
final float loadFactor;
// 預設加載因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空的存儲實體
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 擴容門檻值（threshold）：當哈希表的大小 ≥ 擴容門檻值時，就會擴容哈希表（即擴充HashMap的容量）
// a. 擴容 = 對哈希表進行resize操作（即重建内部資料結構），進而哈希表将具有大約兩倍的桶數
// b. 擴容門檻值 = 容量 x 加載因子
int threshold;
// 存儲資料的Node類型數組，長度 = 2的幂；數組的每個元素 = 1個單連結清單
transient Node<K,V>[] table;
// HashMap中存儲的鍵值對的數量
transient int size;
//用于快速失敗，由于HashMap非線程安全，在對HashMap進行疊代時，如果期間其他線程的參與導緻HashMap的結構發生變化了（比如put，remove等操作），需要抛出異常ConcurrentModificationException
transient int modCount;
/**
* 與紅黑樹相關的參數
*/
// 1. 桶的樹化門檻值：即 連結清單轉成紅黑樹的門檻值，在存儲資料時，當連結清單長度 > 該值時，則将連結清單轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 2. 桶的連結清單還原門檻值：即 紅黑樹轉為連結清單的門檻值，當在擴容（resize（））時（此時HashMap的資料存儲位置會重新計算），在重新計算存儲位置後，當原有的紅黑樹内數量 < 6時，則将 紅黑樹轉換成連結清單
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小樹形化容量門檻值：即 當哈希表中的容量 > 該值時，才允許樹形化連結清單 （即 将連結清單 轉換成紅黑樹）
// 否則，若桶内元素太多時，則直接擴容，而不是樹形化
// 為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
五、源碼分析
5.1、構造方法
在正常構造器中，并沒有馬上為數組table配置設定記憶體空間（有一個入參為指定Map的構造器例外），事實上是在執行第一次put操作的時候才真正建構table數組。
先看看如何執行個體化一個HashMap：
public class HashMapConstructor {
public static void main(String[] args) {
Map<String, String> map = constructorMap1();
}
static <K, V> Map<K, V> constructorMap1(){
return new HashMap<>();
}
static <K, V> Map<K, V> constructorMap2(int capacity){
// 實際上是調用指定“容量大小”和“加載因子”的構造函數
return new HashMap<>(capacity);
}
static <K, V> Map<K, V> constructorMap3(int capacity, float loadFactor){
return new HashMap<>(capacity, loadFactor);
}
static <K, V> Map<K, V> constructorMap4(Map<K, V> map){
return new HashMap<>(map);
}
}
再來看具體的源碼：
/**
* 構造函數1：預設構造函數（無參）
* 加載因子 & 容量（預設） = 0.75、16
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 構造函數2：指定“容量大小”的構造函數
* 加載因子（預設）= 0.75 、容量 = 指定大小
* 注：此處不是真正的門檻值，僅僅隻是将傳入的容量大小轉化為：>傳入容量大小的最小的2的幂，該門檻值後面會重新計算
*/
public HashMap(int initialCapacity) {
// 實際上是調用指定“容量大小”和“加載因子”的構造函數
// 隻是在傳入的加載因子參數 = 預設加載因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 構造函數3：指定“容量大小”和“加載因子”的構造函數
* 注：此處不是真正的門檻值，僅僅隻是将傳入的容量大小轉化為：>傳入容量大 小的最小的2的幂，該門檻值後面會重新計算
*/
public 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;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 将傳入的容量大小轉化為：>大于傳入容量大小的最小的2的幂
*/
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;
}
/**
* 構造函數4：包含“子Map”的構造函數
* 即 構造出來的HashMap包含傳入Map的映射關系
* 加載因子 & 容量（預設） = 0.75、16
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将傳入的子Map中的全部元素逐個添加到HashMap中
putMapEntries(m, false);
}
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);
}
// 已初始化，并且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);
}
}
}
5.2、put
public V put(K key, V value) {
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;
// 1.table未初始化或者長度為0，進行擴容
// 這裡可以發現初始化哈希表的時機 = 第1次調用put函數時，即調用resize() 初始化建立
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.計算插入存儲的數組索引i：(n - 1) & hash
// 3.取出數組中該索引處的元素（也是連結清單中的第一個Node元素），若為空，則直接在該數組位置建立節點，插入完畢
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 4.若不為空，即該索引處已經有節點元素存在，需判斷是否有hash沖突
else {
Node<K,V> e; K k;
// a.如果桶中第一個元素(即連結清單中的第一個節點，也即數組中的節點)和新加入的元素的hash值相等，key相等，會直接用新值替換舊值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一個元素指派給e
e = p;
// b.若新插入的元素與桶中第一個元素hash值不相等，即key不相等，需判斷是連結清單還是紅黑樹
// 若為紅黑樹，調用相應方法加入
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 若是為連結清單
else {
// 周遊連結清單
for (int binCount = 0; ; ++binCount) {
// (e = p.next) == null表示到達連結清單的尾部，如果成立，說明連結清單中沒有節點的Key值和新加入的元素的Key值相同
if ((e = p.next) == null) {
// 在連結清單最末插入結點
p.next = newNode(hash, key, value, null);
// 結點數量達到門檻值，轉化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循環
break;
}
// 判斷連結清單中結點的key值與插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
p = e;
}
}
// 表示在桶中找到key值、hash值與插入元素相等的結點
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 通路後回調，預設實作為空
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 結構性修改，用于多線程時抛出異常
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 預設實作為空
return null;
}
put方法大緻過程：
1.如果是第一次調用put，會先調用resize方法初始化table數組，預設容量16；
2.計算插入存儲的數組索引i，判斷該索引下數組是否有Node節點，若沒有，直接插入；
3.若存在，需判斷是否有hash沖突：
a.若新插入的Key和數組中該索引下的Node元素Key（連結清單中的第一個Node元素）相同（hash相同，Key也相同），則直接替換；
b.若新插入的Key與連結清單中的第一個Node元素Key不相同，就接着周遊，分連結清單和紅黑樹兩種形式，都是存在就替換，不存在就加入；
4.插入成功後，判斷實際存在的鍵值對數量size > 最大容量threshold，進而決定是否需要擴容。
5.3、get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table已經初始化，長度大于0，并且根據hash尋找table中的項（也即連結清單中的首節點）也不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶中第一項(數組元素)相等，直接傳回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 否則周遊桶中的節點
if ((e = first.next) != null) {
// 為紅黑樹節點，在紅黑樹中查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否則，在連結清單中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
5.4、resize
final Node<K,V>[] resize() {
// 儲存之前table為old table
Node<K,V>[] oldTab = table;
// 儲存之前table大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 儲存之前table門檻值
int oldThr = threshold;
int newCap, newThr = 0;
// 之前table大小大于0
if (oldCap > 0) {
// 之前table大于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 門檻值為最大整形，直接傳回
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍（使用左移，效率更高）後，小于最大容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 門檻值翻倍，使用左移，效率更高
newThr = oldThr << 1; // double threshold
}
// 之前門檻值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 之前容量oldCap = 0并且之前門檻值oldThr = 0，使用預設值（如使用HashMap()構造函數，之後再插入一個元素會調用resize函數，會進入這一步）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新門檻值為0
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"})
// 新初始化一個newCap容量大小的table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 更新table數組
table = newTab;
// 之前的table已經初始化過
if (oldTab != null) {
// 複制元素，重新進行hash
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 { // preserve order
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
進行擴容，會伴随着一次重新hash配置設定，并且會周遊hash表中所有的元素，是非常耗時的。在編寫程式中，要盡量避免resize。
六、疑問解答
6.1、HashMap的長度為什麼要是2的n次方？
1.效率更高
一般利用hash碼計算出一個數組的索引，常用方式是"h % length"，也就是求餘的方式，但這種方式效率不如位運算，恰好又有"當容量是2^n時，h & (length - 1) == h % length"。
2.更符合Hash算法均勻分布，減少碰撞
length-1的值是所有二進制位全為1，這種情況下，index 的結果等同于 HashCode 後幾位的值，隻要輸入的 HashCode 本身分布均勻，Hash 算法的結果就是均勻的。
HashMap的長度為什麼設定為2的n次方
6.2、modCount變量的作用
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
從forEach循環中可以發現 modCount 參數的作用。就是在疊代器疊代Map中的元素時，不能編輯（增加，删除，修改）Map中的元素。如果在疊代時修改，則抛出ConcurrentModificationException異常。
6.3、為什麼在計算數組下标前，需對哈希碼進行二次處理：擾動處理？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這是JDK1.8中根據Key計算hash值的方法，然後用這個hash值去計算數組下标(hash & (length-1))，觀察上面的 hash 方法，發現并不是直接用 hashCode 與 length-1 做位運算，而是(h = key.hashCode()) ^ (h >>> 16)，為什麼這麼處理？
是為了加大哈希碼低位的随機性（因為 length 是2的n次方， length-1 的二進制全是1，這樣同 hash 值與運算時，數組下标就取決于 hash 值的低位），使得分布更均勻，進而提高對應數組存儲下标位置的随機性 & 均勻性，最終減少Hash沖突。
6.4、為什麼 HashMap 中 String、Integer 這樣的包裝類适合作為 key 鍵
因為String是不可變的，而且已經重寫了equals()和hashCode()方法了。其他的包裝類也有這個特點。
不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和擷取時傳回不同的hashcode的話，那麼就不能從HashMap中找到你想要的對象。
不可變性還有其他的優點如線程安全。如果可以僅僅通過将某個field聲明成final就能保證hashCode是不變的，那麼請這麼做吧。因為擷取對象的時候要用到equals()和hashCode()方法，那麼鍵對象正确的重寫這兩個方法是非常重要的。如果兩個不相等的對象傳回不同的hashcode的話，那麼碰撞的幾率就會小些，這樣就能提高HashMap的性能。
6.5、重新調整HashMap大小存在什麼問題嗎？
當多線程的情況下，可能産生條件競争，如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試着調整大小。
JDK1.7中，在調整大小的過程中，存儲在連結清單中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會将元素放在連結清單的尾部，而是放在頭部，這是為了避免尾部周遊(tail traversing)。
此時若（多線程）并發執行 put（）操作，一旦出現擴容情況，則 容易出現 環形連結清單，進而在擷取資料、周遊連結清單時 形成死循環（Infinite Loop），即 死鎖的狀态。
JDK1.7相關擴容：
void resize(int newCapacity) {
// 1. 儲存舊數組（old table）
Entry[] oldTable = table;
// 2. 儲存舊容量（old capacity ），即數組長度
int oldCapacity = oldTable.length;
// 3. 若舊容量已經是系統預設最大容量了，那麼将門檻值設定成整型的最大值，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 4. 根據新容量（2倍容量）建立1個數組，即新table
Entry[] newTable = new Entry[newCapacity];
// 5. （重點分析）将舊數組上的資料（鍵值對）轉移到新table中，進而完成擴容 ->>分析1.1
transfer(newTable);
// 6. 新數組table引用到HashMap的table屬性上
table = newTable;
// 7. 重新設定門檻值
threshold = (int)(newCapacity * loadFactor);
}
/**
* 作用：将舊數組上的資料（鍵值對）轉移到新table中，進而完成擴容
* 過程：按舊連結清單的正序周遊連結清單、在新連結清單的頭部依次插入
*/
void transfer(Entry[] newTable) {
// 1. src引用了舊數組
Entry[] src = table;
// 2. 擷取新數組的大小 = 擷取新容量大小
int newCapacity = newTable.length;
// 3. 通過周遊 舊數組，将舊數組上的資料（鍵值對）轉移到新數組中
for (int j = 0; j < src.length; j++) {
// 3.1 取得舊數組的每個元素
Entry<K, V> e = src[j];
if (e != null) {
// 3.2 釋放舊數組的對象引用（for循環後，舊數組不再引用任何對象）
src[j] = null;
do {
// 3.3 周遊 以該數組元素為首 的連結清單
// 注：轉移連結清單時，因是單連結清單，故要儲存下1個結點，否則轉移後連結清單會斷開
Entry<K, V> next = e.next;
// 3.3 重新計算每個元素的存儲位置
int i = indexFor(e.hash, newCapacity);
// 3.4 将元素放在數組上：采用單連結清單的頭插入方式 = 在連結清單頭上存放資料 = 将數組位置的原有資料放在後1個指針、将需放入的資料放到數組位置中
// 即 擴容後，可能出現逆序：按舊連結清單的正序周遊連結清單、在新連結清單的頭部依次插入
e.next = newTable[i];
newTable[i] = e;
// 通路下1個Entry鍊上的元素，如此不斷循環，直到周遊完該連結清單上的所有節點
e = next;
} while (e != null);
// 如此不斷循環，直到周遊完數組上的所有資料元素
}
}
}
JDK 1.8 轉移資料操作 = 按舊連結清單的正序周遊連結清單、在新連結清單的尾部依次插入，是以不會出現連結清單 逆序、倒置的情況，故不容易出現環形連結清單的情況。但 JDK 1.8 還是線程不安全，因為無加同步鎖保護。
參考博文：
Java源碼分析：關于 HashMap 1.8 的重大更新