前言
HashMap是Java后端工程師面試的必問題涵叮，因為其中的知識點太多，很適合用來考察面試者的Java基礎(chǔ)。今天基于jdk1.8來研究一下HashMap的底層實現(xiàn)。
HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
JDK1.7是數(shù)組+鏈表
JDK1.8是數(shù)組+鏈表+紅黑樹
HashMap在jdk8中相較于jdk7在底層實現(xiàn)方面的不同：
- new HashMap();底層沒創(chuàng)建一個長度為16的數(shù)組
- jdk 8底層的數(shù)組是：Node[]，而非Entry[]
- 首次調(diào)用put()方法時贝润，底層創(chuàng)建長度為16的數(shù)組
- jdk7底層結(jié)構(gòu)只：數(shù)組+鏈表。jdk8中底層結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹铝宵。
- 形成鏈表時打掘，七上八下（jdk7:新的元素指向舊的元素,頭插。jdk8：舊的元素指向新的元素鹏秋，尾插）
- 當(dāng)數(shù)組的某一個索引位置上的元素以鏈表形式存在的數(shù)據(jù)個數(shù) > 8 且當(dāng)前數(shù)組的長度 > 64時尊蚁，此時此索引位置上的所數(shù)據(jù)改為使用紅黑樹存儲。
數(shù)據(jù)結(jié)構(gòu)圖
hashMap中幾個重要的字段(JDK1.8)
//默認(rèn)初始容量為16侣夷，0000 0001 右移4位 0001 0000為16横朋，主干數(shù)組的初始容量為16，而且這個數(shù)組
//必須是2的倍數(shù)(后面說為什么是2的倍數(shù))
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量為int的最大值除2
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)加載因子為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//閾值百拓，如果主干數(shù)組上的鏈表的長度大于8琴锭，鏈表轉(zhuǎn)化為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//hash表擴(kuò)容后晰甚，如果發(fā)現(xiàn)某一個紅黑樹的長度小于6，則會重新退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//當(dāng)hashmap容量大于64時决帖，鏈表才能轉(zhuǎn)成紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
//臨界值=主干數(shù)組容量*負(fù)載因子
int threshold;
hashMap的構(gòu)造方法：
//initialCapacity為初始容量厕九，loadFactor為負(fù)載因子
public HashMap(int initialCapacity, float loadFactor) {
//初始容量小于0，拋出非法數(shù)據(jù)異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量最大為MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負(fù)載因子必須大于0地回，并且是合法數(shù)字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//將初始容量轉(zhuǎn)成2次冪
this.threshold = tableSizeFor(initialCapacity);
}
//tableSizeFor的作用就是扁远，如果傳入A，當(dāng)A大于0刻像，小于定義的最大容量時畅买，
// 如果A是2次冪則返回A，否則將A轉(zhuǎn)化為一個比A大且差距最小的2次冪细睡。
//例如傳入7返回8皮获，傳入8返回8，傳入9返回16
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;
}
//調(diào)用上面的構(gòu)造方法纹冤，自定義初始容量，負(fù)載因子為默認(rèn)的0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默認(rèn)構(gòu)造方法购公，負(fù)載因子為0.75萌京，初始容量為DEFAULT_INITIAL_CAPACITY=16，初始容量在第一次put時才會初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//傳入一個MAP集合的構(gòu)造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
HashMap的數(shù)據(jù)插入原理
- 判斷數(shù)組是否為空宏浩，為空進(jìn)行初始化,在實例化以后知残，底層創(chuàng)建了長度是16的一維數(shù)組Entry[] table。
- 數(shù)組不為空比庄，首先求妹，調(diào)用key所在類的hashCode()計算key1哈希值，此哈希值經(jīng)過(n - 1) & hash計算以后佳窑，得到在Entry數(shù)組中的存放位置制恍。
- 判斷table[index] 此位置上是否存在數(shù)據(jù)，沒有數(shù)據(jù)就構(gòu)造一個Node節(jié)點存放在 table[index] 中
- 如果此位置上存在數(shù)據(jù)神凑，發(fā)生了hash沖突(意味著此位置上存在一個或多個數(shù)據(jù)(以鏈表形式存在))
? ? 4.1 比較key1和已存在數(shù)據(jù)的哈希值净神，如果key1的哈希值與已經(jīng)存在的數(shù)據(jù)的哈希值都不相同，此時key1-value1添加成功溉委。
? ? 4.2 如果key1的哈希值和已經(jīng)存在的某一個數(shù)據(jù)(key2-value2)的哈希值相同
? ? 4.3 繼續(xù)調(diào)用key1所在類的equals(key2)方法比較：
? ? ? ? ①如果equals()返回false：此時key1-value1添加成功鹃唯。
? ? ? ? ②如果equals()返回true： 使用value1替換value2- 判斷首節(jié)點是不是紅黑樹節(jié)點
? ? 5.1 如果首節(jié)點是紅黑樹節(jié)點（TreeNode），將鍵值對添加到紅黑樹瓣喊。
? ? 5.2 如果首節(jié)點是鏈表坡慌，進(jìn)行遍歷尋找元素，有就覆蓋無則新建藻三，將鍵值對添加到鏈表洪橘。添加之后會判斷鏈表長度是否長度大于 8并且數(shù)組長度大于64跪者，大于的話鏈表轉(zhuǎn)換為紅黑樹。
插入完成之后判斷當(dāng)前節(jié)點數(shù)是否大于閾值梨树，如果大于開始擴(kuò)容為原數(shù)組的二倍坑夯。
put源碼分析
public V put(K key, V value) {
/**
* 將key傳入hash方法，計算其對應(yīng)的hash值：
*
* 此處如果傳入的int類型的值：
* ①向一個Object類型賦值一個int的值時抡四，會將int值自動封箱為Integer柜蜈。
* ②integer類型的hashcode都是他自身的值，即h=key指巡；h >>> 16為無符號右移16位淑履，低位擠走，高位補(bǔ)0藻雪；^ 為按位異或,
* 即轉(zhuǎn)成二進(jìn)制后秘噪，相異為1，相同為0勉耀，由此可發(fā)現(xiàn)指煎，當(dāng)傳入的值小于 2的16次方-1 時，調(diào)用這個方法返回的值便斥，都是自身的值至壤。
*/
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent是true的話，不要改變現(xiàn)有的值
//evict為true的話枢纠，表處于創(chuàng)建模式
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為空像街，長度為0，調(diào)用resize方法晋渺，調(diào)整table的長度（resize方法在下圖中）
if ((tab = table) == null || (n = tab.length) == 0)
/* 這里調(diào)用resize镰绎，其實就是第一次put時，對數(shù)組進(jìn)行初始化木西。
如果是默認(rèn)構(gòu)造方法會執(zhí)行resize中的這幾句話：
newCap = DEFAULT_INITIAL_CAPACITY; 新的容量等于默認(rèn)值16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
threshold = newThr; 臨界值等于16*0.75
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; 將新的node數(shù)組賦值給table畴栖，然后return newTab
如果是自定義的構(gòu)造方法則會執(zhí)行resize中的：
int oldThr = threshold;
newCap = oldThr; 新的容量等于threshold，這里的threshold都是2的倍數(shù)户魏，原因在
于傳入的數(shù)都經(jīng)過tableSizeFor方法驶臊，返回了一個新值，上面解釋過
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
threshold = newThr; 新的臨界值等于 (int)(新的容量*負(fù)載因子)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; return newTab;
*/
n = (tab = resize()).length; //將調(diào)用resize后構(gòu)造的數(shù)組的長度賦值給n
if ((p = tab[i = (n - 1) & hash]) == null) //將數(shù)組長度與計算得到的hash值比較
tab[i] = newNode(hash, key, value, null);//位置為空叼丑，將i位置上賦值一個node對象
else { //位置不為空
Node<K,V> e; K k;
if (p.hash == hash && // 如果這個位置的old節(jié)點與new節(jié)點的key完全相同
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 則e=p
else if (p instanceof TreeNode) // 如果p已經(jīng)是樹節(jié)點的一個實例关翎，既這里已經(jīng)是樹了
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //p與新節(jié)點既不完全相同，p也不是treenode的實例
for (int binCount = 0; ; ++binCount) { //一個死循環(huán)
if ((e = p.next) == null) { //e=p.next,如果p的next指向為null
p.next = newNode(hash, key, value, null); //指向一個新的節(jié)點
if (binCount >= TREEIFY_THRESHOLD - 1) // 如果鏈表長度大于等于8
treeifyBin(tab, hash); //將鏈表轉(zhuǎn)為紅黑樹
break;
}
if (e.hash == hash && //如果遍歷過程中鏈表中的元素與新添加的元素完全相同鸠信，則跳出循環(huán)
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //將p中的next賦值給p,即將鏈表中的下一個node賦值給p纵寝，
//繼續(xù)循環(huán)遍歷鏈表中的元素
}
}
if (e != null) { //這個判斷中代碼作用為：如果添加的元素產(chǎn)生了hash沖突，那么調(diào)用
//put方法時，會將他在鏈表中他的上一個元素的值返回
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //判斷條件成立的話爽茴，將oldvalue替換
//為newvalue葬凳，返回oldvalue；不成立則不替換室奏，然后返回oldvalue
e.value = value;
afterNodeAccess(e); //這個方法在后面說
return oldValue;
}
}
++modCount; //記錄修改次數(shù)
if (++size > threshold) //如果元素數(shù)量大于臨界值火焰，則進(jìn)行擴(kuò)容
resize(); //下面說
afterNodeInsertion(evict);
return null;
}
resize的源碼詳解，擴(kuò)容機(jī)制胧沫，單元素如何散列到新的數(shù)組中昌简，鏈表中的元素如何散列到新的數(shù)組中，紅黑樹中的元素如何散列到新的數(shù)組中绒怨？
//默認(rèn)構(gòu)造方法與自定義構(gòu)造方法第一次執(zhí)行resize的過程纯赎，這里再說一下擴(kuò)容的過程
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) { //擴(kuò)容肯定執(zhí)行這個分支
if (oldCap >= MAXIMUM_CAPACITY) { //當(dāng)容量超過最大值時，臨界值設(shè)置為int最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //擴(kuò)容容量為2倍南蹂，臨界值為2倍
newThr = oldThr << 1;
}
else if (oldThr > 0) // 不執(zhí)行
newCap = oldThr;
else { // 不執(zhí)行
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 不執(zhí)行
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //將新的臨界值賦值賦值給threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //新的數(shù)組賦值給table
//擴(kuò)容后犬金，重新計算元素新的位置
if (oldTab != null) { //原數(shù)組
for (int j = 0; j < oldCap; ++j) { //通過原容量遍歷原數(shù)組
Node<K,V> e;
if ((e = oldTab[j]) != null) { //判斷node是否為空，將j位置上的節(jié)點
//保存到e,然后將oldTab置為空六剥，這里為什么要把他置為空呢晚顷，置為空有什么好處嗎？疗疟？
//難道是吧oldTab變?yōu)橐粋€空數(shù)組音同，便于垃圾回收？秃嗜？ 這里不是很清楚
oldTab[j] = null;
if (e.next == null) //判斷node上是否有鏈表
newTab[e.hash & (newCap - 1)] = e; //無鏈表，確定元素存放位置顿膨，
//擴(kuò)容前的元素地址為 (oldCap - 1) & e.hash ,所以這里的新的地址只有兩種可能锅锨，一是地址不變，
//二是變?yōu)?老位置+oldCap
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;
/* 這里如果判斷成立恋沃，那么該元素的地址在新的數(shù)組中就不會改變必搞。因為oldCap的最高位的1，在e.hash對應(yīng)的位上為0囊咏，所以擴(kuò)容后得到的地址是一樣的恕洲，位置不會改變 ，在后面的代碼的執(zhí)行中會放到loHead中去梅割，最后賦值給newTab[j]霜第；
如果判斷不成立，那么該元素的地址變?yōu)?原下標(biāo)位置+oldCap户辞，也就是lodCap最高位的1泌类，在e.hash對應(yīng)的位置上也為1，所以擴(kuò)容后的地址改變了底燎，在后面的代碼中會放到hiHead中刃榨，最后賦值給newTab[j + oldCap]
舉個栗子來說一下上面的兩種情況：
設(shè)：oldCap=16 二進(jìn)制為：0001 0000
oldCap-1=15 二進(jìn)制為：0000 1111
e1.hash=10 二進(jìn)制為：0000 1010
e2.hash=26 二進(jìn)制為：0101 1010
e1在擴(kuò)容前的位置為：e1.hash & oldCap-1 結(jié)果為：0000 1010
e2在擴(kuò)容前的位置為：e2.hash & oldCap-1 結(jié)果為：0000 1010
結(jié)果相同弹砚，所以e1和e2在擴(kuò)容前在同一個鏈表上，這是擴(kuò)容之前的狀態(tài)枢希。
現(xiàn)在擴(kuò)容后桌吃，需要重新計算元素的位置，在擴(kuò)容前的鏈表中計算地址的方式為e.hash & oldCap-1
那么在擴(kuò)容后應(yīng)該也這么計算呀苞轿，擴(kuò)容后的容量為oldCap*2=32 0010 0000 newCap=32茅诱，新的計算
方式應(yīng)該為
e1.hash & newCap-1
即：0000 1010 & 0001 1111
結(jié)果為0000 1010與擴(kuò)容前的位置完全一樣。
e2.hash & newCap-1
即：0101 1010 & 0001 1111
結(jié)果為0001 1010,為擴(kuò)容前位置+oldCap呕屎。
而這里卻沒有e.hash & newCap-1 而是 e.hash & oldCap让簿，其實這兩個是等效的，都是判斷倒數(shù)第五位
是0秀睛，還是1尔当。如果是0，則位置不變蹂安，是1則位置改變?yōu)閿U(kuò)容前位置+oldCap椭迎。
再來分析下loTail loHead這兩個的執(zhí)行過程（假設(shè)(e.hash & oldCap) == 0成立）：
第一次執(zhí)行：
e指向oldTab[j]所指向的node對象，即e指向該位置上鏈表的第一個元素
loTail為空,所以loHead指向與e相同的node對象田盈，然后loTail也指向了同一個node對象畜号。
最后，在判斷條件e指向next允瞧，就是指向oldTab鏈表中的第二個元素
第二次執(zhí)行：
lotail不為null简软，所以lotail.next指向e，這里其實是lotail指向的node對象的next指向e述暂，
也可以說是痹升，loHead的next指向了e，就是指向了oldTab鏈表中第二個元素畦韭。此時loHead指向
的node變成了一個長度為2的鏈表疼蛾。然后lotail=e也就是指向了鏈表中第二個元素的地址。
第三次執(zhí)行：
與第二次執(zhí)行類似艺配，loHead上的鏈表長度變?yōu)?察郁，又增加了一個node，loTail指向新增的node
......
hiTail與hiHead的執(zhí)行過程與以上相同转唉，這里就不再做解釋了皮钠。
由此可以看出，loHead是用來保存新鏈表上的頭元素的赠法，loTail是用來保存尾元素的鳞芙，直到遍
歷完鏈表。 這是(e.hash & oldCap) == 0成立的時候。
(e.hash & oldCap) == 0不成立的情況也相同原朝，其實就是把oldCap遍歷成兩個新的鏈表驯嘱，
通過loHead和hiHead來保存鏈表的頭結(jié)點，然后將兩個頭結(jié)點放到newTab[j]與
newTab[j+oldCap]上面去
*/
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; //尾節(jié)點的next設(shè)置為空
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null; //尾節(jié)點的next設(shè)置為空
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap仍然是不安全的,所以在多線程并發(fā)條件下推薦使用ConcurrentHashMap喳坠。
最后
感謝你看到這里鞠评，看完有什么的不懂的可以在評論區(qū)問我，覺得文章對你有幫助的話記得給我點個贊壕鹉，每天都會分享java相關(guān)技術(shù)文章或行業(yè)資訊剃幌，歡迎大家關(guān)注和轉(zhuǎn)發(fā)文章！
