容器類可以大大提高編程效率和編程能力，在Java2中，所有的容器都由SUN公司的Joshua Bloch進(jìn)行了重新設(shè)計，豐富了容器類庫的功能。

         Java2容器類類庫的用途是“保存對象”，它分為兩類：

Collection----一組獨(dú)立的元素，通常這些元素都服從某種規(guī)則。List必須保持元素特定的順序，而Set不能有重復(fù)元素。

Map----一組成對的“鍵值對”對象，即其元素是成對的對象，最典型的應(yīng)用就是數(shù)據(jù)字典，并且還有其它廣泛的應(yīng)用。另外，Map可以返回其所有鍵組成的Set和其所有值組成的Collection，或其鍵值對組成的Set，并且還可以像數(shù)組一樣擴(kuò)展多維Map，只要讓Map中鍵值對的每個“值”是一個Map即可。

1.迭代器

       迭代器是一種設(shè)計模式，它是一個對象，它可以遍歷并選擇序列中的對象，而開發(fā)人員不需要了解該序列的底層結(jié)構(gòu)。迭代器通常被稱為“輕量級”對象，因?yàn)閯?chuàng)建它的代價小。

       Java中的Iterator功能比較簡單，并且只能單向移動：

(1)    使用方法iterator()要求容器返回一個Iterator。第一次調(diào)用Iterator的next()方法時，它返回序列的第一個元素。

(2)    使用next()獲得序列中的下一個元素。

(3)    使用hasNext()檢查序列中是否還有元素。

(4)    使用remove()將迭代器新返回的元素刪除。

Iterator是Java迭代器最簡單的實(shí)現(xiàn)，為List設(shè)計的ListIterator具有更多的功能，它可以從兩個方向遍歷List，也可以從List中插入和刪除元素。

2.List的功能方法

List(interface): 次序是List最重要的特點(diǎn)；它確保維護(hù)元素特定的順序。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素(只推薦LinkedList使用)。一個List可以生成ListIterator，使用它可以從兩個方向遍歷List，也可以從List中間插入和刪除元素。

ArrayList: 由數(shù)組實(shí)現(xiàn)的List。它允許對元素進(jìn)行快速隨機(jī)訪問，但是向List中間插入與移除元素的速度很慢。ListIterator只應(yīng)該用來由后向前遍歷ArrayList，而不是用來插入和刪除元素，因?yàn)檫@比LinkedList開銷要大很多。

LinkedList: 對順序訪問進(jìn)行了優(yōu)化，向List中間插入與刪除得開銷不大，隨機(jī)訪問則相對較慢(可用ArrayList代替)。它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()，這些方法(沒有在任何接口或基類中定義過)使得LinkedList可以當(dāng)作堆棧、隊列和雙向隊列使用。

3.Set的功能方法

Set(interface): 存入Set的每個元素必須是唯一的，因?yàn)镾et不保存重復(fù)元素。加入Set的Object必須定義equals()方法以確保對象的唯一性。Set與Collection有完全一樣的接口。Set接口不保證維護(hù)元素的次序。

HashSet: 為快速查找而設(shè)計的Set。存入HashSet的對象必須定義hashCode()。

TreeSet: 保持次序的Set，底層為樹結(jié)構(gòu)。使用它可以從Set中提取有序的序列。

LinkedHashSet: 具有HashSet的查詢速度，且內(nèi)部使用鏈表維護(hù)元素的順序(插入的次序)。于是在使用迭代器遍歷Set時，結(jié)果會按元素插入的次序顯示。

       HashSet采用散列函數(shù)對元素進(jìn)行排序，這是專門為快速查詢而設(shè)計的；TreeSet采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序元素；LinkedHashSet內(nèi)部使用散列以加快查詢速度，同時使用鏈表維護(hù)元素的次序，使得看起來元素是以插入的順序保存的。需要注意的是，生成自己的類時，Set需要維護(hù)元素的存儲順序，因此要實(shí)現(xiàn)Comparable接口并定義compareTo()方法。

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

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)，在迭代遍歷它時，取得label/value的順序是其插入的次序，或者是最近最少使用(LRU)的次序，速度上比HashMap要慢一點(diǎn)，但在迭代訪問時速度會更快，主要原因是它使用了鏈表維護(hù)內(nèi)部次序。

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

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

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

2.hashCode()

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

         在HashMap中通過label查找value時，實(shí)際上是計算label對象地址的散列碼來確定value的。一般情況下，我們是使用基類Object的方法hashCode()來生成散列碼，它默認(rèn)是使用對象的地址來計算的，因此由第一個對象new Apple(5)和第二個對象new Apple(5)生成的散列碼是不同的，不能完成正確的查找。通常，我們可以編寫自己的hashCode()方法來覆蓋基類的原始方法，但與此同時，我們必須同時實(shí)現(xiàn)equals()方法來判斷當(dāng)前的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，如果對象中用于等價比較的信息沒有改變，那么無論調(diào)用x.equals(y)多少次，返回的結(jié)果應(yīng)該保持一致，要么一直是true，要么一直是false。

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

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

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

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

散列表中的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)建散列表時bucket的數(shù)量。可以在構(gòu)造方法中指定HashMap和HashSet的初始化容量。

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

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

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

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

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

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

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

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

編寫正確高效的hashCode()和equals()可以參考Apache的Jakarta Commons項(xiàng)目中的工具。