一、導(dǎo)入語(yǔ)
HashMap是我們最常見(jiàn)也是最長(zhǎng)使用的數(shù)據(jù)結(jié)構(gòu)之一，它的功能強(qiáng)大、用處廣泛。而且也是面試常見(jiàn)的考查知識(shí)點(diǎn)。常見(jiàn)問(wèn)題可能有HashMap存儲(chǔ)結(jié)構(gòu)是什么樣的？HashMap如何放入鍵值對(duì)、如何獲取鍵值對(duì)應(yīng)的值以及如何刪除一個(gè)鍵值對(duì)。今天我們就來(lái)看看HashMap底層的實(shí)現(xiàn)原理。下面我們就開(kāi)始進(jìn)入正題，分析一下hashmap源碼的實(shí)現(xiàn)原理。
二、HashMap構(gòu)造方法以及存儲(chǔ)結(jié)構(gòu)
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY]; init();
}HashMap的構(gòu)造方法有好幾個(gè)，在這里我們就不一一介紹，只說(shuō)一下我們最常見(jiàn)的HashMap無(wú)參構(gòu)造方法。上面的構(gòu)造方法中，有幾個(gè)變量需要我們這里說(shuō)明一下：
loadFactor:加載因子，默認(rèn)值為0.75；
threshold:threshold是一個(gè)閾值，初始值為默認(rèn)為16*0.75。當(dāng)hashmap中存放鍵值對(duì)數(shù)量大于該值時(shí)，表示hashmap容量大小需要擴(kuò)充，一般容量會(huì)翻倍。
table:table其實(shí)是一個(gè)Entry類型的數(shù)組，在hashmap中我們利用數(shù)組和鏈表來(lái)解決hash沖突，這里的table數(shù)組用于存放沖突鏈表的頭結(jié)點(diǎn)。
另外在HahsMap中，我們通過(guò)數(shù)組加鏈表的方式來(lái)存儲(chǔ)Entry節(jié)點(diǎn)（Entry數(shù)據(jù)結(jié)構(gòu)用于存儲(chǔ)鍵值對(duì)）。這里所謂的數(shù)組即是上面提到的table，它是一個(gè)Entry數(shù)組，table對(duì)象中節(jié)點(diǎn)初始化值均為null，當(dāng)我們新插入的節(jié)點(diǎn)第一次散列到該位置時(shí)，會(huì)將節(jié)點(diǎn)插入到table中對(duì)應(yīng)位置。如果后續(xù)存在散列位置相同的節(jié)點(diǎn)，會(huì)以鏈表的方式解決hash沖突。示意圖如下：
