1.集合類庫

通常，程序總是根據(jù)運(yùn)行時(shí)才知道的某些條件去創(chuàng)建新對象，在此之前，不會(huì)知道所需對象的數(shù)量，甚至不知道確切的類型。為了解決這個(gè)普遍的編程問題，需要在任意時(shí)刻和任意位置創(chuàng)建任意數(shù)量的對象。java實(shí)用類庫提供了一套相當(dāng)完整的集合類來解決這個(gè)問題 。其中基本類型是List、Set、Queue和Map，這些對象被稱為集合類。

這里給出一個(gè)經(jīng)常引用的一個(gè)類庫關(guān)系圖：

集合的繼承類關(guān)系圖

從圖中可以看出，Java集合分為Collection和Map兩大種。下面就兩大類型進(jìn)行分別說明：

2. Collection

查看jdk源碼看到Collection接口定義了集合分支的基礎(chǔ)方法，有查詢方法，修改集合方法，批量操作方法和比較與hash方法，這些都是集合的基礎(chǔ)方法。其繼承接口可以分為以下幾類：

• List:有序集合，值允許有重復(fù)

• Set:無需集合，值不允許有重復(fù)

• Queue:保持先進(jìn)先出順序

2.1 List集合: ArrayList&LinkedList

ArrayList底層通過數(shù)組實(shí)現(xiàn)，數(shù)組因?yàn)榭梢酝ㄟ^下標(biāo)訪問成為一個(gè)隨機(jī)訪問第n個(gè)數(shù)效率很高的數(shù)據(jù)結(jié)構(gòu)，隨機(jī)訪問查詢的時(shí)間復(fù)雜度是O(1)，而刪除/增加新的元素到某個(gè)位置時(shí)，需要一個(gè)一個(gè)的移動(dòng)數(shù)組中的元素直至適合的位置，所以時(shí)間復(fù)雜度是O(n)；

LinkedList底層由雙向鏈表實(shí)現(xiàn)，在鏈表中插入元素時(shí)，只需要改變插入位置前后結(jié)點(diǎn)的結(jié)點(diǎn)指向和添加新元素的結(jié)點(diǎn)指向即可，時(shí)間復(fù)雜度是O(1)，在訪問元素的時(shí)候，無論是隨機(jī)方位第幾位的元素還是查詢某個(gè)定值時(shí)，鏈表的時(shí)間復(fù)雜度均為O(n)。

所以，ArrayList適用于隨機(jī)訪問的場景，而LinkedList則適用于頻繁隨機(jī)位置刪除和插入的場景。

如果你想學(xué)習(xí)Java可以來這個(gè)群，首先是二二零，中間是一四二，最后是九零六，里面有大量的學(xué)習(xí)資料可以下載。

2.2 Set集合: HashSet&TreeSet

HashSet：封裝了一個(gè) HashMap對象來存儲(chǔ)所有的集合元素，所有放入 HashSet中的集合元素實(shí)際上由 HashMap的 key來保存，而 HashMap的 value則存儲(chǔ)了一個(gè) PRESENT，它是一個(gè)靜態(tài)的 Object對象。 HashSet的絕大部分方法都是通過調(diào)用 HashMap的方法來實(shí)現(xiàn)的，具體原理在HashMap分析。

TreeSet：TreeSet是基于TreeMap實(shí)現(xiàn)的。TreeSet中的元素支持2種排序方式：自然排序或者根據(jù)創(chuàng)建TreeSet時(shí)提供的 Comparator進(jìn)行排序。這取決于使用的構(gòu)造方法，具體原理在TreeMap分析。

2.3 Queue: PriorityQueue

優(yōu)先級隊(duì)列，元素可以按照任意的順序插入，但總是按照排序的順序進(jìn)行檢索，內(nèi)部實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是堆。堆是一個(gè)可以自我調(diào)整的二叉樹，對樹執(zhí)行添加和刪除的時(shí)候，可以讓最小的元素移動(dòng)到根，而不用花費(fèi)時(shí)間對元素進(jìn)行排序。使用的典型實(shí)例是任務(wù)調(diào)度場景。

3. Map

表示鍵值對，鍵必須是唯一的，不能對同一個(gè)鍵存放兩個(gè)值。

3.1 HashMap

HashMap底層實(shí)現(xiàn)上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。具體如下圖所示：

鏈表散列

從上圖我們可以看出HashMap底層實(shí)現(xiàn)還是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈。其中數(shù)組和鏈表在jdk源碼中體現(xiàn)：

/**The table, resized as necessary.

3.1.1如何插入一個(gè)值

HashMap插入一個(gè)值包括以下幾個(gè)步驟：

1. 調(diào)用hash計(jì)算key的hash值

2. 根據(jù)hash值推算出放在數(shù)組的位置

3. 找到具體數(shù)組某個(gè)位置，遍歷該位置的Entry鏈表，比較key值如果相等則直接替換value，如果不同則插入鏈表的尾部。

可以看出，如果hashCode和hash足夠好，盡可能的減少?zèng)_突，那么對HashMap的訪問等價(jià)于對數(shù)組的隨機(jī)方位，如果不夠好有大量沖突存在，則退化為對鏈表的隨機(jī)方位。

3.1.2再散列rehash

當(dāng)哈希表的容量超過默認(rèn)容量時(shí)，必須調(diào)整table的大小。當(dāng)容量已經(jīng)達(dá)到最大可能值時(shí)，那么該方法就將容量調(diào)整到Integer.MAX_VALUE返回，這時(shí)，需要?jiǎng)?chuàng)建一張新表，將原表的映射到新表中。

rehash

3.1.3容量參數(shù)

可以看出整個(gè)再散列過程是比較耗時(shí)的，需要將所有老數(shù)據(jù)重新計(jì)算后放到新的散列表中。HashMap維護(hù)一個(gè)threshold變量，它始終被定義為當(dāng)前數(shù)組總?cè)萘亢拓?fù)載因子的乘積，他表示的是HashMap的閾值，當(dāng)超過該值，HashMap便會(huì)擴(kuò)容。

關(guān)于負(fù)載因子定義首先看一下HashMap的constructor如下：

public HashMap(int initalCapacity);

其中initalCapacity表示初始化容量，loadFactor表示負(fù)載因子一般是介于0和1之間，它決定了HashMap擴(kuò)容之前，其內(nèi)部數(shù)組的填充度。默認(rèn)情況下，初始量為16，負(fù)載因子為0.75。

負(fù)載因子 =元素個(gè)數(shù)/內(nèi)部數(shù)組總大小

可以看出如果負(fù)載因子大于1，一定會(huì)存在沖突，元素個(gè)數(shù)大于數(shù)組的容量。

3.1.4如何取一個(gè)值

查看jdk源碼可以看出從HashMap中獲取一個(gè)值分為兩種情況當(dāng)key為null的時(shí)候單獨(dú)處理，非null的時(shí)候一套處理邏輯。這里也提醒我們HashMap可以存放key為null的鍵值對。

獲取值get

查看獲取非null的key的值的具體實(shí)現(xiàn)

查找key對應(yīng)Entry對象

分析查找一個(gè)非null的鍵流程：

1. 調(diào)用hash計(jì)算key的hash值

2. 根據(jù)hash值推算出放在數(shù)組的位置

3. 遍歷對應(yīng)位置上的鏈表找到key相同的Entry對象返回即可，找不到則返回為null

3.2 TreeMap

HashMap和LinkedHashMap底層存儲(chǔ)容器都是選擇了數(shù)組，內(nèi)容為內(nèi)部類Entry。但是TreeMap底層通過一顆紅黑樹來維護(hù)，初始化的時(shí)候有個(gè)root根節(jié)點(diǎn)，同時(shí)TreeMap不允許key為null。TreeMap本質(zhì)上就是一棵“紅黑樹”，而 TreeMap的每個(gè) Entry就是該紅黑樹的一個(gè)節(jié)點(diǎn)。

3.2.1紅黑樹

排序二叉樹要么是一棵空二叉樹，要么是具有下列性質(zhì)的二叉樹：

• 若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；

• 若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；

• 它的左、右子樹也分別為排序二叉樹。

排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節(jié)點(diǎn)集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹將變成鏈表。

紅黑樹在原有的排序二叉樹增加了如下幾個(gè)要求：

• 性質(zhì) 1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。

• 性質(zhì) 2：根節(jié)點(diǎn)永遠(yuǎn)是黑色的。

• 性質(zhì) 3：所有的葉節(jié)點(diǎn)都是空節(jié)點(diǎn)（即 null），并且是黑色的。

• 性質(zhì) 4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）

• 性質(zhì) 5：從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。

上面的性質(zhì) 3中指定紅黑樹的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)，而且并葉子節(jié)點(diǎn)都是黑色。但 Java實(shí)現(xiàn)的紅黑樹將使用 null來代表空節(jié)點(diǎn)，因此遍歷紅黑樹時(shí)將看不到黑色的葉子節(jié)點(diǎn)，反而看到每個(gè)葉子節(jié)點(diǎn)都是紅色的。

4. 迭代器（Iterator）

迭代器是一種設(shè)計(jì)模式，在java里它是一個(gè)對象，可以遍歷并選擇序列中的對象，而開發(fā)人員不需要了解該序列的底層結(jié)構(gòu)。迭代器通常被稱為“輕量級”對象，因?yàn)閯?chuàng)建它的代價(jià)小。迭代器接口Iterable是Collection類的父接口。它只有一個(gè)方法: iterator，方法返回一個(gè)代表當(dāng)前集合對象的泛型<T>迭代器，用于之后的遍歷操作。所有的Collection集合對象都實(shí)現(xiàn)這個(gè)Iterable接口，允許使用foreach進(jìn)行遍歷。

常用Iterator遍歷方式

List<Integer> lstint = new ArrayList<Integer>;// Iterator遍歷一Iterator<Integer> iterator = lstint.iterator;while (iterator.hasNext){

5. Fail-Fast機(jī)制

前面敘述的集合類均不是線程安全的，所以java集合(Collection)規(guī)定在使用迭代器的過程中有其他線程修改了同一個(gè)集合類，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。

注意點(diǎn)：迭代器的快速失敗行為無法得到保證，迭代器的快速失敗行為應(yīng)該僅用于檢測 bug。

例如：當(dāng)某一個(gè)線程A通過iterator去遍歷某集合的過程中，若該集合的內(nèi)容同時(shí)被其他線程所改變了；那么線程A訪問集合時(shí)，就會(huì)拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。

5.1實(shí)現(xiàn)原理

這里以HashMap為例進(jìn)行說明，其他集合類實(shí)現(xiàn)類似，這一策略在源碼中的實(shí)現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個(gè)值，具體定義如下：

modCount定義

HashMap在put函數(shù)添加元素時(shí)修改此值代碼如下：

put新增值修改modCount

在迭代器初始化過程中會(huì)將這個(gè)值賦給迭代器的expectedModCount，在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map，將會(huì)拋出ConcurrentModificationException異常，具體代碼如下：

遍歷判斷

5.2遍歷刪除指定元素

在實(shí)際應(yīng)用中，我們常會(huì)遇到一種需求是從集合中刪除符合某個(gè)特定條件的元素，對比下面幾種寫法：

/**

改寫法如注釋中描述由于remove操作導(dǎo)致modCount發(fā)生變化，繼續(xù)遍歷就會(huì)觸發(fā)Fail-Fast機(jī)制。這種寫法如果確定只刪除其中一個(gè)，此時(shí)break掉程序不會(huì)拋異常。

/**

該種寫法通過遍歷數(shù)組的形式，在刪除過程中導(dǎo)致數(shù)組元素減少位置發(fā)生變化影響了最后的結(jié)果。

/**

推薦寫法使用Iterator遍歷并使用迭代器對應(yīng)的remove方法刪除。該刪除方法會(huì)同步size大小以及修改expectCount。

6.總結(jié)

簡單總結(jié)上述各種類使用和實(shí)現(xiàn)特點(diǎn)，如下表所示：

學(xué)習(xí)Java的同學(xué)注意了?。?！

學(xué)習(xí)過程中遇到什么問題或者想獲取學(xué)習(xí)資源的話，歡迎加入Java學(xué)習(xí)交流群，群號碼：415839104我們一起學(xué)Java！