更新時間:2022-08-24 來源:黑馬程序員 瀏覽量:
一、前言：
面試過的人都知道，HashMap是Java程序員在面試中最最最經常被問到的一個點，可以說，不了解HashMap都不好意思說自己是做Java開發的。基本上你去面試十家公司，有七八家都會問到你HashMap。那么今天，就帶著大家從源碼的角度去分析一下，HashMap具體是怎么實現的。
二、HashMap的構造方法
1.HashMap構造方法
我們先來看HashMap的四個構造方法
JavaEE
鴻蒙應用開發
集成電路應用開發
人工智能開發
AI+Linux云計算運維
Python+大數據開發
AI+設計
軟件測試
新媒體+短視頻
HTML&JS+前端
```java
//initialCapacity給定的初始化容量，loadFactor擴容因子
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);
}
public HashMap(int initialCapacity) {
//內部調用了上邊的構造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {//空參構造
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {//構造傳入一個map，將map中的值放到hashmap中
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
```2.構造方法里的putMapEntries方法
剛才構造方法中提到了putMapEntries這個方法，接下來就讓我們一起看一下
//該函數用于將一個map賦值給新的HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//定義變量接收舊hashmap的size
int s = m.size();
//判斷s的容量是否大于0
if (s > 0) {
//判斷當前數組有沒有初始化
if (table == null) { // pre-size
////求出以 舊hashmap數組容量為閾值 的數組容量賦值給ft
float ft = ((float)s / loadFactor) + 1.0F;
//判斷是不是大于最大容量，如果是，賦值為最大容量，否則將ft賦值給t
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//判斷t是否大于threshold(數組擴容閾值)
if (t > threshold)
//通過tablesizefor方法求出大于等于t的最小2的次冪值賦值給threshold（數組擴容閾值）
threshold = tableSizeFor(t);
}
//如果數組長度大于擴容閾值，進行resize擴容操作
else if (s > threshold)
resize();
//循環遍歷取出舊hashmap的值放入當前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);
}
}
}
/*
if (table == null)分支，是判斷當前數組是否初始化，因為在jdk1.8之后，只有當你第一次放值時，才會幫你創建16位的數組。
float ft = ((float)s / loadFactor) + 1.0F經過除運算再加上1.0F是為了向上取整
if (t > threshold)注意一個細節，做判斷的的時候，數組還沒有初始化，這里的threshold的值還是給定的數組長度的值，也就是capacity的值
else if (s > threshold)說明傳入的map集合大于當前的擴容閾值，需要進行resize擴容操作
*/
```tableSizeFor方法
剛才putMapEntries方法中，調用了tableSizeFor方法，接下來我們看一下這個tableSizeFor方法。
作用：創建hashMap對象時調用有參構造，傳入初始容量，需要保證hashMap的初始長度為2的n次冪。
tableSizeFor方法用來計算大于等于并離傳入值最近的2的n次冪的數值，比如傳入15，算出結果為16，傳入17，算出結果為32。
通過二進制的位移，第一次右移一位，第二次右移兩位，第三次右移四位。。。通過五次位移，將范圍內所有的位數都變為1，高位補0，最后得出來的結果再加上1，最后算出來的結果一定是2的n次冪。
//這個方法的作用是找到大于等于給定容量的最小2的次冪值
//>>>表示無符號右移，也叫邏輯右移，即若該數為正，則高位補0，而若該數為負數，則右移后高位同樣補0
7--》8
16--》16
static final int tableSizeFor(int cap) {
//先將數組長度減1，之所以在開始移位前先將容量-1，是為了避免給定容量已經是8,16這樣2的冪時，不減一 直接移位會導致得到的結果比預期大。比如預期16得到應該是16，直接移位的話會得到32。
int n = cap - 1;
//右移一位，在進行或運算，這個時候最高位和次高位就已經都是1，此時是2個1
n |= n >>> 1;
//右移兩位，在進行或運算，這個時候由上次運算得出的兩個1，變成了四個1
n |= n >>> 2;
//右移四位
n |= n >>> 4;
//右移八位
n |= n >>> 8;
//右移十六位，這個時候所有的位數都變為了1
n |= n >>> 16;
//n+1操作，是為了進1，這個時候算出來的數值就一點是 2的n次冪
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
```移位的思想
2的整數冪用二進制表示都是最高有效位為1，其余全是0。
對任意十進制數轉換為2的整數冪，結果是這個數本身的最高有效位的前一位變成1，最高有效位以及其后的位都變為0。
核心思想是，先將最高有效位以及其后的位都變為1，最后再+1，就進位到前一位變成1，其后所有的滿2變0。所以關鍵是如何將最高有效位后面都變為1。
先移位，再或運算。
> 右移一位，再或運算，就有兩位變為1;
>
> 右移兩位，再或運算，就有四位變為1，，，
>
> 最后右移16位再或運算，保證32位的int類型整數最高有效位之后的位都能變為1。
三、HashMap的底層原理
先來看幾個重要的參數：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認數組初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;//數組最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認加載因子
static final int TREEIFY_THRESHOLD = 8;//樹化的閾值
static final int UNTREEIFY_THRESHOLD = 6;//由樹退化到鏈表的閾值
static final int MIN_TREEIFY_CAPACITY = 64;//樹化最小數組容量
//node節點，繼承了Map.entry,在Entry原有的K,V的基礎上追加了hash和next字段
//分別表示key的hash值和下一個節點
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//重寫了計算hash的方法
//將 Hash 值的高 16 位右移并與原 Hash 值取異或運算(^)，混合高 16 位和低 16 位的值
//得到一個更加散列的低 16 位的 Hash 值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```HashMap在JDK1.8之前的實現方式數組+鏈表,
但是在JDK1.8后對HashMap進行了底層優化,改為了由 **數組+鏈表或者數值+紅黑樹**實現,主要的目的是提高查找效率
1. Jdk8數組+鏈表或者數組+紅黑樹實現，當鏈表中的元素大于等于8 個并且數組長度大于等于64以后， 會將鏈表轉換為紅黑樹，當紅黑樹節點 小于 等于6 時又會退化為鏈表。
2. 當new HashMap()時，底層沒有創建數組，首次調用put()方法示時，會調用resize方法，底層創建長度為16的數組，jdk8底層的數組是：Node[],而非Entry[]，用數組容量大小乘以加載因子得到一個值，一旦數組中存儲的元素個數超過該值就會調用resize方法將數組擴容到原來的兩倍，在做擴容的時候會生成一個新的數組，原來的所有數據需要重新計算哈希碼值重新分配到新的數組，所以擴容的操作非常消耗性能。
默認的負載因子大小為0.75，數組大小為16。也就是說，默認情況下，那么當HashMap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍。
3. 在我們Java中任何對象都有hashcode，hash算法就是通過hashcode與自己進行向右位移16的異或運算。這樣做是為了使高位的16位hash也能參與運算，使運算出來的hash值足夠隨機，足夠分散，還有產生的數組下標足夠隨機。
map.put(k,v)實現原理：
(1)首先將k,v封裝到Node對象當中(節點)。
(2)先調用k的hashCode()方法得出哈希值，并通過哈希算法轉換成數組的下標。
(3)下標位置上如果沒有任何元素，就把Node添加到這個位置上。如果說下標對應的位置上有鏈表。此時，就會拿著k和鏈表上每個節點的k進行equal。如果所有的equals方法返回都是false，那么這個新的節點將被添加到鏈表的末尾。如其中有一個equals返回了true，那么這個節點的value將會被覆蓋。
HashMap中的put()方法
```java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
```putVal()方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷數組是否未初始化
if ((tab = table) == null || (n = tab.length) == 0)
//如果未初始化，調用resize方法 進行初始化
n = (tab = resize()).length;
//通過 & 運算求出該數據（key）的數組下標并判斷該下標位置是否有數據
if ((p = tab[i = (n - 1) & hash]) == null)
//如果沒有，直接將數據放在該下標位置
tab[i] = newNode(hash, key, value, null);
//該數組下標有數據的情況
else {
Node<K,V> e; K k;
//判斷該位置數據的key和新來的數據是否一樣
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果一樣，證明為修改操作，該節點的數據賦值給e,后邊會用到
e = p;
//判斷是不是紅黑樹
else if (p instanceof TreeNode)
//如果是紅黑樹的話，進行紅黑樹的操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//新數據和當前數組既不相同，也不是紅黑樹節點，證明是鏈表
else {
//遍歷鏈表
for (int binCount = 0; ; ++binCount) {
//判斷next節點，如果為空的話，證明遍歷到鏈表尾部了
if ((e = p.next) == null) {
//把新值放入鏈表尾部
p.next = newNode(hash, key, value, null);
//因為新插入了一條數據，所以判斷鏈表長度是不是大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果是，進行轉換紅黑樹操作
treeifyBin(tab, hash);
break;
}
//判斷鏈表當中有數據相同的值，如果一樣，證明為修改操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//把下一個節點賦值為當前節點
p = e;
}
}
//判斷e是否為空（e值為修改操作存放原數據的變量）
if (e != null) { // existing mapping for key
//不為空的話證明是修改操作，取出老值
V oldValue = e.value;
//一定會執行 onlyIfAbsent傳進來的是false
if (!onlyIfAbsent || oldValue == null)
//將新值賦值當前節點
e.value = value;
afterNodeAccess(e);
//返回老值
return oldValue;
}
}
//計數器，計算當前節點的修改次數
++modCount;
//當前數組中的數據數量如果大于擴容閾值
if (++size > threshold)
//進行擴容操作
resize();
//空方法
afterNodeInsertion(evict);
//添加操作時 返回空值
return null;
}
```map中resize方法
//擴容、初始化數組
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//如果當前數組為null的時候，把oldCap老數組容量設置為0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//老的擴容閾值
int oldThr = threshold;
int newCap, newThr = 0;
//判斷數組容量是否大于0，大于0說明數組已經初始化
if (oldCap > 0) {
//判斷當前數組長度是否大于最大數組長度
if (oldCap >= MAXIMUM_CAPACITY) {
//如果是，將擴容閾值直接設置為int類型的最大數值并直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果在最大長度范圍內，則需要擴容 OldCap << 1等價于oldCap*2
//運算過后判斷是不是最大值并且oldCap需要大于16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 等價于oldThr*2
}
//如果oldCap<0，但是已經初始化了，像把元素刪除完之后的情況，那么它的臨界值肯定還存在， 如果是首次初始化，它的臨界值則為0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//數組未初始化的情況，將閾值和擴容因子都設置為默認值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//初始化容量小于16的時候，擴容閾值是沒有賦值的
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;
//判斷當前下標為j的數組如果不為空的話賦值個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 {
//比如老數組容量是16，那下標就為0-15
//擴容操作*2，容量就變為32，下標為0-31
//低位：0-15，高位16-31
//定義了四個變量
// 低位頭 低位尾
Node<K,V> loHead = null, loTail = null;
// 高位頭 高位尾
Node<K,V> hiHead = null, hiTail = null;
//下個節點
Node<K,V> next;
//循環遍歷
do {
//取出next節點
next = e.next;
//通過 與操作 計算得出結果為0
if ((e.hash & oldCap) == 0) {
//如果低位尾為null，證明當前數組位置為空，沒有任何數據
if (loTail == null)
//將e值放入低位頭
loHead = e;
//低位尾不為null，證明已經有數據了
else
//將數據放入next節點
loTail.next = e;
//記錄低位尾數據
loTail = e;
}
//通過 與操作 計算得出結果不為0
else {
//如果高位尾為null，證明當前數組位置為空，沒有任何數據
if (hiTail == null)
//將e值放入高位頭
hiHead = e;
//高位尾不為null，證明已經有數據了
else
//將數據放入next節點
hiTail.next = e;
//記錄高位尾數據
hiTail = e;
}
//如果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;
}
```map.get(k)實現原理
(1)、先調用k的hashCode()方法得出哈希值，并通過哈希算法轉換成數組的下標。
(2)、在通過數組下標快速定位到某個位置上。重點理解如果這個位置上什么都沒有，則返回null。如果這個位置上有單向鏈表，那么它就會拿著參數K和單向鏈表上的每一個節點的K進行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節點的K和參數K進行equals返回true，那么此時該節點的value就是我們要找的value了，get方法最終返回這個要找的value。
HashMap中的get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
```getNode()方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判斷數組不為null并且長度大于0，并且通過hash算出來的數組下標的位置不為空，證明有數據
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判斷數組的位置的key的hash和內容是否等同與要查詢的數據
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))))
//發現key的話就返回
return e;
} while ((e = e.next) != null);
}
}
//沒有查詢到返回null
return null;
}四、HashMap常見面試題分析
為何HashMap的數組長度一定是2的次冪?
首先，HashMap的初始化的數組長度一定是2的n次的，每次擴容仍是原來的2倍的話，就不會破壞這個規律，每次擴容后，原數據都會進行數據遷移，根據二進制的計算，擴容后數據要么在原來位置，要么在【原來位置+擴容長度】，這樣就不需要重新hash，效率上更高。
HashMap中，如果想存入數據，首先它需要根據key的哈希值去定位落入哪個桶中
HashMap的做法，我總結的是，三步：>>>無符號右移、^異或、&與
具體是：拿著key的哈希值，先“>>>”無符號右移16位，然后“^”異或上key的哈希值，得到一個值，再拿著這個值去“&”上數組長度減一
最后得出一個數(如果數組長度是15的話，那這個數就是一個0-15之間的一個數)，這個數就是得出的數組腳標位置，也就是存入的桶的位置。
由上邊可以知道，定位桶的位置最后需要做一個 “&” 與運算，&完了得出一個數，就是桶的位置
知道了這些以后，再來說為什么HashMap的長度之所以一定是2的次冪?
至少有以下**兩個原因**：
1、HashMap的長度是2的次冪的話，可以讓**數據更散列更均勻的分布**，更充分的利用數組的空間
怎么理解呢?下面舉例子說一下如果不是2的次冪的數的話假設數組長度是一個奇數，那參與最后的&運算的肯定就是偶數，那偶數的話，它二進制的最后一個低位肯定是0，0做完&運算得到的肯定也是0，那意味著&完后得到的數的最低位一定是0最低位一定是0的話，那說明一定是一個偶數，換句話說就是：&完得到的數一定是一個偶數，所以&完獲取到的腳標永遠是偶數位，那意味著奇數位的腳標永遠都沒值，**有一半的空間是浪費的**奇數說完了，來說一下偶數，假設數組長度是一個偶數，比如6，那參與&運算的就是55的二進制 00000000 00000000 00000000 00000101發現任何一個數&上5，倒數第二低位永遠是0，那就意味著&完以后，最起碼肯定得不出2或者3(這點剛開始不好理解，但是好好想一下就能明白)意味著第二和第三腳標位肯定不會有值。
雖然偶數的話，不會像奇數那么夸張會有一半的腳標位得不到，但是也總會有一些腳標位得不到的。**所以不是2的次冪的話，不管是奇數還是偶數，就肯定注定了某些腳標位永遠是沒有值的，而某些腳標位永遠是沒有值的，就意味著浪費空間，會讓數據散列的不充分，這對HashMap來說絕對是個災難!**
2、HashMap的長度一定是2的次冪，還有另外一個原因，那就是在擴容遷移的時候不需要再重新通過哈希定位新的位置了。擴容后，元素新的位置，要么在原腳標位，要么在原腳標位+擴容長度這么一個位置。
比如擴容前長度是8，擴容后長度是16 第一種情況： 擴容前： 00000000 00000000 00000000 00000101 &00000000 00000000 00000000 00000111 8-1=7 ------------------------------------- 101 ===== 5 原來腳標位是5 擴容后： 00000000 00000000 00000000 00000101 &00000000 00000000 00000000 00001111 16-1=15 ------------------------------------- 101 ===== 5 擴容后腳標位是5(原腳標位) 第二種情況： 擴容前： 00000000 00000000 00000000 00001101 &00000000 00000000 00000000 00000111 8-1=7 ------------------------------------- 101 ===== 5 原來腳標位是5 擴容后： 00000000 00000000 00000000 00001101 &00000000 00000000 00000000 00001111 16-1=15 ------------------------------------- 1101 ===== 13 擴容后腳標位是13(原腳標位+擴容長度) ```
擴容后到底是在原來位置還是在原腳標位+擴容長度的位置，主要是看新擴容最左邊一個1對應的上方數字是0還是1如果是0則擴容后在原來位置，如果是1則擴容后在原腳標位+擴容長度的位置HashMap源碼里擴容也是這么做的。
總結來說，就是hash&(n-1)這個計算有關。如果不為n不為2的n次方的話，那轉換為二進制情況下，n-1就會有某一位為0，那與hash做了&運算后，該位置永遠為0，那么計算出來的數組位置就永遠會有某個下標的數組位置是空的，也就是這個位置永遠不會有值。
JDK1.8中HashMap的性能優化
JDK1.8在1.7的基礎上對一些操作進行了優化。
| 不同 | JDK1.7 | JDK1.8 |
| ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 存儲結構 | 數組+鏈表 | 數組+鏈表+紅黑樹 |
| 初始化方式 | 單獨函數inflateTable() | 集成至擴容方法resize() |
| hash值計算方式 | 擾動處理=9次擾動=4次位運算+5次異或運算 | 擾動處理=2次擾動=1次位運算+1次異或運算 |
| 存放數據規則 | 無沖突時，存放數組;沖突時存放鏈表 | 無沖突時，存放數組;沖突&鏈表長度<8:c存放單鏈表;沖突&鏈表長度 >8:樹化并存放紅黑樹 |
| 插入數據方式 | 頭插法(將原位置的數據移動到后一位，再插入數據到該位置) | 尾插法 (直接插入鏈表尾部/紅黑樹) |
| 擴容后存儲位置的計算方式 | 全部按照原來的方法進行運算(hashCode()->>擾動函數->>(h&length-1)) | 按照擴容后的規則計算(即擴容后位置=原位置或原位置+舊容量) |
注意：JDK1.8里轉換為紅黑樹的時候，數組長度必須大于64，如果數組長度小于64，鏈表長度達到8的話，會進行resize擴容操作。
五、總結
看到這里，我們已經HashMap的源碼和實現有了清晰的理解，并且對它的構造方法再到它的一個put數據和get數據的一個源碼解析，還有一些它里邊比較精妙和重要的一些方法也都探索清楚了，希望這些知識點可以在大家以后的面試中也能夠幫助到大家，斬獲一個心儀的offer。
.jpg)