一、導(dǎo)入語
HashMap是我們最常見也是最長使用的數(shù)據(jù)結(jié)構(gòu)之一,它的功能強(qiáng)大、用處廣泛。而且也是面試常見的考查知識(shí)點(diǎn)。常見問題可能有HashMap存儲(chǔ)結(jié)構(gòu)是什么樣的?HashMap如何放入鍵值對(duì)、如何獲取鍵值對(duì)應(yīng)的值以及如何刪除一個(gè)鍵值對(duì)。今天我們就來看看HashMap底層的實(shí)現(xiàn)原理。下面我們就開始進(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è),在這里我們就不一一介紹,只說一下我們最常見的HashMap無參構(gòu)造方法。上面的構(gòu)造方法中,有幾個(gè)變量需要我們這里說明一下:
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ù)組和鏈表來解決hash沖突,這里的table數(shù)組用于存放沖突鏈表的頭結(jié)點(diǎn)。
另外在HahsMap中,我們通過數(shù)組加鏈表的方式來存儲(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沖突。示意圖如下: