在介紹完Collections框架的各個(gè)接口之后，下面我們來看一下各接口都有哪些具體的實(shí)現(xiàn)類，以及他們的用途。

實(shí)現(xiàn)類按照可以分成如下幾類：

• General-purpose implementations are the most commonly used implementations, designed for everyday use. They are summarized in the table below.
• Special-purpose implementations are designed for use in special situations and display nonstandard performance characteristics, usage restrictions, or behavior.
• Concurrent implementations are designed to support high concurrency, typically at the expense of single-threaded performance. These implementations are part of the java.util.concurrent package.
• Wrapper implementations are used in combination with other types of implementations, often the general-purpose ones, to provide added or restricted functionality.
• Convenience implementations are mini-implementations, typically made available via static factory methods, that provide convenient, efficient alternatives to general-purpose implementations for special collections (for example, singleton sets).
• Abstract implementations are skeletal implementations that facilitate the construction of custom implementations — described later in the Custom Collection Implementations section. An advanced topic, it's not particularly difficult, but relatively few people will need to do it.

我們先來總結(jié)一下general-purpose的實(shí)現(xiàn)類：

General-purpose Implementations

Interfaces	Implementations
	Hash table	Resizable array	Tree	Linked list	Hash table + Linked list
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Queue				LinkedList
Map	HashMap		TreeMap		LinkedHashMap

注意LinkedList同時(shí)實(shí)現(xiàn)了List和Queue兩種接口。

下表是gegeneral-purpose implementations、special-purpose implementations和concurrent implementations的總結(jié)：

Interfaces	gegeneral-purpose	special-purpose	concurrent
Set	HashSet TreeSet LinkedHashSet	EnumSet CopyOnWriteArraySet
List	ArrayList LinkedList	CopyOnWriteArrayList
Queue	LinkedList PriorityQueue		LinkedBlockingQueue ArrayBlockingQueue PriorityBlockingQueue DelayQueue SynchronousQueue
Map	HashMap TreeMap LinkedHashMap	EnumMap WeakHashMap IdentityHashMap	ConcurrentHashMap

1. Set實(shí)現(xiàn)類

Set有三種general-purpose的實(shí)現(xiàn)類，HashSet、TreeSet和LinkedHashSet。其中HashSet速度最快（多數(shù)操作都是常數(shù)時(shí)間），TreeSet（多數(shù)操作都是log級時(shí)間），但TreeSet有序。LinkedHashSet能提供按照插入順序排列的遍歷，他的速度接近于HashSet，但空間消耗稍大（hash table ＋ linked list）。

HashSet和LinkedHashSet都能在構(gòu)造函數(shù)中指定初始的capacity，和load factor，而TreeSet使不能的。

有一點(diǎn)需要注意的是，HashSet的遍歷時(shí)間是與它自身的容量大小（而不是儲存的元素個(gè)數(shù)）成正比的（線性關(guān)系）。因此，如果你要自己指定初始capacity的話，不要搞得太大，那樣不僅浪費(fèi)空間，而且浪費(fèi)時(shí)間。LinkedHashSet的遍歷時(shí)間只與元素個(gè)數(shù)成正比

Set有兩種special-purpose的實(shí)現(xiàn)類：EnumSet和CopyOnWriteArraySet。

·EnumSet的空間和時(shí)間性能都很好，可以作為傳統(tǒng)上基于int的“位標(biāo)志”的替換形式，具有高品質(zhì)、類型安全的優(yōu)勢。
·CopyOnWriteArraySet適合于遍歷操作的數(shù)量大大超過可變操作的數(shù)量時(shí)，以及在不能或不想進(jìn)行同步遍歷，但又需要從并發(fā)線程中排除沖突時(shí)很有用

具體請參見API doc


2. List實(shí)現(xiàn)類

List有兩種General-purpose的實(shí)現(xiàn)類：ArrayList和LinkedList。一般情況下，使用ArrayList總是最好的選擇，因?yàn)樗加每臻g小，速度又快。除非你需要大量頻繁的插入刪除操作，這時(shí)LinkedList可能更加適合。

ArrayList能在構(gòu)造函數(shù)中指定capacity，LinkedList不能。

List有一種special-purpose的implementation - CopyOnWriteArrayList，具體參考API doc


3. Queue實(shí)現(xiàn)類

Queue有兩種general-purpose的實(shí)現(xiàn)類：LinkedList和PriorityQueue。LinkedList提供了一種FIFO隊(duì)列，而PriorityQueue則是根據(jù)元素的自然順序或是指定的Comparator來排列元素。

在java.util.concurrent包里又一個(gè)擴(kuò)展了Queue的BlockingQueue接口。他有如下一些實(shí)現(xiàn)類：

• LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
• ArrayBlockingQueue — a bounded FIFO blocking queue backed by an array
• PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
• DelayQueue — a time-based scheduling queue backed by a heap
• SynchronousQueue — a simple rendezvous mechanism that uses the BlockingQueue interface

4. Map實(shí)現(xiàn)類

Map有三種general-purpose的實(shí)現(xiàn)類：HashMap、TreeMap和LinkedHashMap。如果你需要SortedMap的操作，或者需要按序遍歷Map，就用TreeMap；如果你不關(guān)心遍歷的順序，只關(guān)心速度，那就用HashMap；如果你需要接近于HashMap的性能，又想能按元素插入順序來遍歷，就用LinkedHashMap。

其實(shí)Map和Set是很相似的，只不過一個(gè)是元素集合，一個(gè)是“鍵值對”集合。上面介紹的Set中各實(shí)現(xiàn)類的性質(zhì)也同樣適用于Map

需要注意的是，LinkedHashMap提供了一個(gè)方法：removeEldestEntry。通過重寫這個(gè)方法，可以定義自覺的策略－在將新映射關(guān)系添加到映射時(shí)自動移除舊的映射關(guān)系。具體參見API doc

Map有三種Special-purpose的實(shí)現(xiàn)類：EnumMap, WeakHashMap,和IdentityHashMap。
Map的Concurrent實(shí)現(xiàn)類：ConcurrentHashMap。


下面來介紹一下Wrapper實(shí)現(xiàn)類

Wrapper實(shí)現(xiàn)類是在提供的Collection實(shí)例基礎(chǔ)之上添加一些額外的功能，就好像設(shè)計(jì)模式中的decorator

所有的Wrapper都包含在Collections類中，有static方法來創(chuàng)建。

1. Synchronization Wrappers

public static <T> Collection<T>







synchronizedCollection(Collection<T> c);







public static <T> Set<T>







synchronizedSet(Set<T> s);







public static <T> List<T>







synchronizedList(List<T> list);







public static <K,V> Map<K,V>







synchronizedMap(Map<K,V> m);







public static <T> SortedSet<T>







synchronizedSortedSet(SortedSet<T> s);







public static <K,V> SortedMap<K,V>







synchronizedSortedMap(SortedMap<K,V> m);















需要注意的是，不要以為加上Synchronization Wrappers的包裝就可以不管同步操作了，當(dāng)遍歷的時(shí)候，我們還是要對Collection對象加上對象







加上對象鎖。這是因?yàn)楸闅v操作是由對Collection內(nèi)部的多個(gè)操作的調(diào)用組成的。







下面的代碼演示了如何在遍歷時(shí)同步：

注意如果我們是在遍歷Map，不管我們是用key還是用value什么遍歷，都要將鎖加在Map上：

2. Unmodifiable Wrappers















Unmodifiable Wrappers提供如下兩種用途：















2.1. 使Collection不可修改。注意要做到這一點(diǎn)，我們必須在使用Unmodifiable Wrappers后，放棄原來的Collection的引用。







2.2. 運(yùn)行某客戶端對你的數(shù)據(jù)進(jìn)行只讀操作。這時(shí)你可以保留原本的Collection的引用，使得你可以隨意操作Collection，而客戶只讀















public static <T> Collection<T>







unmodifiableCollection(Collection<? extends T> c);







public static <T> Set<T>







unmodifiableSet(Set<? extends T> s);







public static <T> List<T>







unmodifiableList(List<? extends T> list);







public static <K,V> Map<K, V>







unmodifiableMap(Map<? extends K, ? extends V> m);







public static <T> SortedSet<T>







unmodifiableSortedSet(SortedSet<? extends T> s);







public static <K,V> SortedMap<K, V>







unmodifiableSortedMap(SortedMap<K, ? extends V> m);























3. Checked Interface Wrappers







Collections類中提供的各種Collections.checked... 操作，返回指定 collection 的一個(gè)動態(tài)類型安全視圖。試圖插入一個(gè)錯(cuò)誤類型的元素將



導(dǎo)致立即拋出 ClassCastException。假設(shè)在生成動態(tài)類型安全視圖之前，collection 不包含任何類型不正確的元素，并且所有對該collection



的后續(xù)訪問都通過該視圖進(jìn)行，則可以保證 該 collection 不包含類型不正確的元素。







具體參見API doc











4. Convenience Implementations







4.1 List View of an Array － Arrays.asList()







Arrays.asList()方法返回?cái)?shù)組的一個(gè)List視圖。任何對返回的list上的操作都將寫回到數(shù)組上，反之亦然。但要注意的是，返回的list并不支持



add、remove操作。







Q：如何得到一個(gè)固定長度的list？



A：List<String> list = Arrays.asList(new String[size]);











4.2 Immutable Multiple-Copy List







參見Collections.nCopies()方法







4.3 Immutable Singleton Set







參見Collections.singleton()方法







4.4 Empty Set, List, and Map Constants







Collections.emptySet(), Collections.emptyList(), Collections.emptyMap()