周浩

Java 容器類學習心得

一心得

1.? 接口
整個 Java 容器類的基礎是容器接口（例如 Collection ， Map 等接口），而不是類。使用接口的最大好處在于將容器的實現與容器的接口分開，這就意味著你可以使用相同的方法訪問容器而不用關心容器是由什么樣的數據結構實現的。同樣， Iterator 接口也使得用戶可以使用相同的方法訪問不同的容器類。以上這些是通用算法的基礎。

1.1?Collection 接口
Collection 接口有如下基本方法：
boolean add(Object obj) ：如果添加對象后，集合確實發生了變化，則返回 true ；否則返回 false
Iterator iterator() ：返回一個實現了 Iterator 接口的對象
此外，還有
int size(),boolean isEmpty() ， boolean contains(Object obj) ， void clear() 等許多有用的方法

1.2?Map 接口
Map 用于存放關鍵字 / 值對。有如下基本方法：
Object get(Object key)
Object put(Object key,Object balue)
Set keySet()
Set entrySet()
此外，還有其他有用的方法。
需要注意的是，從表面看它似乎就是一種由鍵值對構成的集合，但實際上并不是這樣。不過另一方面假如將 Map 的某一部分看作集合，有時候也還是顯得非常方便的。換言之你可以創建一個集合用它來表達 Map 的那一部分。綜上所述，一個 Map 可以返回的東西包括它的鍵值構成的一個 Set 、由它的值構成的一個集合或者由它的鍵值對構成的一個 Set 。

1.3?Iterator 接口
Iterator 接口有下面 3 個基本方法：
Object next() ：返回迭代器剛越過的元素的引用
boolean hasNext() ：判斷容器內是否還有可供訪問的元素
void remove() ：刪除迭代器剛越過的元素
注意： Java 中的迭代器與 STL 中的迭代器在概念上有很重要的區別。在 STL 中，迭代器類似于數組的索引，使用這種迭代器可以查看存放在該位置上的元素（類似于通過數組索引 i 來訪問 c[i] 一樣）。 Java 中的迭代器并不這樣運行。查看與位置的變化緊密的結合在一起。每次通過 next() 訪問一個元素的同時，迭代器的位置會自動向前走一步。
這個問題可以這樣理解： Java 中的迭代器指向的位置并不是元素，而是元素之間。這樣，每次調用 next() 時，迭代器便越過下一個元素，同時返回它剛越過的那個元素的引用。
根據上面的說明，很容易得出下面的代碼是錯誤的：
it.remove();
it.remove();
而下面的代碼是正確的：
it.remove();
it.next();
it.remove();
迭代器的典型應用
Iterator it=c.iterator();
while(it.hasNext())
{
?Object obj=it.next();
?//do something with obj
}

1.4? 子接口
1.4.1?List 接口
List 從 Collection 接口中分立出來是因為 List 的特點——有序的集合。這里指的有序并不是按照大小排好序的（ Sorted ），而是指集合是可以以確定的順序訪問的序列。針對 List 的這個特點，它比 Collection 接口增加了通過索引進行操作的方法。例如， add 、 remove 、 get 、 set 等方法的參數表中都可以加入索引的數值，從而操作處在索引位置處的元素。

1.4.2?Set 接口
Set 與 List 的不同，它里面的元素是無序的；所以，不能通過任何索引的方法來操作 Set 對象

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.? 抽象容器類
2.1? 抽象容器類包括 AbstractCollection ， AbstractList ， AbstractSet 等等

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

3.? 具體的容器
3.1?ArrayList 與 LinkedList
都是實現了 List 接口的類，是有序集。 List 接口支持通過索引的方法來訪問元素，對于這一點， ArrayList 沒有任何問題；但是對于 LinkedList 則有很大的問題，鏈表本身不應該支持隨機存儲，但是作為 List 的一個實現，鏈表也提供了對隨機訪問的支持，但是效率很低。每次通過索引的方法都是進行一次遍歷。我認為，其實就不應該讓鏈表支持隨機訪問；而 Java 這樣實現我想是因為整個集合框架的體系，使得鏈表與數組可以使用同樣的方法使用。綜上所述，對于 LinkedList 最好不使用隨機訪問，而使用迭代器。

3.2?TreeSet
3.2.1?TreeSet 是 SortedSet 的一個實現。根據數據結構的知識可以知道，樹的效率非常高，而且 Java 標準庫中有 TreeSet 這樣的類，以后應該盡量使用 TreeSet 來提高程序的效率。
3.2.2? 需要注意的是： TreeSet 作為有序集，它通過 compareTo 或者 Comparator 來將集合元素排序。任何具有相同比較值的元素（無論它們是否 equals() ），在 TreeSet 中都作為同一個元素，從而不能有重復。這樣以來，即使是不同的對象也不能加入到集合中，這一點有時候很不方便。我在編寫 A* 算法時，不同狀態有時候對應著同一個啟發函數值，那么這些不同的狀態就無法加入到 TreeSet 中。

3.3?HashSet
3.3.1?HashSet 是非常高效的數據結構，與 TreeSet 不同， HashSet 是比較對象的 equals() 方法來區分不同的對象。這樣只有真正不同的對象才能不被重復的加入到集合中。
3.3.2? 需要注意的是： HashSet 效率非常高，但是對象的 hashCode 函數不好確定。一般默認的對象的 hashCode 函數是根據對象的內存地址得到的。好的 hashCode 函數是 HashSet 成功運用的關鍵。

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

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

總結：千萬記住這句話——沒有最好的容器（數據結構），要根據不同的問題選擇不同的容器，以此來達到功能的要求和效率的最優。

二、 Java2 中的容器類庫

自 Java1.2 之后 Java 版本統稱為 Java2 ， Java2 中的容器類庫才可以說是一種真正意義上的集合框架的實現。基本完全重新設計，但是又對 Java1 中的一些容器類庫在新的設計上進行了保留，這主要是為了向下兼容的目的，當用 Java2 開發程序時，應盡量避免使用它們， Java2 的集合框架已經完全可以滿足你的需求。有一點需要提醒的是，在 Java1 中容器類庫是同步化的，而 Java2 中的容器類庫都是非同步化，這可能是對執行效率進行考慮的結果。
Java2 中的集合框架提供了一套設計優良的接口和類，使程序員操作成批的數據或對象元素極為方便。這些接口和類有很多對抽象數據類型操作的 API ，而這是我們常用的且在數據結構中熟知的。例如 Maps ， Sets ， Lists ， Arrays 等。并且 Java 用面向對象的設計對這些數據結構和算法進行了封裝，這就極大的減化了程序員編程時的負擔。程序員也可以以這個集合框架為基礎，定義更高級別的數據抽象，比如棧、隊列和線程安全的集合等，從而滿足自己的需要。
Java2 的集合框架，抽其核心，主要有三類： List 、 Set 和 Map 。如下圖所示：

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

三、未來的 Java 容器類庫

前面幾部分對 Java 中容器類庫的過去與現在的狀況進行了討論，然而就在寫下此文時， Sun 已經開始通過某種途徑分發 J2SE1.5 的 Alpha 測試版了。在今年的 JavaOne 大會上，諸多大師描繪了 Java 的美好未來與在下一個版本中即將加入的一些新特性，其中為容器類庫加入的一個重要特性就是泛型。
其實泛型并不是什么新東西，在其它一些面向對象的語言中早已存在，如 C++ 。泛型的基本目標很簡單：能夠保證你使用一種類型安全的容器。那么到底怎樣一種類型安全呢？我們先看下面這一段沒有使用泛型特性的代碼：

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

2.??? public ?class?Generics{

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

4.??? ?????*? 輸出一個 String 類型的列表，假設所給參數 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.?? }

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

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

2.??? public ?class?Generics{

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

4.??? ?????*? 輸出一個 String 類型的列表，限制了所給參數 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 類型，而是 String 類型

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

11.?? ????}

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

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

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

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

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

17.?? ????????list.add(new?Generics());??// 無法通過，編譯時錯誤

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

19.?? ????}

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