Java容器類學習心得，歡迎拍磚

Java容器類學習心得

由于我對C++比較熟悉，是以學習Java應該重點體會Java帶來的新概念。本文基本上是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中的靜态通用方法，也可以編寫自己的通用方法。

（具體的算法的内容在此略去）

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