摘要：當(dāng)使用迭代器訪問集合元素時(shí)，中的元素不能被改變，只能通過的方法刪除上一次方法返回的集合元素才可以否則將會(huì)引發(fā)異常。可以確保集合元素處于有序狀態(tài)。返回中所有鍵值對(duì)組成的視圖，每個(gè)集合元素都是是的內(nèi)部類對(duì)象。這種集合稱為視圖。

集合包括兩大接口：Collection 和 Map。

Map

TreeMap

HashMap

LinkedHashMap

Collection

Set

HashSet

TreeSet

LinkedHashSet

List

ArrayList

LinkedList

Queue

PriorityQueue

Deque

ArrayDeque

LinkedList

集合中常用的四個(gè)接口：Comparable, Comparator, Iterable, Iterator。

interface Comparable{
    public int compareTo(E obj);
}
interface Comparator{
    public int compare(E obj1, E obj2);
    boolean equals(Object obj);
}
interface Iterable{
    Iterator iterator(){};
}
interface Iterator{
    public boolean hasNext(){};
    public E next(){};
    public void remove(){};
}

remove() 方法可以刪除 next() 方法返回的元素，但是不可以連續(xù)使用 remove() 方法。因?yàn)?Iterator 對(duì)象中有一個(gè)成員變量 current 保存 next() 方法的返回值，當(dāng)調(diào)用 remove() 刪除元素后，current 會(huì)被置為 null。所以不能連續(xù)調(diào)用 remove()。

當(dāng)使用 Iterator 迭代器訪問 Collection 集合元素時(shí)，Collection 中的元素不能被改變，只能通過 Iterator 的 remove 方法刪除上一次 next 方法返回的集合元素才可以；否則將會(huì)引發(fā)異常。
Iterator 采用了快速失敗（fast-fail）機(jī)制，一旦在迭代過程中檢測(cè)到該集合已經(jīng)被修改（增加或刪除元素），程序立即引發(fā) ConcurrentModifactionException 異常，而不是顯示修改后的結(jié)果，這樣可以避免共享資源而引發(fā)的潛在問題。
Collection 接口中定義的方法：也是 Set 的方法

public interface Collection extends Iterable {
    int size();
    boolean isEmpty();
    boolean contains(Object o);  //o 是Entry<>對(duì)象
    Iterator iterator();
    Object[] toArray();
     T[] toArray(T[] a);
    boolean add(E e);    //當(dāng)對(duì)象存在時(shí)，不添加，返回false
    boolean remove(Object o);   //o 是Entry<>對(duì)象
    boolean containsAll(Collection c);
    boolean addAll(Collection c);
    boolean removeAll(Collection c);
    default boolean removeIf(Predicate filter){
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    boolean retainAll(Collection c);
    void clear();
    boolean equals(Object o);
    int hashCode();  
}

AbstractCollection抽象類，它為除 size()和iterator()之外的其他方法提供了默認(rèn)實(shí)現(xiàn)。

方法見 Collection 方法

HashSet

HashSet 中的元素可以是 null 。

HashSet 集合插入和刪除元素的過程是：

先調(diào)用元素的 hashCode()，計(jì)算出元素所在的槽號(hào)。

然后在對(duì)應(yīng)槽與鏈表中的每個(gè)結(jié)點(diǎn)使用 equals() 方法進(jìn)行比較，判斷是否相等。由于無須判斷大小關(guān)系。所以不會(huì)使用到 Comparable/Comparator 接口。

此外，HashCode 中的 contains(Object),remove(Object) 和 Iterator 中的 remove() 方法都是按照上述方法再對(duì)應(yīng)槽中進(jìn)行處理。不會(huì)遍歷整個(gè)集合。

TreeSet

TreeSet可以確保集合元素處于有序狀態(tài)。與 HashSet集合相比，TreeSet還提供了如下幾個(gè)額外的方法：

Comparator comparator() ：如果 TreeSet采用了定制排序，則該方法返回定制排序所用的 Comparator；如果采用自然排序，則返回 null。
Object first()：返回集合中的第一個(gè)元素。
Object last()：返回集合中的最后一個(gè)元素。
Object lower(Object e)：返回集合中小于指定元素的最大元素，參考元素不需要是 TreeSet集合里的元素。
Object higher(Object e)：返回集合中大于指定元素的最小元素，參考元素不需要是TreeSet集合里的元素。
Sorted subSet(Object fromElement, Object toElement)：返回此 TreeSet 的子集合，范圍從 fromElement（包含）到toElement（不包含）。
Sorted headSet(Object toElement)：返回此TreeSet中小于toElement 的元素組成的子集。
Sorted tailSet(Object fromElement)：返回此TreeSet中由大于或等于 fromElement 的元素組成的子集。

TreeSet 采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)集合元素。在對(duì)集合進(jìn)行遍歷時(shí)，每個(gè)值將按照排序后的順序呈現(xiàn)。TreeSet 支持兩種排序方法：自然排序和定制排序。默認(rèn)情況下，TreeSet 采用自然排序。如果需要定制排序，需要在創(chuàng)建 TreeSet 對(duì)象時(shí)，添加 Comparator 對(duì)象作為參數(shù)。

TreeSet 使用 Comparable/Comparator 來比較元素的大小，以及判斷元素是否相等。TreeSet 中元素不可以為 null，因?yàn)?null 無法比較大小。

List 集合代表一個(gè)元素有序、可重復(fù)的集合，集合中每個(gè)元素都有其對(duì)應(yīng)的順序索引。List 集合默認(rèn)按元素添加順序設(shè)置元素的索引。因此List集合里增加了一些根據(jù)索引來操作集合元素的方法。

void add(int index, Object element)：將元素 element 插入 List 集合的 index 處。
boolean addAll(int index, Collection c)：將集合 c 所包含的所有元素都插入到 List 集合的 index 處。
Object get(int index)：返回集合 index 索引處的元素。
int indexOf(Object o)：返回對(duì)象在 List 集合中第一次出現(xiàn)的位置索引。
int lastIndexOf(Object o)：返回對(duì)象在List 集合中最后一次出現(xiàn)的位置索引。
Object remove(int index)：刪除并返回 index 索引處的元素。
Object set(int index , Object element)：將 index 處的元素替換成 element對(duì)象，返回被替換的就元素。
List subList(int fromIndex,int toIndex)：返回從索引 fromIndex（包含）到索引toIndex（不包含）處所有集合元素組成的子集合。
void sort(Comparator c)：根據(jù) Comparator 對(duì) List 集合的元素排序。

List 不考慮元素的大小關(guān)系，所以通過元素的 equals 方法判斷元素是否相等，僅在查找元素時(shí)使用。

ListIterator 接口

List 額外提供了一個(gè) listIterator() 方法，該方法返回一個(gè) ListIterator 對(duì)象，ListIterator 接口是 Iterator 的子接口，提供了專門操作 List 的方法。ListIterator接口在Iterator 接口基礎(chǔ)上增加了如下方法：

boolean hasPrevious()：返回該迭代器關(guān)聯(lián)的集合是否還有上一個(gè)元素。
Object previous()：返回該迭代器的上一個(gè)元素。
void add(Object o)
void set(Object o)：用一個(gè)新元素取代調(diào)用 next() 或previous() 返回的上一個(gè)元素。
int nextIndex()：返回next域所指元素的索引
int previousIndex()：返回下一次調(diào)用previous 方法時(shí)返回元素的索引，即next域索引- 1

iteraotr 中有一個(gè)成員 cur 下標(biāo)，記錄遍歷的當(dāng)前位置，

調(diào)用 next()，會(huì)返回 cur 位置處的元素，并將 cur = cur + 1 or cur = cur.next。

調(diào)用 prevoius()，會(huì)返回 cur - 1 or cur.previous 處的元素，并將 cur = cur - 1 or cur = cur.previous。

調(diào)用 add()，對(duì)于 arrayList 而言，會(huì)將元素插入 cur 位置處，后面的元素后移一位，且 cur = cur + 1。對(duì)于 LinkedList 而言，會(huì)將元素插入 cur.previous 處。即會(huì)插在 next() 元素的前面， previous() 元素的后面。

新元素插入(offer)到隊(duì)列的尾部，訪問元素(poll)會(huì)返回隊(duì)列頭部的元素。通常，隊(duì)列不允許隨機(jī)訪問隊(duì)列中的元素。Queue 接口中定義了如下幾個(gè)方法：

void add(Object e)：將指定元素加入此隊(duì)列的尾部。如果隊(duì)列滿，則拋出異常。
Object remove()：獲取隊(duì)列頭部的元素，并刪除該元素。如果隊(duì)列為空，則拋出異常。
Object element()：獲取隊(duì)列頭部的元素，但是不刪除該元素。如果隊(duì)列為空，則拋出異常。
boolean offer(Object e)：將指定元素加入此隊(duì)列的尾部，如果隊(duì)列滿，返回false。
Object poll()：獲取隊(duì)列頭部的元素，并刪除該元素，如果隊(duì)列為空，則返回null。
Object peek()：獲取隊(duì)列頭部的元素，但是不刪除該元素。如果隊(duì)列為空，則返回null。

PriorityQueue 內(nèi)部數(shù)據(jù)結(jié)構(gòu)是最小堆。PriorityQueue 不允許插入 null 元素，PriorityQueue 的元素有兩種排序方式：自然排序和定制排序。

Deque 接口里定義了一些雙端隊(duì)列的方法，這些方法允許從兩端來操作隊(duì)列的元素。

Object getFirst()：獲取但不刪除雙端隊(duì)列的第一個(gè)元素。
Object getLast()：獲取但不刪除雙端隊(duì)列的最后一個(gè)元素。
Object removeFirst()：獲取并刪除雙端隊(duì)列的第一個(gè)元素。
Object removeLast()：獲取并刪除雙端隊(duì)列的最后一個(gè)元素。
boolean offerFirst(Object e)：將指定元素插入該雙端隊(duì)列的開頭。
boolean offerLast(Object e)：將指定元素插入該雙端隊(duì)列的末尾。
void addFirst(Object e)：將指定元素插入該雙端隊(duì)列的開頭。
void addLast(Object e)：將指定元素插入該雙端隊(duì)列的尾部。
Object removeFirstOccurrence(Object o)：獲取并刪除雙端隊(duì)列的第一次出現(xiàn)的元素o。
Object removeLastOccurrence(Object o)：獲取并刪除雙端隊(duì)列的最后一次出現(xiàn)的元素o。
Object pollFirst()：獲取并刪除雙端隊(duì)列頭部的元素。如果隊(duì)列為空，則返回null；
Object pollLast()：獲取并刪除雙端隊(duì)列尾部的元素。如果隊(duì)列為空，則返回null；
Object peekFirst()：獲取隊(duì)列頭部的元素，但是不刪除該元素。如果隊(duì)列為空，則返回null；
Object peekLast()：獲取隊(duì)列尾部的元素，但是不刪除該元素。如果隊(duì)列為空，則返回null；
Object pop()（棧方法）：pop出該雙端隊(duì)列所表示的棧的棧頂元素。相當(dāng)于 removeFirst()。
void push(Object e)（棧方法）：將一個(gè)元素 push 進(jìn)該雙端隊(duì)列所表示的棧的棧頂。相當(dāng)于 addFirst(e)；
Iterator descendingIterator()：返回該雙端隊(duì)列對(duì)應(yīng)的迭代器，該迭代器將以逆向順序來迭代隊(duì)列中的元素。

實(shí)現(xiàn)Deque 接口的類都可以用來作為棧使用，但是實(shí)現(xiàn)棧的棧頂是在隊(duì)列的頭部。

ArrayDeque 實(shí)現(xiàn)類

Deque 接口提供了一個(gè)典型的實(shí)現(xiàn)類： ArrayDeque，它是一個(gè)基于數(shù)組實(shí)現(xiàn)的雙端隊(duì)列，創(chuàng)建 Deque 時(shí)同樣可指定一個(gè) numElements參數(shù)，該參數(shù)用于指定 Object[] 數(shù)組的長(zhǎng)度；如果不指定 numElements 參數(shù)，Deque 底層數(shù)組的長(zhǎng)度為16；

LinkdeList 實(shí)現(xiàn)類

LinkdeList 類是 List 接口的實(shí)現(xiàn)類 --- 這意味著它是一個(gè) List 集合。除此之外，LinkdeList 還實(shí)現(xiàn)了Deque接口，可以被當(dāng)成雙端隊(duì)列來使用，因此既可以作為棧來使用，也可以作為隊(duì)列使用。

如果把 Map 里的所有 key放在一起，他們組成了一個(gè)keySet集合（所有的 key沒有順序，key與 key 之間不能重復(fù)）。

如果把 Map 里的所有 value 放在一起來看，他們構(gòu)成一個(gè) Collection：元素可以重復(fù)，每個(gè)元素可以根據(jù)索引來查找，只是 Map 中的索引不再是下標(biāo)，而是對(duì)應(yīng)的key。

Map 接口中定義的常用方法有：

int size()：返回該Map里的鍵值對(duì)的個(gè)數(shù)。
void clear()：刪除該 Map 對(duì)象中的所有 key-value對(duì)。
boolean isEmpty()：查詢?cè)揗ap 是否為空，如果為空，則返回true；
boolean containsKey(Object key)：查詢 Map 中是否包含指定的 key，如果包含則返回true。
boolean containsValue(Object value)：查詢 Map 中是否包含一個(gè)或多個(gè) value,如果包含則返回 true。
V get(Object key)：返回指定key 所對(duì)應(yīng)的 value；如果此 Map 中不包含該 key，則返回null。
default V getOrDefault(Object key, V defaultValue)：獲取與key對(duì)應(yīng)的value，若key不存在，則返回defaultValue
V put(K key,V value)：添加一個(gè)鍵值對(duì)，如果當(dāng)前 Map 中已有一個(gè)相同的key，則用新的鍵值對(duì)覆蓋原來的鍵值對(duì)，并返回原來的value。
void putAll(Map<？ extends K,? extends V> m)：將指定Map中的所有鍵值對(duì)復(fù)制到本Map中。
Object remove(Object key)：刪除指定key對(duì)應(yīng)的鍵值對(duì)，返回被刪除key關(guān)鍵的value，如果該key不存在，則返回null；
Set keySet()：返回該Map 中所有 key 組成的Set視圖。可以從集中刪除元素，Map中對(duì)應(yīng)的鍵值對(duì)會(huì)被刪除，但不能添加元素
Collection values()：返回該Map里所有value組成的Collection視圖。可以從集合中刪除元素（只會(huì)刪除一個(gè)鍵值對(duì)），所刪除的值及對(duì)應(yīng)的鍵將從Map中刪除，不能增加元素。
Set> entrySet()：返回 Map中所有鍵值對(duì)組成的Set視圖，每個(gè)集合元素都是 Map.Entry（Entry 是 Map 的內(nèi)部類）對(duì)象。可以從集中刪除元素，它們將從映射中刪除元素，但不能增加任何元素。

Map 接口中包括一個(gè)內(nèi)部接口 Entry，該接口封裝了一個(gè)鍵值對(duì)。Entry 包含如下三個(gè)方法：

Object getKey()：返回該Entry里包含的value值。
Object getVlaue()：返回該Entry里包含的value值。
Object setValue(V value)：設(shè)置該Entry里包含的value值，并返回新設(shè)置的alue值

為了成功地在 HashMap 中存儲(chǔ)元素，用作key 的對(duì)象必須實(shí)現(xiàn) hashCode() 方法 和 equals() 方法。

判斷value相等的方法是：使用value的equals()方法返回值來判斷。

綜上可以，不考慮元素大小序的集合(HashSet,ArrayList,LinkedList,ArrayDeque,HashMap)都是通過 equals() 判斷元素是否相等，且允許元素為 null。考慮元素大小關(guān)系的集合(TreeSet，PriorityQueue，TreeMap) 都是通過 compareTo/compare() 來判斷相等。

Map 視圖(view)

Map 有三種視圖：keySet、values、entrySet。需要說明的是：keySet 方法返回了一個(gè)實(shí)現(xiàn)類 Set 接口的類對(duì)象，而不是 HashSet 或 TreeSet，這個(gè)類的方法對(duì)原 map進(jìn)行操作。這種集合稱為視圖。values返回值是 Collection 接口的實(shí)現(xiàn)對(duì)象、entrySet 返回的是一個(gè)實(shí)現(xiàn) Set> 類型的對(duì)象。可以通過 keySet、values、entrySet 來遍歷 Map 的鍵、值、鍵值對(duì)。

如果在鍵集視圖上調(diào)用迭代器的 remove() 方法，實(shí)際上會(huì)從映射中刪除這個(gè)鍵對(duì)應(yīng)的鍵值對(duì)。不能向鍵集試圖增加元素，如果試圖調(diào)用 add()，會(huì)拋出異常。entrySet 有同樣的限制。

輕量級(jí)集合包裝器

Arrays 的靜態(tài)方法 asList(Object ... a) 將返回包裝了普通數(shù)組的 List 包裝器。這個(gè)方法可以將數(shù)組傳遞給一個(gè)期望得到列表或集合參數(shù)的方法。它是數(shù)組的視圖對(duì)象，類型為 List<>，帶有訪問底層數(shù)組的 get 和 set 方法。但是改變數(shù)組大小的所有方法（例如，與迭代器相關(guān)的 add 和 remove 方法）都會(huì)拋出異常。

操作集合的工具類：Collections

Java 提供了一個(gè)操作 Set、List 和 Map 等集合的工具類：Collections，該工具類里提供了大量方法對(duì)集合元素進(jìn)行排序、查詢和修改等操作，還提供了將集合對(duì)象設(shè)置為不可變、對(duì)集合對(duì)象實(shí)現(xiàn)同步控制等方法。

排序操作

Collections 提供了如下常用的類方法用于對(duì) List 集合元素進(jìn)行排序：

void reverse(List list)：反轉(zhuǎn)指定 List集合中元素的排序。
void shuffle(List list)：對(duì)List 集合元素進(jìn)行隨機(jī)排序。
void sort(List list)：根據(jù)元素的自然順序?qū)χ付↙ist集合的元素按升序進(jìn)行排序。
void sort(List list, Comparator c)：根據(jù)指定Comparator 產(chǎn)生的順序?qū)ist集合元素進(jìn)行排序。
void swap(List list, int i,int j)：將指定List 集合中的 i處元素和 j處元素進(jìn)行交換。
void rotate(List list, int distance)：當(dāng) distance 為正數(shù)時(shí)，將 list 集合的后 distance個(gè)元素“整體”移到前面；當(dāng) distance為負(fù)數(shù)時(shí)，將 list集合的前 distance 個(gè)元素“整體”移到后面。

查找、替換操作

Collections 還提供了如下常用的用于查找、替換集合元素的類方法。

int binarySearch(List list, Object key)：使用二分搜索大搜索指定的 List集合，以獲得指定對(duì)象在 List 集合中的索引。如果要使該方法可以正常工作，必須保證 List 中的元素已經(jīng)處于有序狀態(tài)。
Object max(Collection coll)：根源元素的自然順序，返回給定集合中的最大元素。
Object max(Collection coll ,Comparator comp)：根據(jù)Comparator 指定的順序，返回給定集合中的最大元素。
Object min(Collection coll)：根源元素的自然順序，返回給定集合中的最小元素。
Object min(Collection coll ,Comparator comp)：根據(jù)Comparator 指定的順序，返回給定集合中的最小元素。
void fill(List list， Object obj)：使用指定元素obj替換指定List集合中的所有元素。
int frequency(Collection c, Object o)：返回指定集合中指定元素的出現(xiàn)次數(shù)。
int indexOfSubList(List source, List target)：返回子 List對(duì)象在父 List對(duì)象中第一次出現(xiàn)的位置索引；如果父List中沒有出現(xiàn)這樣的子 List，則返回 -1；
int lastIndexOfSubList(List source, List target)：返回子 List對(duì)象在父 List對(duì)象中最后一次出現(xiàn)的位置索引；如果父List中沒有出現(xiàn)這樣的子 List，則返回 -1；
boolean replaceAll(List list, Object olbVal, Object newVal)：使用一個(gè)新值 newVal 替換 List對(duì)象的所有舊值 oldVal。

同步控制

Collections 類提供了多個(gè) synchromizedXxx()方法，該方法可以將指定集合包裝成線程同步的集合，從而可以解決多線程并發(fā)訪問集合時(shí)的線程安全問題。例如：

public class Test{
  public static void main(String[] args){
    Collection c = Collections.synchronizedCollection(new ArrayList());
    List list = Collections.synchronizedList(new ArrayList());
    Set s = Collections.synchronizedSet(new ArrayHashSet());
    Map m = Collections.synchronizedMap(new HashMap());    
  }
}

在上述程序中，直接將新創(chuàng)建的集合對(duì)象傳給 Collections 的 synchronizedXxx 方法，這樣就可以 直接獲取 Set、List、Map 的線程安全實(shí)現(xiàn)版本。