javahashset和hashmap源碼剖析-編程開(kāi)發(fā)技術(shù)

《javahashset和hashmap源碼剖析-編程開(kāi)發(fā)技術(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、JavaHashSct和HashMap源碼剖析-編程開(kāi)發(fā)技術(shù)JavaHashSet和HashMap源碼剖析原文出處：CarpenterLee總體介紹之所以把HashSet和HashMap放在一起講解，是因?yàn)槎咴贘ava里有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說(shuō)血s力Se方里面有一個(gè)朋(適配器模式)。因此本文將重點(diǎn)分析HashMap.HashMap實(shí)現(xiàn)了疑如接口，允許放入mill元索，除該類(lèi)未實(shí)現(xiàn)同步外，其余跟Ilashtablc大致相同，跟如不同，該容器不保證元素順序，根據(jù)需要該容器可能會(huì)對(duì)元素重新哈希，元

2、素的順序也會(huì)被重新打散，因此不同時(shí)間迭代同一個(gè)HashMap的順序可能會(huì)不同。根據(jù)對(duì)沖突的處理方式不同，哈希表有兩種實(shí)現(xiàn)方式，一種開(kāi)放地址方式(Openaddressing),另一種是沖突鏈表方式(Separatechainingwithlinkedlists)。Java?屁sAtfep采用的是沖突鏈表方式oEntryvK,V>[]tableHashMap纟吉buckets0X1■■2■■3X4■■5X6X7■■muedeukey

3、value?key

4、valueX左〉右!口汁做Tkey

5、value?key

6、valu

7、eX從上圖容易看出，如果選擇合適的哈希函數(shù)，put()和gct()方法可以在常數(shù)時(shí)間內(nèi)完成。但在對(duì)/fes加徹7進(jìn)行迭代時(shí)，需耍遍歷整個(gè)table以及后而跟的沖突鏈表。因此對(duì)于迭代比較頻繁的場(chǎng)景，不宜將血3加血的初始大小設(shè)的過(guò)大。有兩個(gè)參數(shù)可以影響HashMap的性能：初始容量(inilalcapacity)和負(fù)載系數(shù)(loadfactor)o初始容量指定了初始table的大小，負(fù)載系數(shù)用來(lái)指定自動(dòng)擴(kuò)容的臨界值。當(dāng)entry的數(shù)量超iicapacity*loadfactor吋,容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元索較多的

8、場(chǎng)景，將初始容量設(shè)大可以減少重新哈希的次數(shù)。將對(duì)向放入到HashMap或Zfes力SeZ■屮II寸，有兩個(gè)方法需要特別關(guān)心：hashCode()和equals()ohashCode0方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里，當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí)，equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以，如果耍將自定義的對(duì)象放入到HashMap或HashSet屮,需要@Override?hashCode()和equals()方法。方法剖析get0get(Objectkey)方法根據(jù)指定的key值返冋對(duì)應(yīng)的value,

9、該方法調(diào)用了getEntry(Objectkey)得到相應(yīng)的entry,然后返冋entry.getValueO。因此getEntry()是算法的核心。算法思想是首先通過(guò)heishO函數(shù)得到對(duì)應(yīng)bucket的卜?標(biāo)，然后依次遍歷沖突鏈表，通過(guò)key.equals(k)方法來(lái)判斷是否是要找的那個(gè)entry。從上圖容易看出，如果選擇合適的哈希函數(shù)，put()和gct()方法可以在常數(shù)時(shí)間內(nèi)完成。但在對(duì)/fes加徹7進(jìn)行迭代時(shí)，需耍遍歷整個(gè)table以及后而跟的沖突鏈表。因此對(duì)于迭代比較頻繁的場(chǎng)景，不宜將血3加血的初始大小設(shè)的過(guò)大

10、。有兩個(gè)參數(shù)可以影響HashMap的性能：初始容量(inilalcapacity)和負(fù)載系數(shù)(loadfactor)o初始容量指定了初始table的大小，負(fù)載系數(shù)用來(lái)指定自動(dòng)擴(kuò)容的臨界值。當(dāng)entry的數(shù)量超iicapacity*loadfactor吋,容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元索較多的場(chǎng)景，將初始容量設(shè)大可以減少重新哈希的次數(shù)。將對(duì)向放入到HashMap或Zfes力SeZ■屮II寸，有兩個(gè)方法需要特別關(guān)心：hashCode()和equals()ohashCode0方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里，當(dāng)多個(gè)

11、對(duì)象的哈希值沖突時(shí)，equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以，如果耍將自定義的對(duì)象放入到HashMap或HashSet屮,需要@Override?hashCode()和equals()方法。方法剖析get0get(Objectkey)方法根據(jù)指定的key值返冋對(duì)應(yīng)的value,該方法調(diào)用了getEntry(Objectkey)得到相應(yīng)的entry,然后返冋entry.getValueO。因此getEntry()是算法的核心。算法思想是首先通過(guò)heishO函數(shù)得到對(duì)應(yīng)bucket的卜?標(biāo)，然后依次遍歷沖突

12、鏈表，通過(guò)key.equals(k)方法來(lái)判斷是否是要找的那個(gè)entry。上圖中hash(k)&(table,length-1)等價(jià)于hash(k)%table.length,原因是HashMap要求table,length必須是2的指數(shù)，因此table,length-1就是二進(jìn)制低位全是1,跟hash