hashmap

HashMap 的實例有兩個參數影響其性能：初始容量 和載入因子。容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。載入因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。在Java編程語言中，載入因子默認值為0.75，默認哈希表元為101。

注意，此實現不是同步的。如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須 保持外部同步。（結構上的修改是指添加或刪除一個或多個映射關係的任何操作；以防止對映射進行意外的非同步訪問，如下：

Map m = Collections.synchronizedMap(new HashMap(...));

由所有此類的“collection 視圖方法”所返回的迭代器都是快速失敗 的：在迭代器創建之後，如果從結構上對映射進行修改，除非通過迭代器本身的 remove方法，而不冒在將來不確定的時間發生任意不確定行為的風險。

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的併發修改時，編寫依賴於此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用於檢測程序錯誤。

遍歷Hash中的元素

在Hash中可以直接使用以下方法遍歷(所有鍵)KeySet

然後通過鍵可以找出需要的值

基於哈希表的Map介面的實現。此實現提供所有可選的映射操作，並允許使用null值和null鍵。（除了不同步和允許使用null之外，HashMap類與Hashtable大致相同。）此類不保證映射的順序，特別是不保證該順序恆久不變。另外，HashMap是非線程安全的，也就是說在多線程的環境下，可能會存在問題，而Hashtable是線程安全的。

此實現假定哈希函數將元素正確分佈在各桶之間，可為基本操作（get 和 put）提供穩定的性能。迭代集合視圖所需的時間與 HashMap 實例的“容量”（桶的數量）及其大小（鍵-值映射關係數）的和成比例。所以，如果迭代性能很重要，則不要將初始容量設置得太高（或將載入因子設置得太低）。 HashMap 的實例有兩個參數影響其性能：初始容量和載入因子。容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。載入因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時，通過調用 rehash 方法將容量翻倍。通常，默認載入因子 (.75) 在時間和空間成本上尋求一種折衷。載入因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設置初始容量時應該考慮到映射中所需的條目數及其載入因子，以便最大限度地降低 rehash 操作次數。如果初始容量大於最大條目數乘以載入因子，則不會發生 rehash 操作。如果很多映射關係要存儲在 HashMap 實例中，則相對於按需執行自動的 rehash 操作以增大表的容量來說，使用足夠大的初始容量創建它將使得映射關係能更有效地存儲。注意，此實現不是同步的。如果多個線程同時訪問此映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。（結構上的修改是指添加或刪除一個或多個映射關係的操作；僅改變與實例已經包含的鍵關聯的值不是結構上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創建時完成這一操作，以防止對映射進行意外的不同步訪問); 由所有此類的“集合視圖方法”所返回的迭代器都是快速失敗的：在迭代器創建之後，如果從結構上對映射進行修改，除非通過迭代器自身的 remove 或 add方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對併發的修改，迭代器很快就會完全失敗，而不冒在將來不確定的時間任意發生不確定行為的風險。注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的併發修改時，不可能作出任何堅決的保證。快速失敗迭代器盡最大努力拋出。編寫依賴於此異常程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用於檢測程序錯誤。

前面介紹了，HashMap是基於HashCode的，在所有對象的超類Object中有一個HashCode()方法，但是它和equals方法一樣，並不能適用於所有的情況，這樣我們就需要重寫自己的HashCode()方法。下面就舉這樣一個例子：

在這個例子中，Element用來索引對象Figureout,也即Element為key，Figureout為value。在Figureout中隨機生成一個浮點數，如果它比0.5大，列印"OK!"，否則列印"Impossible!"。之後查看Element(3)對應的Figureout結果如何。

結果卻發現，無論運行多少次，得到的結果都是"Not found"。也就是說索引Element(3)並不在HashMap中。這怎麼可能呢？

原因得慢慢來說：Element的HashCode方法繼承自Object，而Object中的HashCode方法返回的HashCode對應於當前的地址，也就是說對於不同的對象，即使它們的內容完全相同，用HashCode（）返回的值也會不同。這樣實際上違背了意圖。因為在使用HashMap時，希望利用相同內容的對象索引得到相同的目標對象，這就需要HashCode()在此時能夠返回相同的值。在上面的例子中，大家期望new Element(i) (i=5)與 Element test=new Element(5)是相同的，而實際上這是兩個不同的對象，儘管它們的內容相同，但它們在內存中的地址不同。因此很自然的，上面的程序得不到大家設想的結果。下面對Element類更改如下：

在這裡Element覆蓋了Object中的hashCode()和equals()方法。覆蓋hashCode()使其以number的值作為hashcode返回，這樣對於相同內容的對象來說它們的hashcode也就相同了。而覆蓋equals()是為了在HashMap判斷兩個key是否相等時使結果有意義（有關重寫equals()的內容可以參考我的另一篇文章《重新編寫Object類中的方法 》）。修改後的程序運行結果如下：

h2:

Get the result for Element:

OK!

請記住：如果你想有效的使用HashMap，你就必須重寫在其的HashCode()。

還有兩條重寫HashCode()的原則：

不必對每個不同的對象都產生一個唯一的hashcode，只要你的HashCode方法使get()能夠得到put()放進去的內容就可以了。即"不唯一原則"。

生成hashcode的演演算法盡量使hashcode的值分散一些，不要很多hashcode都集中在一個範圍內，這樣有利於提高HashMap的性能。即"分散原則"。

至於第二條原則的具體原因，有興趣者可以參考Bruce Eckel的《Thinking in Java》，在那裡有對HashMap內部實現原理的介紹，這裡就不贅述了。

掌握了這兩條原則，你就能夠用好HashMap編寫自己的程序了。不知道大家注意沒有，java.lang.Object中提供的三個方法：clone()，equals()和hashCode()雖然很典型，但在很多情況下都不能夠適用，它們只是簡單的由對象的地址得出結果。這就需要我們在自己的程序中重寫它們，其實java類庫中也重寫了千千萬萬個這樣的方法。利用面向對象的多態性——覆蓋，Java的設計者很優雅的構建了Java的結構，也更加體現了Java是一門純OOP語言的特性。

在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的鏈表：

我們把關鍵的方法拿出來分析：

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記錄其位置。