周浩

1.4.2?Set 接口
Set 與 List 的不同，它里面的元素是無(wú)序的；所以，不能通過(guò)任何索引的方法來(lái)操作 Set 對(duì)象

1.4.3?ListIterator 接口
使用與 List 的迭代器，比 Iterator 接口增加了一些方法（例如 add() 等）。此外，由于 List 是雙向表，所以還增加了 Object previous() 和 boolean hasPrevious() 方法，用法與 next() 和 hasNext() 一樣。

1.4.4?SortedMap 接口
包含如下基本方法：
Comparator comparator()
Object firstKey()
Object lastKey()

2.? 抽象容器類(lèi)
2.1? 抽象容器類(lèi)包括 AbstractCollection ， AbstractList ， AbstractSet 等等

2.2? 為什么要有抽象結(jié)合類(lèi)？
例如 Collection 接口中定義了許多有用的方法，如果實(shí)現(xiàn) Collection 接口的每個(gè)類(lèi)都自行實(shí)現(xiàn)這么多的方法，那將是非常麻煩的。為了使實(shí)現(xiàn) Collection 接口的類(lèi)的實(shí)現(xiàn)更容易， AbstractCollection 類(lèi)讓一些基本方法（比如 add() 和 iterator() ）變成了抽象的方法，而利用這些基本方法的其他方法（例如 addAll() 等等）則具體實(shí)現(xiàn)了。

3.? 具體的容器
3.1?ArrayList 與 LinkedList
都是實(shí)現(xiàn)了 List 接口的類(lèi)，是有序集。 List 接口支持通過(guò)索引的方法來(lái)訪問(wèn)元素，對(duì)于這一點(diǎn)， ArrayList 沒(méi)有任何問(wèn)題；但是對(duì)于 LinkedList 則有很大的問(wèn)題，鏈表本身不應(yīng)該支持隨機(jī)存儲(chǔ)，但是作為 List 的一個(gè)實(shí)現(xiàn)，鏈表也提供了對(duì)隨機(jī)訪問(wèn)的支持，但是效率很低。每次通過(guò)索引的方法都是進(jìn)行一次遍歷。我認(rèn)為，其實(shí)就不應(yīng)該讓鏈表支持隨機(jī)訪問(wèn)；而 Java 這樣實(shí)現(xiàn)我想是因?yàn)檎麄€(gè)集合框架的體系，使得鏈表與數(shù)組可以使用同樣的方法使用。綜上所述，對(duì)于 LinkedList 最好不使用隨機(jī)訪問(wèn)，而使用迭代器。

3.2?TreeSet
3.2.1?TreeSet 是 SortedSet 的一個(gè)實(shí)現(xiàn)。根據(jù)數(shù)據(jù)結(jié)構(gòu)的知識(shí)可以知道，樹(shù)的效率非常高，而且 Java 標(biāo)準(zhǔn)庫(kù)中有 TreeSet 這樣的類(lèi)，以后應(yīng)該盡量使用 TreeSet 來(lái)提高程序的效率。
3.2.2? 需要注意的是： TreeSet 作為有序集，它通過(guò) compareTo 或者 Comparator 來(lái)將集合元素排序。任何具有相同比較值的元素（無(wú)論它們是否 equals() ），在 TreeSet 中都作為同一個(gè)元素，從而不能有重復(fù)。這樣以來(lái)，即使是不同的對(duì)象也不能加入到集合中，這一點(diǎn)有時(shí)候很不方便。我在編寫(xiě) A* 算法時(shí)，不同狀態(tài)有時(shí)候?qū)?yīng)著同一個(gè)啟發(fā)函數(shù)值，那么這些不同的狀態(tài)就無(wú)法加入到 TreeSet 中。

3.3?HashSet
3.3.1?HashSet 是非常高效的數(shù)據(jù)結(jié)構(gòu)，與 TreeSet 不同， HashSet 是比較對(duì)象的 equals() 方法來(lái)區(qū)分不同的對(duì)象。這樣只有真正不同的對(duì)象才能不被重復(fù)的加入到集合中。
3.3.2? 需要注意的是： HashSet 效率非常高，但是對(duì)象的 hashCode 函數(shù)不好確定。一般默認(rèn)的對(duì)象的 hashCode 函數(shù)是根據(jù)對(duì)象的內(nèi)存地址得到的。好的 hashCode 函數(shù)是 HashSet 成功運(yùn)用的關(guān)鍵。

4.? 視圖
4.1? 什么是視圖？
對(duì)映象類(lèi)使用 keySet() 方法，仿佛該方法建立了一個(gè)新的集合，并將影響的所有關(guān)鍵字都填入這個(gè)集合。實(shí)際情況并非如此，對(duì)這個(gè)集合的任何操作都將反映到原始的映象對(duì)象上。
實(shí)際上， keySet() 返回的是一個(gè)實(shí)現(xiàn) Set 接口的對(duì)象，對(duì)該對(duì)象的操作就是對(duì)映象的操作。這樣的集合成為視圖。
4.2? 視圖的應(yīng)用
4.2.1? 將現(xiàn)有的容器變?yōu)榫€程安全的容器：使用 Collections.synchronizedCollection(Collection c) 方法，在 SDK 文檔中該方法的解釋是“ Returns a synchronized (thread-safe) collection backed by the specified collection ”。
4.2.2? 將現(xiàn)有的容器變?yōu)橹蛔x的容器：使用 Collections.unmodifiableCollection(Collection c) 方法，在 SDK 文檔中該方法的解釋是“ Returns an unmodifiable view of the specified collection. ”。
4.2.3? 子范圍
4.2.4?Arrays 類(lèi)中的 asList() 方法

5.? 通用算法
通用的集合接口帶來(lái)的一大好處就是可以編寫(xiě)通用算法。可以使用 Collections 中的靜態(tài)通用方法，也可以編寫(xiě)自己的通用方法。
（具體的算法的內(nèi)容在此略去）

總結(jié)：千萬(wàn)記住這句話——沒(méi)有最好的容器（數(shù)據(jù)結(jié)構(gòu)），要根據(jù)不同的問(wèn)題選擇不同的容器，以此來(lái)達(dá)到功能的要求和效率的最優(yōu)。

二、 Java2 中的容器類(lèi)庫(kù)

自 Java1.2 之后 Java 版本統(tǒng)稱為 Java2 ， Java2 中的容器類(lèi)庫(kù)才可以說(shuō)是一種真正意義上的集合框架的實(shí)現(xiàn)。基本完全重新設(shè)計(jì)，但是又對(duì) Java1 中的一些容器類(lèi)庫(kù)在新的設(shè)計(jì)上進(jìn)行了保留，這主要是為了向下兼容的目的，當(dāng)用 Java2 開(kāi)發(fā)程序時(shí)，應(yīng)盡量避免使用它們， Java2 的集合框架已經(jīng)完全可以滿足你的需求。有一點(diǎn)需要提醒的是，在 Java1 中容器類(lèi)庫(kù)是同步化的，而 Java2 中的容器類(lèi)庫(kù)都是非同步化，這可能是對(duì)執(zhí)行效率進(jìn)行考慮的結(jié)果。
Java2 中的集合框架提供了一套設(shè)計(jì)優(yōu)良的接口和類(lèi)，使程序員操作成批的數(shù)據(jù)或?qū)ο笤貥O為方便。這些接口和類(lèi)有很多對(duì)抽象數(shù)據(jù)類(lèi)型操作的 API ，而這是我們常用的且在數(shù)據(jù)結(jié)構(gòu)中熟知的。例如 Maps ， Sets ， Lists ， Arrays 等。并且 Java 用面向?qū)ο蟮脑O(shè)計(jì)對(duì)這些數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行了封裝，這就極大的減化了程序員編程時(shí)的負(fù)擔(dān)。程序員也可以以這個(gè)集合框架為基礎(chǔ)，定義更高級(jí)別的數(shù)據(jù)抽象，比如棧、隊(duì)列和線程安全的集合等，從而滿足自己的需要。
Java2 的集合框架，抽其核心，主要有三類(lèi)： List 、 Set 和 Map 。如下圖所示：

從圖上可以看出， List 和 Set 繼承了 Collection ，而 Map 則獨(dú)成一體。初看上去可能會(huì)對(duì) Map 獨(dú)成一體感到不解，它為什么不也繼承 Collection 呢？但是仔細(xì)想想，這種設(shè)計(jì)是合理的。一個(gè) Map 提供了通過(guò) Key 對(duì) Map 中存儲(chǔ)的 Value 進(jìn)行訪問(wèn)，也就是說(shuō)它操作的都是成對(duì)的對(duì)象元素，比如 put() 和 get() 方法，而這是一個(gè) Set 或 List 所不就具備的。當(dāng)然在需要時(shí)，你可以由 keySet() 方法或 values() 方法從一個(gè) Map 中得到鍵的 Set 集或值的 Collection 集。
1 、 Collection 接口提供了一組操作成批對(duì)象的方法，用 UML 表示的方法列表如下：
它提供了基本操作如添加、刪除。它也支持查詢操作如是否為空 isEmpty() 方法等。為了支持對(duì) Collection 進(jìn)行獨(dú)立操作， Java 的集合框架給出了一個(gè) Iterator ，它使得你可以泛型操作一個(gè) Collection ，而不需知道這個(gè) Collection 的具體實(shí)現(xiàn)類(lèi)型是什么。它的功能與 Java1 中的 Enumeration 類(lèi)似，只是更易掌握和使用，功能也更強(qiáng)大。在建立集合框架時(shí)， Sun 的開(kāi)發(fā)團(tuán)隊(duì)考慮到需要提供一些靈活的接口，用來(lái)操作成批的元素，又為了設(shè)計(jì)的簡(jiǎn)便，就把那些對(duì)集合進(jìn)行可選操作的方法與基本方法放到了一起。因?yàn)橐粋€(gè)接口的實(shí)現(xiàn)者必須提供對(duì)接口中定義的所有方法的實(shí)現(xiàn)，這就需要一種途徑讓調(diào)用者知道它正在調(diào)用 ? 的可選方法當(dāng)前不支持。最后開(kāi)發(fā)團(tuán)隊(duì)選擇使用一種信號(hào)，也即拋出一種不支持操作例外 (UnsupportedOperationException) ，如果你在使用一個(gè) Collection 中遇到一個(gè)上述的例外，那就意味著你的操作失敗，比如你對(duì)一個(gè)只讀 Collection 添加一個(gè)元素時(shí)，你就會(huì)得到一個(gè)不支持操作例外。在你實(shí)現(xiàn)一個(gè)集合接口時(shí)，你可以很容易的在你不想讓用戶使用的方法中拋出 UnsupportOperationException 來(lái)告訴使用者這個(gè)方法當(dāng)前沒(méi)有實(shí)現(xiàn)， UnsupportOperationException 是 RuntimeException 的一個(gè)擴(kuò)展。
另外 Java2 的容器類(lèi)庫(kù)還有一種 Fail?fast 的機(jī)制。比如你正在用一個(gè) Iterator 遍歷一個(gè)容器中的對(duì)象，這時(shí)另外一個(gè)線程或進(jìn)程對(duì)那個(gè)容器進(jìn)行了修改，那么再用 next() 方法時(shí)可能會(huì)有災(zāi)難性的后果，而這是你不愿看到的，這時(shí)就會(huì)引發(fā)一個(gè) ConcurrentModificationException 例外。這就是 fail － fast 。
2 、 List 接口對(duì) Collection 進(jìn)行了簡(jiǎn)單的擴(kuò)充，它的具體實(shí)現(xiàn)類(lèi)常用的有 ArrayList 和 LinkedList 。你可以將任何東西放到一個(gè) List 容器中，并在需要時(shí)從中取出。 ArrayList 從其命名中可以看出它是一種類(lèi)似數(shù)組的形式進(jìn)行存儲(chǔ)，因此它的隨機(jī)訪問(wèn)速度極快，而 LinkedList 的內(nèi)部實(shí)現(xiàn)是鏈表，它適合于在鏈表中間需要頻繁進(jìn)行插入和刪除操作。在具體應(yīng)用時(shí)可以根據(jù)需要自由選擇。前面說(shuō)的 Iterator 只能對(duì)容器進(jìn)行向前遍歷，而 ListIterator 則繼承了 Iterator 的思想，并提供了對(duì) List 進(jìn)行雙向遍歷的方法。
3 、 Set 接口也是 Collection 的一種擴(kuò)展，而與 List 不同的時(shí)，在 Set 中的對(duì)象元素不能重復(fù)，也就是說(shuō)你不能把同樣的東西兩次放入同一個(gè) Set 容器中。它的常用具體實(shí)現(xiàn)有 HashSet 和 TreeSet 類(lèi)。 HashSet 能快速定位一個(gè)元素，但是你放到 HashSet 中的對(duì)象需要實(shí)現(xiàn) hashCode() 方法，它使用了前面說(shuō)過(guò)的哈希碼的算法。而 TreeSet 則將放入其中的元素按序存放，這就要求你放入其中的對(duì)象是可排序的，這就用到了集合框架提供的另外兩個(gè)實(shí)用類(lèi) Comparable 和 Comparator 。一個(gè)類(lèi)是可排序的，它就應(yīng)該實(shí)現(xiàn) Comparable 接口。有時(shí)多個(gè)類(lèi)具有相同的排序算法，那就不需要在每分別重復(fù)定義相同的排序算法，只要實(shí)現(xiàn) Comparator 接口即可。
集合框架中還有兩個(gè)很實(shí)用的公用類(lèi)： Collections 和 Arrays 。 Collections 提供了對(duì)一個(gè) Collection 容器進(jìn)行諸如排序、復(fù)制、查找和填充等一些非常有用的方法， Arrays 則是對(duì)一個(gè)數(shù)組進(jìn)行類(lèi)似的操作。
4 、 Map 是一種把鍵對(duì)象和值對(duì)象進(jìn)行關(guān)聯(lián)的容器，而一個(gè)值對(duì)象又可以是一個(gè) Map ，依次類(lèi)推，這樣就可形成一個(gè)多級(jí)映射。對(duì)于鍵對(duì)象來(lái)說(shuō)，像 Set 一樣，一個(gè) Map 容器中的鍵對(duì)象不允許重復(fù)，這是為了保持查找結(jié)果的一致性 ; 如果有兩個(gè)鍵對(duì)象一樣，那你想得到那個(gè)鍵對(duì)象所對(duì)應(yīng)的值對(duì)象時(shí)就有問(wèn)題了，可能你得到的并不是你想的那個(gè)值對(duì)象，結(jié)果會(huì)造成混亂，所以鍵的唯一性很重要，也是符合集合的性質(zhì)的。當(dāng)然在使用過(guò)程中，某個(gè)鍵所對(duì)應(yīng)的值對(duì)象可能會(huì)發(fā)生變化，這時(shí)會(huì)按照最后一次修改的值對(duì)象與鍵對(duì)應(yīng)。對(duì)于值對(duì)象則沒(méi)有唯一性的要求。你可以將任意多個(gè)鍵都映射到一個(gè)值對(duì)象上，這不會(huì)發(fā)生任何問(wèn)題（不過(guò)對(duì)你的使用卻可能會(huì)造成不便，你不知道你得到的到底是那一個(gè)鍵所對(duì)應(yīng)的值對(duì)象）。 Map 有兩種比較常用的實(shí)現(xiàn)： HashMap 和 TreeMap 。 HashMap 也用到了哈希碼的算法，以便快速查找一個(gè)鍵， TreeMap 則是對(duì)鍵按序存放，因此它便有一些擴(kuò)展的方法，比如 firstKey(),lastKey() 等，你還可以從 TreeMap 中指定一個(gè)范圍以取得其子 Map 。鍵和值的關(guān)聯(lián)很簡(jiǎn)單，用 pub(Object?key,Object?value) 方法即可將一個(gè)鍵與一個(gè)值對(duì)象相關(guān)聯(lián)。用 get(Object?key) 可得到與此 key 對(duì)象所對(duì)應(yīng)的值對(duì)象。

三、未來(lái)的 Java 容器類(lèi)庫(kù)

前面幾部分對(duì) Java 中容器類(lèi)庫(kù)的過(guò)去與現(xiàn)在的狀況進(jìn)行了討論，然而就在寫(xiě)下此文時(shí)， Sun 已經(jīng)開(kāi)始通過(guò)某種途徑分發(fā) J2SE1.5 的 Alpha 測(cè)試版了。在今年的 JavaOne 大會(huì)上，諸多大師描繪了 Java 的美好未來(lái)與在下一個(gè)版本中即將加入的一些新特性，其中為容器類(lèi)庫(kù)加入的一個(gè)重要特性就是泛型。
其實(shí)泛型并不是什么新東西，在其它一些面向?qū)ο蟮恼Z(yǔ)言中早已存在，如 C++ 。泛型的基本目標(biāo)很簡(jiǎn)單：能夠保證你使用一種類(lèi)型安全的容器。那么到底怎樣一種類(lèi)型安全呢？我們先看下面這一段沒(méi)有使用泛型特性的代碼：

1.??? import ?java.util.*;

2.??? public ?class?Generics{

3.??? ????/**

4.??? ?????*? 輸出一個(gè) String 類(lèi)型的列表，假設(shè)所給參數(shù) list 中所有元素都為 String 。

5.??? ?????*/

6.??? ????public?static?void?printList(List?list){

7.??? ????????for(int?i=0;i<list.size();i++){

8.??? ????????????System.out.println(((String)list.get(i)).toString());

9.??? ????????}

10.?? ????}

11.?? ????public?static?void?main(String[]?args){

12.?? ????????List?list=new?ArrayList();

13.?? ????????for(int?i=0;i<9;i++){

14.?? ????????????list.add("Number:"+Integer.toString(i));

15.?? ????????}

16.?? ????????//list.add(new?Generics());??//(1)

17.?? ????????printList(list);

18.?? ????}

19.?? }

上面的代碼很簡(jiǎn)單，定義了一個(gè)靜態(tài)方法來(lái)打印一個(gè)元素為 String 類(lèi)型的 List ，然而正如你看到的一樣，如果你試著將 (1) 行中前面的注釋去掉，你就會(huì)得到一個(gè) ClassCastException 例外，因?yàn)?/span> printList 會(huì)將 list 中的每個(gè)元素都轉(zhuǎn)型為 String ，而在遇到最后一個(gè)元素時(shí)發(fā)現(xiàn)它是一個(gè) Generics 類(lèi)型從而無(wú)法完成轉(zhuǎn)型，例外就被拋出。這種情況在 Java 編程中很容易出現(xiàn)，原因是 Java 的容器類(lèi)庫(kù)通常保存的是 Object 類(lèi)型，而這是所有類(lèi)的直接或間接超類(lèi)，這就允許你將任何類(lèi)型的元素添加到一個(gè) List 中而不會(huì)給你任何提示，有經(jīng)驗(yàn)的程序員可能會(huì)自己編寫(xiě)一個(gè)容器類(lèi)來(lái)限制添加到其中的元素，這是一個(gè)編程技巧。但是現(xiàn)在我們就再也不用那樣做了，泛型機(jī)制會(huì)為我們做好這件事。那就看一下用泛型機(jī)制對(duì)上面代碼進(jìn)行的改進(jìn)：

1.??? import ?java.util.*;

2.??? public ?class?Generics{

3.??? ????/**

4.??? ?????*? 輸出一個(gè) String 類(lèi)型的列表，限制了所給參數(shù) list 中所有元素都為 String

5.??? ?????*/

6.??? ????public?static?void?printList(ArrayList<String>?list){

7.??? ????????for(int?i=0;i<list.size();i++){

8.??? ????????????System.out.println(list.get(i).toString());

9.??? ????????????//get() 返回的不再是 Object 類(lèi)型，而是 String 類(lèi)型

10.?? ????????}

11.?? ????}

12.?? ????public?static?void?main(String[]?args){

13.?? ????????ArrayList?list=new?ArrayList<String>();?// 注意此行中聲明語(yǔ)法的變化

14.?? ????????for(int?i=0;i<9;i++){

15.?? ????????????list.add("Number:"+Integer.toString(i));?// 只能向其中添加 String 類(lèi)型

16.?? ????????}

17.?? ????????list.add(new?Generics());??// 無(wú)法通過(guò)，編譯時(shí)錯(cuò)誤

18.?? ????????printList(list);

19.?? ????}

20. }
    正如在代碼中所看到的，容器的聲明有了變化，即在一個(gè)容器類(lèi)后面用 <> 來(lái)說(shuō)明你想要放入這個(gè)容器中的元素類(lèi)型，那么接下來(lái)你只能向這個(gè)容器加那種類(lèi)型，否則編譯就無(wú)法通過(guò)。在 printList 中也省去了轉(zhuǎn)型的麻煩。當(dāng)然有了泛型，并不是說(shuō)以前的聲明方法不能用了，你完全可以還用以前的方法，這沒(méi)有任何問(wèn)題。其實(shí)根據(jù) JSR 中對(duì) for 語(yǔ)句功能的增強(qiáng)，遍歷一個(gè)容器也會(huì)更加簡(jiǎn)單。
    當(dāng)然泛型的使用方法不只如此，這里并沒(méi)有對(duì)它進(jìn)行完整描述，只想告訴你，泛型確實(shí)為我們編程提供了便利，但是仍然需要用心去學(xué)習(xí)和掌握。
    隨著 Java 的進(jìn)一步完善，它的功能和易用性也得到提高，我有理由相信 Java 在計(jì)算機(jī)語(yǔ)言中所占的位置也會(huì)更加牢固，讓喜愛(ài) Java 的人更加喜愛(ài)它。祝愿 Java 一路走好！