在Java的世界裡無論類還是各種數據其結構的處理是整個程序的邏輯以及性能的關鍵由於本人接觸了一個有關性能與邏輯同時並存的問題於是就開始研究這方面的問題找遍了大大小小的論壇也把《Java 虛擬機規范》《apressllections()bmocrshareconnector》和《Thinking in Java》翻了也找不到很好的答案於是一氣之下把JDK的src 解壓出來研究擴然開朗遂寫此文跟大家分享感受和順便驗證我理解還有沒有漏洞 這裡就拿HashMap來研究吧
HashMap可謂JDK的一大實用工具把各個Object映射起來實現了鍵－－值對應的快速存取但實際裡面做了些什麼呢？
在這之前先介紹一下負載因子和容量的屬性大家都知道其實一個 HashMap 的實際容量就 因子*容量其默認值是 ×＝ 這個很重要對效率很一定影響！當存入HashMap的對象超過這個容量時HashMap 就會重新構造存取表這就是一個大問題我後面慢慢介紹反正如果你已經知道你大概要存放多少個對象最好設為該實際容量的能接受的數字
兩個關鍵的方法put和get
先有這樣一個概念HashMap是聲明了 MapCloneable Serializable 接口和繼承了 AbstractMap 類裡面的 Iterator 其實主要都是其內部類HashIterator 和其他幾個 iterator 類實現當然還有一個很重要的繼承了MapEntry 的 Entry 內部類由於大家都有源代碼大家有興趣可以看看這部分我主要想說明的是 Entry 內部類它包含了hashvaluekey 和next 這四個屬性很重要put的源碼如下
public Object put(Object key Object value) {
Object k = maskNull(key);
這個就是判斷鍵值是否為空並不很深奧其實如果為空它會返回一個static Object 作為鍵值這就是為什麼HashMap允許空鍵值的原因
int hash = hash(k);
int i = indexFor(hash tablelength);
這連續的兩步就是 HashMap 最牛的地方！研究完我都汗顏了其中 hash 就是通過 key 這個Object的 hashcode 進行 hash然後通過 indexFor 獲得在Object table的索引值
table？不要驚訝其實HashMap也神不到哪裡去它就是用 table 來放的最牛的就是用 hash 能正確的返回索引其中的hash算法我跟JDK的作者 Doug 聯系過他建議我看看《The art of programing vol》可恨的是我之前就一直在找我都找不到他這樣一提我就更加急了可惜口袋空空啊！
不知道大家有沒有留意 put 其實是一個有返回的方法它會把相同鍵值的 put 覆蓋掉並返回舊的值！如下方法徹底說明了 HashMap 的結構其實就是一個表加上在相應位置的Entry的鏈表
for (Entry e = table[i]; e != null; e = enext) {
if (ehash == hash && eq(k ekey)) {
Object oldvalue = evalue;
evalue = value; //把新的值賦予給對應鍵值
erecordAccess(this); //空方法留待實現
return oldvalue; //返回相同鍵值的對應的舊的值
}
}
modCount++; //結構性更改的次數
addEntry(hash k value i); //添加新元素關鍵所在！
return null; //沒有相同的鍵值返回
}
我們把關鍵的方法拿出來分析
void addEntry(int hash Object key Object value int bucketIndex) {
table[bucketIndex] = new Entry(hash key value table[bucketIndex]);
因為 hash 的算法有可能令不同的鍵值有相同的hash碼並有相同的table索引
如
key＝
和key＝Object g的hash都是－
那它經過indexfor之後的索引一定都為i
這樣在new的時候這個Entry的next就會指向這個原本的table[i]
再有下一個也如此
形成一個鏈表
和put的循環對定e
next獲得舊的值
到這裡
HashMap的結構
大家也十分明白了吧？
if (size++ >= threshold) //這個threshold就是能實際容納的量
resize( * tablelength); //超出這個容量就會將Object table重構
所謂的重構也不神就是建一個兩倍大的table（我在別的論壇上看到有人說是兩倍加把我騙了）然後再一個個indexfor進去！注意！！這就是效率！！如果你能讓你的HashMap不需要重構那麼多次效率會大大提高！
說到這裡也差不多了get比put簡單得多大家了解putget也差不了多少了對於collections我是認為它是適合廣泛的當不完全適合特有的如果大家的程序需要特殊的用途自己寫吧其實很簡單（作者是這樣跟我說的他還建議我用LinkedHashMap我看了源碼以後發現LinkHashMap其實就是繼承HashMap的然後override相應的方法有興趣的同人自己looklook）建個 Object table寫相應的算法就ok啦
舉個例子吧像 Vectorlist 啊什麼的其實都很簡單最多就多了的同步的聲明其實如果要實現像Vector那種插入刪除不多的可以用一個Object table來實現按索引存取添加等
如果插入刪除比較多的可以建兩個Object table然後每個元素用含有next結構的一個table存如果要插入到i但是i已經有元素用next連起來然後size＋＋並在另一個table記錄其位置
From:http://tw.wingwit.com/Article/program/Java/hx/201311/27015.html
