在Java的世界里，無論類還是各種數據，其結構的處理是整個程序的邏輯以及性能的關鍵。由于本人接觸了一個有關性能與邏輯同時并存的問題，于是就開始研究這方面的問題。找遍了大大小小的論壇，也把《Java 虛擬機規范》，《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》，和《Thinking in Java》翻了也找不到很好的答案，于是一氣之下把JDK的 src 解壓出來研究，擴然開朗，遂寫此文，跟大家分享感受和順便驗證我理解還有沒有漏洞。 這里就拿HashMap來研究吧。
　　
　　HashMap可謂JDK的一大實用工具，把各個Object映射起來，實現了“鍵－－值”對應的快速存取。但實際里面做了些什么呢？

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

　　兩個關鍵的方法，put和get：

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

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

　　這個就是判斷鍵值是否為空，并不很深奧，其實如果為空，它會返回一個static Object 作為鍵值，這就是為什么HashMap允許空鍵值的原因。

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

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

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

　　不知道大家有沒有留意 put 其實是一個有返回的方法，它會把相同鍵值的 put 覆蓋掉并返回舊的值！如下方法徹底說明了 HashMap 的結構，其實就是一個表加上在相應位置的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; //把新的值賦予給對應鍵值。
　　e.recordAccess(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＝“33”和key＝Object g的hash都是－8901334，那它經過indexfor之后的索引一定都為i，這樣在new的時候這個Entry的next就會指向這個原本的table[i]，再有下一個也如此，形成一個鏈表，和put的循環對定e.next獲得舊的值。到這里，HashMap的結構，大家也十分明白了吧？

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

　　所謂的重構也不神，就是建一個兩倍大的table（我在別的論壇上看到有人說是兩倍加1，把我騙了），然后再一個個indexfor進去！注意�。∵@就是效率�。∪绻�你能讓你的HashMap不需要重構那么多次，效率會大大提高！

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

　　舉個例子吧，像 Vector，list 啊什么的其實都很簡單，最多就多了的同步的聲明，其實如果要實現像Vector那種，插入，刪除不多的，可以用一個Object table來實現，按索引存取，添加等。

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