在Java的世界里，無(wú)論類還是各種數(shù)據(jù)，其結(jié)構(gòu)的處理是整個(gè)程序的邏輯以及性能的關(guān)鍵。由于本人接觸了一個(gè)有關(guān)性能與邏輯同時(shí)并存的問(wèn)題，于是就開始研究這方面的問(wèn)題。找遍了大大小小的論壇，也把《Java 虛擬機(jī)規(guī)范》，《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》，和《Thinking in Java》翻了也找不到很好的答案，于是一氣之下把JDK的 src 解壓出來(lái)研究，擴(kuò)然開朗，遂寫此文，跟大家分享感受和順便驗(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 類，里面的 Iterator 其實(shí)主要都是其內(nèi)部類HashIterator 和其他幾個(gè) iterator 類實(shí)現(xiàn)，當(dāng)然還有一個(gè)很重要的繼承了Map.Entry 的 Entry 內(nèi)部類，由于大家都有源代碼，大家有興趣可以看看這部分，我主要想說(shuō)明的是 Entry 內(nè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》可恨的是，我之前就一直在找，我都找不到，他這樣一提，我就更加急了，可惜口袋空空?。。。?br>
不知道大家有沒(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)不完全適合特有的，如果大家的程序需要特殊的用途，自己寫吧，其實(shí)很簡(jiǎn)單。（作者是這樣跟我說(shuō)的，他還建議我用LinkedHashMap,我看了源碼以后發(fā)現(xiàn)，LinkHashMap其實(shí)就是繼承HashMap的，然后override相應(yīng)的方法，有興趣的同人，自己looklook）建個(gè) Object table，寫相應(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記錄其位置。
