Flyingis

    作者：Flyingis

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

1.Map的功能方法

Map(interface): 維護(hù)label和value的關(guān)聯(lián)性，使得可以通過label查找value。

HashMap: Map基于散列表的實(shí)現(xiàn)，取代了Hashtable。插入和查詢label/value的開銷是固定的，并且可以通過構(gòu)造器設(shè)置容量和負(fù)載因子，以調(diào)整容器的性能。

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

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

WeakHashMap: Weak Key映射，允許釋放映射所指向的對(duì)象。當(dāng)映射之外沒有引用指向某個(gè)label時(shí)，此label可以被垃圾收集器回收。

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

2.hashCode()

         當(dāng)使用標(biāo)準(zhǔn)庫中的類Integer作為HashMap的label時(shí)，程序能夠正常運(yùn)行，但是使用自己創(chuàng)建的類作為HashMap的label時(shí)，通常犯一個(gè)錯(cuò)誤。

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

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

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

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

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

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

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

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

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

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

3.HashMap的性能因子

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

初始化容量(initial capacity): 創(chuàng)建散列表時(shí)bucket的數(shù)量。可以在構(gòu)造方法中指定HashMap和HashSet的初始化容量。

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

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

4.重寫hashCode()的關(guān)鍵

(1)     對(duì)同一個(gè)對(duì)象調(diào)用hashCode()都應(yīng)該生成同樣的值。

(2)     hashCode()方法不要依賴于對(duì)象中易變的數(shù)據(jù)，當(dāng)數(shù)據(jù)發(fā)生變化時(shí)，hashCode()就會(huì)生成一個(gè)不同的散列碼，即產(chǎn)生了一個(gè)不同的label。

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

(4)     散列碼應(yīng)該更關(guān)心速度，而不是唯一性，因?yàn)樯⒘写a不必是唯一的。

(5)     好的hashCode()應(yīng)該產(chǎn)生分步均勻的散列碼。在Effective Java(Addison-Wesley 2001)中，Joshua Bloch給hashCode()給出了設(shè)計(jì)指導(dǎo)，可以參考。