Java容器類學習心得
由于我對C++比較熟悉，所以學習Java應該重點體會Java帶來的新概念。本文基本上是Java標準庫中集合框架的基本概念，沒有例子。寫本文的目的在于方便我很長時間后若是忘了這些東西可以通過這片文章迅速回憶起來。
1. 接口
整個Java容器類的基礎是容器接口（例如Collection，Map等接口），而不是類。使用接口的最大好處在于將容器的實現(xiàn)與容器的接口分開，這就意味著你可以使用相同的方法訪問容器而不用關心容器是由什么樣的數(shù)據(jù)結構實現(xiàn)的。同樣，Iterator接口也使得用戶可以使用相同的方法訪問不同的容器類。以上這些是通用算法的基礎。China
1.1 Collection接口
Collection接口有如下基本方法：
boolean add(Object obj)：如果添加對象后，集合確實發(fā)生了變化，則返回true；否則返回false
Iterator iterator()：返回一個實現(xiàn)了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的某一部分看作集合，有時候也還是顯得非常方便的。換言之你可以創(chuàng)建一個集合用它來表達Map的那一部分。綜上所述，一個Map可以返回的東西包括它的鍵值構成的一個Set、由它的值構成的一個集合或者由它的鍵值對構成的一個Set。
1.3 Iterator接口
Iterator接口有下面3個基本方法：
Object next()：返回迭代器剛越過的元素的引用
boolean hasNext()：判斷容器內是否還有可供訪問的元素
void remove()：刪除迭代器剛越過的元素
注意：Java中的迭代器與STL中的迭代器在概念上有很重要的區(qū)別。在STL中，迭代器類似于數(shù)組的索引，使用這種迭代器可以查看存放在該位置上的元素（類似于通過數(shù)組索引i來訪問c[i]一樣）。Java中的迭代器并不這樣運行。查看與位置的變化緊密的結合在一起。每次通過next()訪問一個元素的同時，迭代器的位置會自動向前走一步。
這個問題可以這樣理解：Java中的迭代器指向的位置并不是元素，而是元素之間。這樣，每次調用next()時，迭代器便越過下一個元素，同時返回它剛越過的那個元素的引用。
根據(jù)上面的說明，很容易得出下面的代碼是錯誤的：
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等方法的參數(shù)表中都可以加入索引的數(shù)值，從而操作處在索引位置處的元素。
1.4.2 Set接口
Set與List的不同，它里面的元素是無序的；所以，不能通過任何索引的方法來操作Set對象China It Power . ComZKWED
1.4.3 ListIterator接口
使用與List的迭代器，比Iterator接口增加了一些方法（例如add()等）。此外，由于List是雙向表，所以還增加了Object previous()和boolean hasPrevious()方法，用法與next()和hasNext()一樣。China It Power . ComZKWED
1.4.4 SortedMap接口
包含如下基本方法：
Comparator comparator()
Object firstKey()
Object lastKey()China It Power . ComZKWED
2. 抽象容器類
2.1 抽象容器類包括AbstractCollection，AbstractList，AbstractSet等等China It Power . ComZKWED
2.2 為什么要有抽象結合類？
例如Collection接口中定義了許多有用的方法，如果實現(xiàn)Collection接口的每個類都自行實現(xiàn)這么多的方法，那將是非常麻煩的。為了使實現(xiàn)Collection接口的類的實現(xiàn)更容易，AbstractCollection類讓一些基本方法（比如add()和iterator()）變成了抽象的方法，而利用這些基本方法的其他方法（例如addAll()等等）則具體實現(xiàn)了。China It Power . ComZKWED
3. 具體的容器
3.1 ArrayList與LinkedList
都是實現(xiàn)了List接口的類，是有序集。List接口支持通過索引的方法來訪問元素，對于這一點，ArrayList沒有任何問題；但是對于LinkedList則有很大的問題，鏈表本身不應該支持隨機存儲，但是作為List的一個實現(xiàn)，鏈表也提供了對隨機訪問的支持，但是效率很低。每次通過索引的方法都是進行一次遍歷。我認為，其實就不應該讓鏈表支持隨機訪問；而Java這樣實現(xiàn)我想是因為整個集合框架的體系，使得鏈表與數(shù)組可以使用同樣的方法使用。綜上所述，對于LinkedList最好不使用隨機訪問，而使用迭代器。China It Power . ComZKWED
3.2 TreeSet
3.2.1 TreeSet是SortedSet的一個實現(xiàn)。根據(jù)數(shù)據(jù)結構的知識可以知道，樹的效率非常高，而且Java標準庫中有TreeSet這樣的類，以后應該盡量使用TreeSet來提高程序的效率。
3.2.2 需要注意的是：TreeSet作為有序集，它通過compareTo或者Comparator來將集合元素排序。任何具有相同比較值的元素（無論它們是否equals()），在TreeSet中都作為同一個元素，從而不能有重復。這樣以來，即使是不同的對象也不能加入到集合中，這一點有時候很不方便。我在編寫A*算法時，不同狀態(tài)有時候對應著同一個啟發(fā)函數(shù)值，那么這些不同的狀態(tài)就無法加入到TreeSet中。China It Power . ComZKWED
3.3 HashSet
3.3.1 HashSet是非常高效的數(shù)據(jù)結構，與TreeSet不同，HashSet是比較對象的equals()方法來區(qū)分不同的對象。這樣只有真正不同的對象才能不被重復的加入到集合中。
3.3.2 需要注意的是：HashSet效率非常高，但是對象的hashCode函數(shù)不好確定。一般默認的對象的hashCode函數(shù)是根據(jù)對象的內存地址得到的。好的hashCode函數(shù)是HashSet成功運用的關鍵。China It Power . ComZKWED
4. 視圖
4.1 什么是視圖？
對映象類使用keySet()方法，仿佛該方法建立了一個新的集合，并將影響的所有關鍵字都填入這個集合。實際情況并非如此，對這個集合的任何操作都將反映到原始的映象對象上。
實際上，keySet()返回的是一個實現(xiàn)Set接口的對象，對該對象的操作就是對映象的操作。這樣的集合成為視圖。
4.2 視圖的應用
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類中的asList()方法China It Power . ComZKWED
5. 通用算法
通用的集合接口帶來的一大好處就是可以編寫通用算法?？梢允褂肅ollections中的靜態(tài)通用方法，也可以編寫自己的通用方法。
（具體的算法的內容在此略去）China It Power . ComZKWED
總結：千萬記住這句話——沒有最好的容器（數(shù)據(jù)結構），要根據(jù)不同的問題選擇不同的容器，以此來達到功能的要求和效率的最優(yōu)。
