Flyingis

    作者：Flyingis

標準的Java類庫中包含了幾種類型的Map，它們都擁有同樣的基本接口Map，但是行為特性各不相同，主要表現在效率、鍵值對的保存、元素呈現次序、對象的保存周期和判定鍵是否等價的策略等方面。

1.Map的功能方法

Map(interface): 維護label和value的關聯性，使得可以通過label查找value。

HashMap: Map基于散列表的實現，取代了Hashtable。插入和查詢label/value的開銷是固定的，并且可以通過構造器設置容量和負載因子，以調整容器的性能。

LinkedHashMap: 在HashMap的基礎上做了一些改進，在迭代遍歷它時，取得label/value的順序是其插入的次序，或者是最近最少使用(LRU)的次序，速度上比HashMap要慢一點，但在迭代訪問時速度會更快，主要原因是它使用了鏈表維護內部次序。

TreeMap: 查看label或label/value時，元素會被排序，其次序由Comparable或Comparator決定，因此查詢所得到的結果是經過排序的。另外，它是唯一帶有subMap()方法的Map具體類，即返回一個子樹。它也是SortedMap接口的唯一實現，subMap()方法也是從該接口繼承的。

WeakHashMap: Weak Key映射，允許釋放映射所指向的對象。當映射之外沒有引用指向某個label時，此label可以被垃圾收集器回收。

IdentityHashMap: 使用==代替equals()對label進行比較的散列映射。

2.hashCode()

         當使用標準庫中的類Integer作為HashMap的label時，程序能夠正常運行，但是使用自己創建的類作為HashMap的label時，通常犯一個錯誤。

         在HashMap中通過label查找value時，實際上是計算label對象地址的散列碼來確定value的。一般情況下，我們是使用基類Object的方法hashCode()來生成散列碼，它默認是使用對象的地址來計算的，因此由第一個對象new Apple(5)和第二個對象new Apple(5)生成的散列碼是不同的，不能完成正確的查找。通常，我們可以編寫自己的hashCode()方法來覆蓋基類的原始方法，但與此同時，我們必須同時實現equals()方法來判斷當前的label是否與表中存在的label相同。正確的equals()方法滿足五個條件：

(1)     自反性。對于任意的x，x.equals(x)一定返回true。

(2)     對稱性。對于任意的x和y，如果y.equals(x)返回true，則x.equals(y)也返回true。

(3)     傳遞性。對于任意的x、y、z，如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true。

(4)     一致性。對于任意的x和y，如果對象中用于等價比較的信息沒有改變，那么無論調用x.equals(y)多少次，返回的結果應該保持一致，要么一直是true，要么一直是false。

(5)     對任何不是null的x，x.equals(null)一定返回false。

equals()比較的是對象的地址，如果要使用自己的類作為HashMap的label，必須同時重載hashCode()和equals()方法。

使用散列的目的：想要使用一個對象來查找另一個對象。使用TreeSet或TreeMap也能實現此目的。另外，還可以自己實現一個Map，此時，必須提供Map.entrySet()方法來生成Map.Entry對象的Set。

使用散列的價值：速度，散列使得查詢可以快速進行。散列將label保存載數組中方便快速查詢，因為存儲一組元素最快的數據結構是數組，用它來表示label的信息(后面有信息的描述)，而不是label本身。通過label對象計算得到一個數字，作為數組的下標，這個數字就是散列碼(即前面所述的信息)。該散列碼具體是通過定義在基類Object中，可能由程序員自定義的類覆蓋的hashCode()方法，即散列函數生成。為了解決數組容量帶來的限制，可以使不同的label生成相同的下標，保存在一個鏈表list中，每一個鏈表就是數組的一個元素。查詢label時就可以通過對list中的信息進行查找，當散列函數比較好，數組的每個位置中的list長度較短，則可以快速查找到數組元素list中的某個位置，提高了整體速度。

散列表中的slot通常稱為bucket，為了使散列分步均勻，bucket的值一般取質數。但事實證明，質數實際上并不是散列bucket的理想容量，近來Java散列實現都使用2的冪，具體如何驗證以后再續。

3.HashMap的性能因子

容量(capacity): 散列表中bucket的數量。

初始化容量(initial capacity): 創建散列表時bucket的數量。可以在構造方法中指定HashMap和HashSet的初始化容量。

尺寸(size): 散列表中記錄的數量。(數組的元素個數，非list中元素總和)

負載因子(load factor): 尺寸/容量。負載因子為0，表示空的散列表，0.5表示半滿的散列表。輕負載的散列表具有沖突少，適宜插入與查詢的特點，但是使用迭代器遍歷會比較慢。較高的負載會減少所需空間大小。當負載達到指定值時，容器會自動成倍地增加容量，并將原有的對象重新分配，存入新的bucket中，這個過程稱為“重散列”。

4.重寫hashCode()的關鍵

(1)     對同一個對象調用hashCode()都應該生成同樣的值。

(2)     hashCode()方法不要依賴于對象中易變的數據，當數據發生變化時，hashCode()就會生成一個不同的散列碼，即產生了一個不同的label。

(3)     hashCode()不應依賴于具有唯一性的對象信息，例如對象地址。

(4)     散列碼應該更關心速度，而不是唯一性，因為散列碼不必是唯一的。

(5)     好的hashCode()應該產生分步均勻的散列碼。在Effective Java(Addison-Wesley 2001)中，Joshua Bloch給hashCode()給出了設計指導，可以參考。