集合(collection)

本章節介紹集合框架。在這裡你將知道什麼是集合已經它們是如何讓你更輕鬆的變出更棒的程式碼。你將會學到集合框架的核心元素——介面、實現和演算法。

簡介

集合有時候也稱為容器、集裝箱(Container)——聚合多個元素到單一集合裡的物件。集合被用來儲存、檢索、操作和交流彙總陣列。典型的，它們代表組成自然組的資料項，比如撲克(卡片的集合)、郵件夾(信的集合)、電話簿(姓名和電話號碼的對映)。

什麼是集合框架？

表示和操縱集合的統一架構即是集合框架。所有的集合框架包含以下內容：

• 介面：這些都是表示集合的抽象資料型別。介面允許獨立地操作集合的表現細節。在面嚮物件語言中，介面通常形成一個層次結構。
• 實現(implementations):這是集合介面實現的具體細節。本質上講，他們是可服用的資料結構。
• 演算法：這是執行有用計算的方法，比方說實現集合介面物件的排序、查詢。演算法是多型的，也就是集合介面內的同一個方法具有不同的實現。本質上講，演算法是可重用的功能。

且不說Java集合框架，比較著名的集合框架非C 標準模板庫以及Smalltalk的集合架構莫屬。以前，集合框架十分複雜，給人的印象便是十分難學。我們堅信，Java集合框架打破了這種慣例。

集合框架的好處

• 減少編碼的工作量。通過提供有用的資料結構及其演算法，集合框架可以讓你只關注業務邏輯而不是底層的實現。通過促進互操作性，Java集合框架讓你從編寫通訊類、適配類中解放出來。
• 提升編碼速度和質量：Java集合框架提供了高質量、高效能資料結構演算法的實現。介面的不同實現可交換性使程式可以輕而易舉的改變實現。不用做編寫資料結構的苦差，從而剩餘更多的時間和經歷來提升程式碼質量和效能。
• 允許不相關APIs間具有互操作性。集合介面是來回傳遞集合的本地化語言。
• 減少學習和使用新API的時間。
• 減少設計新APIs所耗費的精力。不必重複製造輪子，可以使用標準的集合介面。
• 促進軟體重用。新的符合標準集合介面的資料結構自然而然地被重用。實現介面的演算法也是一樣的。

介面

核心的集合介面封裝不同型別的集合，如下圖所示。這些介面允許獨立地操作集合的表示細節。核心集合介面是Java集合框架的地基。如下圖所示，核心集合介面構成了一個層級。

Set是特殊的集合(Collection),SortedSet是特殊的Set,等等。注意，層級包含兩種不同的樹——Map不是集合。

注意，所有核心的集合介面都是泛型的。例如：

public interface Collection<E>...

語法告訴你，這個介面是泛型化的。當你宣告一個集合例項的時候，應當指明它的型別。指定型別可以允許編譯器在編譯時，驗證你放入集合元素型別的正確性，因此在一定程度上減少了執行時期的錯誤。

當你理解如何使用這些介面，你將會了更加理解Java集合框架。本章節主要討論如何高效地使用這些介面，包括何時使用，使用哪個介面。你也將學到每個介面的程式設計風格以充分利用它們。

為了管理多個集合介面，Java平臺不為每種集合型別的每個變體提供獨立的介面(變體如不可變、固定大小等)。每個介面內的修改操作都被設計成可選的。如果執行一個不能支援的操作，就會丟擲UnsupportedOperationException。

以下列舉了核心集合介面的描述：

• 集合(Collection)。集合層級的根。集合表示一組物件(所熟知的元素:elements)。集合介面是所有集合實現的最小公分母，並在需要最大通用性的情況下用於傳遞集合並對它們進行操作。一些集合的型別允許元素重複，一些則不允許。一些集合是有序的，一些卻是無序的。Java平臺沒有提供這些介面的直接實現，但提供了更具體子介面的實現，例如Set和List.
• 集合(Set)。不能包含重複元素的集合。該介面模擬數學上的集合抽象，被用於表示集合，例如課程構成了學生的安排表，機器的操作。
• 清單、條目(List)。有序的(有時候稱為序列)集合。List可以包含重複元素，List的使用者可以精確地控制到集合的每個元素的操作，如哪個地方插入，哪個地方獲取元素。
• 佇列(Queue)。在處理之前用於儲存多個元素的集合。除了擁有Collection基本操作外，還可以進行插入、提取、檢查(inspection)操作。

典型地但不是必須的，元素時FIFO(先入，先出)的。優先佇列是個特殊的存在，即根據比較器或者元素的自然順序排序元素。無論使用什麼順序，佇列頭部的元素總是會被進行remove或者poll操作。在FIFO佇列中，所有新元素都是被插入到隊尾。其它種類的佇列或許使用其他的放置策略。

• 雙端佇列(Deque)。在處理之前用於儲存多個元素的集合。除了擁有Collection基本操作外，還可以進行插入、提取、檢查(inspection)操作。

雙端佇列可以用作FIFO或者LIFO(後入，先出)。在雙端佇列中，所有的新元素都可以在對位進行插入、移除、檢索。

• 地圖(Map)。將key對映到value的物件。Map不能包含重複的key。每個key可以對映到最多一個value。

最後兩個核心集合介面僅僅是Set和Map的排序版：

• 排序的集合(SortedSet)。元素是升序的集合。提供幾個額外的操作以最大限度發揮排序的優勢。
• 排序Map(SortedMap)。key是升序的Map.

Collection介面

集合是一組物件(elements)。集合介面在期望的最大通用性情況下被用來傳遞物件的集合。例如你擁有一個Collection<string> c，它可能是List或者Set或者任何型別的Collection。以下程式碼用所有在c內的元素來初始化ArrayList：

List<String> list = new ArrayList<String>(c);

Collection介面包含基本操作的方法，如size(),boolean isEmpty(), boolean contains(Object element), boolean add(E element), boolean remove(Object element), 和Iterator<E> iterator().

它也包含了操作整個集合的方法， 如boolean containsAll(Collection<?> c), boolean addAll(Collection<? extends E> c), boolean removeAll(Collection<?> c), boolean retainAll(Collection<?> c), 和void clear()。

此外，額外的為陣列操作的方法如Object[] toArray() and <T> T[] toArray(T[] a)。

jdk8及其之後，介面也暴露了 Stream<E> stream() 和Stream<E> parallelStream()，以獲取集合的序列流或者併發流。

集合表示一組物件。告訴你集合裡有多少個元素(size,isEmpty);某個物件是否在集合中(contains);往集合內新增元素，移除集合裡的元素(add,remove);提供集合的迭代器(iterator);

add方法被定義，這樣集合允許元素重複和不可重複就有意義起來了。它保證add方法執行後集合會包含所新增元素，如果集合在呼叫add後會改變，則返回true。同理，remove操作也一樣。

遍歷介面(Traversing Collections)

有三種方式來遍歷集合:

• 使用聚合操作(aggregate)。
• 使用for-each構造。
• 使用迭代器。

聚合操作遍歷集合

JDK 8及其之後，遍歷集合首選的方法就是在集合上獲取流，然後執行聚合操作。聚合操作是使用lambda表示式來使程式更加有效，使用的程式碼行數更少。如：

myShapesCollection.stream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));
//如果你的計算機有足夠的核數，那麼可以使用平行流
myShapesCollection.parallelStream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));
//列印集合並用逗號分隔開
String joined = elements.stream()
.map(Object::toString)
.collect(Collectors.joining(", "));
//計算薪水的總數
int total = employees.stream()
.collect(Collectors.summingInt(Employee::getSalary)));

集合框架提供了許多批量操作(bulk operations)，如操縱則整個集合的方法 containsAll, addAll, removeAll。

for-each遍歷結合

for-each構造讓你可以在集合或陣列上簡潔地遍歷。

for (Object o : collection)
System.out.println(o);

迭代器遍歷結合

一個迭代器(Iterator)是一個允許你遍歷集合併有選擇性的移除集合元素的物件。呼叫集合的iterator方法，你會得到一個迭代器。以下是迭代器的介面：

public interface Iterator<E> {
boolean hasNext(); //有元素，則返回true
E next();          //返回迭代器的下一個元素
void remove(); //optional
}

注意，呼叫每個next()後只能呼叫一次remove()方法，否則丟擲異常。

注意，Iterator.remove是迭代過程中唯一安全的操作方式。在迭代過程用其他方式修改底層程式碼，則集合的行為是不確定的(不安全)。

使用迭代器而不是用for-each construct當：

• 移除當前元素。for-each構造隱藏了迭代器，因此你不能呼叫remove。for-each構造內進行過濾操作是不安全的。
• 並行遍歷多個集合。

以下程式教你如何在任意集合下進行過濾——即遍歷並移除元素：

static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}

上面的例子體現了多型性的好處，任意Collection的子類都適用以上方法。

集合介面的批量操作

批量操作是在整個集合上進行操作(粒度大)。你可以用基本的操作來實現以下的操作，但是大多數情況下這種實現會十分無效。以下是一些批量的操作：

• containsAll。如果目標集合包含指定集合的所有元素，則返回true.
• addAll。將指定集合的所有元素新增到目標集合中。
• removeAll。移除指定集合和目標集合共有的元素。
• retainAll。交集：保留目標集合和指定集合共有的元素。
• clear。移除所有集合內的元素。

以上操作，如果目標集合被修改，則返回true。

以下程式碼是從一個集合中移除掉具體的元素：

//singleton()方法是靜態工廠方法，返回的是不可變的
c.removeAll(Collections.singleton(e));

Collection介面陣列操作

toArray()方法是集合和舊的APIs(期望入參是arrays)之間的橋樑。陣列操作允許集合元素被翻譯成一個陣列。簡答的形式是建立一個新的Object陣列(沒有任何引數)。複雜一點的是允許呼叫者提供一個入參作為陣列型別的輸出。如：

Object[] a = c.toArray();
String[] a = c.toArray(new String[0]);

Set介面

Set是Collection的一種，它不能包含重複的元素。它模擬數學抽象集合。Set介面僅包含從Collection介面繼承而來的方法，以及新增對重複元素的限制。Set也新增了更為強大的equals和hashCode操作，這樣即使實現的型別不同也能進行有意義的對比。如果兩個Set集合內的元素一模一樣，則這兩個Set集合相同(equals)。

Java平臺包含三種Set的實現：HashSet,TreeSet和LinkedHashSet。HashSet將元素儲存在一個Hash table中，是效能最佳的實現。然而它並不保證也不關心迭代的順序。TreeSet將元素儲存在一顆紅黑樹中，據元素值排序，它比HashSet慢多了。LinkedHashSet用一個hash table和Linked list來實現，它保證了元素插入的順序，它比HashSet代價稍微高些。

如果你想去掉集合中重複的元素，以下一行語句即可解決：

Collection<Type> noDups = new HashSet<Type>(c);
//JDK 8及其之後，用聚合操作，你可以很容易地將元素放入Set集合中
c.stream()
.collect(Collectors.toSet()); // no duplicates
//取people集合中的name，放到TreeSet中
Set<String> set = people.stream()
.map(Person::getName)
.collect(Collectors.toCollection(TreeSet::new));
//保留插入順序並去重
Collection<Type> noDups = new LinkedHashSet<Type>(c);
//去重並保留插入順序
public static <E> Set<E> removeDups(Collection<E> c) {
return new LinkedHashSet<E>(c);
}

Set介面的基本操作

• size(): Set集合內元素的個數。
• isEmpty(): 判斷為空。
• add(): 往集合內新增元素，新增成功返回true。
• remove(): 移除元素，成功返回true。
• iterator(): 返回Set集合的迭代器。

去重示例：

import java.util.*;
import java.util.stream.*;
public class FindDups {
public static void main(String[] args) {
Set<String> distinctWords = Arrays.asList(args).stream()
.collect(Collectors.toSet()); 
System.out.println(distinctWords.size()  
" distinct words: "   
distinctWords);
}
}
//for-each
import java.util.*;
public class FindDups {
public static void main(String[] args) {
Set<String> s = new HashSet<String>();
for (String a : args)
s.add(a);
System.out.println(s.size()   " distinct words: "   s);
}
}

注意，程式碼總是涉及到其介面型別而不是實現型別。這是強烈推薦的程式設計實踐，因為改變實現只需改變其建構函式即可(非常靈活)。而儲存集合的變數或者引數都是使用Collection的實現型別而不是其介面型別。

此外，並不能保證程式會起作用，假如程式執行了非標準的實現操作，就會導致程式執行失敗。

以上的程式碼使用HashSet來實現去重的，並不能保證其順序，如果你想讓去重後的結果為值有序，則將Set的實現改成TreeSet即可。

Set介面的批量操作

假設s1和s2是集合：

• s1.containsAll(s2)。如果s2是s1的子集，返回true。
• s1.addAll(s2)。 並集。
• s1.retainAll(s2)。交集。
• s1.removeAll(s2)。移除共有元素。

找到重複的元素以及不重複的元素：

import java.util.*;
public class FindDups2 {
public static void main(String[] args) {
Set<String> uniques = new HashSet<String>();
Set<String> dups    = new HashSet<String>();
for (String a : args)
if (!uniques.add(a))
dups.add(a);
// Destructive set-difference
uniques.removeAll(dups);
System.out.println("Unique words:    "   uniques);
System.out.println("Duplicate words: "   dups);
}
}
//output
Unique words:    [left, saw, came]
Duplicate words: [i]

Set<Type> symmetricDiff = new HashSet<Type>(s1);//去重
symmetricDiff.addAll(s2);//並集
Set<Type> tmp = new HashSet<Type>(s1);//去重
tmp.retainAll(s2);//交集
symmetricDiff.removeAll(tmp);//s1與s2並集 - s1與s2交集

Set介面的陣列操作

和Collection介面相比，它具有Collection所有的陣列操作，除此之外，它不具備任何額外的陣列操作。

List介面

List是Collection的插入有序版本，有時被稱為序列(sequence)。List可以包含重複元素。除了從Collection那裡繼承而來的方法外，還提供額外的方法：

• 根據位置訪問元素(Positional access)。根據元素在list內的位置操作元素。如get, set, add, addAll, 和remove.
• 搜尋(Search)。搜尋指定元素在list中的位置並返回，如 indexOf 和 lastIndexOf.
• 迭代器(Iteration)。繼承Iterator 語義，且充分利用list的自然序列。如listIterator 。
• 觀察範圍(range_view)。subList方法提供list內部的範圍操作。

Java平臺包含兩種型別的List實現，一種是ArrayList，這是效能比較好的一種。另一種是LinkedList，常用於對查詢要求不高，但是插入、移除頻繁的操作。

Collection操作

從Collection那裡繼承而來的方法含義和之前的一樣，只不過remove操作總是移除掉list第一個出現的指定元素。add 和 addAll操作總是將新的元素追加到list的末尾。如：

//list2追加到list1末尾
list1.addAll(list2);
//list2追加到list3後
List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);
//JDK 8及其之後，聚合name到list
List<String> list = people.stream()
.map(Person::getName)
.collect(Collectors.toList());

和Set一樣，List也重寫了equals和hashCode方法，因此兩個list元素可以進行邏輯的對比是否相等而不用理會List的具體實現。如果兩個List內的元素位置一樣，對應位置的元素一樣，則這兩個List集合相等。

按照位置訪問與搜尋操作

交換List集合內的兩個元素:

public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
//原始碼中是
@SuppressWarnings({"rawtypes", "unchecked"})
public static void swap(List<?> list, int i, int j) {
// private method
final List l = list;
//l.set(j, l.get(i))返回j位置舊值
l.set(i, l.set(j, l.get(i)));
}

不管實現型別，下面的多型演算法是交換List內部的兩個元素：

//Collections方法內 it is fair 機率均等
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--)
swap(list, i - 1, rnd.nextInt(i));
}
//列印打亂順序的List集合
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
for (String a : args)
list.add(a);
Collections.shuffle(list, new Random());
System.out.println(list);
}
}
//優化列印
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}

上面的shuffle方法，因為rnd是公正的，故所有的排列是機會均等的；因為只需要交換list.size()-1次，因此也是快速的。

迭代器(Iterators)

和你所預想的一樣Iterator返回List的迭代器，迭代器會以適當的順序遍歷List集合。List也提供了一個更加強大的迭代器，稱為ListIterator，它允許你從兩個方向(往前、往後)遍歷List;遍歷List的同時修改List;獲取迭代器當前的位置索引。

ListIterator除了包含從Iterator繼承而來的方法hasNext, next和 remove之外，還擁有hasPrevious,previous 以及當前迭代器迭代到哪個位置的索引資訊。

//從集合末尾向前迭代
for (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) {
Type t = it.previous();
...
}

ListIterator所提供的方法如下：

//無參建構函式，指標指向List的開頭
ListIterator<E> listIterator();
//有參構造，從index位置開始遍歷
ListIterator<E> listIterator(int index);
hasPrevious()//是否有前一個元素
previous()//返回前一個元素,cursor往回移動;next是往前移動
int nextIndex();//下一個位置索引
int previousIndex();

ListIterator迭代器的遊標總是介於兩個元素之間，如下程式碼示例：

//List有四個元素
List<String> list = Arrays.asList(
"element", "element2", "element3", "element4");
ListIterator<String> it = list.listIterator();
System.out.println(it.previousIndex());
System.out.println(it.next());
System.out.println(it.next());
System.out.println(it.next());
System.out.println(it.next());
System.out.println(it.nextIndex());
//output
-1
element
element2
element3
element4
4

ListIterator迭代器應用場景

//起初遊標處於-1到0之間，執行it.next()遊標處於0到1之間
public int indexOf(E e) {
for (ListIterator<E> it = listIterator(); it.hasNext(); )
if (e == null ? it.next() == null : e.equals(it.next()))
return it.previousIndex();
// Element not found
return -1;
}
public static <E> void replace(List<E> list, E val, E newVal) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
if (val == null ? it.next() == null :             val.equals(it.next()))
it.set(newVal);
} 
public static <E> 
void replace(List<E> list, E val, List<? extends E> newVals) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){
if (val == null ? it.next() == null : val.equals(it.next())) {
it.remove();
for (E e : newVals)
it.add(e);
}
}
}

Range-View 操作

subList(int fromIndex, int toIndex)即是Range-View操作，對目標集合擷取子集合，是半開區間即[fromIndex,toIndex)。

view隱含的意思修改subList操作的結果會影響到源List，同樣，修改源List**也會影響**到subList返回的子集合。

應用場景，範圍查詢、洗牌發牌

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);
public class Deal {
public static void main(String[] args) {
if (args.length < 2) {
System.out.println("Usage: Deal hands cards");
return;
}
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
// Make a normal 52-card deck.
String[] suit = new String[] {
"spades", "hearts", 
"diamonds", "clubs" 
};
String[] rank = new String[] {
"ace", "2", "3", "4",
"5", "6", "7", "8", "9", "10", 
"jack", "queen", "king" 
};
List<String> deck = new ArrayList<String>();
for (int i = 0; i < suit.length; i  )
for (int j = 0; j < rank.length; j  )
deck.add(rank[j]   " of "   suit[i]);
// Shuffle the deck.
Collections.shuffle(deck);
if (numHands * cardsPerHand > deck.size()) {
System.out.println("Not enough cards.");
return;
}
for (int i = 0; i < numHands; i  )
System.out.println(dealHand(deck, cardsPerHand));
}
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
//深拷貝
List<E> hand = new ArrayList<E>(handView);
//subList操作的結果也會如實反映在源List即deck
handView.clear();
return hand;
}
}

List的演算法

• sort。使用歸併排序，是穩定的演算法(排序後，相同元素的位置還是保持不變)。
• shuffle。偽隨機洗牌。
• reverse。
• rotate。旋轉rotate(List<?> list, int distance)。
• swap。
• replaceAll。
• fill。
• copy。
• binarySearch。
• indexOfSubList。
• lastIndexOfSubList。

Queue介面

佇列是在處理之前儲存元素的集合。除了基本的集合(Collection)操作之外，佇列還提供了額外的插入、移除和檢查操作。Queue介面如下所示：

public interface Queue<E> extends Collection<E> {
E element(); //返回頭部元素，empty時 丟擲異常
//往隊裡中新增元素，不允許加入null值。
//不用add而用offer的原因是佇列容量受限，會丟擲異常
boolean offer(E e);
E peek();//返回頭部元素，但不移除,empty時返回null
E poll();//返回並移除頭部元素，empty時返回Null
E remove();//返回並移除頭部元素，empty時丟擲異常
}

每一個Queue方法以兩種形式存在：

1. 操作失敗，則丟擲異常。
2. 操作失敗，則返回特定的值，如null或false。

如下表所示：

典型地，Queue都是先進先出(FIFO:first in first out)的，一個例外就是根據值組織元素的優先佇列(詳見物件排序)。無論什麼物件以何種方式排序，通過remove,poll操作都可以移除掉佇列頭部元素。在FIFO的佇列中，新元素被插入對位。其它種類的佇列可能會使用其他的新增規則。每一個實現Queue介面的佇列都必須指定排序的規則。

Queue的實現類是有可能限制其持有元素的個數的，這種佇列是有界的。一些位於java.util.concurrent內的Queue實現類是有界的，但位於java.util內的Queue實現類是無界的。

從Collection內繼承而來的add方法，如果使用它來新增元素時違反了Queue的容量會丟擲IllegalStateException異常，因此單獨地為這種場景提供了offer操作，如果新增不成功，它並不會丟擲異常，只會返回false。

remove,poll都是移除佇列頭元素，究竟是哪一個元素被移除，那是排序策略函式的事情了。當佇列為empty時，remove操作會丟擲NoSuchElementException而poll操作返回null。

element,peek操作只會返回佇列頭部元素。當佇列為empty時，element操作會丟擲NoSuchElementException而peek操作返回null。

佇列的實現通常不允許插入null元素，Queue的實現類LinkedList類是一個特例。LinkedList允許插入null元素的原因是歷史原因造成的，但是你應該儘量不要插入null元素，因為poll,peek操作在空佇列的情況下返回null(究竟是空佇列的原因，還是因為元素本身就是null?不得而知，故應儘量不插入null元素)。

Queue的實現類通常不重寫equals,hashCode，而是直接使用Object那一套。

Queue的實現類不定義 blocking queue方法，而在併發程式設計中又經常用到。這些等待元素的出現或空間可用的方法定義在java.util.concurrent.BlockingQueue中，它也是繼承自Queue介面。

舉個例子

//輸入一個整數，以降序方式加入到佇列中，
//再每隔1秒鐘一個個從佇列頭中移除出去。
public class Countdown {//倒計時功能，只為解釋說明優先佇列的行為
public static void main(String[] args) throws InterruptedException {
int time = Integer.parseInt(args[0]);
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = time; i >= 0; i--)
queue.add(i);
while (!queue.isEmpty()) {
System.out.println(queue.remove());
Thread.sleep(1000);
}
}
}
//集合排序，只為解釋說明優先佇列的行為 
//用Collections.sort()更為自然，普通，推薦
static <E> List<E> heapSort(Collection<E> c) {
Queue<E> queue = new PriorityQueue<E>(c);
List<E> result = new ArrayList<E>();
while (!queue.isEmpty())
result.add(queue.remove());
return result;
}

Deque介面

通常和deck發音一樣，一個Deque是一個雙端佇列。雙端佇列是元素的線性集合，支援在兩個端點處插入和移除元素。Deque介面是比Stack 和Queue擁有更加豐富的抽象資料型別，因為它即實現了Stack又實現了Queue。Deque介面定義了在Deque例項兩段處訪問元素的方法。方法包括插入、移除、檢索元素。預定義的類如ArrayDeque和LinkedList都實現了Deque介面。

注意到Deque介面可以被用作FIFO的佇列，也可以用作LIFO的棧。Deque介面內的方法被分割成三部分。

插入

方法addFirst，offerFirst是在Deque例項前插入元素。方法addLast，offerLast是在Deque例項末尾插入元素。當Deque例項的容量是有限制的應當優先選擇offerFirst和offerLast，因為其它兩個方法可能會丟擲異常。

移除

方法removeFirst，pollFirst是在Deque例項前移除元素。方法removeLast，pollLast是在Deque例項末尾移除元素。當Deque為空時，方法pollFirst和pollLast返回null，而其它兩個方法會丟擲異常。

檢索

方法 getFirst 和peekFirst 是 Deque 例項檢索首元素的方法. 不會從 Deque 例項中移除元素. 類似地, 方法 getLast 和peekLast是檢索 末位元素. 如果 deque為empty，則方法 getFirst 和getLast 丟擲異常，然而方法 peekFirst 和peekLast 卻返回NULL.

以下總結出了12個插入、移除、檢索Deque的方法：

操作型別     首元素           末元素
插入   `addFirst(e)`      `addLast(e)`
`offerFirst(e)`     `offerLast(e)`
移除   `removeFirst(e)`   `removeLast(e)`
`pollFirst(e)`     `pollLast(e)` 
檢索   `getFirst(e)`       `getLast(e)`
`peekFirst(e)`     `peekLast(e)`        

除了以上的基本操作方法之外，Deque介面也提供了其它的方法，如removeFirstOccurence，這個方法是移除第一次存在於Deque介面內的元素，如果不存在，則Deque例項保持不變。類似的方法是removeLastOccurence,它是移除最後一次存在於Deque介面內的元素，如果存在則返回true,否則返回false.

Map介面

Map是將key對映到value的物件。Map不能包含兩個一樣的key，但是多個key可以對映到同一個value。Map介面包含基本的操作，例如put,get,remove,containskey,size,empty,批量操作，如putAll,clear。以及集合檢視，如keySet，entrySet,values。

Java平臺包含三種目的的Map實現:hashMap,TreeMap,LinkedHashMap.他們和Set介面類似。

本章節主要討論Map介面。但首先先舉幾個jdk1.8的聚合操作例子。在物件導向的程式設計世界中，模擬真實世界的物件是普片的任務，因此將員工按照部門分組是合理的：

// Group employees by department
Map<Department, List<Employee>> byDept = employees.stream()
.collect(Collectors.groupingBy(Employee::getDepartment));

或者計算一個部門的工資：

// Compute sum of salaries by department
Map<Department, Integer> totalByDept = employees.stream()
.collect(Collectors.groupingBy(Employee::getDepartment,
Collectors.summingInt(Employee::getSalary)));

或者統計學生成績是否通過

// Partition students into passing and failing
Map<Boolean, List<Student>> passingFailing = students.stream()
.collect(Collectors.partitioningBy(s -> s.getGrade()>= PASS_THRESHOLD)); 

你也可以將人們以城市分組

// Classify Person objects by city
Map<String, List<Person>> peopleByCity
= personStream.collect(Collectors.groupingBy(Person::getCity));

或者將集合按照城市和狀態歸類

// Cascade Collectors 
Map<String, Map<String, List<Person>>> peopleByStateAndCity
= personStream.collect(Collectors.groupingBy(Person::getState,
Collectors.groupingBy(Person::getCity)))

更深入的聚合操作和lambda表示式請看聚合操作章節。

Map介面的基本操作

Map的基本操作包括put,get,containsKey,containsValue,size和isEmpty，它的表現和Hashtable的一模一樣。下面的程式碼統計入參出現的頻率：

public class Freq {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<String, Integer>();
// Initialize frequency table from command line
for (String a : args) {
Integer freq = m.get(a);
m.put(a, (freq == null) ? 1 : freq   1);
}
System.out.println(m.size()   " distinct words:");
System.out.println(m);
}
}

用到的詭計就是本程式中put語句的第二個引數。如果key存在，則為1，否則個數增加1。

//輸入引數
if it is to be it is up to me to delegate
//輸出
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

如果想輸出的順序是按照字母表來的，那麼輸出如下：

8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

如果想要讓輸出保持輸入的順序，那麼

8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

和Set、List一樣，equals和hashCode方法也是必須的，這樣Map才能任意型別情況下判斷兩個map例項是否相等。假如兩個map例項的key和value對映一模一樣，則這兩個map例項邏輯相等。

一個栗子，k,v是Map的實現型別，而m是一個和Map

Map<K, V> copy = new HashMap<K, V>(m);

Map介面的批量操作

//清空Map
clear
//dumping one Map into another
putAll
//如果入參為空則使用預設值，否則使用入參覆蓋預設值
static <K, V> Map<K, V> newAttributeMap(Map<K, V>defaults, Map<K, V> overrides) {
Map<K, V> result = new HashMap<K, V>(defaults);
result.putAll(overrides);
return result;
}

集合檢視Collection views

集合檢視即是可以使Map用Collection方式來展示：

• keySet—Map內key的集合。
• values—Map內value的Collection,不是set，因為value可能有重複值。
• entrySet—Map內key-value對的集合，Map內嵌入一個Map.Entry的介面。

集合檢視的唯一目的是迭代Map：

//遍歷key
for (KeyType key : m.keySet())
System.out.println(key);
// Filter a map based on some 
// property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();
for (Map.Entry<KeyType, ValType> e : m.entrySet())
System.out.println(e.getKey()   ": "   e.getValue());

有些人擔心，每次返回Map的集合檢視都會例項化一個Collection，這大可放心，Map集合檢視是單例項的。

有了這3個集合檢視，那麼在迭代的時候就可以進行移除操作。

有了entrySet檢視，就可以通過Map.Entry的setValue進行修改值的操作。

collection檢視提供幾種移除元素的方法—remove,removeAll,retainAll和clear操作，此外還有Iterator.remove。

使用集合檢視的原因：Map Algebra(代數)

第一個Map集合是否是否包含第二個Map集合

if (m1.entrySet().containsAll(m2.entrySet())) {
...
}

兩個Map集合內的key集合是否相等

if (m1.keySet().equals(m2.keySet())) {
...
}

驗證一個Map集合內的Key集合是否包含必填屬性，並不包含非法屬性

static <K, V> boolean validate(Map<K, V> attrMap, Set<K> requiredAttrs, Set<K>permittedAttrs) {
boolean valid = true;
Set<K> attrs = attrMap.keySet();
if (! attrs.containsAll(requiredAttrs)) {
Set<K> missing = new HashSet<K>(requiredAttrs);
missing.removeAll(attrs);
System.out.println("Missing attributes: "   missing);
valid = false;
}
if (! permittedAttrs.containsAll(attrs)) {
Set<K> illegal = new HashSet<K>(attrs);
illegal.removeAll(permittedAttrs);
System.out.println("Illegal attributes: "   illegal);
valid = false;
}
return valid;
}

共有key集合

Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
commonKeys.retainAll(m2.keySet());

同理

//差集
m1.entrySet().removeAll(m2.entrySet());
m1.keySet().removeAll(m2.keySet());

多重對映Multimaps

一個key對應多個value，如Map<String, List<String>> m = new HashMap<String, List<String>>();

物件排序(Object Ordering)

一個列表可以通過以下方式進行排序：

Collections.sort(l)

如果List由String元素構成，那麼它將按照字母順序進行排序。如果構成元素是Date,那麼它將以時間順序進行排序。String,Date都實現了Comparable介面。Comparable的實現類提供了自然排序的方法。下列表格列舉了常見的實現了Comparable的介面。

實現了Comparable的類：

如果你嘗試排序一個沒有實現Comparable介面的類的例項集合，那麼會報錯，而不管你是使用Collections.sort(list) 還是使用Collections.sort(list) 。一個元素可以和另一個元素比較被稱為相互可比(mutually comparable)，雖然不同種類的元素可以進行相互比較，但是上表所列舉的都禁止進行組間比較。

定製化物件排序

詳情請點選我

值得借鑑的地方就是對比的地方，如下所示：

 //三目運算子比較簡潔，雖然看起來比較費勁
public int compareTo(Name n) {
int lastCmp = lastName.compareTo(n.lastName);
return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
}
//先對比是否相等，在對比大小 三目運算子是從左到右執行
public static int compare(long x, long y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

SortedSet介面

SortedSet是一個維護其內元素升序排序的集合(Set)。排序的方式是依據元素的自然排序(即實現Comparable介面)或者呼叫SortedSet建構函式時所傳入的入參Comparator。除了普通的Set操作，SortedSet還提供了以下操作：

1. 範圍檢視。允許在SortedSet上執行任意範圍的操作。
2. 端點。返回SortedSet首元素或者尾元素。
3. 獲取比較器Comparator。如果有的話就返回。

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

SortedMap介面

同理SortedMap介面有如下方法：

public interface SortedMap<K, V> extends Map<K, V>{
Comparator<? super K> comparator();
SortedMap<K, V> subMap(K fromKey, K toKey);
SortedMap<K, V> headMap(K toKey);
SortedMap<K, V> tailMap(K fromKey);
K firstKey();
K lastKey();
}

介面的總結

Collection的核心是Java集合框架的核心。

Java集合框架層次結構由兩部分不同的介面樹構成：

• 第一顆樹以Collection為起頭，為所有繼承或實現Collection提供了基本的操作，如add和remove。它的子介面有Set,List,Queue。
• Set介面不允許有重複元素。子介面SortedSet為其內元素排好序。
• List介面提供插入有序的集合，當你需要精確控制每一個元素是使用它。你可以從指定位置檢索List內的元素。
• Queue介面是FIFO，提供了額外的插入、提取和檢查操作。
• Deque可支援FIFO，LIFO。可以在雙端進行插入、提取和檢查操作。
• 第二顆樹以Map介面起頭，和HashTable類似，將key對映到value。
• Map的子介面SortedMap通過Comparator介面維持一個k-v升序的順序。

聚合操作(Aggregate Operations)

請移步lambda表示式教程。