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

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

Map

TreeMap

HashMap

LinkedHashMap

Collection

Set

HashSet

TreeSet

LinkedHashSet

List

ArrayList

LinkedList

Queue

PriorityQueue

Deque

ArrayDeque

LinkedList

集合中常用的四個接口：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() 方法返回的元素，但是不可以連續使用 remove() 方法。因為 Iterator 對象中有一個成員變量 current 保存 next() 方法的返回值，當調用 remove() 刪除元素后，current 會被置為 null。所以不能連續調用 remove()。

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

public interface Collection extends Iterable {
    int size();
    boolean isEmpty();
    boolean contains(Object o);  //o 是Entry<>對象
    Iterator iterator();
    Object[] toArray();
     T[] toArray(T[] a);
    boolean add(E e);    //當對象存在時，不添加，返回false
    boolean remove(Object o);   //o 是Entry<>對象
    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()之外的其他方法提供了默認實現。

方法見 Collection 方法

HashSet

HashSet 中的元素可以是 null 。

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

先調用元素的 hashCode()，計算出元素所在的槽號。

然后在對應槽與鏈表中的每個結點使用 equals() 方法進行比較，判斷是否相等。由于無須判斷大小關系。所以不會使用到 Comparable/Comparator 接口。

此外，HashCode 中的 contains(Object),remove(Object) 和 Iterator 中的 remove() 方法都是按照上述方法再對應槽中進行處理。不會遍歷整個集合。

TreeSet

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

Comparator comparator() ：如果 TreeSet采用了定制排序，則該方法返回定制排序所用的 Comparator；如果采用自然排序，則返回 null。
Object first()：返回集合中的第一個元素。
Object last()：返回集合中的最后一個元素。
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 采用紅黑樹的數據結構來存儲集合元素。在對集合進行遍歷時，每個值將按照排序后的順序呈現。TreeSet 支持兩種排序方法：自然排序和定制排序。默認情況下，TreeSet 采用自然排序。如果需要定制排序，需要在創建 TreeSet 對象時，添加 Comparator 對象作為參數。

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

List 集合代表一個元素有序、可重復的集合，集合中每個元素都有其對應的順序索引。List 集合默認按元素添加順序設置元素的索引。因此List集合里增加了一些根據索引來操作集合元素的方法。

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)：返回對象在 List 集合中第一次出現的位置索引。
int lastIndexOf(Object o)：返回對象在List 集合中最后一次出現的位置索引。
Object remove(int index)：刪除并返回 index 索引處的元素。
Object set(int index , Object element)：將 index 處的元素替換成 element對象，返回被替換的就元素。
List subList(int fromIndex,int toIndex)：返回從索引 fromIndex（包含）到索引toIndex（不包含）處所有集合元素組成的子集合。
void sort(Comparator c)：根據 Comparator 對 List 集合的元素排序。

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

ListIterator 接口

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

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

iteraotr 中有一個成員 cur 下標，記錄遍歷的當前位置，

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

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

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

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

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

PriorityQueue 內部數據結構是最小堆。PriorityQueue 不允許插入 null 元素，PriorityQueue 的元素有兩種排序方式：自然排序和定制排序。

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

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

實現Deque 接口的類都可以用來作為棧使用，但是實現棧的棧頂是在隊列的頭部。

ArrayDeque 實現類

Deque 接口提供了一個典型的實現類： ArrayDeque，它是一個基于數組實現的雙端隊列，創建 Deque 時同樣可指定一個 numElements參數，該參數用于指定 Object[] 數組的長度；如果不指定 numElements 參數，Deque 底層數組的長度為16；

LinkdeList 實現類

LinkdeList 類是 List 接口的實現類 --- 這意味著它是一個 List 集合。除此之外，LinkdeList 還實現了Deque接口，可以被當成雙端隊列來使用，因此既可以作為棧來使用，也可以作為隊列使用。

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

如果把 Map 里的所有 value 放在一起來看，他們構成一個 Collection：元素可以重復，每個元素可以根據索引來查找，只是 Map 中的索引不再是下標，而是對應的key。

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

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

Map 接口中包括一個內部接口 Entry，該接口封裝了一個鍵值對。Entry 包含如下三個方法：

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

為了成功地在 HashMap 中存儲元素，用作key 的對象必須實現 hashCode() 方法 和 equals() 方法。

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

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

Map 視圖(view)

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

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

輕量級集合包裝器

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

操作集合的工具類：Collections

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

排序操作

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

void reverse(List list)：反轉指定 List集合中元素的排序。
void shuffle(List list)：對List 集合元素進行隨機排序。
void sort(List list)：根據元素的自然順序對指定List集合的元素按升序進行排序。
void sort(List list, Comparator c)：根據指定Comparator 產生的順序對List集合元素進行排序。
void swap(List list, int i,int j)：將指定List 集合中的 i處元素和 j處元素進行交換。
void rotate(List list, int distance)：當 distance 為正數時，將 list 集合的后 distance個元素“整體”移到前面；當 distance為負數時，將 list集合的前 distance 個元素“整體”移到后面。

查找、替換操作

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

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

同步控制

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

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

在上述程序中，直接將新創建的集合對象傳給 Collections 的 synchronizedXxx 方法，這樣就可以 直接獲取 Set、List、Map 的線程安全實現版本。