? ? ? ?由經典面試題引入，講解一下HashMap的底層數(shù)據(jù)結構？這個面試題你當然可以只答，HashMap底層的數(shù)據(jù)結構是由（數(shù)組+鏈表+紅黑樹）實現(xiàn)的，但是顯然面試官不太滿意這個答案，畢竟這里有一個坑需要你去填，那就是在回答HashMap的底層數(shù)據(jù)結構時需要考慮JDK的版本，因為在JDK8中相較于之前的版本做了一些改進，不僅僅是增加了紅黑樹的數(shù)據(jù)結構、還包括了鏈表結點的插入由頭插法改成了尾插法，這些都是底層數(shù)據(jù)結構的優(yōu)化問題。
?JDK8中HashMap的數(shù)據(jù)結構
? ? ? ? 從上面數(shù)據(jù)結構原理圖中我們能看出數(shù)組和鏈表是如何組合使用的，數(shù)組不是實際保存數(shù)據(jù)的結構，數(shù)組保存的是Node<K,V>的對象引用地址，實際保存數(shù)據(jù)的是Node<K,V>結點類。數(shù)組中的每個位置只能保存一個Node<K,V>對象，通過鏈表可以在同一位置保存多個數(shù)據(jù)，還有鏈表會在一定條件下轉化為紅黑樹。
- table數(shù)組
// 用于保存 Node<K,V> 類型的數(shù)組
transient Node<K,V>[] table;- ?HashMap的默認初始化容量，指的是table數(shù)組大小
// HashMap的默認初始化容量為16，1位運算左移4位
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; - ?HashMap的默認負載因子，用于計算閾值
// HashMap的負載因子用于計算閾值，超過閾值即負載過大需要數(shù)組擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;- ?HashMap的閾值，當HashMap中的元素個數(shù)超過閾值時，數(shù)組會擴容為原大小的2倍
// 擴容的閾值(默認閾值 = 默認數(shù)組容量 * 負載因子)，默認為12 = 16 * 0.75
int threshold;- ?HashMap的鏈表轉換為紅黑樹的閾值
// 樹化的閾值，不是唯一條件，而是必須條件
static final int TREEIFY_THRESHOLD = 8;- Node<K,V>結點類
// HashMap源碼的靜態(tài)內部類
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 保存key計算出的hash碼
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;
}
...
}?HashMap的構造方法
- HashMap的無參構造
// 此時只設置了默認的負載因子，即數(shù)組未初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}- HashMap的帶負載因子和數(shù)組容量的構造方法
// 可設置自定義負載因子和數(shù)組容量
public HashMap(int initialCapacity, float loadFactor) {
// 數(shù)組容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
// 數(shù)組容量不能大于MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負載因子不能小于等于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
// 用于計算table數(shù)組的最終大小，因為數(shù)組大小必需為2的n次方數(shù)
this.threshold = tableSizeFor(initialCapacity);
}- HashMap的可傳入Map集合數(shù)據(jù)的構造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 遍歷Map取出集合的數(shù)據(jù)依次放入HashMap中
putMapEntries(m, false);
}?HashMap的put方法
- ?HashMap的put方法，實際調用了putVal方法
public V put(K key, V value) {
// 計算key的哈希值，創(chuàng)建Node<K,V>結點放入數(shù)組中
return putVal(hash(key), key, value, false, true);
}- ?HashMap的hash方法返回的哈希值，并不是直接調用Object對象的hashCode()方法返回的那個哈希值，而是經過了異或運算后的哈希值。
// 計算key的哈希值的方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}- ?異或運算就是兩個二進制數(shù)值按位比較，同位的值相同為0，同位的值不同為1。我們分析一下，先計算出key的哈希值用作第一個數(shù)，再把key的哈希值右移16位作為第二個數(shù)，然后再把兩個數(shù)值進行異或運算（^）。因為增加了高16位的參與，這樣計算出的哈希值會利用到了key的所有信息參與運算，增加了擾動因素，能降低哈希沖突的概率。還有在后面計算數(shù)組下標時我們會發(fā)現(xiàn)，由于是使用與運算（&），在數(shù)組的長度沒有達到2的17次方的情況下，高16位是無法使用到的，所以這也是增加高16位運算的原因。
// 425918570 對應的32位的二進制哈希值
// 高16位 低16位
0001 1001 0110 0011 --- 0000 0000 0110 1010 // 原始哈希值
0000 0000 0000 0000 --- 0001 1001 0110 0011 // 原始哈希值右移16位的值，即高16位
0001 1001 0110 0011 --- 0001 1001 0000 1001 // 異或運算得到的哈希值- putVal方法是添加數(shù)據(jù)的核心方法，table數(shù)組會在第一次添加元素時進行初始化，默認初始化容量為16，在添加數(shù)據(jù)時需要通過哈希值計算出數(shù)據(jù)放入的table數(shù)組所在的索引下標位置。添加完元素后需要判斷數(shù)組是否需要擴容，擴容大小是原數(shù)組的兩倍。
// HashMap添加數(shù)據(jù)的核心方法，
// onlyIfAbsent = false表示key相等時會覆蓋舊value
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數(shù)組是第一次使用時才進行初始化，懶惰使用
if ((tab = table) == null || (n = tab.length) == 0)
// resize()包括了數(shù)組的初始化和擴容
n = (tab = resize()).length;
// table數(shù)組當前計算出的下標位置還未保存過元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 創(chuàng)建新結點，直接放入計算出的數(shù)組下標位置中
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 出現(xiàn)哈希沖突，需要判斷是否是相同key,因為不同key也可能有相同的哈希值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// key相同，賦值給e,走下面更新新值并返回舊值代碼
e = p;
// 當前計算的數(shù)組下標保存的是樹結點，即紅黑樹結構
else if (p instanceof TreeNode)
// 采用紅黑樹的插入方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 從數(shù)組下標所在的頭結點開始遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 找到尾結點，在尾結點后插入新結點，即尾插法
if ((e = p.next) == null) {
// 先插入結點，再判斷閾值，故鏈表長度大于8時才是樹化必須條件
p.next = newNode(hash, key, value, null);
// 鏈表的長度大于8時，走樹化方法
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 如果當前遍歷到的鏈表結點和需要添加的數(shù)據(jù)key相同，則無需插入，直接退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 添加結點數(shù)據(jù)時發(fā)現(xiàn)key已經存在，此時不是插入而是更新
if (e != null) {
V oldValue = e.value;
// put相同key的數(shù)據(jù)時會覆蓋舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回當前key的舊值
return oldValue;
}
}
++modCount;
// HashMap中元素個數(shù)大于閾值，進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}- putVal方法中添加Node<K,V>的結點元素時，如何計算元素所在的table數(shù)組下標位置呢？這里就需要用到我們的哈希值了，我們可以利用哈希值對數(shù)組的長度進行取模運算，這樣就可以把取模運算的結果當做數(shù)組的下標位置。但是實際源碼中并不是這樣做的，而是采用了與運算（&），利用哈希值和數(shù)組的最大索引下標進行按位與運算。這兩種方式都可以保證算出的下標都可能取到數(shù)組的所有桶下標，且不會數(shù)組越界，但是與運算效率更高。
// 32位的二進制哈希值
// 高16位 低16位
0001 1001 0110 0011 --- 0001 1001 0000 1001 // 最終計算出的哈希值
0000 0000 0000 0000 --- 0000 0000 0000 1111 // table數(shù)組的最大索引下標，使用默認大小就是15
0000 0000 0000 0000 --- 0000 0000 0000 1001 // 與運算（&）的結果 9，即下標位置HashMap的數(shù)組長度為2的n次方數(shù)的原因
- 面試經常會問HashMap的數(shù)組長度為什么強制使用2的冪次方數(shù)？要回答這個問題，那么我們就需要知道數(shù)組長度在哪個地方用到了，通過源碼我們發(fā)現(xiàn)數(shù)組的長度被用于添加元素時計算數(shù)組的下標位置。數(shù)組下標是通過與運算（&）計算出來的，與運算的特點是（全1為1，有0為0），而2的冪次方數(shù)減一正好保證后面全為1，這樣就可以使與運算計算的結果降低相同值的概率，本質就是減少哈希沖突的概率。
// 數(shù)組下標計算公式
int i = (n - 1) & hash
// 當hash值為10，數(shù)組長度n為9時
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 影響&運算的有效位為1位，容易產生哈希沖突
0000 0000 0000 0000 --- 0000 0000 0000 1000 // (n - 1)的值為8
0000 0000 0000 0000 --- 0000 0000 0000 1000 // 計算出的數(shù)組下標為8
// 當hash值為10，數(shù)組長度n為16時
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 影響&運算結果的有效位為4位，不易產生哈希沖突
0000 0000 0000 0000 --- 0000 0000 0000 1111 // (n - 1)的值為15
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 計算出的數(shù)組下標為10
- 數(shù)組擴容后Node<K,V>元素的存放的數(shù)組下標位置變化不大，只有兩種可能，不是在新數(shù)組的原索引值位置，就是在原索引值+原數(shù)組長度的位置。我們知道數(shù)組擴容是在原數(shù)組容量的基礎上乘以2，根據(jù)原理可推斷，在重新計算元素保存的數(shù)組下標位置時，(n - 1)帶來的影響很小，只會增加一個有效位的計算。即擴容前(n - 1) = 15是4個1，擴容后(n - 1) = 31是5個1。
// 數(shù)組下標計算公式
int i = (n - 1) & hash
// 當hash值為10，擴容前，數(shù)組長度n為16
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // &運算結果的有效位為4位
0000 0000 0000 0000 --- 0000 0000 0000 1111 // (n - 1)的值為15
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 計算出的數(shù)組下標為10
// 當hash值為10，擴容后，數(shù)組長度n為32
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // &運算結果的有效位為5位，增加一位有效位計算
0000 0000 0000 0000 --- 0000 0000 0001 1111 // (n - 1)的值為31
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 計算出的數(shù)組下標還是10HashMap的鏈表樹化的條件
- ?鏈表什么時候樹化，我們可以查看在添加結點時判斷是否需要樹化的源碼邏輯。
// 樹化的閾值，不是唯一條件，而是必須條件
static final int TREEIFY_THRESHOLD = 8;
// 當遍歷的結點數(shù)大于等于8時
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 進入是否需要樹化的方法
treeifyBin(tab, hash);- ? 從源碼中我們可以了解到鏈表轉換為紅黑樹需要滿足兩個條件：一是數(shù)組的容量需要大于64，二是鏈表的長度要大于閾值8。當必要條件鏈表的長度要大于8時，才會選擇優(yōu)化縮短鏈表長度，此時不一定就需要直接轉換為紅黑樹，還可以通過擴容數(shù)組的方式來使鏈表長度變短，所以當數(shù)組的容量小于64時，是采取數(shù)組擴容來優(yōu)化鏈表的。
// 將鏈表結點轉換為紅黑樹，如果數(shù)組容量太小則先擴容數(shù)組
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 數(shù)組為空或容量小于64，擴容數(shù)組
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);
// 將數(shù)組中的普通結點鏈表替換成樹結點的雙向鏈表
if ((tab[index] = hd) != null)
// 構造生成紅黑樹
hd.treeify(tab);
}
}?JDK8的HashMap為什么在鏈表中使用尾插法代替了頭插法
- 鏈表結點的頭插法，就是在鏈表的頭部插入數(shù)據(jù)，就是每次插入的新結點數(shù)據(jù)都會成為鏈表的頭結點。JDK7的HashMap中是否真的使用了頭插法，我們可以從源碼中求證。
// 用于添加Entry<K,V>結點的方法，jdk1.7叫Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
// table數(shù)組保存的頭結點Entry保存到e變量
Entry<K,V> e = table[bucketIndex];
// 1. 把e元素作為新結點的next結點，即原頭結點作為新結點的下一個結點
// 2. 新結點作為頭結點保存到table[bucketIndex]，即頭插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
// HashMap中保存的元素總數(shù)+1
size++;
}- 鏈表結點的尾插法，就是在鏈表的尾部插入數(shù)據(jù)，這樣就需要遍歷鏈表找到尾結點，使尾結點的Node<K,V> next結點指向新結點。JDK8的HashMap添加結點使用尾插法的源碼實現(xiàn)就是如此，前面在源碼中已經看到過。
// 從數(shù)組下標所在的頭結點開始遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 找到尾結點，在尾結點后插入新結點，即尾插法
if ((e = p.next) == null) {
// 新結點作為尾結點的next結點，并成為新尾結點
p.next = newNode(hash, key, value, null);
// 鏈表的長度大于8時，走樹化方法
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 如果當前遍歷到的鏈表結點和需要添加的數(shù)據(jù)key相同，則無需插入，直接退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}- ?了解了頭插法和尾插法的區(qū)別，那么JDK8中的HashMap為什么拋棄了頭插法而使用尾插法呢？這是因為頭插法在數(shù)組擴容時，鏈表重新在新數(shù)組中生成時會導致鏈表元素倒序，這里比較難理解。因為鏈表的遍歷是從頭結點開始的，而鏈表插入是頭插法，會一直更新頭結點；所以就是最早插入的結點成為尾結點，最后插入的結點成為頭結點，這是頭插法的特點。這里的鏈表元素倒序表面上看起來問題不大，但是在多線程同時操作一個HashMap的情況下容易產生死鏈問題，這才是根本的。
?
- ??JDK7中的HashMap在數(shù)組擴容時為什么會死鏈，當然這是并發(fā)問題，是可能出現(xiàn)，不是說一定就會死鏈。我們要結合擴容的源碼進行分析，不一定要非常深入理解，能找到問題所在就行。
// jdk1.7的擴容過程
void transfer(Entry[] newTable, boolean rehash) {
// 獲取新數(shù)組的容量
int newCapacity = newTable.length;
// 遍歷舊數(shù)組，獲取頭結點，單節(jié)點也是鏈表
for (Entry<K,V> e : table) {
// 遍歷鏈表
while(null != e) {
// 取出當前結點的next結點
Entry<K,V> next = e.next;
// 判斷是否需要重新計算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 因為數(shù)組擴容了，重新計算元素存放的數(shù)組位置
int i = indexFor(e.hash, newCapacity);
// 當前添加的結點e作為頭結點，所以它的e.next指向舊的頭結點
e.next = newTable[i];
// 最新添加的結點成為新數(shù)組保存的頭結點，每次更新頭結點，即頭插法
newTable[i] = e;
// 遍歷的寫法，取下一個節(jié)點，
e = next;
}
}
}- ?分析Entry[ ] newTable作為外部傳入的引用變量存在線程安全問題，Entry[ ] table不是方法的局部變量也存在線程安全問題。我們通過分析知道，頭插法會導致鏈表結點元素倒序，即從A > B > C變?yōu)镃 > B > A，這就出現(xiàn)了大問題。在多線程環(huán)境下，如果一個線程完成了擴容，Entry[ ] table會引用新數(shù)組Entry[ ] newTable，由于鏈表結點引用指向發(fā)生了倒序，那么另一個線程就會產生死鏈，在遍歷中產生死鏈會陷入死循環(huán)。
// 假設擴容前當前遍歷的鏈表為： A > B > C
// 分析t1線程發(fā)生死鏈的情況，有兩個線程 t1 和 t2，都在執(zhí)行擴容操作
while(null != e) {
// t2線程未擴容成功時，t1線程執(zhí)行，當 e = B，e.next一定為 C
Entry<K,V> next = e.next;
// t1線程發(fā)生上下文切換，此時t2線程先完成了擴容
// 由于鏈表倒序為：C > B > A，當 e = B時，e.next的引用變?yōu)榱?A， next還是引用 C
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// B結點指向頭結點C,即 B > c > B，發(fā)生死鏈
e.next = newTable[i];
// B結點變?yōu)轭^結點
newTable[i] = e;
// 繼續(xù)遍歷，下一個節(jié)點變?yōu)镃,由于死鏈會變?yōu)樗姥h(huán)
e = next;
}JDK8的HashMap為什么引入了紅黑樹的數(shù)據(jù)結構文章來源：http://www.zghlxwxcb.cn/news/detail-412209.html
- ?紅黑樹是一種自平衡二叉搜索樹，并不是完全平衡的二叉樹。完全平衡二叉樹需要自旋多次才能達到平衡，而紅黑樹不需要多次自旋，同樣有很好的查詢性能，缺點是引入了結點顏色維護，變得更加復雜。
文章來源地址http://www.zghlxwxcb.cn/news/detail-412209.html
- 《算法導論》中對于紅黑樹的定義：①每個結點不是紅結點就是黑結點 ；②根結點是黑色的；?③每個葉子節(jié)點（NIL）都是黑的；④如果一個節(jié)點是紅的，那么它的兩個兒子都是黑的；⑤對于任意一個結點，其到葉子節(jié)點（NIL）的所有路徑上的黑結點數(shù)都是相等的。HashMap中使用紅黑樹的目的是為了提升查詢效率，因為鏈表過長，會導致查詢效率變低。HashMap中的鏈表會在數(shù)組容量大于64和鏈表長度大于8時轉換為紅黑樹，同時紅黑樹也會在結點數(shù)小于等于6時退化為鏈表。?
到了這里，關于由淺入深了解HashMap源碼的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
