Java基礎教程--集合

一.Java集合框架

??集合，有時也稱為容器，是一個用來存儲和管理多個元素的對象。Java中的集合框架定義了一套規(guī)范，用來表示和操作集合，使具體操作與實現(xiàn)細節(jié)解耦。集合框架都包含下列內(nèi)容：

接口：這些是表示集合的抽象數(shù)據(jù)類型，它們定義了集合中常見的操作。
實現(xiàn)：為各種集合提供了具體的實現(xiàn)。
算法：這些是對實現(xiàn)集合接口的對象執(zhí)行有用計算（如搜索和排序）的方法。算法被認為是多態(tài)的：也就是說，相同的方法可以用于集合接口的不同實現(xiàn)。
??集合框架有以下優(yōu)點：

減少編程工作：通過提供有用的數(shù)據(jù)結構和算法，集合可以讓我們專注于程序的重要部分，而不是考慮如何實現(xiàn)集合。
提高程序速度和質(zhì)量：集合框架提供了各種集合的高性能、高質(zhì)量實現(xiàn)，使得我們在編寫代碼時不必過多地考慮程序的速度和性能。
促進代碼重用：如果我們要實現(xiàn)自己的集合，只需要實現(xiàn)集合框架中的標準接口，就可以應用集合框架提供的算法，而無需重復地“造輪子”。
二.接口

??下圖是集合框架中的核心接口：

??Java中的集合框架分為Collection和Map兩類。下面是這兩個接口的聲明：

public interface Collection<E> extends Iterable<E> {...}
public interface Map<K,V> {...}

??可以看到，Java中的集合都是泛型的。在聲明集合時，應該指定集合中包含的對象類型。這樣編譯器可以幫我們驗證放入集合中的對象類型是否正確，從而減少運行時的錯誤。
??現(xiàn)在對上圖中的接口進行介紹：

Collection：集合層次結構的根接口。集合表示一組被稱為元素的對象，不同的集合有不同的特點。例如，有些集合允許存在重復的元素，有些則不允許；有些集合的元素是有序的，有些則是無序的。這個接口定義了所有集合都應該具有的行為，至于這些特性行為則交給子接口去定義。Java平臺不提供這個接口的直接實現(xiàn)，而是提供它的子接口的實現(xiàn)。
Set：不能包含重復元素的集合。這個接口是對數(shù)學概念中的集合的抽象。
List：List表示有序集合。注意，這個有序的意思是位置有序，而不是內(nèi)容有序。它與Set的區(qū)別在于，Set沒有位置的概念，并且List允許有重復的元素。
Queue：Queue是對數(shù)據(jù)結構中的隊列的抽象。隊列按照（但不一定）FIFO（first in first out，先進先出）方式對元素進行存放，它的插入和刪除操作是在不同的兩端進行的。
Deque：Deque表示雙端隊列，它與Queue的不同之處在于它的兩端都支持插入和刪除。
Map：映射層次結構的根接口。它可以用來存儲多個鍵值對，但是Map中不能包含重復鍵。
??最后的兩個接口僅僅是Set和Map接口的排序版本：

SortedSet：按升序維護Set中的元素。它提供了幾個額外的操作來利用Set中的順序。
SortedMap：按鍵的升序來維護Map中的鍵值對。它也提供了幾個額外的操作來利用Map中的順序。
??下面分別對這些接口進行介紹。

1.Collection接口

??集合表示一組被稱為元素的對象，它與數(shù)組的最大區(qū)別就是數(shù)組的長度是固定的，而集合的長度是可以動態(tài)變化的。當我們無法事先預估元素的個數(shù)時，就可以選擇使用集合。此外，使用集合還可以利用集合為我們提供的大量實用的方法。
??Collection接口用在需要最大通用性地傳遞集合的地方。例如，按照慣例，每種集合的實現(xiàn)都有一個接受Collection參數(shù)的構造方法。這個方法被稱為轉換構造器，它使用指定集合中的所有元素來初始化新的集合，無論給定的集合是什么類型。換句話說，使用這個構造方法可以轉換集合的類型。
??例如，現(xiàn)在有一個Collection類型的集合c，它可能是一個List，Set，或者其他類型的集合。下面的代碼使用c中的所有元素來初始化一個新的ArrayList（List接口的一種實現(xiàn)）：

List<String> list = new ArrayList<>(c);
??Collection接口中包含了一些基本操作：

這兩個方法都可以將集合轉換為數(shù)組。不過，toArray()方法只能將集合轉換為Object數(shù)組，而Object數(shù)組又無法直接強制轉換為其他類型的數(shù)組，因此這個方法的實用性就要差一些。而toArray(T[] a)方法則可以直接將集合轉換為T類型的數(shù)組，如果參數(shù)a的長度小于集合中元素的個數(shù)，該函數(shù)會返回一個包含集合中所有元素的新的數(shù)組；如果參數(shù)a的長度大于等于集合中元素的個數(shù)，該函數(shù)就會使用數(shù)組a來返回，并且在a[size]放置一個null，size表示集合中元素的個數(shù)，這樣toArray(T[] t)方法的調(diào)用者就可以知道null后面已經(jīng)沒有集合元素了。不過，一般我們傳遞的數(shù)組只是為了傳遞數(shù)組的類型，因此我們會傳遞一個空的數(shù)組進去。例如，假設現(xiàn)在有一個存放字符串的集合，要將它轉換為字符串數(shù)組，可以像下面這樣寫：

String[] y = x.toArray(new String[0]);
??從Java8之后，Collection接口中增加了兩個與流（Stream）相關的方法，Stream stream()和Stream parallelStream()，它們分別用于獲取集合的順序流和并行流。有關流與聚合操作的內(nèi)容會在稍后進行介紹。

遍歷Collection

??有三種遍歷Collection的操作：(1)增強型for循環(huán)；(2)迭代器；(3)聚合操作。
(1)增強型for循環(huán)
??我們早在流程控制一文中已經(jīng)提到了增強型for循環(huán)。增強型for循環(huán)可以用來遍歷數(shù)組或實現(xiàn)了Iterable接口的類。從上面的Collection接口的聲明可以看到，Collection接口繼承了Iterable接口，這意味著所有的集合都可以使用增強型for循環(huán)來遍歷。例如：
public void traverseWithFor(Collection&lt;String&gt; collection) {<br/>for(String str : collection) {<br/>System.out.println(str);<br/>}<br/>}

(2)迭代器

??迭代器（也稱作游標）是一種可以訪問容器中的元素的對象。由于各種容器的內(nèi)部結構不同，它們的遍歷方式也就不盡相同。為了使對容器內(nèi)元素的遍歷方式更加簡單和統(tǒng)一，Java引入了迭代器模式。迭代器模式提供了一種方法順序訪問一個聚合對象中的各種元素，但又不暴露該對象的內(nèi)部表示。Java中定義的迭代器接口是Iterator，每個迭代器都必須實現(xiàn)這個接口。這個接口中最主要的三個方法是：
boolean hasNext();<br/>E next();<br/>void remove();<br/>}

?hasNext方法用于判斷迭代器所在的位置后面是否存在元素，而next方法則會返回迭代器所在位置后面的元素并移動迭代器，如果沒有下一個元素，這個方法會拋出NoSuchElementException。remove方法會移除上一個由next返回的元素，但是這個方法只能在每次調(diào)用next后調(diào)用一次。
??如何獲取迭代器呢？或者說什么樣的對象才能獲取迭代器呢？實際上，如果要從一個對象上獲取迭代器，那么這個對象必須是可迭代的，也就是說這個類必須實現(xiàn)Iterable接口，通過Iterable的iterator方法可以獲取到迭代器。Collection接口繼承了Iterable接口，也就是說所有的集合都是可迭代的，因此可以從所有的集合對象上獲取迭代器，并使用迭代器對集合進行遍歷。例如：
public void traverseWithIterator(Collection&lt;String&gt; collection) {<br/>Iterator &lt;String&gt; it = collection.iterator();<br/>while(it.hasNext()) {<br/>System.out.println(it.next());<br/>}<br/>}

如果要在遍歷的過程中刪除元素，那么使用迭代器的remove方法是最安全的做法，調(diào)用Collection中定義的remove方法可能會引起錯誤。例如：

public void removeSomething(Collection<String> collection, String something) {
    for(int i = 0;i < collection.size(); ++i){
        if(collection.get(i).equals(something)) {
            collection.remove(i);
        }
    }
}

?這種方式的問題在于，刪除某個元素后，集合內(nèi)元素的索引發(fā)生變化，而我們的索引也在變化，所以會導致你在遍歷的時候漏掉某些元素。而且，如果在刪除元素時引起了集合的收縮（當集合中的元素個數(shù)小于集合的容量且達到一定程度后，集合會自動進行縮容操作），那么我們的最后幾次循環(huán)可能會造成索引越界。所以，更安全的做法是：
public void removeSomething(Collection&lt;String&gt; collection, String something) {<br/>Iterator &lt;String&gt; it = collection.iterator();<br/>while(it.hasNext()) {<br/>if(it.next().equals(something)) {<br/>it.remove();<br/>}<br/>}<br/>}

(3)聚合操作
??在Java8及更高版本中，迭代集合的首選方法是獲取流并對其執(zhí)行聚合操作。聚合操作通常與lambda表達式結合使用，以使用較少的代碼使程序更具表現(xiàn)力。以下代碼按順序遍歷一個形狀集合并打印出紅色的形狀：
myShapesCollection.stream()<br/>.filter(e -&gt; e.getColor() == Color.RED)<br/>.forEach(e -&gt; System.out.println(e.getName()));

?同樣，您可以輕松地請求并行流，如果集合足夠大并且您的CPU具有足夠的核心，這可能是有意義的：
myShapesCollection.parallelStream()<br/>.filter(e -&gt; e.getColor() == Color.RED)<br/>.forEach(e -&gt; System.out.println(e.getName()));

?使用此API操作集合元素的方法有很多種。例如，您可能希望將一個Collection的元素轉換為String對象，然后將它們連接起來，用逗號分隔：
String joined = elements.stream()<br/>.map(Object::toString)<br/>.collect(Collectors.joining(", "));

    或者對所有員工的工資進行求和：

int total = employees.stream()
.collect(Collectors.summingInt(Employee::getSalary)));
??這里只是簡單的對集合的聚合操作進行一個簡單的展示，稍后我們將會詳細地介紹聚合操作。

批量操作

??批量操作對于整個集合進行操作。下面是Collection中的批量操作：

containsAll(Collection<?> c)：如果集合中包含指定集合的所有元素，則返回true。
addAll(Collection<? extends E> c)：將指定集合的所有元素添加到當前集合。
removeAll(Collection<?> c)：從集合中刪除指定集合中的所有元素。
retainAll(Collection<?> c)：從當前集合中刪除指定集合中不存在的元素，相當于求交集操作。
clear()：從集合中刪除所有元素。
??如果集合發(fā)生了變化，那么addAll，removeAll和retainAll將會返回true。
??為了展示批量操作的效率，下面的例子從集合c中刪除指定元素e：

c.removeAll(Collections.singleton(e));
??或者說，要從集合中刪除所有null元素：

c.removeAll(Collections.singleton(null));
??Collections.singleton是一個靜態(tài)工廠方法，它返回一個只包含一個元素的Set。Collections類提供了大量操作集合的方法，我們會在下面逐一進行介紹。

2.Set接口

??Set是Collection接口的子接口，它表示不能含有重復元素的集合，這一點和數(shù)學中的集合相同。Set接口包含了繼承自Collection接口中的方法并添加了禁止重復元素的限制。
??下面是一個簡單但實用的使用Set的例子。假設現(xiàn)在有一個集合，我們希望創(chuàng)建另一個包含相同元素但刪除了所有重復元素的集合：

Collection<Type> noDups = new HashSet<>(c);
??Set最大的特點就是不包含重復項，因此在構造過程中會自動去除重復的元素，而無需我們關心。上面使用的HashSet是Set接口的一個實現(xiàn)，我們會在稍后介紹各接口的常用實現(xiàn)。
??由于Set接口繼承自Collection接口，因此大部分方法都和Collection接口中的方法相同，這里不再贅述。此外，從Java 9之后，Set接口還提供了of和copyOf兩個用于快速創(chuàng)建集合的靜態(tài)方法，不過需要注意的是，它們創(chuàng)建的都是不可變的Set，也就是說集合一經(jīng)創(chuàng)建就不能再添加或刪除元素。其中of方法接受0個或多個參數(shù)，并返回包含這些元素的不可變集合，而copyOf則根據(jù)指定的集合來創(chuàng)建包含該集合中元素的不可變集合。下面是使用這兩個方法的例子：

Set<Integer> set1 = Set.of(1, 2);
Set<Integer> set2 = Set.copyOf(set1);
??此外，對于Set來說，只要兩個集合的元素都是相等的，那么我們就認為這兩個集合是相等的。這與Object類默認的equals方法不同，因此在實現(xiàn)Set接口時，我們還需要重新定義equals和hashcode方法。

3.List接口

??List也是Collection接口的子接口，它表示有序集合，并且它可以包含重復元素，有時也將其稱之為列表。除了繼承自Collection的方法外，它還支持以下操作：

位置訪問：根據(jù)在列表中的位置來操作元素，例如get、set、add、addAll和remove等方法。
查找：查找指定的對象并返回其在列表中的位置，查找方法包括indexOf和lastIndexOf。
迭代：除了繼承自Collection接口的iterator方法，List接口還提供了listIterator方法來獲取利用列表的順序性對列表進行遍歷的迭代器。
視圖操作：subList方法獲取一個子列表的視圖，對它進行操作實際上就是對原列表進行操作。
排序：按照指定的比較規(guī)則對列表中的元素進行排序。
替換：按照指定的規(guī)則對列表中的元素進行替換。
??由于List接口繼承自Collection接口，因此Collection中的方法不再介紹。此外，List接口中也包含of和copyOf靜態(tài)方法，除了它返回的是不可變的List之外，其他都和上面Set接口中的這兩個方法一致。下面對List接口中特有的方法進行介紹。

位置訪問

??下面是List接口中與位置有關的操作：

add(int index, E element)：將指定元素插入到指定位置上。
addAll(int index, Collection<? extends E> c)：將指定集合中的元素插入到指定位置上。
get?(int index)：獲取指定位置上的元素。
remove?(int index)：移除指定位置上的元素。
set?(int index, E element)：使用指定元素替換指定位置上的元素。
??這些方法的使用都比較簡單，這里不再一一舉例。

搜索

??List接口中提供了indexOf和lastIndexOf兩個方法來對指定元素進行查找，它們與contains最大的區(qū)別就是如果找到元素，就可以返回元素在列表中的位置。如果沒有找到，這兩個方法將會返回-1。由于列表允許重復的元素，因此indexOf會返回從前向后查找時該元素第一次出現(xiàn)的位置，而lastIndexOf會返回從后向前查找時該元素第一次出現(xiàn)的位置。例如：

List<Integer> intList = List.of(0, 1, 2, 1, 0);
System.out.println(intList.indexOf(1));
System.out.println(intList.lastIndexOf(1));
??上面的例子將會輸出：

1
3
迭代器

??除了繼承自Collection接口的iterator方法，List接口還提供了listIterator方法，使用這個方法可以獲取一個ListIterator類型的迭代器。使用這種迭代器可以以任一方向對列表進行遍歷，在遍歷期間修改列表（不只是刪除，還可以插入和替換），或者是獲取迭代器的當前位置。
??ListIterator接口是Iterator接口的子接口，除了繼承自Iterator接口的三個方法外（hasNext、next和remove），它還新增了六個方法。下面是這九個方法的簡介：

hasNext()：判斷迭代器所在的位置后面是否有元素。
next()：返回迭代器所在位置后面的元素并向后移動迭代器。
hasPrevious()：判斷迭代器所在的位置前面是否有元素。
previous()：返回迭代器所在位置前面的元素并向前移動迭代器。
previousIndex()：返回迭代器所在位置的前一個元素的索引。
nextIndex()：返回迭代器所在位置的后一個元素的索引。
add(E e)：將指定元素插入到迭代器所在的位置前面。
set(E e)：使用指定元素替換上一次next或previous操作返回的元素。
remove()：移除上一次next或previous操作返回的元素。
??這里有必要解釋一下ListIterator的位置的概念。對于一個ListIterator來說，它的游標并不指向某個元素，而是位于兩個元素之間。如果一個列表有n個元素，那么ListIterator的游標的位置就有n+1個，例如：

?上圖中的列表共有4個元素，那么游標可能出現(xiàn)的位置就有5個，分別是0，1，2，3，4。

??List接口的listIterator方法有兩種形式。listIterator()返回一個游標在0處的迭代器，listIterator(int index)返回一個指定位置的迭代器，例如上圖中，list.listIterator(4)就會返回最后一個位置的迭代器。通過這兩個方法和ListIterator，就可以從任意位置，任意方向去遍歷列表。
??需要注意的是，remove和set方法并沒有涉及到迭代器的位置，它們操作的是上一次next或previous操作返回的元素。除此之外，在調(diào)用next或previous之后，調(diào)用remove之前，這中間不能調(diào)用add方法；而在調(diào)用next或previous之后，調(diào)用set之前，這中間不能調(diào)用add或remove方法。這是由于如果在set或remove之前進行了其他操作，列表會發(fā)生變化，此時再調(diào)用這兩個方法有可能產(chǎn)生歧義，因此為了避免這種情況，這兩個方法將會拋出IllegalArgumentException。

視圖操作

??subList(int fromIndex, int toIndex)是一個視圖操作，它返回一個子列表，這個子列表包含了原列表中索引在fromIndex到toIndex（不包括toIndex）之間的元素。之所以說subList是一個視圖操作，是因為它返回的子列表的元素都是原列表中的元素，而不是它們的拷貝。對子列表的操作也會影響到原列表。
??例如，下面的例子從列表中移除子列表視圖中的元素：

list.subList(fromIndex, toIndex).clear();

??這比我們使用迭代器去刪除這些元素簡潔不少。下面的例子在指定的范圍中查找元素：

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

??注意，上面的例子中返回的是元素在子列表中的索引，而不是在原列表中的索引。
??盡管subList操作非常強大，但在使用時必須小心。在修改了原列表后，不要再使用之前的subList，否則可能會出現(xiàn)異常，例如：
List&lt;String&gt; list = new ArrayList&lt;&gt;();<br/>list.add("0");<br/>list.add("1");<br/>list.add("2");<br/>list.add("3");<br/>List&lt;String&gt; subList = list.subList(0,2);<br/>list.remove(1);<br/>System.out.println(subList);

?上面的程序中，subList是索引為0和1的兩個元素的視圖，從原集合中刪除索引為1的元素，視圖也會隨著改變。但是對于我們來說，如果這個操作在其他的方法中，那么我們無法感知視圖的變化，程序也有可能會拋出異常。為了避免這種情況，建議在修改原始列表后，不要再使用之前的視圖，而是應該重新獲取。

排序

??List接口提供了一個默認方法sort?(Comparator<? super E> c)，它接受一個Comparator類型的對象作為參數(shù)，然后根據(jù)該對象中定義的比較規(guī)則對列表進行排序。Comparator定義了某種類型的比較規(guī)則，它只有一個抽象方法compare(T o1, T o2)，因此它是一個函數(shù)式接口，也就是說可以向sort方法傳遞lambda表達式。當o1大于o2時，compare方法返回正數(shù)；當o1小于o2時，compare方法返回負數(shù)；當o1等于o2時，compare方法返回0。
??現(xiàn)在假設我們有一個Apple類，這個類有weight以及其他的屬性。當一個Apple的weight大于另一個Apple的weight時，我們就認為這個Apple是“大于”另一個Apple的。根據(jù)這個定義，我們來編寫用于排序Apple列表的Comparator：
public class AppleComparator implements Comparator&lt;Apple&gt; {<br/>public int compare(Apple a1, Apple a2) {<br/>return a1.getWeight() - a2.getWeight();<br/>}<br/>}

?現(xiàn)在就可以對Apple列表appleList進行排序了：

appliList.sort(new AppleComparator());
??當然，可以使用更加簡潔的lambda表達式，這樣就無需編寫AppleComparator類了，只需要像下面這樣：

appleList.sort((a1, a2) -> a1.getWeight() - a2.getWeight());
??sort方法首先將列表轉換為數(shù)組，然后使用歸并排序對數(shù)組進行排序，最后再將數(shù)組中的元素放回列表中。該sort方法提供了快速、穩(wěn)定的排序（排序算法的穩(wěn)定性是排序前后相等元素的相對順序不發(fā)生改變）。

替換

??List接口提供了一個默認方法replaceAll?(UnaryOperator operator)，用于替換列表中的元素。這個方法接受一個UnaryOperator對象作為參數(shù)，這是Java中定義的一個函數(shù)式接口，因此我們一般直接向replaceAll方法傳遞lambda表達式。UnaryOperator接口的抽象方法apply接受一個參數(shù)，對它執(zhí)行某些操作然后返回操作后的結果。replaceAll方法會對所有的元素執(zhí)行apply方法，然后用返回的結果替換原來的元素。
??利用這個方法可以對滿足條件的元素執(zhí)行替換操作。例如，現(xiàn)在有一個存放字符的集合charList，我們需要找到其中的小寫字母并將其轉換為大寫字母：
charList.replaceAll(c -> {
if (Character.isLowerCase(c)) {
return Character.toUpperCase(c);
}
return c;
});

列表算法

??除了List接口中聲明的這些方法以外，Collections類還提供了許多操作List的方法。下面對這些方法進行簡要地介紹：

sort——對指定的列表進行排序，本質(zhì)上只是調(diào)用了List自身的sort方法。
shuffle——隨機打亂列表中元素的順序。
reverse——反轉列表。
rotate——將列表按照指定的距離進行旋轉。
swap——交換兩個指定索引處的元素。
replaceAll——使用指定的新元素替換指定的舊元素。
fill——使用指定元素替換列表中的所有元素。
copy——將源List中的元素拷貝到目標List。
binarySearch——使用二分查找算法在列表中查找元素，前提是列表必須是排好序的（升序）。
indexOfSubList——從前向后查找子列表在指定列表中出現(xiàn)的位置，若未找到則返回-1。
lastIndexOfSubList——從后向前查找子列表在指定列表中出現(xiàn)的位置，若未找到則返回-1。
4.Queue接口

??隊列是在處理之前保存元素的集合。除了基本的集合操作外，Queue接口還新增了以下方法：

E element();
boolean offer(E e);
E peek();
E poll();
E remove();

??Queue的每種方法都存在兩種形式：一種是在操作失敗的時候拋出異常，另一種在操作失敗的時候返回特定值（null或false，取決于操作類型）。下表列出了這些方法：

?隊列通常（但不一定）是按照先進先出（FIFO，first in first out）的方式來保存元素。優(yōu)先級隊列除外，它們根據(jù)元素的值對元素進行排序。無論使用什么順序，隊列頭部的元素都是通過調(diào)用remove或poll方法將會被刪除的那個元素。在FIFO隊列中，所有的新元素都被插入隊列的尾部。其他類型的隊列可能使用不同的排列規(guī)則。每個Queue接口的實現(xiàn)都必須指定其排序特性。

??有些類型的隊列會限制元素的個數(shù)，這樣的隊列被認為是有界的。java.util.concurrent包中的某些Queue的實現(xiàn)是有界的，而java.util包中的Queue的實現(xiàn)則不是。
??Queue接口中的add方法繼承自Collection接口，它向隊列中插入一個元素。如果元素的個數(shù)超出容量限制，這個方法會拋出一個IllegalStateException異常。另一個向隊列中插入元素的方法是offer方法，當插入失敗時，這個方法將會返回false。當使用有界隊列時，更推薦使用這個方法。
??remove和poll方法都返回并移除隊列頭部的元素。當隊列為空時，remove拋出NoSuchElementException異常，而poll則返回null。
??element和peek方法返回但不移除隊列頭部的元素。當隊列為空時，element拋出NoSuchElementException異常，而peek則返回null。
??Queue的實現(xiàn)類通常來說不允許插入null元素。但LinkedList類是個例外，它也是Queue的實現(xiàn)類，但是它允許插入null。在使用LinkedList時應該避免插入null元素，因為null被peek和poll方法作為特殊的返回值。
??下面的例子將隊列用作一個倒計時器：
public void countdown(int seconds) throws InterruptedException {<br/>int time = Integer.parseInt(seconds);<br/>Queue&lt;Integer&gt; queue = new LinkedList&lt;Integer&gt;();<br/>for (int i = time; i &gt;= 0; i--)<br/>queue.add(i);<br/>while (!queue.isEmpty()) {<br/>System.out.println(queue.remove());<br/>Thread.sleep(1000);<br/>}<br/>}

該程序將會每秒輸出一個數(shù)字，這個數(shù)字代表倒計時所剩的秒數(shù)。由于我們?nèi)腙爼r是按照從大到小的順序，而出隊時也是從大到小的順序，這正好證明了隊列的先進先出的特性。

5.Deque接口

??Deque是Queue的子接口，它表示雙端隊列。雙端隊列是支持在兩端進行插入和刪除操作的隊列。正是由于雙端隊列支持在兩端進行操作，它既可以被用作后進先出的棧，也可以被用作先進先出的隊列。
??由于Deque支持在兩端進行插入、刪除和查看操作，再加上每種操作都有拋出異常和返回特殊值兩種形式，因此Deque接口中共定義了以下12個訪問元素的方法：

以上這些方法與除了操作的位置不同外，其余與Queue中的方法完全相同，這里不再贅述。除此之外，Deque還提供了removeFirstOccurence和removeLastOccurence兩個方法，這兩個方法分別刪除指定元素在Deque中第一次和最后一次出現(xiàn)的位置。

6.Map接口

??Map接口表示映射結構，它是對數(shù)學概念中的映射的抽象，可以將它理解為存儲鍵值對的集合。但實際上它并不是集合，它是Java集合框架中映射結構的頂級接口。通過給定的鍵可以很快地從Map中找到對應的值。Map中不能包含重復的鍵，如果向Map中插入鍵相同的鍵值對，那么Map中這個鍵對應的值將會被新的值覆蓋。
??下面是Map接口中定義的基本方法：

需要注意的是，某些Map實現(xiàn)支持null值，而有些則不支持。因此，當使用get方法獲取value時，若返回null，則需要根據(jù)對應的實現(xiàn)類來進行判斷是key不存在還是key對應的value是null。當然，為了保險起見，可以先調(diào)用containsKey來判斷指定的key是否存在。
??除了操作單個元素的基本操作外，Map中還定義了兩個批量操作映射的方法：

?Map中定義了一個內(nèi)部接口Entry，它用來表示Map中的一個鍵值對。Entry接口提供了getKey和getValue方法，可以分別獲得鍵值對的鍵和值。Map接口還提供了一個靜態(tài)方法entry(K key,V value)，這個方法將會根據(jù)指定的key和value生成一個不可變的Entry類型的對象。

??Map接口提供了針對鍵、值和鍵值對的集合視圖：

keySet——返回包含Map中所有鍵的Set。
values——返回包含Map中所有值的Collection。這個Collection不會是Set，因為多個鍵可能對應相同的值。
entrySet——返回包含Map中所有鍵值對的Set。
??Map接口中還提供了幾個可以直接返回Map實例的方法：

7.SortedSet接口

??SortedSet是Set接口的子接口，它實際上是Set的排序版本。它對內(nèi)部的元素按照自然順序或者在構建SortedSet的實例時指定的Comparator來對元素進行排序。我們上面提到的TreeSet就實現(xiàn)了SortedSet接口。除了繼承自Set接口的方法外，SortedSet還提供了以下操作：

范圍視圖：獲取任意范圍內(nèi)的元素的視圖。
訪問雙端元素：返回第一個或最后一個元素。
獲取比較器：返回排序使用的比較器（如果有）。
??SortedSet中定義了以下方法：
`public interface SortedSet<E> extends Set<E> {
// Range-view
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);

// Endpoints
E first();
E last();

// Comparator access
Comparator<? super E> comparator();

}`
?SortedSet的視圖操作共有三個方法：

subSet(E fromElement, E toElement)：返回包含范圍在fromElement（包含）到toElement（不包含）之間的元素的集合。
headSet(E toElement)：返回小于toElement的元素的集合。
tailSet(E fromElement)：返回大于fromElement的元素的集合。
??與List的視圖不同，即使修改了原集合，SortedSet的視圖仍然有效。List的視圖是原集合中的特定元素，當原集合發(fā)生結構性的變化后，視圖無法繼續(xù)保持原來的特定元素；而SortedSet的視圖則是原集合中特定范圍內(nèi)的元素，只與范圍有關，因此在修改了原集合之后，視圖仍然有效。
??訪問雙端元素的方法是first()和last()，它們分別返回SortedSet中的第一個元素和最后一個元素。
??通過comparator()方法可以獲取SortedSet在排序時使用的比較器。如果集合內(nèi)元素是按照自然順序排序的，這個方法將會返回null。

8.SortedMap接口

??SortedMap是Map接口的子接口，它實際上是Map的排序版本。它按照自然順序或者在構建SortedMap的實例時指定的Comparator來對鍵進行排序。與SortedSet類似，它也提供了以下操作：

范圍視圖：獲取鍵在指定范圍內(nèi)的子映射的視圖。
訪問雙端鍵：返回第一個或最后一個鍵。
獲取比較器：返回排序使用的比較器（如果有）。
??SortedMap中定義了以下方法：
`public interface SortedMap<K, V> extends Map<K, V>{
// Range-view
SortedMap<K, V> subMap(K fromKey, K toKey);
SortedMap<K, V> headMap(K toKey);
SortedMap<K, V> tailMap(K fromKey);

// Endpoints
K firstKey();
K lastKey();

// Comparator access
Comparator<? super K> comparator();

}`
?這些方法與SortedSet中定義的方法基本類似，可以類比參照上一小節(jié)中對這些方法的介紹，這里不再進行過多描述。

三.實現(xiàn)

??在講完了Java集合框架中的基本接口后，現(xiàn)在我們來學習這些接口的實現(xiàn)。本文描述了以下幾種實現(xiàn)：

通用實現(xiàn)——最常用的實現(xiàn)，專為日常使用而設計。
專用實現(xiàn)——專門為一些特殊場景設計，性能、限制或行為可能與通用實現(xiàn)不同。
并發(fā)實現(xiàn)——旨在支持高并發(fā)性。
包裝實現(xiàn)——包裝其他類型的實現(xiàn)（通常是通用實現(xiàn)），以增加或限制功能。
便捷實現(xiàn)——通常是通過靜態(tài)工廠方法提供的迷你實現(xiàn)，為特殊集合（例如單例集）的實現(xiàn)提供方便、有效的替代方案。
抽象實現(xiàn)——可以理解為骨架實現(xiàn)，有助于方便、快速地構建自定義實現(xiàn)。
??下面將依次對第二節(jié)中提到的接口的實現(xiàn)進行介紹。在介紹實現(xiàn)時，由于之前已經(jīng)對各接口中定義的方法做了說明，因此不再重復闡述，只是描述各實現(xiàn)類的特點和注意事項。

1.Set實現(xiàn)

通用實現(xiàn)

??Java平臺中提供的Set接口的通用實現(xiàn)是HashSet、TreeSet和LinkedHashSet。HashSet將元素存在一個哈希表中，是性能最佳的實現(xiàn)，但是它不能保證迭代的順序。TreeSet將元素存儲在一個紅黑樹中，根據(jù)元素的值來進行排序，它比HashSet慢得多。LinkedHashSet同時具備了鏈表和哈希表的特點，使用鏈表來保存插入順序，使用哈希表來快速定位元素，也就是說它的遍歷順序和插入順序是一致的，但同時它的成本也是最高的。在實際使用過程中，可以靈活選擇這幾種Set。如果對遍歷的順序沒有要求或者不需要遍歷，可以選擇HashSet；如果在遍歷時需要按照元素的值進行排序，可以選擇TreeSet；如果需要按照插入順序遍歷，可以選擇LinkedHashSet。
??實際上，有關這些實現(xiàn)類還有很多實現(xiàn)細節(jié)沒有介紹。由于本系列是基礎教程，因此不再過多深入。后續(xù)會推出閱讀Java源碼的系列，屆時將會對Java中部分常用的類的源碼進行詳細介紹，敬請期待。

專用實現(xiàn)

??Java提供了兩個Set接口的專用實現(xiàn)——EnumSet和CopyOnWriteArraySet。
??EnumSet是為枚舉類型提供的高性能實現(xiàn)。EnumSet的所有成員必須具有相同的枚舉類型。下面是EnumSet類中提供的構造EnumSet的工廠方法：

    ![](https://s1.51cto.com/images/blog/201905/05/ec48240994362d5dead1c7251369b80c.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)

?EnumSet內(nèi)部維護了一個存儲該枚舉類型所有成員的數(shù)組，還有一個表示每個枚舉成員是否存在于集合內(nèi)的“位向量”，這個“位向量”可能是long也可能是long數(shù)組。因為每個枚舉對象都有一個序號，因此位向量使用序號對應的位上的0或1來表示該對象是否存在于集合中。例如，現(xiàn)在我們有一個關于星期的枚舉類型：

public enum Day {
    SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY
}

??我們使用of方法來創(chuàng)建一個EnumSet實例：

Set<Day> days = EnumSet.of(Day.TUESDAY, Day.FRIDAY);

??那么對于這個EnumSet來說，它的位向量是下面這樣的：
![](https://s1.51cto.com/images/blog/201905/05/69e24db7477b8e1ac7c8452866b1cbf3.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)
實際上，EnumSet是一個抽象類。java.util包中提供了它的兩個子類，分別是RegularEnumSet和JumboEnumSet，RegularEnumSet使用一個long變量來表示位向量，而JumboEnumSet則使用long數(shù)組來表示位向量。在使用EnumSet的工廠方法構建實例時，它會自己選擇使用哪個子類，而無需我們關心。
??現(xiàn)在來看另外一個專用實現(xiàn)——CopyOnWriteArraySet。在介紹這個類之前，首先我們要了解一下CopyOnWrite的概念。這個術語的字面意思是在寫的時候復制，實際上也是這么做的。在修改某個數(shù)據(jù)時，我們先拷貝一份副本，在副本上進行寫操作，然后再替換之前的數(shù)據(jù)。這樣可以避免在寫數(shù)據(jù)時，因為加鎖而造成其他讀線程等待的情況。CopyOnWriteArraySet內(nèi)部使用數(shù)組來保存元素，當對集合進行修改操作時（例如add、set或remove等），它會先將數(shù)組拷貝出一個副本，然后對這個副本進行操作，最后再將對原數(shù)組的引用指向新的數(shù)組。實際上，CopyOnWriteArraySet內(nèi)部使用了下文中List接口的實現(xiàn)類CopyOnWriteArrayList來保存元素，而CopyOnWriteArrayList才是真正使用數(shù)組來實現(xiàn)的。
??正是由于這個機制，CopyOnWriteArraySet具有以下特點：

它適用于讀操作遠遠多于寫操作的場景，因為寫操作代價較高，它通常意味著復制整個底層數(shù)組；
它是線程安全的；
迭代器不支持remove操作；
讀進程有可能讀到的是過時的數(shù)據(jù)；
讀寫進程之間沒有競爭，但是寫進程之間還是需要加鎖。
2.List實現(xiàn)

通用實現(xiàn)

??Java集合框架中提供了兩個List集合的通用實現(xiàn)——ArrayList和LinkedList。ArrayList內(nèi)部使用數(shù)組實現(xiàn)，因此它的訪問速度非?？?。但正是由于它內(nèi)部使用數(shù)組，因此在指定位置處添加或刪除元素時需要移動后面所有的元素。需要注意的是，它并不是線程安全的。不過，可以使用Collections類的synchronizedList方法來將一個ArrayList轉換為線程安全的對象。
??如果需要頻繁地在List的開頭添加或刪除元素并且元素的個數(shù)非常多時，則應考慮使用LinkedList。它是使用鏈表來實現(xiàn)的，因此它的添加和刪除元素操作非?？?。但正是由于鏈式結構，因此它的訪問速度則需要花費線性時間。此外，LinkedList還實現(xiàn)了Deque，因此它支持Deque接口中定義的操作。
??在使用List時，要充分考量程序的性能，來選擇使用ArrayList還是LinkedList。一般來說，ArrayList更快。

專用實現(xiàn)

??Java提供了兩個List接口的專用實現(xiàn)——Vector和CopyOnWriteArrayList。
??Vector是線程安全的List，并且它比經(jīng)過Collections.synchronizedList處理過的ArrayList還要快一點。但是Vector中含有大量的遺留代碼，畢竟它從Java1.0就開始存在了，當時還沒有集合框架。從Java1.2開始，這個類被改進以實現(xiàn)List接口，使其成為Java集合框架的一員。因此，在使用Vector時，應該盡量使用List接口去操作。
??CopyOnWriteArrayList的原理在上文中對CopyOnWriteArraySet的介紹中已經(jīng)做了說明，這里不再贅述。

3.Map實現(xiàn)

通用實現(xiàn)

??Map接口的三個通用實現(xiàn)分別是HashMap、TreeMap和LinkedHashMap。如果你想要最快的速度而不關心迭代順序，請使用HashMap。如果需要SortMap操作或按鍵排序的迭代順序，請使用TreeMap。如果需要接近HashMap的速度和按插入順序迭代，請使用LinkedHashMap。這三個實現(xiàn)和Set接口中的三個通用實現(xiàn)非常類似。
??雖然LinkedHashMap默認是按照插入順序來排序，但是可以在構造LinkedHashMap實例時指定另外一種排序規(guī)則。這種規(guī)則按照最近對每個鍵值對的訪問次數(shù)來排序，通過這種Map可以很方便地構建LRU緩存（Least Recently Used，一種緩存策略）。LinkedHashMap還提供了removeEldestEntry方法，通過覆蓋該方法，可以定義何時刪除舊緩存。例如，假如我們的緩存最多只允許100個元素，在緩存中的元素個數(shù)達到100個之后，每次添加新元素時都要清除舊元素，從而保持100個元素的穩(wěn)定狀態(tài)，可以像下面這樣：

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

??實際上，還有一個Map接口的通用實現(xiàn)——Hashtable（注意小寫）。它也是從Java1.0開始就存在的一個“元老”。從Java1.2開始，它被改進以實現(xiàn)Map接口。它是線程安全的，但是由于效率較低，單線程時可以使用HashMap來代替，多線程時又可以使用下文中的ConcurrentHashMap來代替，因此這個類現(xiàn)在已經(jīng)不再推薦使用。

專用實現(xiàn)

??Java提供了三個Map接口的專用實現(xiàn)——EnumMap，WeakHashMap和IdentityHashMap。
??EnumMap用在那些需要將枚舉元素作為鍵的映射中，它的底層是使用數(shù)組來實現(xiàn)的。EnumMap是一個Map與枚舉鍵一起使用的高性能實現(xiàn)。該實現(xiàn)將Map接口的豐富性和安全性與數(shù)組的速度相結合。如果要將枚舉映射到值，則應始優(yōu)先考慮EnumMap。
??WeakHashMap只存儲對其鍵的弱引用。JVM提供了四種類型的引用，分別是強引用、弱引用、軟引用和虛引用，可以讓程序員來決定某些對象的生命周期，有利于JVM進行垃圾回收。在進行垃圾回收時，若某個對象只具有弱引用，它一定會被回收。因此，當WeakHashMap中的鍵不再被外部引用時，JVM將會對它進行回收，該鍵值對也會消失。
??IdentityHashMap在比較鍵時使用引用相等性代替對象相等性。在正常的Map實現(xiàn)中，當key1.equals(key2)返回true時，我們就認為這兩個key是相等的；而在IdentityHashMap中，只有當key1==key2時，才認為這兩個key是相等的。

并發(fā)實現(xiàn)

??ConcurrentHashMap時Java提供的一個高并發(fā)、高性能的Map實現(xiàn)，它位于java.util.concurrent包中。這個實現(xiàn)在執(zhí)行讀操作時不需要加鎖。因為這個類旨在作為Hashtable的替代品，因此，除了實現(xiàn)ConcurrentMap接口外（為線程安全Map定義的接口），它還保留了大量Hashtable中的遺留代碼。因此，在使用ConcurrentHashMap時，應該盡量使用ConcurrentMap或Map接口去操作。

4.Queue實現(xiàn)

通用實現(xiàn)

??Queue接口的通用實現(xiàn)包括LinkedList和PriorityQueue。
??我們已經(jīng)在List實現(xiàn)中介紹了LinkedList，為什么還要在Queue實現(xiàn)中再次提到它呢？這是因為LinkedList同時實現(xiàn)了List接口和Deque接口，而Deque接口又是Queue的子接口。因此，LinkedList可以算是List、Queue和Deque的實現(xiàn)。當我們使用不同的接口去引用LinkedList實例時，它就會表現(xiàn)出不同的行為。
??PriorityQueue用來表示基于堆結構的優(yōu)先級隊列。它使用指定的排序規(guī)則來對元素進行排序，而不是按照隊列默認的先進先出的順序。在對PriorityQueue進行遍歷時，迭代器不保證以任何特定順序遍歷優(yōu)先級隊列的元素。如果需要有序遍歷，可以使用Arrays.sort(pq.toArray())。

并發(fā)實現(xiàn)

??java.util.concurrent包中提供了一組Queue實現(xiàn)類，這些類都是線程安全的，因此可以在多線程中使用。這些類都實現(xiàn)了BlockingQueue接口，這個接口繼承了Queue接口并且增加了一些額外的操作，支持當獲取隊列元素但是隊列為空時，會阻塞等待隊列中有元素再返回或超時返回；也支持添加元素時，如果隊列已滿，那么等到隊列可以放入新元素時再放入或超時返回。
??下表是BlockingQueue接口中操作元素的方法，除了繼承自Queue接口的拋出異常和返回特定值的形式外，又增加了阻塞和超時兩種形式：
![](https://s1.51cto.com/images/blog/201905/05/84e5908eb76b43ca5dfacf63940f77a8.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)

?下面是BlockingQueue接口的實現(xiàn)類：

LinkedBlockingQueue——由鏈式節(jié)點實現(xiàn)的有界FIFO阻塞隊列。
ArrayBlockingQueue——由數(shù)組實現(xiàn)的有界FIFO阻塞隊列。
PriorityBlockingQueue——由堆實現(xiàn)的×××阻塞優(yōu)先級隊列。
DelayQueue——支持延時獲取元素的×××阻塞隊列。
SynchronousQueue——同步阻塞隊列，無容量，它的每個插入操作都要等待其他線程相應的移除操作，反之亦然。
??此外，java.util.concurrent包中還定義了TransferQueue接口，它是BlockingQueue的子接口。在添加元素時，除了BlockingQueue中定義的方法，TransferQueue還定義了transfer和tryTransfer方法。transfer方法在傳遞元素時，若存在消費者，則立即將元素傳遞給消費者，否則將元素插入到隊列尾部；tryTransfer方法在傳遞元素時，若存在消費者，則立即將元素傳遞給消費者，否則將元素插入到隊列尾部，若在指定的時間內(nèi)元素沒有被消費者獲取，則將該元素從隊列中移除并返回false。TransferQueue接口有一個基于鏈式節(jié)點的×××實現(xiàn)——LinkedTransferQueue。

5.Deque實現(xiàn)

通用實現(xiàn)

??Deque接口的通用實現(xiàn)包括LinkedList和ArrayDeque。ArrayDeque使用可調(diào)整大小的數(shù)組實現(xiàn)，而 LinkedList則是鏈表實現(xiàn)。
??LinkedList允許null元素，而ArrayDeque則不允許。在效率方面，ArrayDeque比LinkedList兩端的添加和刪除操作更高效。LinkedList的最佳使用方式是在迭代期間刪除元素。不過LinkedList并不是迭代的理想結構，并且它比ArrayDeque占用更多的內(nèi)存。此外，無論是LinkedList還是ArrayDeque均不支持多個線程的并發(fā)訪問。

并發(fā)實現(xiàn)

??LinkedBlockingDeque類是Deque接口的并發(fā)實現(xiàn)。和BlockingQueue相同，它在獲取雙端隊列元素但是隊列為空時，會阻塞等待隊列中有元素再返回或超時返回；也支持在雙端添加元素時，如果隊列已滿，那么等到隊列可以放入新元素時再放入或超時返回。

6.包裝實現(xiàn)

??位于java.utils包中的Collections也是Java集合框架的一員，但它不是任意一種集合，而是一個包裝類。它包含各種有關集合操作的靜態(tài)方法，這個類不能實例化。它就像一個工具類，服務于集合框架。
??這個類提供了很多的靜態(tài)工廠方法，通過這些方法，可以提供具有某些特性的集合（例如空集合，同步集合，不可變集合等），或者包裝指定的集合，使之具有某些特性。下面對這個類中的一些方法進行介紹。

同步包裝器

??同步包裝器將自動同步（線程安全）特性添加到任意集合上。Collection，Set，List，Map，SortedSet和 SortedMap接口都有一個靜態(tài)工廠方法。

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);

??每一個方法都會返回指定集合的包裝對象，這個集合是線程安全的。所有對于集合的操作都應該通過這個集合來完成，保證這一點最簡單的方法就是不再保留對原集合的引用。
??面對并發(fā)訪問，用戶必須在迭代時手動同步返回的集合。這是因為迭代是通過對集合的多次訪問來完成的，而返回的集合雖然是同步的，但是它只能保證每一次對集合的操作都是線程安全的，而不能保證對于幾個的多次操作也是安全的，因此這些操作必須組成一個單獨的原子操作。以下是迭代通過包裝器返回的同步集合的習慣用法：

Collection<Type> c = Collections.synchronizedCollection(myCollection);
synchronized(c) {
    for (Type e : c)
        foo(e);
}

??有關synchronized關鍵字和多線程的內(nèi)容會在之后的文章中進行介紹。

不可變包裝器

??不可變包裝器可以使集合變?yōu)椴豢勺兗?，從而具有只讀屬性，任何會對集合進行改變的操作都會拋出一個UnsupportedOperationException。與同步包裝器一樣，六個核心接口中的每一個都有一個靜態(tài)工廠方法：

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);

??為了保證集合的絕對不變性，應該在獲取集合的不可變包裝后，不再保留對原集合的引用。

7.便捷實現(xiàn)

??本節(jié)描述了幾種便捷實現(xiàn)，當您不需要集合的全部功能時，它們比通用實現(xiàn)更方便，更高效。本節(jié)中的所有實現(xiàn)都是通過靜態(tài)工廠方法提供的。

數(shù)組的列表視圖

??Arrays.asList方法可以接受一個數(shù)組并返回該數(shù)組的列表視圖。對于集合的改變會應用在數(shù)組上，反之亦然。集合的大小就是數(shù)組的大小且不能更改，如果再集合視圖上調(diào)用可能會修改集合大小的方法將會拋出一個UnsupportedOperationException。
??這個實現(xiàn)的一般用途是作為數(shù)組和集合之間的橋梁。它允許我們將數(shù)組傳遞給需要Collection或List的方法。這種實現(xiàn)還有一個用途，如果我們需要固定大小的List，它比任何通用實現(xiàn)都要高效：

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

指定元素的集合

??下面的方法可以根據(jù)指定的元素來創(chuàng)建集合：

Arrays.asList(T... a)——返回包含指定的若干個元素的不可變List。
Collections.nCopies(int n, T o)——返回包含n個指定元素o的不可變List（這些元素都是o的引用）。
Collections.singleton(T o)——返回只包含該對象的不可變Set。
空集合或空映射

??Collections類提供了返回空Set、List和Map的方法，它們分別是emptySet()、emptyList()和emptyMap()。

四.算法

??本節(jié)中所有的算法都來自Collections類，這些算法絕大多數(shù)都以List實例作為參數(shù)，也有少部分是以Collection實例作為參數(shù)的。下面是這些算法：

sort(List list)——按照自然順序對List進行排序。
sort?(List list, Comparator<? super T> c)——根據(jù)指定的比較器對List進行排序。
shuffle?(List<?> list)——使用默認隨機源打亂List元素順序。
shuffle?(List<?> list, Random rnd)——使用指定隨機源打亂List元素順序。
reverse(List<?> list)——反轉List中的元素順序。
fill?(List<? super T> list, T obj)——使用指定元素替換List中的所有元素。
copy?(List<? super T> dest, List<? extends T> src)——將src中的元素拷貝到dest中。dest的size要大于等于src的size。
swap?(List<?> list, int i, int j)——交換指定位置的元素。
addAll?(Collection<? super T> c, T... elements)——將若干元素添加到指定的Collection中。
binarySearch?(List<? extends Comparable<? super T>> list, T key)——使用二分搜索算法在List中查找指定元素。該List必須是按照升序排列，且使用自然順序排序。
binarySearch?(List<? extends T> list, T key, Comparator<? super T> c)——使用二分搜索算法在List中查找指定元素。該List必須是按照升序排列。調(diào)用者需要提供比較器以用于在查找過程中進行比較。
frequency?(Collection<?> c, Object o)——返回指定元素在Collection中出現(xiàn)的次數(shù)。
disjoint?(Collection<?> c1, Collection<?> c2)——如果兩個集合沒有交集，返回true，否則返回false。
min?(Collection<? extends T> coll)或max?(Collection<? extends T> coll)——返回根據(jù)自然順序排列的最小值或最大值。
min?(Collection<? extends T> coll, Comparator<? super T> comp)或max?(Collection<? extends T> coll, Comparator<? super T> comp)——返回根據(jù)指定比較器排列的最小值或最大值。