不論是android面試還是java面試，都會問到hashmap的原理和怎么實現的，今天我們就來總結下；
一、HashMap(數組+鏈表+紅黑樹)原理
HashMap底層使用數組，每個數組元素存的是Node類型（或者TreeNode），table的每一個位置，又可以稱為Hash桶，也就是說，會將相同hash值的元素存放到一個Hash桶中（這里的hash值，是指對key計算的hash值），也就是在Table的下標中相同，為了解決同一個位置有多個元素（沖突），HashMap用來拉鏈法和紅黑樹兩種數據結構來解決沖突
1、數據結構參數的含義
// 閾值（容量*加載因子）。當HashMap中的鍵值對超過了該值，HashMap就會進行擴容
int threshold;
// 哈希表的加載因子，描述的是HashMap滿的程度。接近0表示很空，1表示填滿了
final float loadFactor;
// 默認的初始容量-必須是2的冪，默認值是16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 能存的最大元素數量。默認值是1 << 30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認的加載因子0.75，當map中的元素個數達到容量的75%時會觸發擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶的樹化閾值：即鏈表轉成紅黑樹的閾值，在存儲數據時，當鏈表長度 > 該值時，則將鏈表轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 桶的鏈表還原閾值：即紅黑樹轉為鏈表的閾值，當原有的紅黑樹內數量 < 6 時，則將紅黑樹轉換成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹形化容量閾值：即當哈希表中的容量 > 該值時，允許鏈表轉換成紅黑樹，否則直接擴容
static final int MIN_TREEIFY_CAPACITY = 64;
2、構造方法：
// 構造一個空的HashMap，具有默認的初始容量
public HashMap() {
// 負載系數，默認值是0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 使用指定的初始值構造一個空的HashMap
public HashMap(int initialCapacity) {
// 初始容量和負載系數
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 使用指定的初始值構造一個空的HashMap
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;
}
3、Node節點和TreeNode節點
在HashMap中，存的value不是put的K-V，而是一個Node類型，還有一個TreeNode類型，可以和Node類型相關轉換
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V 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;
}
}4、hash計算以及確定下標
/**
* 計算key的hash值：
* 1.如果key為null，則hash值為0
* 2.如果key不為null，將key的hashCode值和高16位進行異或計算（異或：相同為0，不同為1）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
5、resize擴容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold表示觸發擴容的閾值（size >= capacity * loadfactor時會擴容）
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap大于0證明已經對map進行過操作，并非剛創建map的時候
if (oldCap > 0) {
// 如果當前容量允許的大于最大容量，則將閾值設置為整數最大值，不會進行復制操作
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果2倍舊容量未超過允許的最大容量，并且舊容量達到了默認的初始容量16，則新的擴容閾值設置2倍的舊容量
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 使用HashMap(capacity)或者HashMap(capacity, loadFactor)創建map
// 這是初次擴容，新容量設置為threshold，也就是capacity*loadFactor
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 第一次擴容，使用new HashMap()這種方式創建map，容量和負載因子都使用默認
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 設置下一次進行擴容的閾值
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;
// 下面是將舊數組中的元素復制到新申請的數組中
// 因為在舊數組中節點的索引計算方式：oldIndex=(oldCapacity - 1) & key.hash，
// 當數組的容量發生變化后，需要重新確定節點的索引，新的節點位置有兩種可能：
// 1.newIndex=oldIndex，索引不變，前提是key.hash & oldCapacity結果為0
// 2.newIndex=oldIndex+oldCapacity，不是第一種情況，就是第二種情況
if (oldTab != null) {
// 遍歷舊數組（oldCap長度）
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
// 遍歷鏈表，將鏈表分為兩部分，一部分（loHead）是索引不變，一部分（hiHead）的新索引是 oldIndex+oldCapacity
// 然后將鏈表放入對應的數組中
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;
}關于擴容，在Java7的HashMap中，如果發生多線程更改HashMap（同時擴容），則可能會引起鏈表產生環的問題，這是因為Java7只是使用了數組加鏈表，插入鏈表的時候使用頭插法，并且在擴容的時候鏈表節點的順序會發生改變；而Java8在插入節點時使用是尾插法，在擴容的時候鏈表節點的順序不會發生改變，可以避免出現環的問題。但這并不能說明Java8的HashMap就可以支持并發修改，因為其內部很多操作都沒有保證原子性（比如兩個線程同時插入元素，size++，都未做原子性保證。?
6、resize時紅黑樹的split拆分
和鏈表一樣，紅黑樹中的元素也需要挨個確定新索引位置，同樣是分為2部分，一部分是索引不變，一部分的新索引為oldIndex+oldCapacity。
注意：split是HashMap中的內部類TreeNode的方法，而不是HashMap的方法。
/**
* 擴容時，對同一個hash桶中的元素（紅黑樹）進行拆分，有可能拆分為兩部分
* part1.節點的hash和原數組的容量與之后為0 -> 移到新表后，索引和舊表保持不變
* part2.節點的hash和原數組的容量與之后不為0 -> 移到新表后，新索引為"oldIndex+oldCapacity"
* 這兩部分，在做完拆分后，判斷是否需要將樹轉換為鏈表，如果各自的數量未超過UNTREEIFY_THRESHOLD(默認為6)，則需轉換為鏈表
*
* @param map hashMap實例本身
* @param tab 擴容新申請的數組
* @param index 本次要拆分的下標索引（對應舊數組）
* @param bit 舊數組的容量
*/
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
// loHead鏈著索引不變的節點
TreeNode<K,V> loHead = null, loTail = null;
// hiHead鏈著索引改變的節點
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;
// 如果當前節點和原數組的容量與之后為0，則擴容后的索引位置和與在舊表保持一致
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
} else {
// 如果當前節點和原數組的容量與之后不為0，則擴容后的索引位置為"oldIndex+oldCapacity"
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;
// 高位節點不為空，說明原鏈表元素被拆分了，切地位紅黑樹節點個數大于6，不滿足轉鏈表條件，需要重新樹化
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;
// 低位節點不為空，說明原鏈表元素被拆分了，切地位紅黑樹節點個數大于6，不滿足轉鏈表條件，需要重新樹化
if (loHead != null)
hiHead.treeify(tab);
}
}
}
7、鏈表轉紅黑樹
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果map的容量（數組的長度）為0，或者小于MIN_TREEIFY_CAPACITY（默認64），則進行擴容操作，而不進行轉換紅黑樹
// 底層數組，也稱為hash桶，也就是說hash桶的數量小于64時，則會進行擴容操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
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);
}
}8、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;
// 初始狀態，HashMap為空，則需要擴容，n為擴容后的容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 要放入的位置沒有其他項（沒有沖突），則直接放入該位置
tab[i] = newNode(hash, key, value, null);
else {
// 計算后，要放入的位置已經有了其他項，需要解決沖突（拉鏈法或者紅黑樹）
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 上一步操作后，p指向的該"桶"的第一個Node，判斷位置是否匹配，如果位置匹配，且key相同，表示是put的數據已經存在，直接覆蓋即可
e = p;
else if (p instanceof TreeNode)
// 如果p指向的是TreeNode，也就是紅黑樹存儲的節點，那么就將新增元素加入到紅黑樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// p指向的是鏈表頭結點，則利用尾插法，將新節點插入到末尾（遍歷過程中發現相同節點則進行覆蓋）
for (int binCount = 0; ; ++binCount) {
// 走到尾節點
if ((e = p.next) == null) {
// 將新節點插到末尾
p.next = newNode(hash, key, value, null);
// 判斷鏈表的長度是否達到樹化的閾值，如果是，則將鏈表轉換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 注意并不一定會轉換為紅黑樹，還與tab的長度有關，tab.length<MIN_TREEIFY_CAPACITY時，仍舊采取擴容，而非樹化
treeifyBin(tab, hash);
break;
}
// 如果是已經存在的節點，則中斷循環，后面將進行覆蓋value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 數據已經存在，則進行覆蓋操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 計數加一（用來快速失?。?br> ++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}9、get操作
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* get的時候，最關鍵的就是，先根據key的hash值找到桶位置，然后在根據key來查找
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 根據key進行hash后的位置存在數據，如果不存在，則直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 根據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) {
// 如果節點時紅黑樹的節點類型，則遍歷紅黑樹，進行查找
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;
}10、remove操作
remove有兩個接口，remove(key)、remove(key,value)，內部都是調用一個removeNode方法，如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 實現了Map接口中的remove方法
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// map不為空，且hash對應的位置不為空，才進行查找，否則認為未找到，返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 匹配hash地址的第一個節點是否匹配，hash和key都匹配，則證明找到了要刪除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 遍歷紅黑樹
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 遍歷鏈表
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果node為null，證明未找到key對應的元素
// node不為null，則根據調用的remove(key)還是remove(key,value)來判斷
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 要刪除的節點匹配，如果是樹節點類型，則從樹中刪除節點
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 要刪除的節點時第一個節點時，直接將頭結點的下一個節點往前提一個位置（舊頭節點被刪除）
tab[index] = node.next;
else
// 非頭結點，修改指針，將下一個節點賦給父節點的next
p.next = node.next;
// 修改次數加一，元素數量減一
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}二、hashmap常見的面試題
1.講下對HashMap的認識
- HashMap 存儲的是鍵值對 key - value，key 具有唯一性，采用了鏈地址法來處理哈希沖突。當往 HashMap 中添加元素時，會計算 key 的 hash 值取余得出元素在數組中的的存放位置。
- HashMap底層的數據結構在 JDK1.8 中有了較大的變化，1.8之前采用數組加鏈表的數據結構，1.8采用數組加鏈表加紅黑樹的數據結構。
- HashMap 是線程不安全的，線程安全可以使用 HashTable 和 ConcurrentHashMap 。
- 在 1.8 版本的中 hash() 和 resize( ) 方法也有了很大的改變，提升了性能。
- 鍵和值都可存放null，鍵只能存放一個null，鍵為null時存放入table[0]。
2.HashMap的一些參數
//HashMap的默認初始長度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap的最大長度2的30次冪
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap的默認加載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap鏈表升級成紅黑樹的臨界值
static final int TREEIFY_THRESHOLD = 8;
//HashMap紅黑樹退化成鏈表的臨界值
static final int UNTREEIFY_THRESHOLD = 6;
//HashMap鏈表升級成紅黑樹第二個條件：HashMap數組(桶)的長度大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap底層Node桶的數組
transient Node<K,V>[] table;
//擴容閾值，當你的hashmap中的元素個數超過這個閾值，便會發生擴容
//threshold = capacity * loadFactor
int threshold;
3.為什么HashMap的長度必須是2的n次冪？
- 在計算存入結點下標時，會利用 key 的 hsah 值進行取余操作，而計算機計算時，并沒有取余等運算，會將取余轉化為其他運算
- 當n為2次冪時，會滿足一個公式：(n - 1) & hash = hash % n，就可以用位運算代替取余運算，計算更加高效
4.HashMap 為什么在獲取 hash 值時要進行位運算
換種問法：能不能直接使用key的hashcode值計算下標存儲？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}如果使用直接使用hashCode對數組大小取余，那么相當于參與運算的只有hashCode的低位，高位是沒有起到任何作用的，所以我們的思路就是讓 hashCode取值出的高位也參與運算，進一步降低hash碰撞的概率，使得數據分布更平均，我們把這樣的操作稱為擾動。
(h >>> 16)是無符號右移16位的運算，右邊補0，得到 hashCode 的高16位。
(h = key.hashCode()) ^ (h >>> 16) 把 hashCode 和它的高16位進行異或運算，可以使得到的 hash 值更加散列，盡可能減少哈希沖突，提升性能。
而這么來看 hashCode 被散列 (異或) 的是低16位，而 HashMap 數組長度一般不會超過2的16次冪，那么高16位在大多數情況是用不到的，所以只需要拿 key 的 HashCode 和它的低16位做異或即可利用高位的hash值，降低哈希碰撞概率也使數據分布更加均勻。
5.HashMap在JDK1.7和JDK1.8中有哪些不同？ HashMap的底層實現
在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易；所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，使用一種叫做拉鏈法的方式可以解決哈希沖突。
JDK1.8主要解決或優化了以下問題：
resize 擴容和 計算hash 優化
引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考;
解決了多線程死循環問題，但仍是非線程安全的，多線程時可能會造成數據丟失問題
6.HashMap的put方法的具體流程？
源碼，上面有代碼
HashMap是懶加載，只有在第一次put時才會創建數組。
- 判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；
- 根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；
- 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals；
- 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；
- 遍歷table[i]，并記錄遍歷長度，如果遍歷過程中發現key值相同的，則直接覆蓋value，沒有相同的key則在鏈表尾部插入結點，插入后判斷該鏈表長度是否大等于8，大等于則考慮樹化，如果數組的元素個數小于64，則只是將數組resize，大等于才樹化該鏈表；
- 插入成功后，判斷數組中的鍵值對數量size是否超過了閾值threshold，如果超過，進行擴容。
7.HashMap 的 get 方法的具體流程？
源碼，上面有代碼
- 首先根據 hash 方法獲取到 key 的 hash 值；
- 然后通過 hash & (length - 1) 的方式獲取到 key 所對應的Node數組下標 ( length對應數組長度 )；
- 首先判斷此結點是否為空，是否就是要找的值，是則返回空，否則判斷第二個結點是否為空，是則返回空，不是則判斷此時數據結構是鏈表還是紅黑樹
- 鏈表結構進行順序遍歷查找操作，每次用 == 符號 和 equals( ) 方法來判斷 key 是否相同，滿足條件則直接返回該結點。鏈表遍歷完都沒有找到則返回空；
- 紅黑樹結構執行相應的 getTreeNode( ) 查找操作；
8.HashMap的擴容操作是怎么實現的？
不管是JDK1.7或者JDK1.8 當put方法執行的時候，如果table為空，則執行resize()方法擴容，默認長度為16；
JDK1.7擴容
條件：發生擴容的條件必須同時滿足兩點
特點：先擴容，再添加（擴容使用的頭插法），頭插法會使鏈表發生反轉，多線程環境下可能會死循環
JDK1.8擴容
條件：
- 當前存儲的數量大于等于閾值
- 當某個鏈表長度>=8，但是數組存儲的結點數size() < 64時
- 特點：先插后判斷是否需要擴容（擴容時是尾插法）
- 缺點：多線程下，1.8會有數據覆蓋
9.鏈表升級成紅黑樹的條件
鏈表長度大于8時才會考慮升級成紅黑樹，是有一個條件是 HashMap 的 Node 數組長度大于等于64（不滿足則會進行一次擴容替代升級）；
10.紅黑樹退化成鏈表的條件
- 擴容 resize( ) 時，紅黑樹拆分成的 樹的結點數小于等于臨界值6個，則退化成鏈表；
- 刪除元素 remove( ) 時，在 removeTreeNode( ) 方法會檢查紅黑樹是否滿足退化條件，與結點數無關。如果紅黑樹根 root 為空，或者 root 的左子樹/右子樹為空，root.left.left 根的左子樹的左子樹為空，都會發生紅黑樹退化成鏈表；
11.HashMap是怎么解決哈希沖突的？
- 使用鏈地址法（使用散列表）來鏈接擁有相同下標的數據；
- 使用2次擾動函數（hash函數）來降低哈希沖突的概率，使得數據分布更平均；
- 引入紅黑樹進一步降低遍歷的時間復雜度，使得遍歷更快；
