1.集合類庫
通常，程序總是根據(jù)運行時才知道的某些條件去創(chuàng)建新對象，在此之前，不會知道所需對象的數(shù)量，甚至不知道確切的類型。為了解決這個普遍的編程問題，需要在任意時刻和任意位置創(chuàng)建任意數(shù)量的對象。java實用類庫提供了一套相當完整的集合類來解決這個問題 。其中基本類型是List、Set、Queue和Map，這些對象被稱為集合類。
這里給出一個經(jīng)常引用的一個類庫關系圖：
集合的繼承類關系圖
從圖中可以看出，Java集合分為Collection和Map兩大種。下面就兩大類型進行分別說明：
2. Collection
查看jdk源碼看到Collection接口定義了集合分支的基礎方法，有查詢方法，修改集合方法，批量操作方法和比較與hash方法，這些都是集合的基礎方法。其繼承接口可以分為以下幾類：
List:有序集合，值允許有重復
Set:無需集合，值不允許有重復
Queue:保持先進先出順序
2.1 List集合: ArrayList&LinkedList
ArrayList底層通過數(shù)組實現(xiàn)，數(shù)組因為可以通過下標訪問成為一個隨機訪問第n個數(shù)效率很高的數(shù)據(jù)結構，隨機訪問查詢的時間復雜度是O(1)，而刪除/增加新的元素到某個位置時，需要一個一個的移動數(shù)組中的元素直至適合的位置，所以時間復雜度是O(n)；
LinkedList底層由雙向鏈表實現(xiàn)，在鏈表中插入元素時，只需要改變插入位置前后結點的結點指向和添加新元素的結點指向即可，時間復雜度是O(1)，在訪問元素的時候，無論是隨機方位第幾位的元素還是查詢某個定值時，鏈表的時間復雜度均為O(n)。
所以，ArrayList適用于隨機訪問的場景，而LinkedList則適用于頻繁隨機位置刪除和插入的場景。
如果你想學習Java可以來這個群，首先是二二零，中間是一四二，最后是九零六，里面有大量的學習資料可以下載。
2.2 Set集合: HashSet&TreeSet
HashSet：封裝了一個 HashMap對象來存儲所有的集合元素，所有放入 HashSet中的集合元素實際上由 HashMap的 key來保存，而 HashMap的 value則存儲了一個 PRESENT，它是一個靜態(tài)的 Object對象。 HashSet的絕大部分方法都是通過調用 HashMap的方法來實現(xiàn)的，具體原理在HashMap分析。
TreeSet：TreeSet是基于TreeMap實現(xiàn)的。TreeSet中的元素支持2種排序方式：自然排序或者根據(jù)創(chuàng)建TreeSet時提供的 Comparator進行排序。這取決于使用的構造方法，具體原理在TreeMap分析。
2.3 Queue: PriorityQueue
優(yōu)先級隊列，元素可以按照任意的順序插入，但總是按照排序的順序進行檢索，內部實現(xiàn)的數(shù)據(jù)結構是堆。堆是一個可以自我調整的二叉樹，對樹執(zhí)行添加和刪除的時候，可以讓最小的元素移動到根，而不用花費時間對元素進行排序。使用的典型實例是任務調度場景。
3. Map
表示鍵值對，鍵必須是唯一的，不能對同一個鍵存放兩個值。
3.1 HashMap
HashMap底層實現(xiàn)上是一個“鏈表散列”的數(shù)據(jù)結構，即數(shù)組和鏈表的結合體。具體如下圖所示：
鏈表散列
從上圖我們可以看出HashMap底層實現(xiàn)還是數(shù)組，只是數(shù)組的每一項都是一條鏈。其中數(shù)組和鏈表在jdk源碼中體現(xiàn)：
/**The table, resized as necessary.
3.1.1如何插入一個值
HashMap插入一個值包括以下幾個步驟：
調用hash計算key的hash值
根據(jù)hash值推算出放在數(shù)組的位置
找到具體數(shù)組某個位置，遍歷該位置的Entry鏈表，比較key值如果相等則直接替換value，如果不同則插入鏈表的尾部。
可以看出，如果hashCode和hash足夠好，盡可能的減少沖突，那么對HashMap的訪問等價于對數(shù)組的隨機方位，如果不夠好有大量沖突存在，則退化為對鏈表的隨機方位。
3.1.2再散列rehash
當哈希表的容量超過默認容量時，必須調整table的大小。當容量已經(jīng)達到最大可能值時，那么該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要創(chuàng)建一張新表，將原表的映射到新表中。
rehash
3.1.3容量參數(shù)
可以看出整個再散列過程是比較耗時的，需要將所有老數(shù)據(jù)重新計算后放到新的散列表中。HashMap維護一個threshold變量，它始終被定義為當前數(shù)組總容量和負載因子的乘積，他表示的是HashMap的閾值，當超過該值，HashMap便會擴容。
關于負載因子定義首先看一下HashMap的constructor如下：
public HashMap(int initalCapacity);
其中initalCapacity表示初始化容量，loadFactor表示負載因子一般是介于0和1之間，它決定了HashMap擴容之前，其內部數(shù)組的填充度。默認情況下，初始量為16，負載因子為0.75。
負載因子 =元素個數(shù)/內部數(shù)組總大小
可以看出如果負載因子大于1，一定會存在沖突，元素個數(shù)大于數(shù)組的容量。
3.1.4如何取一個值
查看jdk源碼可以看出從HashMap中獲取一個值分為兩種情況當key為null的時候單獨處理，非null的時候一套處理邏輯。這里也提醒我們HashMap可以存放key為null的鍵值對。
獲取值get
查看獲取非null的key的值的具體實現(xiàn)
查找key對應Entry對象
分析查找一個非null的鍵流程：
調用hash計算key的hash值
根據(jù)hash值推算出放在數(shù)組的位置
遍歷對應位置上的鏈表找到key相同的Entry對象返回即可，找不到則返回為null
3.2 TreeMap
HashMap和LinkedHashMap底層存儲容器都是選擇了數(shù)組，內容為內部類Entry。但是TreeMap底層通過一顆紅黑樹來維護，初始化的時候有個root根節(jié)點，同時TreeMap不允許key為null。TreeMap本質上就是一棵“紅黑樹”，而 TreeMap的每個 Entry就是該紅黑樹的一個節(jié)點。
3.2.1紅黑樹
排序二叉樹要么是一棵空二叉樹，要么是具有下列性質的二叉樹：
若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
它的左、右子樹也分別為排序二叉樹。
排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節(jié)點集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹將變成鏈表。
紅黑樹在原有的排序二叉樹增加了如下幾個要求：
性質 1：每個節(jié)點要么是紅色，要么是黑色。
性質 2：根節(jié)點永遠是黑色的。
性質 3：所有的葉節(jié)點都是空節(jié)點（即 null），并且是黑色的。
性質 4：每個紅色節(jié)點的兩個子節(jié)點都是黑色。（從每個葉子到根的路徑上不會有兩個連續(xù)的紅色節(jié)點）
性質 5：從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。
上面的性質 3中指定紅黑樹的每個葉子節(jié)點都是空節(jié)點，而且并葉子節(jié)點都是黑色。但 Java實現(xiàn)的紅黑樹將使用 null來代表空節(jié)點，因此遍歷紅黑樹時將看不到黑色的葉子節(jié)點，反而看到每個葉子節(jié)點都是紅色的。
4. 迭代器（Iterator）
迭代器是一種設計模式，在java里它是一個對象，可以遍歷并選擇序列中的對象，而開發(fā)人員不需要了解該序列的底層結構。迭代器通常被稱為“輕量級”對象，因為創(chuàng)建它的代價小。迭代器接口Iterable是Collection類的父接口。它只有一個方法: iterator，方法返回一個代表當前集合對象的泛型<T>迭代器，用于之后的遍歷操作。所有的Collection集合對象都實現(xiàn)這個Iterable接口，允許使用foreach進行遍歷。
常用Iterator遍歷方式
List<Integer> lstint = new ArrayList<Integer>;// Iterator遍歷一Iterator<Integer> iterator = lstint.iterator;while (iterator.hasNext){
5. Fail-Fast機制
前面敘述的集合類均不是線程安全的，所以java集合(Collection)規(guī)定在使用迭代器的過程中有其他線程修改了同一個集合類，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。
注意點：迭代器的快速失敗行為無法得到保證，迭代器的快速失敗行為應該僅用于檢測 bug。
例如：當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內容同時被其他線程所改變了；那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。
5.1實現(xiàn)原理
這里以HashMap為例進行說明，其他集合類實現(xiàn)類似，這一策略在源碼中的實現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內容的修改都將增加這個值，具體定義如下：
modCount定義
HashMap在put函數(shù)添加元素時修改此值代碼如下：
put新增值修改modCount
在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount，在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map，將會拋出ConcurrentModificationException異常，具體代碼如下：
遍歷判斷
5.2遍歷刪除指定元素
在實際應用中，我們常會遇到一種需求是從集合中刪除符合某個特定條件的元素，對比下面幾種寫法：
/**
改寫法如注釋中描述由于remove操作導致modCount發(fā)生變化，繼續(xù)遍歷就會觸發(fā)Fail-Fast機制。這種寫法如果確定只刪除其中一個，此時break掉程序不會拋異常。
/**
該種寫法通過遍歷數(shù)組的形式，在刪除過程中導致數(shù)組元素減少位置發(fā)生變化影響了最后的結果。
/**
推薦寫法使用Iterator遍歷并使用迭代器對應的remove方法刪除。該刪除方法會同步size大小以及修改expectCount。
6.總結
簡單總結上述各種類使用和實現(xiàn)特點，如下表所示：
學習Java的同學注意了?。。?/p>
學習過程中遇到什么問題或者想獲取學習資源的話，歡迎加入Java學習交流群，群號碼：415839104我們一起學Java！
