- Set接口
Set接口與List接口的重要區(qū)別就是它不支持重復(fù)的元素，至多可以包含一個(gè)null類型元素。Set接口定義的是數(shù)學(xué)意義上的“集合”概念。
Set接口主要定義了以下方法：
boolean add(E e)
void clear()
boolean contains(Object o)
boolean isEmpty()
boolean equals(Object obj)
Iterator<E> iterator()
boolean remove(Object o)
boolean removeAll(Collection<?> c)
int size()
Object[] toArray()
<T> T[] toArray(T[] a)
關(guān)于set家族，有一下描述：
- Set接口并沒(méi)有顯式要求其中的元素是有序或是無(wú)序的。
- Set接口有一個(gè)叫做SortedSet的子接口，這個(gè)接口可以用來(lái)實(shí)現(xiàn)對(duì)Set元素的排序。
- SortedSet有叫NavigableSet的子接口，這個(gè)接口定義的方法可以在有序Set中進(jìn)行查找和遍歷。
- Jdk類庫(kù)中實(shí)現(xiàn)了Set接口的類主要有：AbstractSet，HashSet，TreeSet，EnumSet，LinkedHashSet等等。其中HashSet與TreeSet都是AbstractSet的子類。
- Java官方文檔中提到，HashSet和TreeSet分別基于HashMap和TreeMap實(shí)現(xiàn)（我們?cè)诤竺鏁?huì)簡(jiǎn)單介紹HashMap和TreeMap），他們的區(qū)別在于Set<E>接口是一個(gè)對(duì)象的集（數(shù)學(xué)意義上的”集合“），Map<K, V>是一個(gè)鍵值對(duì)的集合。
- Queue接口
- Queue接口是對(duì)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的抽象。
- 一般的隊(duì)列實(shí)現(xiàn)允許我們高效的在隊(duì)尾添加元素，在隊(duì)列頭部刪除元素（First in, First out)。
- Queue<E>接口還有一個(gè)名為Deque的子接口，它允許我們高效的在隊(duì)頭或隊(duì)尾添加/刪除元素，實(shí)現(xiàn)了Deque<E>的接口的集合類即為雙端隊(duì)列的一種實(shí)現(xiàn)（比如LinkedList就實(shí)現(xiàn)了Deque接口）。
- 實(shí)現(xiàn)Queue接口的類主要有：AbstractQueue， ArrayDeque， LinkedList，PriorityQueue，DelayQueue等等。
Queue接口定義了以下方法：
boolean add(E e) //添加一個(gè)元素到隊(duì)列中，若隊(duì)列已滿會(huì)拋出一個(gè)IllegalStateException異常
E element() //獲取隊(duì)頭元素
boolean offer(E e) //添加一個(gè)元素到隊(duì)列中，若隊(duì)列已滿返回false
E peek() //獲取隊(duì)頭元素，若隊(duì)列為空返回null
E poll() //返回并移除隊(duì)頭元素，若隊(duì)列為空返回null
E remove() //返回并移除隊(duì)頭元素
add與offer，element與peek，remove與poll看似是三對(duì)兒功能相同的方法。它們之間的重要區(qū)別在于前者若操作失敗會(huì)拋出一個(gè)異常，后者若操作失敗會(huì)從返回值體現(xiàn)出來(lái)（比如返回false或null），我們可以根據(jù)具體需求調(diào)用它們中的前者或后者。
- Map接口
java官方文檔對(duì)它的定義如下：
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.The Map
interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map’s collection views return their elements. Some map implementations, like the TreeMap
class, make specific guarantees as to their order; others, like the HashMap
class, do not.
大概意思是：一個(gè)把鍵映射到值的對(duì)象被稱作一個(gè)Map對(duì)象。映射表不能包含重復(fù)的鍵，每個(gè)鍵至多可以與一個(gè)值關(guān)聯(lián)。
Map接口提供了三個(gè)集合視圖（關(guān)于集合視圖的概念我們下面會(huì)提到）：鍵的集合視圖、值的集合視圖以及鍵值對(duì)的集合視圖。
一個(gè)映射表的順序取決于它的集合視圖的迭代器返回元素的順序。一些Map接口的具體實(shí)現(xiàn)（比如TreeMap）,保證元素有一定的順序，其它一些實(shí)現(xiàn)（比如HashMap）則不保證元素在其內(nèi)部有序。
Map接口讓我們能夠根據(jù)鍵快速檢索到它所關(guān)聯(lián)的值。也就是利用這個(gè)特性，Struts2框架中用ContextMap作為容器封裝一次請(qǐng)求所需的所有數(shù)據(jù)。 我們先來(lái)看看Map接口定義了哪些方法：
void clear()
boolean containsKey(Object key) //判斷是否包含指定鍵
boolean containsValue(Object value) //判斷是否包含指定值
boolean isEmpty()
V get(Object key) //返回指定鍵映射的值
V put(K key, V value) //放入指定的鍵值對(duì)
V remove(Object key)
int size()
Set<Map.Entry<K,V>> entrySet()
Set<K> keySet()
Collection<V> values()
Map接口的具體實(shí)現(xiàn)類主要有：AbstractMap，EnumMap，HashMap，LinkedHashMap，TreeMap。HashTable。
- 我們看一下HashMap的官方定義：
HashMap<K, V>是基于哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)的Map接口具體實(shí)現(xiàn)，允許null鍵和null值。這個(gè)類與HashTable近似等價(jià)，區(qū)別在于HashMap不是線程安全的并且允許null鍵和null值。由于基于哈希表實(shí)現(xiàn)，所以HashMap內(nèi)部的元素是無(wú)序的。HashMap對(duì)與get與put操作的時(shí)間復(fù)雜度是常數(shù)級(jí)別的（在散列均勻的前提下）。對(duì)HashMap的集合視圖進(jìn)行迭代所需時(shí)間與HashMap的capacity（bucket的數(shù)量）加上HashMap的尺寸（鍵值對(duì)的數(shù)量）成正比。因此，若迭代操作的性能很重要，不要把初始capacity設(shè)的過(guò)高（不要把load factor設(shè)的過(guò)低）。
有兩個(gè)因素會(huì)影響一個(gè)HashMap對(duì)象的性能：intial capacity（初始容量）和load factor（負(fù)載因子）。intial capacity就是HashMap對(duì)象剛創(chuàng)建時(shí)其內(nèi)部的哈希表的“桶”的數(shù)量（請(qǐng)參考哈希表的定義）。load factor等于maxSize / capacity，也就是HashMap所允許的最大鍵值對(duì)數(shù)與桶數(shù)的比值。增大load factor可以節(jié)省空間但查找一個(gè)元素的時(shí)間會(huì)增加，減小load factor會(huì)占用更多的存儲(chǔ)空間，但是get與put的操作會(huì)更快。當(dāng)HashMap中的鍵值對(duì)數(shù)量超過(guò)了maxSize（即load factor與capacity的乘積），它會(huì)再散列，再散列會(huì)重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)，桶數(shù)（capacity）大約會(huì)增加到原來(lái)的兩倍。
HashMap的構(gòu)造器如下：
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map<? extends K,? extends V> m) //創(chuàng)建一個(gè)新的HashMap，用m的數(shù)據(jù)填充
常用方法如下：
void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
V get(Object key)
V put(K key, V value)
boolean isEmpty()
V remove(Object key)
int size()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()
Set<K> keySet()
它們的功能都很直觀，更多的使用細(xì)節(jié)可以參考Java官方文檔，這里就不貼上來(lái)了。這里簡(jiǎn)單地提一下WeakHashMap，它與HashMap的區(qū)別在于，存儲(chǔ)在其中的key是“弱引用”的，也就是說(shuō)，當(dāng)不再存在對(duì)WeakHashMap中的鍵的外部引用時(shí)，相應(yīng)的鍵值對(duì)就會(huì)被回收。關(guān)于WeakHashMap和其他類的具體使用方法及注意事項(xiàng)，大家可以參考官方文檔。
- 下面我們來(lái)簡(jiǎn)單地介紹下另一個(gè)Map接口的具體實(shí)現(xiàn)——TreeMap。
它的官方定義是這樣的：
TreeMap<K, V>一個(gè)基于紅黑樹的Map接口實(shí)現(xiàn)。TreeMap中的元素的有序的，排序的依據(jù)是存儲(chǔ)在其中的鍵的natural ordering（自然序，也就是數(shù)字從小到大，字母的話按照字典序）或者根據(jù)在創(chuàng)建TreeMap時(shí)提供的Comparator對(duì)象，這取決于使用了哪個(gè)構(gòu)造器。TreeMap的containsKey, get, put和remove操作的時(shí)間復(fù)雜度均為log(n)。
TreeMap有以下構(gòu)造器：
TreeMap() //使用自然序?qū)ζ湓剡M(jìn)行排序
TreeMap(Comparator<? super K> comparator) //使用一個(gè)比較器對(duì)其元素進(jìn)行排序
TreeMap(Map<? extends K,? extends V> m) //構(gòu)造一個(gè)與映射表m含有相同元素的TreeMap，用自然序進(jìn)行排列
TreeMap(SortedMap<K,? extends V> m) //構(gòu)造一個(gè)與有序映射表m含有相同元素及元素順序的TreeMap
它的常見(jiàn)方法如下：
K ceilingKey(K key)
void clear()
Comparator<? super K> comparator() //返回使用的比較器，若按自然序則返回null
boolean containsKey(Object key)
boolean containsValue(Object value)
NavigableSet<K> descendingKeySet() //返回一個(gè)包含在TreeMap中的鍵的逆序的NavigableSet視圖
NavigableMap<K,V> descendingMap()
Set<Map.Entry<K,V>> entrySet()
Map.Entry<K,V> firstEntry() //返回鍵最小的鍵值對(duì)
Map.Entry<K,V> floorEntry(K key) //返回一個(gè)最接近指定key且小于等于它的鍵對(duì)應(yīng)的鍵值對(duì)
K floorKey(K key)
V get(Object key)
Set<K> keySet()
Map.Entry<K,V> lastEntry() //返回與最大的鍵相關(guān)聯(lián)的鍵值對(duì)
K lastKey()
建議讀者先了解下紅黑樹這個(gè)數(shù)據(jù)結(jié)構(gòu)的原理及實(shí)現(xiàn)（可參考算法（第4版） (豆瓣)），然后再去看官方文檔中關(guān)于這個(gè)類的介紹，這樣學(xué)起來(lái)會(huì)事半功倍。
- 再簡(jiǎn)單地介紹下NavigableMap<K, V>這個(gè)接口：
實(shí)現(xiàn)了這個(gè)接口的類支持一些navigation methods，比如lowerEntry（返回小于指定鍵的最大鍵所關(guān)聯(lián)的鍵值對(duì)），floorEntry（返回小于等于指定鍵的最大鍵所關(guān)聯(lián)的鍵值對(duì)），ceilingEntry（返回大于等于指定鍵的最小鍵所關(guān)聯(lián)的鍵值對(duì)）和higerEntry（返回大于指定鍵的最小鍵所關(guān)聯(lián)的鍵值對(duì)）。一個(gè)NavigableMap支持對(duì)其中存儲(chǔ)的鍵按鍵的遞增順序或遞減順序的遍歷或訪問(wèn)。NavigableMap<K, V>接口還定義了firstEntry、pollFirstEntry、lastEntry和pollLastEntry等方法，以準(zhǔn)確獲取指定位置的鍵值對(duì)。
總的來(lái)說(shuō)，NavigableMap<K, V>接口正如它的名字所示，支持我們?cè)谟成浔碇小弊杂傻暮叫小?，正向或者反向迭代其中的元素并獲取我們需要的指定位置的元素。TreeMap實(shí)現(xiàn)了這個(gè)接口。
- 視圖（View）與包裝器
Java中的集合視圖是用來(lái)查看集合中全部或部分?jǐn)?shù)據(jù)的一個(gè)”窗口“，只不過(guò)通過(guò)視圖我們不僅能查看相應(yīng)集合中的元素，對(duì)視圖的操作還可能會(huì)影響到相應(yīng)的集合。比如TreeMap和HashMap的keySet()方法就會(huì)返回一個(gè)相應(yīng)映射表對(duì)象的視圖。通過(guò)使用視圖可以獲得其他的實(shí)現(xiàn)了Map接口或Collection接口的對(duì)象。
也就是說(shuō)，keySet方法返回的視圖是一個(gè)實(shí)現(xiàn)了Set接口的對(duì)象，這個(gè)對(duì)象中又包含了一系列鍵對(duì)象。 - 輕量級(jí)包裝器
Arrays.asList方法包裝了Java數(shù)組的集合視圖（實(shí)現(xiàn)了List接口）。請(qǐng)看以下代碼：
public static void main(String[] args) {
String[] strings = {"first", "second", "third"};
List<String> stringList = Arrays.asList(strings);
String s1 = stringList.get(0);
System.out.println(s1);
stringList.add(0, "new first");
}
注意：以上代碼會(huì)編譯成功，但是在運(yùn)行時(shí)會(huì)拋出一個(gè)UnsupportedOperationException異常，原因是調(diào)用了改變列表大小的add方法。Arrays.asList方法返回的封裝了底層數(shù)組的集合視圖不支持對(duì)改變數(shù)組大小的方法（如add方法和remove方法）的調(diào)用（但是可以改變數(shù)組中的元素）。
- 子范圍
很多集合類型建立一個(gè)稱為子范圍（subrange）的集合視圖。例如以下代碼抽出group中的第10到19個(gè)元素（從0開(kāi)始計(jì)數(shù)）組成一個(gè)子范圍：
List subgroup = group.subList(10, 20); //group為一個(gè)實(shí)現(xiàn)了List接口的集合
List接口所定義的操作都可以應(yīng)用于子范圍，包括那些會(huì)改變列表大小的方法，比如以下方法會(huì)把subgroup列表清空，同時(shí)group中相應(yīng)的元素也會(huì)從列表中移除：
subgroup.clear();
對(duì)于實(shí)現(xiàn)了SortedSet<E>接口的有序集或是實(shí)現(xiàn)了SortedMap<K, V>接口的有序映射表，我們也可以為他們創(chuàng)建子范圍。SortedSet接口定義了以下三個(gè)方法：
SortedSet<E> subSet(E from, E to);
SortedSet<E> headSet(E to);
SortedSet<E> tailSet(E from);
SortedMap也定義了類似的方法：
SortedMap<K, V> subMap(K from, K to);
SortedMap<K, V> headMap(K to);
SortedMap<K, V> tailMap(K from);
- 不可修改的視圖
Collections類中的一些方法可以返回不可修改視圖（unmodifiable views)：
Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
- 同步視圖
若集合可能被多個(gè)線程并發(fā)訪問(wèn)，那么我們就需要確保集合中的數(shù)據(jù)不會(huì)被破壞。Java類庫(kù)的設(shè)計(jì)者使用視圖機(jī)制來(lái)確保常規(guī)集合的線程安全。比如，我們可以調(diào)用以下方法將任意一個(gè)實(shí)現(xiàn)了Map接口的集合變?yōu)榫€程安全的：
Map<String, Integer> map = Collections.synchronizedMap(new HashMap<String, Integer>()); - 集合視圖的本質(zhì)
集合視圖本身不包含任何數(shù)據(jù)，它只是對(duì)相應(yīng)接口的包裝。集合視圖所支持的所有操作都是通過(guò)訪問(wèn)它所關(guān)聯(lián)的集合類實(shí)例來(lái)實(shí)現(xiàn)的。我們來(lái)看看HashMap的keySet方法的源碼：
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet<K> {
public final int size() {
return size;
}
public final void clear() {
HashMap.this.clear();
}
public final Iterator<K> iterator() {
return new KeyIterator();
}
public final boolean contains(Object o) {
return containsKey(o);
}
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null) throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc) throw new ConcurrentModificationException();
}
}
}
可以看到，實(shí)際上keySet()方法返回一個(gè)內(nèi)部final類KeySet的實(shí)例。我們可以看到KeySet類本身沒(méi)有任何實(shí)例變量。我們?cè)倏碖eySet類定義的size()實(shí)例方法，它的實(shí)現(xiàn)就是通過(guò)直接返回HashMap的實(shí)例變量size。還有clear方法，實(shí)際上調(diào)用的就是HashMap對(duì)象的clear方法。
keySet方法能夠讓你直接訪問(wèn)到Map的鍵集，而不需要復(fù)制數(shù)據(jù)或者創(chuàng)建一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，這樣做往往比復(fù)制數(shù)據(jù)到一個(gè)新的數(shù)據(jù)結(jié)構(gòu)更加高效。
- Collections類
Collections類與Collection接口的區(qū)別：Collection是一個(gè)接口，而Collections是一個(gè)類（可以看做一個(gè)靜態(tài)方法庫(kù)）。下面我們看一下官方文檔對(duì)Collections的描述：
Collections類包含了大量用于操作或返回集合的靜態(tài)方法。它包含操作集合的多態(tài)算法，還有包裝集合的包裝器方法等等。這個(gè)類中的所有方法在集合或類對(duì)象為空時(shí)均會(huì)拋出一個(gè)NullPointerException。
- 說(shuō)下面試經(jīng)常問(wèn)的HsahMap和HashTable的區(qū)別：
- 正如上文所說(shuō)，HashMap<K,V>是基于哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)，其中鍵和值都是對(duì)象，并且不能包含重復(fù)鍵，但可以包含重復(fù)值。HashMap允許null key和null value，而hashtable不允許。
- HashMap是Hashtable的輕量級(jí)實(shí)現(xiàn)（非線程安全的實(shí)現(xiàn)），他們都完成了Map接口，主要區(qū)別在于HashMap允許空（null）鍵值（key）,由于非線程安全，效率
上可能高于Hashtable。
HashMap允許將null作為一個(gè)entry的key或者value，而Hashtable不允許。
HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因?yàn)閏ontains方法容易讓人引起誤解。 - Hashtable繼承自Dictionary類，而HashMap是Java1.2引進(jìn)的Map interface的一個(gè)實(shí)現(xiàn)。
- 最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多個(gè)線程訪問(wèn)Hashtable時(shí)，不需要自己為它的方法實(shí)現(xiàn)同步，而HashMap 就必須為之提供外同步。
- Hashtable和HashMap采用的hash/rehash算法都大概一樣，所以性能不會(huì)有很大的差異。
總結(jié)
關(guān)于Java集合框架，我們首先應(yīng)該把握住幾個(gè)核心的接口，請(qǐng)看下圖:
