手机福利在线,日本一区二区综合亚洲

主頁(yè) > 知識(shí)庫(kù) > Java中對(duì)HashMap的深度分析

Java中對(duì)HashMap的深度分析

在Java的世界里，無(wú)論類(lèi)還是各種數(shù)據(jù)，其結(jié)構(gòu)的處理是整個(gè)程序的邏輯以及性能的關(guān)鍵。由于本人接觸了一個(gè)有關(guān)性能與邏輯同時(shí)并存的問(wèn)題，于是就開(kāi)始研究這方面的問(wèn)題。找遍了大大小小的論壇，也把《Java 虛擬機(jī)規(guī)范》，《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》，和《Thinking in Java》翻了也找不到很好的答案，于是一氣之下把JDK的 src 解壓出來(lái)研究，擴(kuò)然開(kāi)朗，遂寫(xiě)此文，跟大家分享感受和順便驗(yàn)證我理解還有沒(méi)有漏洞。這里就拿HashMap來(lái)研究吧。

　　HashMap可謂JDK的一大實(shí)用工具，把各個(gè)Object映射起來(lái)，實(shí)現(xiàn)了“鍵－－值”對(duì)應(yīng)的快速存取。但實(shí)際里面做了些什么呢？

　　在這之前，先介紹一下負(fù)載因子和容量的屬性。大家都知道其實(shí)一個(gè) HashMap 的實(shí)際容量就因子*容量，其默認(rèn)值是 16×0.75＝12；這個(gè)很重要，對(duì)效率很一定影響！當(dāng)存入HashMap的對(duì)象超過(guò)這個(gè)容量時(shí)，HashMap 就會(huì)重新構(gòu)造存取表。這就是一個(gè)大問(wèn)題，我后面慢慢介紹，反正，如果你已經(jīng)知道你大概要存放多少個(gè)對(duì)象，最好設(shè)為該實(shí)際容量的能接受的數(shù)字。

　　兩個(gè)關(guān)鍵的方法，put和get：

　　先有這樣一個(gè)概念，HashMap是聲明了 Map，Cloneable, Serializable 接口，和繼承了 AbstractMap 類(lèi)，里面的 Iterator 其實(shí)主要都是其內(nèi)部類(lèi)HashIterator 和其他幾個(gè) iterator 類(lèi)實(shí)現(xiàn)，當(dāng)然還有一個(gè)很重要的繼承了Map.Entry 的 Entry 內(nèi)部類(lèi)，由于大家都有源代碼，大家有興趣可以看看這部分，我主要想說(shuō)明的是 Entry 內(nèi)部類(lèi)。它包含了hash，value，key 和next 這四個(gè)屬性，很重要。put的源碼如下

　　public Object put(Object key, Object value) {
　　Object k = maskNull(key);

　　這個(gè)就是判斷鍵值是否為空，并不很深?yuàn)W，其實(shí)如果為空，它會(huì)返回一個(gè)static Object 作為鍵值，這就是為什么HashMap允許空鍵值的原因。

　　int hash = hash(k);
　　int i = indexFor(hash, table.length);

　　這連續(xù)的兩步就是 HashMap 最牛的地方！研究完我都汗顏了，其中 hash 就是通過(guò) key 這個(gè)Object的 hashcode 進(jìn)行 hash，然后通過(guò) indexFor 獲得在Object table的索引值。

　　table？？？不要驚訝，其實(shí)HashMap也神不到哪里去，它就是用 table 來(lái)放的。最牛的就是用 hash 能正確的返回索引。其中的hash算法，我跟JDK的作者 Doug 聯(lián)系過(guò)，他建議我看看《The art of programing vol3》可恨的是，我之前就一直在找，我都找不到，他這樣一提，我就更加急了，可惜口袋空空?。。?！

　　不知道大家有沒(méi)有留意 put 其實(shí)是一個(gè)有返回的方法，它會(huì)把相同鍵值的 put 覆蓋掉并返回舊的值！如下方法徹底說(shuō)明了 HashMap 的結(jié)構(gòu)，其實(shí)就是一個(gè)表加上在相應(yīng)位置的Entry的鏈表：

　　for (Entry e = table[i]; e != null; e = e.next) {
　　if (e.hash == hash eq(k, e.key)) {
　　Object oldvalue = e.value;
　　e.value = value; //把新的值賦予給對(duì)應(yīng)鍵值。
　　e.recordAccess(this); //空方法，留待實(shí)現(xiàn)
　　return oldvalue; //返回相同鍵值的對(duì)應(yīng)的舊的值。
　　}
　　}
　　modCount++; //結(jié)構(gòu)性更改的次數(shù)
　　addEntry(hash, k, value, i); //添加新元素，關(guān)鍵所在！
　　return null; //沒(méi)有相同的鍵值返回
　　}

　　我們把關(guān)鍵的方法拿出來(lái)分析：

　　void addEntry(int hash, Object key, Object value, int bucketIndex) {
　　table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);

　　因?yàn)?hash 的算法有可能令不同的鍵值有相同的hash碼并有相同的table索引，如：key＝“33”和key＝Object g的hash都是－8901334，那它經(jīng)過(guò)indexfor之后的索引一定都為i，這樣在new的時(shí)候這個(gè)Entry的next就會(huì)指向這個(gè)原本的table[i]，再有下一個(gè)也如此，形成一個(gè)鏈表，和put的循環(huán)對(duì)定e.next獲得舊的值。到這里，HashMap的結(jié)構(gòu)，大家也十分明白了吧？

　　if (size++ >= threshold) //這個(gè)threshold就是能實(shí)際容納的量
　　resize(2 * table.length); //超出這個(gè)容量就會(huì)將Object table重構(gòu)

　　所謂的重構(gòu)也不神，就是建一個(gè)兩倍大的table（我在別的論壇上看到有人說(shuō)是兩倍加1，把我騙了），然后再一個(gè)個(gè)indexfor進(jìn)去！注意！！這就是效率！！如果你能讓你的HashMap不需要重構(gòu)那么多次，效率會(huì)大大提高！

　　說(shuō)到這里也差不多了，get比put簡(jiǎn)單得多，大家，了解put，get也差不了多少了。對(duì)于collections我是認(rèn)為，它是適合廣泛的，當(dāng)不完全適合特有的，如果大家的程序需要特殊的用途，自己寫(xiě)吧，其實(shí)很簡(jiǎn)單。（作者是這樣跟我說(shuō)的，他還建議我用LinkedHashMap,我看了源碼以后發(fā)現(xiàn)，LinkHashMap其實(shí)就是繼承HashMap的，然后override相應(yīng)的方法，有興趣的同人，自己looklook）建個(gè) Object table，寫(xiě)相應(yīng)的算法，就ok啦。

　　舉個(gè)例子吧，像 Vector，list 啊什么的其實(shí)都很簡(jiǎn)單，最多就多了的同步的聲明，其實(shí)如果要實(shí)現(xiàn)像Vector那種，插入，刪除不多的，可以用一個(gè)Object table來(lái)實(shí)現(xiàn)，按索引存取，添加等。

　　如果插入，刪除比較多的，可以建兩個(gè)Object table，然后每個(gè)元素用含有next結(jié)構(gòu)的，一個(gè)table存，如果要插入到i，但是i已經(jīng)有元素，用next連起來(lái)，然后size＋＋，并在另一個(gè)table記錄其位置。

您可能感興趣的文章:

Java中HashMap和TreeMap的區(qū)別深入理解
JAVA HashMap詳細(xì)介紹和示例
java HashMap通過(guò)value反查key的代碼示例
Java中HashMap和Hashtable及HashSet的區(qū)別
java遍歷HashMap簡(jiǎn)單的方法
舉例詳解Java編程中HashMap的初始化以及遍歷的方法
java無(wú)鎖hashmap原理與實(shí)現(xiàn)詳解
Java8 HashMap的實(shí)現(xiàn)原理分析
java使用hashMap緩存保存數(shù)據(jù)的方法
Java HashMap的工作原理
深入理解Java中的HashMap的實(shí)現(xiàn)機(jī)制
Java集合之HashMap用法詳解

標(biāo)簽：大興安嶺紅河岳陽(yáng) 拉薩鄭州武威亳州馬鞍山

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《Java中對(duì)HashMap的深度分析》，本文關(guān)鍵詞 Java,中對(duì),HashMap,的,深度分析,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。