Java2中的集合框架提供了壹組設計良好的接口和類，這使得程序員可以非常方便地操作批量數據或對象元素。這些接口和類有許多API來操作抽象數據類型，這些數據類型在數據結構中是常用的和眾所周知的。如映射、集合、列表、數組等。而Java用面向對象的設計封裝了這些數據結構和算法，大大減輕了程序員編程時的負擔。程序員還可以基於這個集合框架定義更高級別的數據抽象，比如棧、隊列、線程安全集合等，從而滿足自己的需求。
Java2的集合框架有三個主要類別:列表、集合和映射。List和Set繼承集合，而Map是唯壹的。乍壹看，妳可能會對Map的獨立性感到困惑。為什麽不也繼承收藏？但轉念壹想，這個設計是合理的。映射通過鍵提供對存儲在映射中的值的訪問，也就是說，它操作成對的對象元素，如put()和get()方法，這是集合或列表所沒有的。當然，必要時，可以通過keySet()方法或values()方法從映射中獲取壹組鍵或壹組值。集合接口提供了壹組操作批處理對象的方法。
它提供了添加和刪除等基本操作。它還支持查詢操作，例如isEmpty()方法是否為空。為了支持集合的獨立操作，Java的集合框架給出了叠代器，可以讓妳在不知道集合具體實現類型的情況下，對集合進行壹般性的操作。其功能類似於Java1中的枚舉，但更容易掌握和使用，功能也更強大。在建立集合的框架時，Sun的開發團隊考慮到需要提供壹些靈活的接口來操作壹批元素，為了設計簡單，將集合上可選操作的方法和基本方法放在壹起。因為接口的實現者必須提供接口中定義的所有方法的實現，所以它需要壹種方式來讓調用者知道它正在調用的可選方法當前不受支持。最後，開發團隊選擇使用壹個信號，即拋出壹個UnsupportedOperationException。如果在使用集合時遇到上述異常之壹，就意味著操作失敗。例如，當您將元素添加到只讀集合中時，將會得到不支持的操作異常。當妳實現壹個集合接口時，妳很容易在壹個妳不希望用戶使用的方法中拋出UnsupportOperationException來告訴用戶這個方法目前還沒有實現。UnsupportOperationException是RuntimeException的擴展。
另外，Java2的容器類庫也有Fail fast機制。例如，如果妳正在使用叠代器遍歷壹個容器中的對象，而另壹個線程或進程修改了那個容器，那麽使用next()方法可能會產生災難性的後果，這是妳不希望看到的，然後會引發壹個並發表征異常的異常。這是快速失效。收藏的功能
下表顯示了Collection的所有函數，即可以用Set和List做什麽(不包括從Object自動繼承的方法)。(List有壹些額外的功能。)Map不繼承Collection，所以我們會區別對待。
Boolean add(Object):確保容器可以容納您傳遞給它的參數。如果沒有添加，則返回false。(這是壹個“可選”方法，將在本章後面解釋。)
Boolean addAll(Collection):添加參數集合中包含的所有元素。只要添加了元素，就返回true。
Void clear():清除容器中存儲的所有元素。(可選)
Boolean contains(Object):如果容器包含參數對象，則返回true。
Boolean containsAll(Collection):如果容器包含參數集合中包含的所有元素，則返回true。Boolean isEmpty():如果容器中沒有保存任何元素，則返回true。
Iterator iterator():返回壹個叠代器，可以在容器的元素之間移動。
Boolean removeAll(Collection):刪除容器中參數集合包含的所有元素。只要有東西被刪除，就返回true。(可選)
Boolean retainAll(集合):只保存參數集合中包含的元素(集合論中“交集”的概念)。如果已經更改，則返回true。(可選)
Int size():返回容器中包含的元素數量。
Object[] toArray():返回包含容器中所有元素的數組。
Object[] toArray(Object[] a):返回壹個包含容器中所有元素的數組，並且這個數組不是普通的對象數組，其類型應該與參數數組A的類型相同(需要進行類型轉換)。
註意，隨機訪問沒有get()方法。這是因為集合也包括集合。集合有自己的內部順序(所以隨機訪問是沒有意義的)。所以如果妳想檢查壹個集合的元素，妳必須使用叠代器。
接下來我會講List，Set，Map的各種實現。對於每個容器，我會告訴妳(用星號)默認應該選擇哪個實現。List接口只是擴展了集合。
其具體實現類壹般使用ArrayList和LinkedList。妳可以把任何東西放進壹個列表容器，需要的時候拿出來。ArrayList從名字就可以看出，它是以類數組的形式存儲的，所以它的隨機訪問速度極快，而LinkedList的內部實現是鏈表，適合鏈表中間頻繁的插入和刪除。具體應用中可以根據自己的需求自由選擇。上面提到的叠代器只能向前遍歷容器，而ListIterator繼承了叠代器的思想，提供了雙向遍歷列表的方法。列表的功能
List的基本用法非常簡單。雖然很多時候妳只是用add()添加對象，用get()獲取對象，用Iterator()獲取這個序列的叠代器，但是List還有其他非常有用的方法。
其實有兩種列表:ArrayList，擅長隨機訪問元素，LinkedList，功能更強大。LinkedList不是為快速隨機訪問設計的，但它有壹組更通用的方法。
List(接口):List最重要的特征是順序；它確保元素以壹定的順序保存。List向集合中添加了大量方法，這使它能夠在序列中間插入和刪除元素。(僅推薦用於LinkedList。)List可以做壹個ListIterator對象，妳不僅可以用它在列表中間插入和刪除元素，還可以雙向遍歷列表。
ArrayList*:由數組實現的列表。它可以進行快速隨機訪問，但在列表中間插入和刪除元素的速度很慢。ListIterator只能在逆向遍歷ArrayList時使用，所以不要用它來插入和刪除元素，因為和LinkedList相比，在ArrayList中使用ListIterator的系統開銷更高。
LinkedList:針對順序訪問進行了優化。在列表中間插入和刪除元素的開銷也不大。隨機訪問相對較慢。(使用ArrayList。)此外，它還有addFirst()、addLast()、getFirst()、getLast()、removeFirst()和removeLast()等方法(這些方法、接口和基類都沒有定義)，妳可以把它作為堆棧、隊列或者雙向隊列來使用。
記住，容器只是壹個用來存放物品的盒子。如果這個小盒子能幫妳解決所有的問題，那麽妳就不用擔心它是如何實現的(大多數情況下，這是使用對象的基本概念)。如果開發環境中有其他因素會導致固定的性能開銷，ArrayList和LinkedList之間的性能差異就變得不那麽重要了。妳只需要其中壹個，妳甚至可以想象出這樣壹個“完美”的抽象容器；它可以根據自己的目的自動切換底層實現。
LinkedList的用途
用LinkedList創建壹個堆棧
“堆棧”有時被稱為“後進先出”容器。也就是說，最後壹個被“壓”進棧的東西，會最先“彈”出來。和其他Java容器壹樣，推入和彈出的東西都是對象，所以除非妳只使用object的函數，否則彈出的東西壹定要打出來。
LinkedList方法可以直接實現stack的功能，所以不用寫Stack就可以直接使用LinkedList。
如果妳只想要堆棧的功能，那麽繼承是不合適的，因為妳繼承了壹個擁有LinkedList所有方法的類。
用LinkedList排隊
隊列是先進先出(FIFO)容器。也就是說，妳從壹端放東西進去，從另壹端取出東西。所以妳放東西的順序也是妳拿東西的順序。LinkedList具有支持隊列功能的方法，因此它也可以用作隊列。
您還可以使用LinkedList輕松創建壹個deque(雙向隊列)。它很像壹個隊列，除了您可以從任意壹端添加和刪除元素。集合接口也是集合的擴展。
與List不同，集合中的object元素不能重復，這意味著不能將相同的內容放在同壹個集合容器中兩次。其常見的具體實現是HashSet和TreeSet類。HashSet可以快速定位壹個元素，但是妳放在HashSet中的對象需要實現hashCode()方法，這個方法使用上面提到的哈希代碼算法。TreeSet將放入其中的元素按順序存儲，這就要求妳放入其中的對象是可排序的，這就使用了集合框架提供的另外兩個實用類Comparable和Comparator。如果壹個類是可排序的，它應該實現Comparable接口。有時候多個類有相同的排序算法，所以沒必要每次都定義相同的排序算法，實現比較器接口就行了。集合框架中還有兩個有用的公共類:集合和數組。Collections為排序、復制、搜索和填充集合容器提供了壹些非常有用的方法，而Arrays為壹個數組做類似的操作。集合的功能
Set的接口是Collection，所以不像那兩個List，它沒有額外的功能。事實上，Set實際上是壹個集合——它只是以不同的方式表現。這是繼承和多態的完美應用:表達不同的行為。Set會拒絕同值對象的多個實例(壹個對象的“值”是由什麽決定的？這個問題比較復雜，後面再說)。
Set (interface):添加到Set中的每個元素必須是唯壹的；否則，Set不會添加它。要添加壹個集合，對象必須定義equals()，以表明對象的唯壹性。Set的界面和Collection的界面完全壹樣。Set的接口不保證它將按什麽順序存儲元素。
HashSet*:旨在優化查詢速度的集合。要將對象放入HashSet，必須定義hashCode()。
TreeSet:它是壹個底部有壹棵樹的有序集合。所以妳可以從集合中提取壹個有序的序列。
LinkedHashSet(JDK 1.4):內部使用鏈表的集合，既有HashSet的查詢速度，又節省了元素添加的順序(插入順序)。叠代器遍歷集合時，按插入順序訪問。
HashSet保存對象的順序與TreeSet和LinkedHashSet不同。這是因為它們使用不同的方法來存儲和查找元素。(TreeSet使用壹種叫做紅黑樹數據結構的數據結構對元素進行排序，而HashSet使用壹種為快速查找而設計的哈希函數。LinkedHashSet在內部使用hash來提高查詢速度，但是看起來像是壹個鏈表來保存元素的插入順序。妳自己寫類的時候，壹定要記住Set要有壹個判斷元素存儲順序的標準，也就是壹定要實現Comparable接口，定義compareTo()方法。
分類集合
SortedSet(只有壹個TreeSet實現可用)中的元素必須是有序的。這使得SortedSet接口有更多的方法:
Comparator comparator():返回集合使用的比較器對象，或者使用null表示使用自己的排序方法。
Object first():返回最小的元素。
Object last():返回最大的元素。
Sorted Set subset (fromElement，toElement):返回集合的子集，其中的元素從fromElement開始到toElement(包括from元素，不包括to元素)。
SortedSet headSet(toElement):返回Set的子集，其中所有元素都應小於toElement。
排序後的集合頭(to元素):返回集合的子集，其中所有元素都應該大於fromElement。
註意SortedSet是指根據對象的比較順序排序，而不是插入順序。Map是壹個將鍵對象與值對象相關聯的容器。
值對象也可以是映射，以此類推，這樣就可以形成多層次的映射。對於關鍵對象，像Set，Map容器中的關鍵對象不允許重復，以保持搜索結果的壹致性；如果有兩個key對象是相同的，那麽當妳想得到那個key對象對應的value對象的時候就有問題了。可能妳沒有得到妳想要的值對象，會導致混亂，所以鍵的唯壹性很重要，符合集合的性質。當然，在使用過程中，壹個鍵對應的value對象可能會發生變化，然後會根據最後修改的value對象來對應這個鍵。值對象沒有唯壹性要求。妳可以把任意數量的鍵映射到壹個值對象上，這樣不會有什麽問題(但是可能會給妳的使用帶來不便，妳也不知道妳得到的是什麽值對象)。Map有兩種常見的實現:HashMap和TreeMap。HashMap也是用哈希碼算法快速找到壹個鍵，而TreeMap是按順序存儲鍵的，所以它有壹些擴展的方法，比如firstKey()，lastKey()等。您還可以從TreeMap中指定壹個範圍來獲取其子映射。鍵和值之間的關聯非常簡單。您可以使用put(Object key，Object value)方法將鍵與值對象相關聯。使用get(Object key)獲取這個key對象對應的value對象。
地圖的功能
ArrayList允許妳通過數字從壹系列對象中選擇，所以在某種意義上，它把數字和對象聯系起來。但是，如果要根據其他條件在壹個對象序列中進行選擇，應該怎麽做呢？Stack就是壹個例子。它的標準是“選擇最後壹個推入堆棧的對象”。常用的術語map、dictionary或associative array是壹個非常強大的工具，可以在序列中進行選擇。從概念上講，它看起來像壹個數組列表，但它使用另壹個對象來查找對象，而不是數字！這是壹項至關重要的編程技能。
這個概念在Java中表示為Map。put(Object key，Object value)方法向映射添加壹個值，並將該值與鍵(搜索時使用的對象)相關聯。給定鍵後，get(Object key)會返回與之相關的值。還可以使用containsKey()和containsValue()來測試映射是否包含鍵或值。
Java標準類庫中有幾種映射:hashmap、TreeMap、LinkedHashMap、WeakHashMap和IdentityHashMap。他們都實現了Map的基本接口，但在行為上明顯很驚訝。這些差異體現在效率，持有和表示對象對的順序，持有對象的長度，以及如何確定鍵的相等性。
性能是Map的壹大問題。如果妳知道get()是如何工作的，妳會發現，比如在ArrayList中查找對象會相當慢。這就是HashMap的優勢。它不是壹個壹個地慢慢搜索這個鍵，而是用壹個叫做哈希碼的特殊值來搜索。Hash是壹種算法，從目標對象中提取壹些信息，然後生成壹個代表這個對象的“相對唯壹”的int。HashCode()是對象根類的壹個方法，所以所有Java對象都可以生成哈希代碼。HashMap使用對象的hashCode()進行快速搜索。這樣，性能得到了極大的提高。
Map(接口):維護鍵-值關系(對)，以便可以使用鍵來查找值。
HashMap*:基於哈希表的實現。用它代替Hashtable。)提供時間常數插入和查詢。您可以在構造函數中設置哈希表的容量和加載因子。它的性能可以由構造函數來調整。
LinkedHashMap(JDK 1.4):很像HashMap，但是當叠代器用於遍歷時，它將按照插入順序或最近最少使用(LRU)順序被訪問。除了叠代器，其他情況下，只比HashMap慢壹點點。在叠代器的情況下，速度更快，因為內部順序是用鏈表保存的。
TreeMap:基於紅黑樹的數據結構實現。當妳看鍵或者對的時候，妳會發現它們是按順序排列的(按可比或者比較器，我們後面會講到)。TreeMap特性，妳得到的是壹個有序的地圖。TreeMap是Map中唯壹使用subMap()方法的實現。這個方法允許妳得到這個樹的壹部分。
WeakHashMap:弱鍵映射，為壹些特殊問題而設計。它允許Map釋放它持有的對象。如果壹個對象除了作為映射中的壹個鍵之外，在任何地方都沒有它的引用，它將被視為垃圾收集。
Identityhashmap(JDK 1.4):用= =而不是equals()比較鍵的hashmap。它不是為我們的正常使用而設計的，而是為解決特殊問題而設計的。
哈希是在地圖中存儲數據的常用算法。
分類地圖
SortedMap(只實現了TreeMap)必須有有序鍵，所以在這個接口中有壹些添加函數的方法。
Comparator comparator():返回映射使用的比較器，如果使用了對象內置的方法，則返回null。
Object firstKey():返回第壹個鍵。
Object lastKey():返回最後壹個鍵。
SortedMap subMap(fromKey，toKey):返回此映射的子集，其鍵從fromKey到toKey開始，包括前者但不包括後者。
SortedMap headMap(toKey):返回此映射的子集，其鍵都小於toKey。
SortedMap tailMap(fromKey):返回此映射的子集，其鍵都大於或等於fromKey。
對按鍵的順序存儲。因為TreeMap有順序的概念，“位置”是有意義的，所以妳可以得到它的首末元素和它的子集。
LinkedHashMap
為了提高速度，LinkedHashMap hash壹切，遍歷的時候(println()會遍歷整個Map，所以可以看到過程)，也會按照插入順序返回對。此外，還可以在LinkedHashMap的構造函數中將其配置為使用基於訪問的LRU(least-recent-used)算法，這樣未被訪問的元素(也是要刪除的候選元素)就會出現在隊列的最前面。這樣，編寫壹個定期清理程序來節省資源就非常簡單了。