????個人主頁：哈__
期待您的關(guān)注?
在Java中，HashMap結(jié)構(gòu)是被經(jīng)常使用的，在面試當中也是經(jīng)常會被問到的。這篇文章我給大家分享一下我對于HashMap結(jié)構(gòu)源碼的理解。
HashMap的存儲與一般的數(shù)組不同，HashMap的每一個元素存儲的并不是一個值，而是一個引用類型的Node結(jié)點，這也就意味著這個Node結(jié)點有被擴充的可能，因為這個Node結(jié)點可以是一個鏈表的Head結(jié)點，也可以是一棵樹的根節(jié)點。
HashMap的存儲數(shù)組叫做table，也可以稱作“桶”，試想這樣的一個場景：我們在一排放了3個桶，同時我們有4個蘋果，如果我們要把所有的蘋果放到桶當中，那么必然有一個桶中 的蘋果個數(shù)>=2。
這種情況在我們的HashMap中也會出現(xiàn)，我們的HashMap結(jié)構(gòu)是把很多的數(shù)據(jù)存放到一個容量達不到元素個數(shù)的數(shù)組當中，就如同桶和蘋果一樣。
因此我們的HashMap結(jié)果會出現(xiàn)上圖所示的一種沖突，我們成為散列沖突，也叫做Hash沖突 。
出現(xiàn)沖突不要怕，解決沖突就是了，我們的一個桶當中可以放兩個蘋果，自然HashMap的table數(shù)組的一個位置也可以存放兩個元素。
問題來了，我們現(xiàn)在假設(shè)有16個桶，同時間斷性的向桶中放蘋果，而且還要能夠方便我們后續(xù)去拿蘋果和尋找蘋果，那我們這16個桶還夠用嗎？我們這樣子直接把蘋果放進桶里，還能夠方便我們后續(xù)找蘋果嗎？
行了，解決吧，現(xiàn)在假設(shè)你是一位蘋果管理員，你該怎么優(yōu)化一下？你看看這樣子行不行，不就是放蘋果、找蘋果嘛，既然讓我來管理，那我希望把蘋果平均放到桶當中，每次我放的位置盡量不要和之前的蘋果放的位置有沖突，如果桶多的話，你也不能一個一個桶去看吧，所以，我們定義了一個算法，我根據(jù)這個蘋果的生產(chǎn)ID序列號去尋找對應的桶放進去，如同取余放置一樣。這是個不錯的思路。但序列號都是有規(guī)律的，這樣會影響我們的放置，我們希望是一個很隨機的結(jié)果，因此我們給這個序列號隨機變動幾個位置后在選擇桶。在HashMap中，這樣的序列號叫做hashCode值，經(jīng)過一個擾動函數(shù)后，我們的到的擾動的值叫做hash。
如何存放的問題解決了，但蘋果一旦多了還是會產(chǎn)生沖突，一個桶里放8個我還能找得到，但是一個桶里放20個，30個蘋果，那我就找不到那個序列號的蘋果了。
二叉樹我們都學過，倘若我們把桶內(nèi)的蘋果以二叉樹的方式進行存儲，那這樣我們在查找的時候是不是就省了很多時間呢？因此HashMap中的table內(nèi)的一個元素列表長度＞8的時候，進行樹化操作。但也不是非要進行樹化的，畢竟樹化也要浪費很多資源。當我們的桶的數(shù)量<=64的時候，我們不進行樹化操作，我們進行數(shù)組擴容，把table擴大2倍，這樣的話，我們在放蘋果的時候發(fā)生沖突的概率就會降低。但如果容量已經(jīng)達到了64，我們就考慮把鏈表轉(zhuǎn)為紅黑樹（也是二叉樹）了。
以上的過程不知道你是否理解了沒，放蘋果的案例和HashMap存儲元素的過程相似，現(xiàn)在我們來看代碼吧。
一、HashMap中的變量
1.默認容量
HashMap無參構(gòu)造方法調(diào)用時，我們的HashMap數(shù)組的初始容量是16。
/**
* 默認初始化的容量大小，且必須是2的整數(shù)倍
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 162.最大容量
記錄了我們HashMap所能存儲的最大的元素個數(shù)。
/**
* 我們的元素數(shù)組的最大的容量，如果我們設(shè)定的最大容量比這個數(shù)還大
* 那我們就把容量設(shè)定為這個最大的值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;3.負載因子
負載因子決定了HashMap在存儲更多數(shù)據(jù)時如何擴展其容量。默認情況下，當負載因子達到0.75時，HashMap會進行擴容。這意味著，當HashMap中的元素數(shù)量達到數(shù)組容量的0.75倍時，數(shù)組的大小就會翻倍，以便容納更多的數(shù)據(jù)。
為什么選擇0.75作為默認的負載因子呢？這并不是隨意的選擇，而是經(jīng)過深思熟慮后的優(yōu)化值。負載因子實際上是一個權(quán)衡空間和時間的參數(shù)。在理想情況下，如果負載因子為1，這意味著每個索引位置上都有一個鍵值對存在。然而，當兩個或更多的鍵具有相同的哈希值時，就會發(fā)生沖突，這會導致查詢效率降低。因此，通過設(shè)置一個適當?shù)呢撦d因子，可以平衡鍵值對的存儲效率和查詢效率。
通過將負載因子設(shè)置為0.75，可以在空間和時間效率之間取得平衡。這意味著，當數(shù)組接近其容量時，HashMap會進行擴容，以避免因哈希沖突而導致的性能下降。同時，這個值也避免了因頻繁擴容而產(chǎn)生的額外開銷。在大多數(shù)情況下，0.75的負載因子可以提供較好的性能。
/**
* 如果我們并沒有自己初始化一個平衡因子，這個就是默認的平衡因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;4.列表樹化的閾值
/**
* 當列表的長度超過了8，達到9的時候就會把列表轉(zhuǎn)為紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;5.紅黑樹轉(zhuǎn)列表的閾值
一個桶里的蘋果往外拿了很多，就那么幾個蘋果我數(shù)的清，用不到樹了。
/**
* 當樹中的結(jié)點的個數(shù)小于6的時候我們就把紅黑樹轉(zhuǎn)為列表了
*/
static final int UNTREEIFY_THRESHOLD = 6;6.樹化時的最小數(shù)組容量
/**
* 在我們的列表轉(zhuǎn)為紅黑樹的時候，如果我們的數(shù)組長度（也就是容量）達不到64，那我們就擴充數(shù)組
* 而不是進行紅黑樹的轉(zhuǎn)化
**/
static final int MIN_TREEIFY_CAPACITY = 64;?7.元素數(shù)組（存放我們插入的數(shù)據(jù)）
這就是我們的桶。
transient Node<K,V>[] table;8.數(shù)組的大?。ú⒎侨萘浚菍嶋H放了多少個數(shù)據(jù)結(jié)點到table數(shù)組中）?
/**
* 此映射中包含的鍵值映射數(shù)。
*/
transient int size;這些變量看完了之后，我們在介紹一個結(jié)點類Node，我們的元素在存儲的時候都是這個類型。
9.Node結(jié)點
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //hash值
final K key; //key
V value; //value
Node<K,V> next; //記錄下一個元素
}10.擴容閾值
當table中的元素個數(shù)達到了這個值的時候進行resize操作，并非所有node節(jié)點的個數(shù)，而是我們的一維table中存放元素的個數(shù)(存放的鏈表和樹算一個元素)。
/**
* table中存放的元素的個數(shù)達到了這個值進行resize操作
*/
int threshold;二、HashMap的put方法
我們只以無參構(gòu)造的HashMap為例。
HashMap<String,Integer> map = new HashMap<>();
map.put("張三",18);我們看看這個put方法到底干了些什么。
我們點進去這個put方法，發(fā)現(xiàn)調(diào)用的是putVal方法，這個方法有五個參數(shù)，第一個參數(shù)傳入了一個hash方法，第二個就是我們的key，第三個就是value，而后邊的兩個是默認的boolean類型的值，我們不看后邊的兩個。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}hash到底是什么，我們上邊其實也講到過，這是一個擾動函數(shù)，意在把我們要插入的這個元素更加隨機、均勻的分布到table中。想了解這個過程我們先往下走，到了具體的位置在講解。
我們看看這個putVal方法。代碼倒是挺多的，不過沒關(guān)系，你就看我寫的注釋。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//這里初始化了一個tab用于保存我們最終的結(jié)果 還有一個臨時的結(jié)點p
Node<K,V>[] tab; Node<K,V> p; int n, i;
//這種寫法要弄清，=是賦值，==是判斷，如果我們的table還沒有初始化的話
if ((tab = table) == null || (n = tab.length) == 0)
//我們就把這個n記錄成我們這個tab初始化后的大小
n = (tab = resize()).length;
//這里就是進行位置判斷的代碼了，如果當前遍歷的結(jié)點是個空的，我們直接把node放到這個桶里
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //如果當前位置不為空
//定義一個e結(jié)點用于遍歷
Node<K,V> e; K k;
//如果這個結(jié)點的key和我們插入元素的key相同，那我們把這個e指向這個結(jié)點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//但如果不同，而且這個結(jié)點還是個樹形結(jié)點，我們調(diào)用專門的方法遍歷樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果不是樹，那就是鏈表了，我們進行鏈表遍歷去插入我們的新元素
for (int binCount = 0; ; ++binCount) {
//如果我們遍歷到的結(jié)點已經(jīng)遍歷完了，那我們把元素插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果達到了樹化閾值，那我們進行樹化操作
//這里注意一下為什么是-1，因為我們從0開始遍歷，當我們達到了7說明
已經(jīng)遍歷了8次，同時上邊進行了一次插入，結(jié)點數(shù)達到了9
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果當前結(jié)點的key就是我們插入的key，我們不做操作，這是e是有指向的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是空，就說明找到了一個key相同的結(jié)點，我們進行value的替換
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//替換后就return了，不對table結(jié)構(gòu)做影響
return oldValue;
}
}
//如果我們對table的結(jié)構(gòu)影響了，我們把這個值+1
++modCount;
//看看把這個值插進去之后，是否達到了擴容閾值，并不是table中元素的長度滿了之后才擴容的
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}?
在上方的代碼中你看到了這樣的代碼。這樣代碼就是判斷我們元素放到哪個位置的。我們用桶的容量去和hash值進行與操作。
(p = tab[i = (n - 1) & hash假設(shè)當前容量是16，那么你看一下這個與操作的核心部分是什么，n的前28位都是0，與后的結(jié)果也是0，所以真正影響元素位置的只有n的最后四位和元素hashcode的最后四位。結(jié)果也一定是0~15。
h.hashCode =?1101 0111 1011 1100?0101 1011 1011 1010
n-1? ? ?? ? ? ? ? = 0000 0000 0000 0000 0000 0000 0000 1111
那么擾動函數(shù)的作用是什么呢。我們上邊的與操作只算了元素hashcode的后4位，不夠隨機，我們想要讓hashcode的前16位也要影響最后的結(jié)果。所以就有了擾動函數(shù)。?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}h.hashCode? ? ? ? ? ? ?=?1101 0111 1011 1100?0101 1011 1011 1010
h.hashCode >>>16? = 0000 0000 0000 0000?1101 0111 1011 1100?
我們?nèi)∵@兩個值的與結(jié)果，這樣我們的hashcode的高位也能擾動我們放的位置。并非單純的低位和n-1去進行與運算了。
三、resize方法
在上邊的代碼中有個resize方法的調(diào)用，這個方法主要的目的是擴容table。這個resize方法看起來還是非常的恐怖哈。
resize方法解釋了為什么數(shù)組的容量一定是二的整數(shù)倍。
final Node<K,V>[] resize() {
//記錄一下之前的table
Node<K,V>[] oldTab = table;
//算一下之前table的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//記錄一下之前table的擴容閾值
int oldThr = threshold;
//把新的容量和擴容閾值定義出來
int newCap, newThr = 0;
//如果已經(jīng)進行過初始化了
if (oldCap > 0) {
//如果我們之前的空間大小已經(jīng)達到了最大容量 -- 很少出現(xiàn)
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否則的話 我們新的容量等于舊的容量*2 位移運算
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的擴容閾值也*2
newThr = oldThr << 1; // double threshold
}
//這個先不說了
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 這個else重要啊，如果我們沒有進行過初始化，那我們就把新容量定位16 新的擴容閾值定為12
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"})
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;
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;
}我們分析一下下邊的代碼。寫了注釋的直接看看就好，關(guān)于樹的我不說了，只說鏈表。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果我們之前的table不為空的話我們要進行一下元素遷移
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果當前結(jié)點不為空
if ((e = oldTab[j]) != null) {
//清空原來的table中的位置，便于垃圾回收
oldTab[j] = null;
//如果就一個node 把他搬到新的table中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是樹形結(jié)點 調(diào)用split方法
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;
//判斷這個結(jié)點放到高鏈表或者低鏈表中
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;
}
}
}
}
}?什么是高鏈表和低鏈表。在之前我們說到過元素是如何定位的，靠的是hash和數(shù)組容量-1的與操作。但如果我們數(shù)組容量不減1呢？因為我們的數(shù)組容量是2的整數(shù)倍，如果不減1，那么就說明只有一個位置為1，其他的全為0（假設(shè)容量是16）。
h.hashCode =?1101 0111 1011 1100?0101 1011 1011 1010
n? ? ? ? ? ? ? ? ? = 0000 0000 0000 0000 0000 0000 0001?0000
如同上方的例子，這個元素到底分到哪里，就看這個元素的hash值的倒數(shù)第五位，如果是1，就在高鏈表，如果是0就在低鏈表。我們通過這樣的方式來把元素分到低鏈表或者高鏈表當中。
for循環(huán)的最后把我們這個臨時的低鏈表和高鏈表放到我們新的table中。?文章來源：http://www.zghlxwxcb.cn/news/detail-850161.html
最后將新的table返回。文章來源地址http://www.zghlxwxcb.cn/news/detail-850161.html
到了這里，關(guān)于【Java】JDK1.8 HashMap源碼，put源碼詳細講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Java]靜態(tài)代理、動態(tài)代理（基于JDK1.8）](https://imgs.yssmx.com/Uploads/2024/03/837618-1.png)
![[ 環(huán)境搭建篇 ] 安裝 java 環(huán)境并配置環(huán)境變量(附 JDK1.8 安裝包)](https://imgs.yssmx.com/Uploads/2024/02/520717-1.png)
