作爲Java求職者，無數次被問到過集合的知識，同時作爲一位"周角公司小菜面試官”，我也肯定會問面試者集合的知識，所以就有了這篇，源碼較多，建議靜下心來哈，一起學習，一起進步

面嚮對象語言對事物的體現都是以對象的形式，所以爲了方便對多個對象的操作，需要將對象進行存儲，集合就是存儲對象最常用的一種方式，也叫容器。

從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器

• 一種是集合（Collection），存儲一個元素集合

• 另一種是圖（Map），存儲鍵/值對映射。

Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最後是具體實現類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

集合框架是一個用來代表和操縱集合的統一架構。所有的集合框架都包含如下內容：

• 接口：是代表集合的抽象數據類型。例如 Collection、List、Set、Map 等。之所以定義多個接口，是爲了以不同的方式操作集合對象

• 實現（類）：是集合接口的具體實現。從本質上講，它們是可重複使用的數據結構，例如：ArrayList、LinkedList、HashSet、HashMap。

• 算法：是實現集合接口的對象裏的方法執行的一些有用的計算，例如：搜索和排序。這些算法被稱爲多態，那是因爲相同的方法可以在相似的接口上有着不同的實現。

說說常用的集合有哪些吧？

Map 接口和 Collection 接口是所有集合框架的父接口：

1. Collection接口的子接口包括：Set、List、Queue

2. List是有序的允許有重複元素的Collection，實現類主要有：ArrayList、LinkedList、Stack以及Vector等

3. Set是一種不包含重複元素且無序的Collection，實現類主要有：HashSet、TreeSet、LinkedHashSet等

4. Map沒有繼承Collection接口，Map提供key到value的映射。實現類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等

ArrayList 和 Vector 的區別

相同點：

• ArrayList 和 Vector 都是繼承了相同的父類和實現了相同的接口（都實現了List，有序、允許重複和null）

• 底層都是數組（Object[]）實現的

• 初始默認長度都爲 10

不同點：

• 同步性：Vector 中的 public 方法多數添加了 synchronized 關鍵字、以確保方法同步、也即是 Vector 線程安全、ArrayList 線程不安全

• 性能：Vector 存在 synchronized 的鎖等待情況、需要等待釋放鎖這個過程、所以性能相對較差

• 擴容大小：ArrayList在底層數組不夠用時在原來的基礎上擴展 0.5 倍，Vector 默認是擴展 1 倍 擴容機制，擴容方法其實就是新創建一個數組，然後將舊數組的元素都複製到新數組裏面。其底層的擴容方法都在 grow() 中（基於JDK8）

• ArrayList 的 grow()，在滿足擴容條件時、ArrayList以 1.5 倍的方式在擴容（oldCapacity >> 1 ，右移運算，相當於除以 2，結果爲二分之一的 oldCapacity）

• Vector 的 grow()，Vector 比 ArrayList多一個屬性 capacityIncrement，可以指定擴容大小。當擴容容量增量大於 0 時、新數組長度爲 原數組長度**+**擴容容量增量、否則新數組長度爲原數組長度的 2 倍

ArrayList 與 LinkedList 區別

• 是否保證線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；

• 底層數據結構：Arraylist 底層使用的是 Object 數組；LinkedList 底層使用的是雙向循環鏈表數據結構；

• 插入和刪除是否受元素位置的影響：

• ArrayList 採用數組存儲，所以插入和刪除元素的時間複雜度受元素位置的影響。 比如：執行 add(E e) 方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間複雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（ add(intindex,E element) ）時間複雜度就爲 O(n-i)。因爲在進行上述操作的時候集合中第 i 和第 i 個元素之後的(n-i)個元素都要執行向後位/向前移一位的操作。

• LinkedList 採用鏈表存儲，所以插入，刪除元素時間複雜度不受元素位置的影響，都是近似，而數組爲近似。

• ArrayList 一般應用於查詢較多但插入以及刪除較少情況，如果插入以及從刪除較多則建議使用 LinkedList

• 是否支持快速隨機訪問 ：LinkedList 不支持高效的隨機元素訪問，而 ArrayList 實現了 RandomAccess 接口，所以有隨機訪問功能。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應於 get(intindex) 方法)。

• 內存空間佔用：ArrayList 的空間浪費主要體現在在 list 列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因爲要存放直接後繼和直接前驅以及數據）。

高級工程師的我，可不得看看源碼，具體分析下：

• ArrayList工作原理其實很簡單，底層是動態數組，每次創建一個 ArrayList 實例時會分配一個初始容量（沒有指定初始容量的話，默認是 10），以add方法爲例，如果沒有指定初始容量，當執行add方法，先判斷當前數組是否爲空，如果爲空則給保存對象的數組分配一個最小容量，默認爲10。當添加大容量元素時，會先增加數組的大小，以提高添加的效率；

• LinkedList 是有序並且支持元素重複的集合，底層是基於雙向鏈表的，即每個節點既包含指向其後繼的引用也包括指向其前驅的引用。鏈表無容量限制，但雙向鏈表本身使用了更多空間，也需要額外的鏈表指針操作。按下標訪問元素 get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動到位(如果i>數組大小的一半，會從末尾移起)。插入、刪除元素時修改前後節點的指針即可，但還是要遍歷部分鏈表的指針才能移動到下標所指的位置，只有在鏈表兩頭的操作 add() ， addFirst() ， removeLast() 或用 iterator() 上的 remove() 能省掉指針的移動。此外 LinkedList 還實現了 Deque（繼承自Queue接口）接口，可以當做隊列使用。

ps：不會囊括所有方法，只是爲了學習，記錄思想。

ArrayList 和 LinkedList 兩者都實現了 List 接口

構造器

ArrayList 提供了 3 個構造器，①無參構造器 ②帶初始容量構造器 ③參數爲集合構造器

LinkedList 提供了 2 個構造器，因爲基於鏈表，所以也就沒有初始化大小，也沒有擴容的機制，就是一直在前面或者後面插插插~~

插入

ArrayList的 add() 方法

當然也可以插入指定位置，還有一個重載的方法 add(int index, E element)

可以看到每次插入指定位置都要移動元素，效率較低。

再來看 LinkedList 的插入，也有插入末尾，插入指定位置兩種，由於基於鏈表，肯定得先有個 Node

獲取

ArrayList的 get() 方法很簡單，就是在數組中返回指定位置的元素即可，所以效率很高

LinkedList的 get() 方法，就是在內部調用了上邊看到的 node() 方法，判斷在前半段還是在後半段，然後遍歷得到即可。

HashMap的底層實現

什麼時候會使用HashMap？他有什麼特點？

你知道HashMap的工作原理嗎？

你知道 get 和 put 的原理嗎？equals() 和 hashCode() 的都有什麼作用？

你知道hash的實現嗎？爲什麼要這樣實現？

如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？

HashMap 在 JDK 7 和 JDK8 中的實現方式略有不同。分開記錄。

JDK1.7 實現

深入 HahsMap 之前，先要了解的概念

1. initialCapacity：初始容量。指的是 HashMap 集合初始化的時候自身的容量。可以在構造方法中指定；如果不指定的話，總容量默認值是 16 。需要注意的是初始容量必須是 2 的冪次方。（ 1.7中，已知HashMap中將要存放的 KV 個數的時候，設置一個合理的初始化容量可以有效的提高性能 ）

   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   

2. size：當前 HashMap 中已經存儲着的鍵值對數量，即 HashMap.size()

3. loadFactor：加載因子。所謂的加載因子就是 HashMap (當前的容量/總容量) 到達一定值的時候，HashMap 會實施擴容。加載因子也可以通過構造方法中指定，默認的值是 0.75 。舉個例子，假設有一個 HashMap 的初始容量爲 16 ，那麼擴容的閥值就是 0.75 * 16 = 12 。也就是說，在你打算存入第 13 個值的時候，HashMap 會先執行擴容。

4. threshold：擴容閥值。即 擴容閥值 = HashMap 總容量 * 加載因子。當前 HashMap 的容量大於或等於擴容閥值的時候就會去執行擴容。擴容的容量爲當前 HashMap 總容量的兩倍。比如，當前 HashMap 的總容量爲 16 ，那麼擴容之後爲 32 。

5. table：Entry 數組。我們都知道 HashMap 內部存儲 key/value 是通過 Entry 這個介質來實現的。而 table 就是 Entry 數組。

JDK1.7 中 HashMap 由 數組+鏈表 組成（ “鏈表散列” 即數組和鏈表的結合體），數組是 HashMap 的主體，鏈表則是主要爲了解決哈希衝突而存在的（HashMap 採用 “拉鍊法也就是鏈地址法” 解決衝突），如果定位到的數組位置不含鏈表（當前 entry 的 next 指向 null ）,那麼對於查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含鏈表，對於添加操作，其時間複雜度依然爲 O(1)，因爲最新的 Entry 會插入鏈表頭部，即需要簡單改變引用鏈即可，而對於查找操作來講，此時就需要遍歷鏈表，然後通過 key 對象的 equals 方法逐一比對查找。

所謂 “拉鍊法” 就是將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希衝突，則將衝突的值加到鏈表中即可。

源碼解析

構造方法

《阿里巴巴 Java 開發手冊》推薦集合初始化時，指定集合初始值大小。（說明：HashMap 使用HashMap(int initialCapacity) 初始化），原因：https://www.zhihu.com/question/314006228/answer/611170521

HashMap 的前 3 個構造方法最後都會去調用 HashMap(int initialCapacity, float loadFactor) 。在其內部去設置初始容量和加載因子。而最後的 init() 是空方法，主要給子類實現，比如 LinkedHashMap。

put() 方法

最後的 createEntry() 方法就說明了當 hash 衝突時，採用的拉鍊法來解決 hash 衝突的，並且是把新元素是插入到單邊表的表頭。

get() 方法

JDK1.8 實現

JDK 1.7 中，如果哈希碰撞過多，拉鍊過長，極端情況下，所有值都落入了同一個桶內，這就退化成了一個鏈表。通過 key 值查找要遍歷鏈表，效率較低。JDK1.8在解決哈希衝突時有了較大的變化， 當鏈表長度大於閾值（默認爲8）時，將鏈表轉化爲紅黑樹 ，以減少搜索時間。

TreeMap、TreeSet以及 JDK1.8 之後的 HashMap 底層都用到了紅黑樹。紅黑樹就是爲了解決二叉查找樹的缺陷，因爲二叉查找樹在某些情況下會退化成一個線性結構。

源碼解析

構造方法

JDK8 構造方法改動不是很大

確定哈希桶數組索引位置（hash 函數的實現）

HashMap定位數組索引位置，直接決定了hash方法的離散性能。Hash算法本質上就是三步： 取key的hashCode值、高位運算、取模運算 。

爲什麼要這樣呢？

HashMap 的長度爲什麼是2的冪次方?

目的當然是爲了減少哈希碰撞，使 table 裏的數據分佈的更均勻。

1. HashMap 中桶數組的大小 length 總是2的冪，此時， h & (table.length -1) 等價於對 length 取模 h%length 。但取模的計算效率沒有位運算高，所以這是是一個優化。假設 h = 185 ， table.length-1 = 15(0x1111) ，其實散列真正生效的只是低 4bit 的有效位，所以很容易碰撞。

2. 圖中的 hash 是由鍵的 hashCode 產生。計算餘數時，由於 n 比較小，hash 只有低4位參與了計算，高位的計算可以認爲是無效的。這樣導致了計算結果只與低位信息有關，高位數據沒發揮作用。爲了處理這個缺陷，我們可以上圖中的 hash 高4位數據與低4位數據進行異或運算，即 hash ^ (hash >>> 4) 。通過這種方式，讓高位數據與低位數據進行異或，以此加大低位信息的隨機性，變相的讓高位數據參與到計算中。此時的計算過程如下：

   在 Java 中，hashCode 方法產生的 hash 是 int 類型，32 位寬。前16位爲高位，後16位爲低位，所以要右移16位，即 hash ^ (hash >>> 16) 。這樣還增加了hash 的複雜度，進而影響 hash 的分佈性。

put() 方法

resize() 擴容

get() 方法

Hashtable

Hashtable 和 HashMap 都是散列表，也是用”拉鍊法“實現的哈希表。保存數據和 JDK7 中的 HashMap 一樣，是 Entity 對象，只是 Hashtable 中的幾乎所有的 public 方法都是 synchronized 的，而有些方法也是在內部通過 synchronized 代碼塊來實現，效率肯定會降低。且 put() 方法不允許空值。

使用次數太少，不深究。

HashMap 和 Hashtable 的區別

1. 線程是否安全：HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；

2. 效率：因爲線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；

3. 對Null key 和Null value的支持：HashMap 中，null 可以作爲鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值爲 null。。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException。

4. 初始容量大小和每次擴充容量大小的不同 ：

• 創建時如果不指定容量初始值，Hashtable 默認的初始大小爲11，之後每次擴充，容量變爲原來的2n+1。HashMap 默認的初始化大小爲16。之後每次擴充，容量變爲原來的2倍。

• 創建時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充爲2的冪次方大小。也就是說 HashMap 總是使用2的冪次方作爲哈希表的大小,後面會介紹到爲什麼是2的冪次方。

5. 底層數據結構：JDK1.8 以後的 HashMap 在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認爲8）時，將鏈表轉化爲紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

6. HashMap的迭代器（ Iterator ）是fail-fast迭代器，但是 Hashtable的迭代器（ enumerator ）不是 fail-fast的。如果有其它線程對HashMap進行的添加/刪除元素，將會拋出 ConcurrentModificationException ，但迭代器本身的 remove 方法移除元素則不會拋出異常。這條同樣也是 Enumeration 和 Iterator 的區別。

ConcurrentHashMap

HashMap在多線程情況下，在put的時候，插入的元素超過了容量（由負載因子決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原數組的內容重新hash到新的擴容數組中，在多線程的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同一數組下用鏈表表示，造成閉環，導致在get時會出現死循環，所以HashMap是線程不安全的。

Hashtable，是線程安全的，它在所有涉及到多線程操作的都加上了synchronized關鍵字來鎖住整個table，這就意味着所有的線程都在競爭一把鎖，在多線程的環境下，它是安全的，但是無疑是效率低下的。

JDK1.7 實現

Hashtable 容器在競爭激烈的併發環境下表現出效率低下的原因，是因爲所有訪問 Hashtable 的線程都必須競爭同一把鎖，那假如容器裏有多把鎖，每一把鎖用於鎖容器其中一部分數據，那麼當多線程訪問容器裏不同數據段的數據時，線程間就不會存在鎖競爭，，這就是ConcurrentHashMap所使用的鎖分段技術。

在 JDK1.7版本中，ConcurrentHashMap 的數據結構是由一個 Segment 數組和多個 HashEntry 組成。Segment 數組的意義就是將一個大的 table 分割成多個小的 table 來進行加鎖。每一個 Segment 元素存儲的是 HashEntry數組+鏈表，這個和 HashMap 的數據存儲結構一樣。

ConcurrentHashMap 類中包含兩個靜態內部類 HashEntry 和 Segment。HashEntry 用來封裝映射表的鍵值對，Segment 用來充當鎖的角色，每個 Segment 對象守護整個散列映射表的若干個桶。每個桶是由若干個 HashEntry 對象鏈接起來的鏈表。一個 ConcurrentHashMap 實例中包含由若干個 Segment 對象組成的數組。每個 Segment 守護着一個 HashEntry 數組裏的元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得它對應的 Segment 鎖。

Segment 類

Segment 類繼承於 ReentrantLock 類，從而使得 Segment 對象能充當可重入鎖的角色。一個 Segment 就是一個子哈希表，Segment 裏維護了一個 HashEntry 數組，併發環境下，對於不同 Segment 的數據進行操作是不用考慮鎖競爭的。

從源碼可以看到，Segment 內部類和我們上邊看到的 HashMap 很相似。也有負載因子，閾值等各種屬性。

HashEntry 類

HashEntry 是目前我們最小的邏輯處理單元。一個ConcurrentHashMap 維護一個 Segment 數組，一個Segment維護一個 HashEntry 數組。

ConcurrentHashMap 類

默認的情況下，每個ConcurrentHashMap 類會創建16個併發的 segment，每個 segment 裏面包含多個 Hash表，每個 Hash 鏈都是由 HashEntry 節點組成的。

put() 方法

1. 定位segment並確保定位的Segment已初始化 

2. 調用 Segment的 put 方法。

get() 方法

get方法無需加鎖，由於其中涉及到的共享變量都使用volatile修飾，volatile可以保證內存可見性，所以不會讀取到過期數據

JDK1.8  實現

ConcurrentHashMap 在 JDK8 中進行了巨大改動，光是代碼量就從1000多行增加到6000行！1.8摒棄了 Segment (鎖段)的概念，採用了 CAS + synchronized 來保證併發的安全性。

可以看到，和HashMap 1.8的數據結構很像。底層數據結構改變爲採用數組+鏈表+紅黑樹的數據形式。

和 HashMap1.8 相同的一些地方

• 底層數據結構一致

• HashMap初始化是在第一次put元素的時候進行的，而不是init

• HashMap的底層數組長度總是爲2的整次冪

• 默認樹化的閾值爲 8，而鏈表化的閾值爲 6

• hash算法也很類似，但多了一步 & HASH_BITS ，該步是爲了消除最高位上的負符號，hash的負在ConcurrentHashMap中有特殊意義表示在 擴容或者是樹節點

一些關鍵屬性

put() 方法

1. 首先會判斷 key、value是否爲空，如果爲空就拋異常！

2. spread() 方法獲取hash，減小hash衝突
3. 判斷是否初始化table數組，沒有的話調用 initTable() 方法進行初始化

4. 判斷是否能直接將新值插入到table數組中

5. 判斷當前是否在擴容， MOVED 爲-1說明當前ConcurrentHashMap正在進行擴容操作，正在擴容的話就進行協助擴容

6. 當table[i]爲鏈表的頭結點，在鏈表中插入新值，通過synchronized (f)的方式進行加鎖以實現線程安全性。

1. 在鏈表中如果找到了與待插入的鍵值對的key相同的節點，就直接覆蓋

2. 如果沒有找到的話，就直接將待插入的鍵值對追加到鏈表的末尾

7. 當table[i]爲紅黑樹的根節點，在紅黑樹中插入新值/覆蓋舊值

8. 根據當前節點個數進行調整，否需要轉換成紅黑樹(個數大於等於8，就會調用 treeifyBin 方法將tabel[i] 第i個散列桶 拉鍊轉換成紅黑樹)

9. 對當前容量大小進行檢查，如果超過了臨界值（實際大小*加載因子）就進行擴容

我們可以發現 JDK8 中的實現也是 鎖分離 的思想，只是鎖住的是一個 Node，而不是 JDK7 中的 Segment，而鎖住Node 之前的操作是無鎖的並且也是線程安全的，建立在原子操作上。

get() 方法

get 方法無需加鎖，由於其中涉及到的共享變量都使用 volatile 修飾，volatile 可以保證內存可見性，所以不會讀取到過期數據

Hashtable 和 ConcurrentHashMap 的區別

ConcurrentHashMap 和 Hashtable 的區別主要體現在實現線程安全的方式上不同。

• 底層數據結構：JDK1.7的 ConcurrentHashMap 底層採用 分段的數組+鏈表 實現，JDK1.8 採用的數據結構和HashMap1.8的結構類似， 數組+鏈表/紅黑二叉樹 。Hashtable 和 JDK1.8 之前的 HashMap 的底層數據結構類似都是採用 數組+鏈表 的形式，數組是 HashMap 的主體，鏈表則是主要爲了解決哈希衝突而存在的；

• 實現線程安全的方式（重要）：

• 在JDK1.7的時候，ConcurrentHashMap（分段鎖）對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器裏不同數據段的數據，就不會存在鎖競爭，提高併發訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表/紅黑樹的數據結構來實現，併發控制使用 synchronized 和 CAS 來操作。（JDK1.6以後 對 synchronized鎖做了很多優化） 整個看起來就像是優化過且線程安全的 HashMap，雖然在 JDK1.8 中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是爲了兼容舊版本；

• Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭越激烈效率越低。

list 可以刪除嗎，遍歷的時候可以刪除嗎，爲什麼

Java快速失敗（fail-fast）和安全失敗（fail-safe）區別

快速失敗（fail—fast）

在用迭代器遍歷一個集合對象時，如果遍歷過程中對集合對象的內容進行了修改（增加、刪除、修改），則會拋出ConcurrentModificationException。

原理：迭代器在遍歷時直接訪問集合中的內容，並且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發生變化，就會改變 modCount 的值。每當迭代器使用 hashNext()/next() 遍歷下一個元素之前，都會檢測 modCount 變量是否爲 expectedmodCount 值，是的話就返回遍歷；否則拋出異常，終止遍歷。

注意：這裏異常的拋出條件是檢測到 modCount！=expectedmodCount 這個條件。如果集合發生變化時修改modCount 值剛好又設置爲了 expectedmodCount 值，則異常不會拋出。因此，不能依賴於這個異常是否拋出而進行併發操作的編程，這個異常只建議用於檢測併發修改的bug。

場景：java.util包下的集合類都是快速失敗的，不能在多線程下發生併發修改（迭代過程中被修改）。

安全失敗（fail—safe）

採用安全失敗機制的集合容器，在遍歷時不是直接在集合內容上訪問的，而是先複製原有集合內容，在拷貝的集合上進行遍歷。

原理：由於迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改並不能被迭代器檢測到，所以不會觸發 Concurrent Modification Exception。

缺點：基於拷貝內容的優點是避免了Concurrent Modification Exception，但同樣地，迭代器並不能訪問到修改後的內容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發生的修改迭代器是不知道的。

場景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下併發使用，併發修改。

快速失敗和安全失敗是對迭代器而言的。快速失敗：當在迭代一個集合的時候，如果有另外一個線程在修改這個集合，就會拋出ConcurrentModification異常，java.util下都是快速失敗。安全失敗：在迭代時候會在集合二層做一個拷貝，所以在修改集合上層元素不會影響下層。在java.util.concurrent下都是安全失敗

如何避免 fail-fast ？

• 在單線程的遍歷過程中，如果要進行remove操作，可以調用迭代器 ListIterator 的 remove 方法而不是集合類的 remove方法。看看 ArrayList中迭代器的 remove方法的源碼，該方法不能指定元素刪除，只能remove當前遍歷元素。

• 使用併發包( java.util.concurrent )中的類來代替 ArrayList 和 hashMap

• CopyOnWriterArrayList 代替 ArrayList

• ConcurrentHashMap 代替 HashMap

Iterator 和 Enumeration 區別

在Java集合中，我們通常都通過 “Iterator(迭代器)” 或 “Enumeration(枚舉類)” 去遍歷集合。

• 函數接口不同，Enumeration只有2個函數接口。 通過Enumeration，我們只能讀取集合的數據，而不能對數據進行修改。Iterator 只有3個函數接口。Iterator除了能讀取集合的數據之外，也能數據進行刪除操作。

• Iterator支持 fail-fast機制，而Enumeration不支持。Enumeration 是JDK 1.0添加的接口。使用到它的函數包括Vector、Hashtable等類，這些類都是JDK 1.0中加入的，Enumeration存在的目的就是爲它們提供遍歷接口。Enumeration本身並沒有支持同步，而在Vector、Hashtable實現Enumeration時，添加了同步。而Iterator 是JDK 1.2才添加的接口，它也是爲了HashMap、ArrayList等集合提供遍歷接口。Iterator是支持fail-fast機制的：當多個線程對同一個集合的內容進行操作時，就可能會產生fail-fast事件

Comparable 和 Comparator接口有何區別？

Java中對集合對象或者數組對象排序，有兩種實現方式：

• 對象實現Comparable 接口

• Comparable 在 java.lang 包下，是一個接口，內部只有一個方法 compareTo()

• Comparable 可以讓實現它的類的對象進行比較，具體的比較規則是按照 compareTo 方法中的規則進行。這種順序稱爲 自然順序 。

• 實現了 Comparable 接口的 List 或則數組可以使用 Collections.sort() 或者 Arrays.sort() 方法進行排序

• 定義比較器，實現 Comparator接口

• Comparator 在 java.util 包下，也是一個接口，JDK 1.8 以前只有兩個方法： comparable相當於內部比較器。comparator相當於外部比較器

區別：

• Comparator 位於 java.util 包下，而 Comparable 位於 java.lang 包下

• Comparable 接口的實現是在類的內部（如 String、Integer已經實現了 Comparable 接口，自己就可以完成比較大小操作），Comparator 接口的實現是在類的外部（可以理解爲一個是自已完成比較，一個是外部程序實現比較）

• 實現 Comparable 接口要重寫 compareTo 方法, 在 compareTo 方法裏面實現比較。一個已經實現Comparable 的類的對象或數據，可以通過 Collections.sort(list) 或者 Arrays.sort(arr)實現排序。通過 Collections.sort(list,Collections.reverseOrder()) 對list進行倒序排列。

• 實現Comparator需要重寫 compare 方法

HashSet

HashSet是用來存儲沒有重複元素的集合類，並且它是無序的。HashSet 內部實現是基於 HashMap ，實現了 Set 接口。

從 HahSet 提供的構造器可以看出，除了最後一個 HashSet 的構造方法外，其他所有內部就是去創建一個 Hashap 。沒有其他的操作。而最後一個構造方法不是 public 的，所以不對外公開。

HashSet如何檢查重複

HashSet的底層其實就是HashMap，只不過我們 HashSet是實現了Set接口並且把數據作爲K值，而V值一直使用一個相同的虛值來保存 ，HashMap的K值本身就不允許重複，並且在HashMap中如果K/V相同時，會用新的V覆蓋掉舊的V，然後返回舊的V。

Iterater 和 ListIterator 之間有什麼區別？

• 我們可以使用Iterator來遍歷Set和List集合，而ListIterator只能遍歷List

• ListIterator有add方法，可以向List中添加對象，而Iterator不能

• ListIterator和Iterator都有hasNext()和next()方法，可以實現順序向後遍歷，但是ListIterator有hasPrevious()和previous()方法，可以實現逆向（順序向前）遍歷。Iterator不可以

• ListIterator可以定位當前索引的位置，nextIndex()和previousIndex()可以實現。Iterator沒有此功能

• 都可實現刪除操作，但是 ListIterator可以實現對象的修改，set()方法可以實現。Iterator僅能遍歷，不能修改

參考與感謝

所有內容都是基於源碼閱讀和各種大佬之前總結的知識整理而來，輸入並輸出，奧利給。

• https://www.javatpoint.com/java-arraylist

• https://www.runoob.com/java/java-collections.html

• https://www.javazhiyin.com/21717.html

• https://yuqirong.me/2018/01/31/LinkedList內部原理解析/

• https://youzhixueyuan.com/the-underlying-structure-and-principle-of-hashmap.html

• 《HashMap源碼詳細分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源碼詳細分析-JDK1-8

• 《ConcurrentHashMap1.7源碼分析》https://www.cnblogs.com/chengxiao/p/6842045.html

• http://www.justdojava.com/2019/12/18/java-collection-15.1/