在介紹完Collections框架的各個(gè)接口之后，下面我們來(lái)看一下各接口都有哪些具體的實(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.
我們先來(lái)總結(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級(jí)時(shí)間），但TreeSet有序。LinkedHashSet能提供按照插入順序排列的遍歷，他的速度接近于HashSet，但空間消耗稍大（hash table ＋ linked list）。
HashSet和LinkedHashSet都能在構(gòu)造函數(shù)中指定初始的capacity，和load factor，而TreeSet使不能的。
有一點(diǎn)需要注意的是，HashSet的遍歷時(shí)間是與它自身的容量大小（而不是儲(chǔ)存的元素個(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)勢(shì)。
·CopyOnWriteArraySet適合于遍歷操作的數(shù)量大大超過(guò)可變操作的數(shù)量時(shí)，以及在不能或不想進(jìn)行同步遍歷，但又需要從并發(fā)線程中排除沖突時(shí)很有用
具體請(qǐng)參見(jiàn)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來(lái)排列元素。
在java.util.concurrent包里又一個(gè)擴(kuò)展了Queue的BlockingQueue接口。他有如下一些實(shí)現(xiàn)類：
4. Map實(shí)現(xiàn)類
Map有三種general-purpose的實(shí)現(xiàn)類：HashMap、TreeMap和LinkedHashMap。如果你需要SortedMap的操作，或者需要按序遍歷Map，就用TreeMap；如果你不關(guān)心遍歷的順序，只關(guān)心速度，那就用HashMap；如果你需要接近于HashMap的性能，又想能按元素插入順序來(lái)遍歷，就用LinkedHashMap。
其實(shí)Map和Set是很相似的，只不過(guò)一個(gè)是元素集合，一個(gè)是“鍵值對(duì)”集合。上面介紹的Set中各實(shí)現(xiàn)類的性質(zhì)也同樣適用于Map
需要注意的是，LinkedHashMap提供了一個(gè)方法：
removeEldestEntry。通過(guò)重寫這個(gè)方法，可以定義自覺(jué)的策略－在將新映射關(guān)系添加到映射時(shí)自動(dòng)移除舊的映射關(guān)系。具體參見(jiàn)API doc
Map有三種Special-purpose的實(shí)現(xiàn)類：EnumMap, WeakHashMap,和IdentityHashMap。
Map的Concurrent實(shí)現(xiàn)類：ConcurrentHashMap。
下面來(lái)介紹一下Wrapper實(shí)現(xiàn)類
Wrapper實(shí)現(xiàn)類是在提供的Collection實(shí)例基礎(chǔ)之上添加一些額外的功能，就好像設(shè)計(jì)模式中的
decorator
所有的Wrapper都包含在Collections類中，有static方法來(lái)創(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í)候，我們還是要對(duì)Collection對(duì)象加上對(duì)象
加上對(duì)象鎖。這是因?yàn)楸闅v操作是由對(duì)Collection內(nèi)部的多個(gè)操作的調(diào)用組成的。
下面的代碼演示了如何在遍歷時(shí)同步：
Collection<Type> c =
Collections.synchronizedCollection(myCollection);
synchronized(c) {
for (Type e : c)
foo(e);
}
注意如果我們是在遍歷Map，不管我們是用key還是用value什么遍歷，都要將鎖加在Map上：
Map<KeyType, ValType> m =
Collections.synchronizedMap(new HashMap<KeyType, ValType>());
Set<KeyType> s = m.keySet();
synchronized(m) { // Synchronizing on m, not s!
while (KeyType k : s)
foo(k);
}
2. Unmodifiable Wrappers
Unmodifiable Wrappers提供如下兩種用途：
2.1. 使Collection不可修改。注意要做到這一點(diǎn)，我們必須在使用Unmodifiable Wrappers后，放棄原來(lái)的Collection的引用。
2.2. 運(yùn)行某客戶端對(duì)你的數(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è)動(dòng)態(tài)類型安全視圖。試圖插入一個(gè)錯(cuò)誤類型的元素將
導(dǎo)致立即拋出 ClassCastException。假設(shè)在生成動(dòng)態(tài)類型安全視圖之前，collection 不包含任何類型不正確的元素，并且所有對(duì)該collection
的后續(xù)訪問(wèn)都通過(guò)該視圖進(jìn)行，則可以保證 該 collection 不包含類型不正確的元素。
具體參見(jiàn)API doc
4. Convenience Implementations
4.1 List View of an Array － Arrays.asList()
Arrays.asList()方法返回?cái)?shù)組的一個(gè)List視圖。任何對(duì)返回的list上的操作都將寫回到數(shù)組上，反之亦然。但要注意的是，返回的list并不支持
add、remove操作。
Q：如何得到一個(gè)固定長(zhǎng)度的list？
A：List<String> list = Arrays.asList(new String[size]);
4.2 Immutable Multiple-Copy List
參見(jiàn)Collections.nCopies()方法
4.3 Immutable Singleton Set
參見(jiàn)Collections.singleton()方法
4.4 Empty Set, List, and Map Constants
Collections.emptySet(), Collections.emptyList(), Collections.emptyMap()