javahashmap工作原理-java開發(fā)java經(jīng)驗(yàn)技巧

《javahashmap工作原理-java開發(fā)java經(jīng)驗(yàn)技巧》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、JavaHashMap211作原理-編程開發(fā)技術(shù)JavaHashMap工作原理木文由ImportNew?Wing翻譯自coding-geek0歡迎加入翻譯小組。轉(zhuǎn)載請(qǐng)見文末要求。大部分Java開發(fā)者都在使用Map,特別是HashMapoHashMap是種簡(jiǎn)單但強(qiáng)人的方式去存儲(chǔ)和獲取數(shù)據(jù)。但有多少開發(fā)者知道HashMap內(nèi)部如何工作呢？幾天前,我閱讀了java.util.HashMap的大量源代碼(包括Java7和Java8),來深入理解這個(gè)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。在這篇文章中，我會(huì)解釋java.util.HashMap的實(shí)現(xiàn)，描述Jav

2、a8實(shí)現(xiàn)中添加的新特性，并討論性能、內(nèi)存以及使用HashMap吋的一些已知問題。內(nèi)部存儲(chǔ)JavaHashMap類實(shí)現(xiàn)了Map〈K,V>接口。這個(gè)接口中的主要方法包扌乩?Vput(Kkey,Vvalue)?Vget(Objectkey)?Vremove(Objectkey)?BooleancontainsKcy(Objcctkey)HashMap使用了一個(gè)內(nèi)部類Entry〈K,V>來存儲(chǔ)數(shù)據(jù)。這個(gè)內(nèi)部類是一個(gè)簡(jiǎn)單的鍵值對(duì)，并帶有額外兩個(gè)數(shù)據(jù)：?一個(gè)指向其他入口(譯者注：引用對(duì)彖)的引用，這樣HashMap可以存儲(chǔ)類似鏈接列表這樣的

3、對(duì)象。?一個(gè)用來代表鍵的哈希值，存儲(chǔ)這個(gè)值可以避免HashMap在每次需要時(shí)都重新生成鍵所對(duì)應(yīng)的哈希值。下面是Entry在Java7下的一部分代碼:staticclassEntryimplementsMap.Entry{finalKkey;Vvalue;Entrynext;inihash;???}HashMap將數(shù)據(jù)存儲(chǔ)到多個(gè)單向Entry鏈表中(有時(shí)也被稱為桶bucket或者容器orbins)0所有的列表都被注冊(cè)到一個(gè)Entry數(shù)組中(Entry[]數(shù)組),這個(gè)內(nèi)部數(shù)組的默認(rèn)長(zhǎng)

4、度是16。下而這幅圖描述了一個(gè)HashMap實(shí)例的內(nèi)部存儲(chǔ)，它包含一個(gè)nullable對(duì)象組成的數(shù)組。每個(gè)對(duì)彖都連接到另外一個(gè)對(duì)彖，這樣就構(gòu)成了一個(gè)鏈表。uckets/bin所冇具冇相同哈希值的鍵都會(huì)被放到同一個(gè)鏈表(桶)中。具冇不同哈希值的鍵最終可能會(huì)在相同的桶中。當(dāng)用戶調(diào)用put(Kkey,Vvalue)或者get(Objectkey)時(shí)，程序會(huì)計(jì)算對(duì)彖應(yīng)該在的桶的索引。然后，程序會(huì)迭代遍歷對(duì)應(yīng)的列表，來尋找具有相同鍵的Entry對(duì)象(使用鍵的equals()方法)。對(duì)于調(diào)用get()的情況，程序會(huì)返冋值所對(duì)應(yīng)的Entry對(duì)

5、象(如果Entry對(duì)象存在)。對(duì)于調(diào)用put(Kkey,Vvalue)的情況,如果Entry對(duì)象已經(jīng)存在,那么程序會(huì)將值替換為新值，否則，程序會(huì)在單向鏈表的表頭創(chuàng)建一個(gè)新的Entry(從參數(shù)中的鍵和值)。桶(鏈表)的索引，是通過nmp的3個(gè)步驟生成的：?首先獲収鍵的散列碼。?程序重復(fù)散列碼，來阻止針對(duì)鍵的糟糕的哈希函數(shù)，因?yàn)檫@有可能會(huì)將所有的數(shù)據(jù)都放到內(nèi)部數(shù)組的相同的索引(桶)上。?程序拿到重復(fù)后的散列碼，并對(duì)其使川數(shù)組長(zhǎng)度(授小是1)的位掩碼(bit-mask)o這個(gè)操作可以保證索引不會(huì)人于數(shù)組的人小。你可以將其看做是一個(gè)經(jīng)過

6、計(jì)算的優(yōu)化収模函數(shù)。卜?面是生成索引的源代碼：//the"rehash"functioninJAVA7thattakesthehashcodeofthekeystaticinthash(inth){h八二(h?>20)八(h?>12);returnh八(h>>>7)八(h>>>4);//the"rehash"functioninJAVA8thatdirectlytakesthekeystaticfinalinthash(Objectkey){inth;return(key二二nul1)?0:(h二key.hashCode())八

7、(h>>>16);}//thefunctionthatreturnstheindexfromtherehashedhashstaticintindexFor(inth,intlength){returnh&dength~l);}為了更有效地工作，內(nèi)部數(shù)組的大小必須是2的幕值。讓我們看一下為什么：假設(shè)數(shù)組的長(zhǎng)度是17,那么掩碼的值就是16(數(shù)組長(zhǎng)度-1)o16的二進(jìn)制表示是0???010000,這樣對(duì)于任何值H來說，“H&16”的結(jié)果就是16或者0。這意味著長(zhǎng)度為17的數(shù)組只能應(yīng)用到兩個(gè)桶上：一個(gè)是0,另外一個(gè)是16,這樣不是很冇

8、效率。但是如果你將數(shù)組的長(zhǎng)度設(shè)置為2的幕值，例如16,那么按位索引的工作變成“H&15”。15的二進(jìn)制表示是0-001111,索引公式輸出的值可以從0到15,這樣長(zhǎng)度為16的數(shù)組就可以被充分使用了。例如：?如果H=952,它的二進(jìn)制表示是0..011101110