前言
HashMap 是 Java 中一個很常用的容器，不過也是面試的重災區，問題的方式多種多樣。
本文着重講述 HashMap 在JDK 1.7 和 Jdk 1.8 下的原理以及一些面試可能會被問到的問題。
現在先來看看自己能否回答得上這些問題，答案能得滿分嗎？
1.為什麼要用 HashMap，你知道其底層原理嗎？
2.HashMap 中的 hash 值有什麼用？
3.為什麼 HashMap 中的數組長度必須是 2 的幂次方？
4.為什麼建議用 String Integer 這樣的包裝類作為 HashMap 的鍵？
5.JDK 1.7中為什麼會形成死循環？
6.紅黑樹的概念，它的原理是什麼，為什麼要用它？
...
如果對于上面這些問題還不清楚，别急，和我一起往下看。
✔️ 本文閱讀時長約為: 20min
為什麼要用到 HashMap
在 Java 中我們經常用 ArrayList 作為容器來儲存一些資料，它的底層是由順序表實作的，自然查詢快并且是随機通路，但是在其中間增删效率就很慢了。那它的兄弟 LinkedList 怎麼樣呢？LinkedList 底層是由連結清單實作的，連結清單我們知道 增删效率高，但是查找效率慢，每次查詢都要從頭節點開始向後查找 。難道沒有一種容器能綜合它們的優點嗎？诶有，這時候該我們的 HashMap 登場了。
⭐⭐ HashMap 通過鍵值對進行存儲，通過鍵進行查詢，在 JDK 1.7及以前 底層實作是一個 數組 + 連結清單 的形式，而在 JDK 1.7以後 底層是 數組 + 連結清單 + 紅黑樹 。
JDK 1.7及以前的 HashMap
// 數組結構
transient Entry<K,V>[] table;
// 這是連結清單結構中的節點，用于解決 hash碰撞，加入一個 next 記錄下一個節點
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k ;
hash = h;
}
複制代碼 JDK 1.7及以前 -> 數組 + 連結清單
HashaMap HashMap 除了 map 總和 hash 有關 ，那麼這個 hash 到底是什麼？我們知道 Object 類有一個 native 方法叫做 hashCode，傳回的是一個 int 類型的值，那它又有什麼用呢？沒錯，它在我們的 HashMap 中展現出來了。我們來看看 HashMap 中的 hash 方法。
final int hash(Object k) {
// k 是作為目前鍵的對象
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32 ((string) k);
}
h = hashSeed;
}
// 每個對象都有一個 hashCode 值
h ^= k.hashCode() ;
h ^= (h >>> 20) ~ (h >>> 12);
// 通過這些位運算來得到 HashMap 中的 hash
return h ^ (h >>> 7) ^ (h >>> 4);
}
複制代碼 在 HashMap 中通過 hash() 可以得到一個值，而這個值與後續存放資料的下标有關。
// 确定目前鍵值對存放在數組中的下标
static int indexFor(int h, int length) {
// 用計算出的 hash 按位與 上(length - 1)，算出對應數組的下标
return h & (length - 1);
}
複制代碼 這裡的 length 是有一個隐藏的機制，它最開始預設是 16，後面遇到擴容都會 << 1，也就是說 length 永遠是 2的幂次方 。那這 ... 是為什麼呢？
⛅ 我們再來看看這個方法傳回的是什麼。h & (length - 1) ，這句代碼目的是求出數組中的下标，用來存放目前這對鍵值對，那求出的值必須在 0 - (lenght - 1) 之内，是以我們可以大膽猜測，這就是一個求模運算！可是 & 和 % 肯定是不同的操作，按位與怎麼就相當于求模運算了呢？ 這正是因與 length 特殊的限定有關。因為 length 是一個 2的幂次方的數 ，是以減去1後，低位每一位都是1。比如 length = 16，減去以1後就是 00001111，這時候再與 h 按位與就相當于 length 和 h 求模運算了。是以 length是2的幂次方 ，此外轉化成二進制後，1 分布得很均勻，與 h 按位與時得出的結果在 length 上也是均勻的，進而在數組中也是均勻分布，是以有效減少了 hash碰撞 。
public v put(K key, V value) {
if (key == null)
return putForNullKey(value);
// 通過 key 計算hash值
int hash = hash(key);
// 通過 key 找到數組中待存放的下标
int i = indexFor(hash, table.length);
// 連結清單
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
object k;
// 如果這個數組下标中有元素，開始周遊連結清單
if (e.hash == hash && ((k = e.key) == key || key .equals(k))) {
// 如果兩個 hash 值相同，或者鍵相同，則修改 value
V oldValue = e.value;
e.value = Value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 可能兩個 hash 值不同，但計算出的 index 一樣，這就發生了 hash碰撞
// 使用頭插法，将其放在連結清單頭部
addEntry (hash, key, value, i)
return null;
}
複制代碼 addEntry() 内部調用 createEntry()。
void createEntry (int hash, K key, v value, int bucketIndex) {
Entry<K,V> e = table[bueketIndex];
// 注意這裡将 e 傳進去
// 也就是說這裡使用的是 頭插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
複制代碼 ⚡ JDK 1.7 用的是 頭插法 ，這是造成 HashMap 形成死循環的原因之一。⚡
我們剛剛看了 put() 的源碼，做個總結，到這裡我們知道 HashMap 底層是一個 數組 + 連結清單 的一個結構。它會通過計算 key 的 hash值 ，進而與 length - 1 進行按位與算出數組所在的下标。如果算出的 index 和其它元素重複，我們稱之為 哈希碰撞 ，這時會将新來的 鍵值對 放在其對應數組下标的連結清單的第一位(頭插法) 。
現在我們從宏觀上來看看 put() 的整個過程。
PS：做動畫的時候想成尾插了，這裡大家注意一下，不要被誤導，JDK 1.7就是頭插法
前兩個節點算出來的 index 都是 4，發生了 hash碰撞，是以第二個節點通過 頭插法 的方式，放到了連結清單的頭部，第三個節點的 index 是 1，放在了數組下标為 1 的地方。
好了，put() 我們講完後，get() 就不在話下了，它的原理還是和 put() 一樣，先通過 hash 計算出對應數組的下标，然後就去連結清單中周遊，最後傳回相應的結果。現在來講講幾個重要的變量。
// 初始大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 向左位移4位，也就是16
// 加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
複制代碼 HashMap 預設大小就是 16，這個加載因子與它的大小乘積叫作 threshold 門檻值，一旦超過了這個值，HashMap 就會進行一次擴容。不過請大家思考一下，HashMap中擴容會造成什麼問題？
沒錯，一旦擴容 HashMap 中的數組長度就會增加，而我們計算下标正是通過 hash 和 (length - 1)進行按位與 ，是以擴完容後下标肯定會變，那原來儲存的資料就會被打亂。在 JDK 1.7 中的處理辦法是擴完容後(建立一個新的數組，大小是原來的2倍)，會周遊每一個 entry ，進行 rehash ，再次計算 hash 和 數組下标，然後放到新的數組中去。
// 如果目前 size > 門檻值，擴容之後就會調用這個方法，進行 rehash
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// 得到目前節點的下一個節點 next
// 留意一下這段代碼，HashMap形成死循環時會講到
Entry<K,V> next = e.next;
if (rehash) {
// 重新計算hash
e.hash = null == e.key ? 0 : hash(e.key);
}
// 每一個 entry 重新計算數組所對應的下标
int i = indexFor(e.hash, newCapacity;
e.next = newTable[i];
// 放到新的數組中去
newTable[i] = e;
e = next;
}
}
}
複制代碼 ✈️ HashMap 的插入， 查找， 删除 的核心原理都一樣，這裡做個總結。
| 操作 | 原理 |
| 插入 | 先計算 key 的 hash 值，根據 hash 值找到數組位置，再往連結清單中添加元素 |
| 查找 | 先計算 key 的 hash 值，根據 hash 值找到數組位置，再周遊連結清單，找到對應的節點 |
| 删除 | 先計算 key 的 hash 值，根據 hash 值找到數組位置，再從連結清單中找到對應節點，然後删除節點 |
為什麼說 HashMap 會造成死循環？
在多線程下擴容 HashMap 會形成死循環，我們重新回顧 transfer() 後再看看正常情況下的擴容。
成功擴容後，我們發現連結清單被倒置了，現在再來看看 多線程 下對 HashMap 進行擴容形成環形資料結構的情況。
假設現在有兩個線程在同時擴容 HashMap，當 線程A 執行到 Entry<K,V> next = e.next 時被挂起，待到 線程B 擴容完畢後，線程A 重新拿到 CPU時間片 。
因為 線程A 在擴容前執行過 Entry<K,V> next = e.next，是以現在 線程A 的 e 和 next 分别指向 key("cofbro") 和 key("cc")。
現在 線程A 開始擴容，首先執行 newTab[i] = e，将 entry 插入到數組中，随後按照順序執行 e = next，然後進入下一個循環 Entry<K,V> next = e.next，因為此時HashMap已經被 線程B 擴容完成，是以此時的 next = key("cofbro") 。
現在繼續執行上個操作流程，不過由于 key("cofbro").next 沒有節點了，是以 next 是 null。
我們看到這個時候又會将 key("cofbro") 插到連結清單的頭部，死循環就這樣産生了。
JDK 1.7以後的 HashMap
我們現在知道 HashMap 結合了 ArrayList 的查詢效率高的特點以及 LinkedList 插入效率高的特點，但是如果我們要存儲的資料過于龐大，肯定會造成很多次的 哈希沖突，這樣一來，連結清單上的節點會堆積得過多，在做查詢的時候效率又變得很低，又失去了 HashMap 本來的特點。
那麼 JDK 1.8 就做出了改變，使用 數組 + 連結清單 + 紅黑樹 的結構。當節點數不大于8時，還是一個連結清單結構，隻不過插入節點時變成了 尾插法 ，當節點數大于8後，将從連結清單結構轉化成紅黑樹結構，複雜度也從 O(n) 變成 O(logn)。
什麼是紅黑樹
講解 HashMap 原理之前，先來說說 什麼是紅黑樹。
紅黑樹 其實是一顆特殊的 二叉排序樹，它有以下限定：
1.每一個節點都有一個顔色，非黑即紅
2.所有 null節點都是葉子節點，并且和根節點一樣，都是黑色
3.所有紅色節點的子節點都是黑色
4.從任一節點到其葉子節點的所有路徑上都包含相同數目的黑節點
上面這些限定的主要作用其實是保證 從根節點開始向下查找到葉子節點，其最長路徑不多于最短路徑的2倍，也就是說我們去查詢一個資料，最壞情況隻比最好情況差一倍，這樣提高了整體的查詢速度。而 紅黑樹 本身就是一顆特殊的 二叉排序樹，是以它的查詢複雜度從連結清單的 O(n) -> O(logn) 。
♻️ 為了保持紅黑樹上述特性，我們每次插入、删除都需要對其進行一定的處理，才能使得這課紅黑樹一直保持這它的特點，這裡我以插入來舉例。
紅黑樹的變色
由于有 性質4 的存在，是以每次插入的節點都先是 紅色。
1️⃣ 情況1：插入的新節點位于樹的根上、其父節點是黑色
2️⃣ 情況2：如果插入節點的父節點和父兄節點都是紅色，父節點，父兄節點、祖父節點都要變色。
紅黑樹的平衡
為了保持 紅黑樹 的相對平衡以及維護紅黑樹特性，每次插入時會判斷是否進行旋轉。
1️⃣ 情況1：當插入節點的父節點是紅色、父兄節點是黑色且插入節點是左子樹，這時進行一次右旋轉。
步驟：插入節點7，将根節點的左子樹改為新插入節點的兄弟節點，再将根節點作為新插入節點的兄弟節點，最後把新插入節點的父節點改為根節點。
有點懵的話我們再來看看動畫:
2️⃣ 情況2：當插入節點的父節點是紅色、父兄節點是黑色且插入節點是右子樹，這時進行一次左旋轉。
步驟：插入節點30，将根節點的右子樹改為新插入節點的兄弟節點，再将根節點作為新插入節點的兄弟節點，最後把新插入節點的父節點改為根節點。
有些複雜的平衡往往需要經曆兩次旋轉才能完成，比如 左右旋轉（先左再右） 或者 右左旋轉（先右再左），不過都是基于上述兩種變換完成的，搞懂一次旋轉後，二次旋轉是沒有問題的，這裡就不贅述了。
新版HashMap原理
新版的 HashMap 将原來的 Entry 改了個名字變成 Node 了，并且新增了 TreeNode 節點，專門為紅黑樹指定的。
// 就是原來的 Entry<K,V>
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;
}
}
// 紅黑樹節點
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
// 這裡有 next 是因為轉化成紅黑樹結構後，仍然維護着連結清單結構
// 并不會因為轉化成紅黑樹後而将連結清單結構删除掉
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;
}
}
}
複制代碼 同樣的，我們看原理還是從 put() 入手，跟着我來一起看一遍 put() 工作原理。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table為空或者length等于0，就調用resize方法進行初始化（第一次放元素就會第一次調用resize）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過hash值計算下标，将下标位置的頭節點指派給p，如果p為空則在數組對應位置添加一個節點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果數組的目前下标位置不為 null，則進行周遊
// 如果目前節點的key和hash值和之前儲存的一樣，代表找到了目标節點，将其指派給 e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果 p 節點類型是 TreeNode，則調用紅黑樹的putTreeVal方法查找目标節點
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 這裡就是調用連結清單結構的查找方式
// 如果p的next節點為空時，則新增一個節點并插傳入連結表尾部，注意這裡從頭插法改為尾插法
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果節點數查過8，調用treeifyBin()轉為紅黑樹結構
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 如果e節點的hash值和key值都與傳入的相同，代表找到了目标節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 将p指向下一個節點
p = e;
}
}
// 找到目标節點後，用新值替換舊值并傳回舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果插入節點後節點數超過門檻值，則調用resize方法進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
複制代碼 現在再來看看是如何建構紅黑樹的：
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // 獲得下一個節點 next
x.left = x.right = null; // 初始化紅黑樹
if (root == null) { // 初始化根節點
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key; // 得到每一個 key
int h = x.hash; // 得到每一個 hash值
Class<?> kc = null;
// 從根節點周遊，尋找插入位置
// 根據紅黑樹的特性，向左越小，向右越大
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
// 向左查找
dir = -1;
else if (ph < h)
// 向右查找
dir = 1;
// 如果兩個hash值相同，就比較key
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 比較目前這個節點和周遊到的節點的大小
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
// dir <= 0 則向p左邊查找,否則向p右邊查找
// 如果為null，則目前位置就是即将插入的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
// 向左邊查找
if (dir <= 0)
xp.left = x;
// 向右邊查找
else
xp.right = x;
// 這裡就是前面講到的，對二叉樹進行平衡和變色以保持紅黑樹特性
// 就是之前講到的原理
root = balanceInsertion(root, x);
break;
}
}
}
}
// 如果root節點不是節點, 就将其調整為頭節點
moveRootToFront(tab, root);
}
複制代碼 在前面我們看過 JDK 1.7 的 HashMap ,由于原理還是差的不多，是以還是能輕易看懂的。在新版的 HashMap 中增加了 TREEIFY_THRESHOLD 變量，目的就是用來辨別是否将連結清單轉化成紅黑樹。此外還有變化就是 resize(擴容時) 不再像 JDK 1.7 那樣重新計算hash了。
✔️ JDK 1.8是這麼優化的：将擴容後的長度 - 1 按位與 上原來計算出的key的hash值，這樣的好處是：
1.HashMap中計算出的 hash 轉化成二級制後 0 1可以看成是均勻分布的，這樣與 (length - 1) 按位與計算出來的值在數組中也還是均勻分布的
2.是以進行按位與會有兩種結果。某個 node 的hash對應的 (length - 1) 最高位的數如果是1，新數組下标就是 oldIndex + 舊數組的大小，如果是0，新數組下标就是 oldIndex，就是原索引位置
3.這樣的話，相比上個版本的 HashMap 少了一次重新計算hash的過程，提高了一定的效率
// JDK 1.8 的 擴容resize
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果舊表的大小比 Integer.MAX_VALUE 還大這就沒辦法擴容了，直接傳回舊表
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 擴容，将newCap變成oldCap的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的門檻值改為原來的兩倍
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
// 這時将門檻值和容量設定成初始值，因為初次建立 HashMap 就會調用一次 resize
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;
// 周遊舊表所有節點進行重新填裝
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果e.next為空, 說明舊表中該位置隻有1個節點，根據新的索引，放進新表中
if (e.next == null)
// 這就是剛剛講到的新版 HashMap 中計算下标的方法，很精妙
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 有哈希沖突，紅黑樹中進行重hash
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 有哈希沖突，連結清單中進行重hash
// 下标仍然是 原來位置的 節點
Node<K,V> loHead = null, loTail = null;
// 下标是 原位置下标 + oldCap 的節點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 如果e的hash值相對舊表的容量的最高位不是1，則擴容後的索引和原來一樣
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果e的hash值相對舊表的容量的最高位不是1，則擴容後的索引是原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 舊表的資料重新填充到新表上 原索引 的節點
// 将最後一個節點的next設為空
// 并将新表上索引位置為 原索引 的節點設定為頭節點
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 舊表的資料重新填充到新表上 原索引+oldCap 的節點
// 将最後一個節點的next設為空
// 并将新表上索引位置為 原索引+oldCap 的節點設定為頭節點
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 傳回擴容後的新表
return newTab;
}
複制代碼 新版的HashMap的 put()原理到這裡就講完了，查詢和删除還是之前說的，隻要懂了 put()，再去看它們源碼的時候也是很輕松了，到這裡我已經寫了太多了，就不再拿出來講了。
接下來我們回答一下開頭提出的問題。
問題總結
為什麼要用HashMap，你知道底層原理嗎？
複制代碼 答：HashMap結合了查詢效率快以及增删效率快的優點，作為一個容器是非常可貴的。HashMap存的都是一個個鍵值對，我們通過鍵值對對其進行修改和通路，在 JDK 1.7及以前底層是一個數組+連結清單的結構，當發生哈希沖突時，就将節點采用頭插法的方式放在連結清單頭部。在JDK1.7以後底層是一個數組+連結清單+紅黑樹的結構，同樣的，發生哈希沖突時，依舊是插到連結清單裡去，隻不過現在是尾插法，這樣做就是為了避免出現循環資料，另外當連結清單節點大于8時，會轉成紅黑樹進行存儲，但這并不代表删除了連結清單結構，連結清單結構依然存在，當節點數量重新小于8後，紅黑樹又會重新變成連結清單結構。(再說說get(),put()方法原理就差不多了)。
2.HashMap 中的 hash 值有什麼用？
複制代碼 HashMap中的hash值是由hash函數産生的，它是保證HashMap能正常運轉的基石，所有鍵值對進行存儲時的位置都是靠它和 (length - 1) 進行位運算得出的，我們進行插入、通路、删除都必須先得到對應的hash值，再通過它算出對應的索引值，最後才能操作對應的鍵值對。
3.為什麼 HashMap 中的數組長度必須是 2 的幂次方？
複制代碼 因為數組長度減一按位與上hash()，從結果上來看等同于 h % length ，恰好在我們的數組範圍内。此外，數組長度是2的幂次方保證了在與 hash() 進行按位與時，低位的每一位都是1。又因為我們通過 hash()計算出的值可以認為是均勻分布的，是以二者進行按位與後産生的值，也就是索引值，在數組當中就是分布均勻的。另外，在JDK1.8後，因為有上述的特點，當擴容時我們不用再重新計算hash值，隻需要判斷目前節點對應的最高位上是否是1，如果是1，就代表新索引位置為oldIndex + oldCap，如果是0，則新索引位置還是oldIndex。進而減少一次hash計算，提高效率
4.為什麼建議用 String Integer 這樣的包裝類作為 HashMap 的鍵？
複制代碼 首先，這些類内部重寫了hashCode()，equal()方法，本身就遵循HashMap中的規範，可以有效減小hash碰撞的機率。其次，這些類都是final類型，也就是說key是不可變的，避免同一個對象的計算出的hash值不一樣。除了上面所說的，很多容器都不能用基本類型并且也不能存null值也是一個原因。
5.JDK 1.7中為什麼會形成死循環？
複制代碼 JDK1.7中在連結清單中添加節點采用的是頭插法，這就導緻兩個線程同時去擴容HashMap的時候會出現一個線程執行到一少半，比如執行得到 e 和 next，這時另一個線程搶占了CPU時間片并且将HashMap擴容完成，此時HashMap中連結清單是一個倒序。這個時候第一個線程再去擴容時，第一次得到的e就會去通路兩次，在連結清單中插入兩次，這就會導緻循環資料的産生，進而通路時形成死循環。雖然說JDK1.8解決了這個問題，但它依然是線程不安全的，并發場景下還是要使用ConcurrentHashMap。
6.紅黑樹的概念，它的原理是什麼，為什麼要用它？
複制代碼 紅黑樹是一顆特殊的二叉查找樹，它有每一個節點都有一個顔色，非黑即紅、所有 null節點都是葉子節點，并且和根節點一樣，都是黑色等特點。引入它的意義就是為了解決hash碰撞次數過多，導緻連結清單長度太大，查詢耗時的問題。有了紅黑樹，我們查詢效率就提升至O(logn)，這就類似二分查找。(紅黑樹原理就是上面講的，總結一下)
連結：https://juejin.cn/post/7188057359754166331