Java 集合（List、Set、Map 等）相關問答歸納再整理

• 2021 年 3 月 4 日
• 筆記

寫在最前面

這個項目是從20年末就立好的 flag，經過幾年的學習，回過頭再去看很多知識點又有新的理解。所以趁著找實習的準備，結合以前的學習儲備，創建一個主要針對應屆生和初學者的 Java 開源知識項目，專註 Java 後端面試題 + 解析 + 重點知識詳解 + 精選文章的開源項目，希望它能伴隨你我一直進步！

說明：此項目內容參考了諸多部落客（已註明出處），資料，N本書籍，以及結合自己理解，重新繪圖，重新組織語言等等所制。個人之力綿薄，或有不足之處，在所難免，但更新/完善會一直進行。大家的每一個 Star 都是對我的鼓勵 ！希望大家能喜歡。

註：所有涉及圖片未使用網路圖床，文章等均開源提供給大家。

項目名: Java-Ideal-Interview

Github 地址： Java-Ideal-Interview – Github

Gitee 地址：Java-Ideal-Interview – Gitee（碼雲）

持續更新中，在線閱讀將會在後期提供，若認為 Gitee 或 Github 閱讀不便，可克隆到本地配合 Typora 等編輯器舒適閱讀

若 Github 克隆速度過慢，可選擇使用中國 Gitee 倉庫

• 四 集合框架
  • 1. Java 集合框架概述
    • 1.1 什麼是集合框架
      • 1.1.1 數組和集合的區別?
    • 1.2 集合框架體系結構
    • 1.3 請說明Java集合類框架的基本介面有哪些？
    • 1.4 說一說 Java 常見集合的數據結構以及其特點
      • 1.4.1 List
      • 1.4.2 Map
      • 1.4.3 Set
    • 1.5 Collection和Collections的區別
    • 1.6 請簡單說明一下什麼是迭代器？
    • 1.7 請你說說Iterator和ListIterator的區別？
  • 2. List 介面
    • 2.1 闡述 ArrayList 分別與 Vector、LinkedList 的異同點
      • 2.1.1 ArrayList 與 Vector
      • 2.1.2 ArrayList 與 LinkedList
    • 2.2 ArrayLsit 擴容機制和並發修改異常（請跳轉）
    • 2.3 ArrayList集合加入指定大量數據，應該怎麼提高效率
  • 3. Set 介面
    • 3.1 Set 無序性是怎麼理解的
    • 3.2 1.4.4. HashSet 如何檢查重複
  • 4. Map 介面
    • 4.1 HashMap 與 HashTable 、HashSet、HashMap 等的區別
      • 4.1.1 HashMap 與 HashTable
      • 4.1.2 HashMap 與 HashSet
      • 4.1.3 HashMap 與 TreeMap
    • 4.2 HashMap 的長度為什麼是 2 的冪次方
    • 4.3 hash() 中的擾動函數如何解決Hash衝突 ※
    • 4.4 簡單談談 HashMap 中的底層原理
      • 4.4.1 JDK 1.8 之前
      • 4.4.2 JDK 1.8
    • 4.5 HashMap 中載入因子的理解
    • 4.6 ConcurrentHashMap 和 Hashtable 的區別

四 集合框架

1. Java 集合框架概述

1.1 什麼是集合框架

如果一個程式只包含固定數量的且其生命周期都是已知的對象，那麼這是一個非常簡單的程式。

通常，程式總是根據運行時才知道的某些條件去創建新對象。在此之前，不會知道你所需要對象的數量，甚至不知道確切的類型。為了解決這個普遍的編程問題，需要在任意時刻和任意位置創建任意數量的對象。所以，就不能依靠創建命名的引用來持有每一個對象，因為你不知道實際上會需要多少這樣的引用 ——Thinking in Java

首先知道我們所學習的Java語言是一個完全面向對象的語言，而這種語言對事物的描述是通過對象體現的，為了方便對多個對象進行操作，我們就必須把這多個對象進行存儲。

一個基本類型的變數顯然是無法滿足存儲多個對象的，所以應該是一個容器類型的變數，通過前面的知識，我們知道數組和 StringBuffer、StringBuilder 均屬於容器類型。但是呢? StringBuffer 的結果是一個字元串，不一定滿足我們的要求，所以我們只能選擇數組，這就是對象數組。

可是問題又來了，對象數組又不能適應變化的需求，因為數組的長度是固定的，而且他不能根據我們的操作（增刪改查）選擇最好的策略，這個時候，為了適應變化的需求，Java就提供了集合類供我們使用。

1.1.1 數組和集合的區別?

首先數組的長度固定，而集合的長度可變，其次數組存儲的是同一種類型的元素，而集合可以存儲不同類型的元素，最後數組可以存儲基本數據類型，也可以存儲引用數據類型

雖然數組看起來有一絲不太靈活，但數組也確實是保存一組對象的有效方法，如果想要保存一組基本數據類型，我們也推薦使用這種方法，只是由於其長度固定，導致它在很多時候也受到一些限制。

1.1.1.1 集合的彈性空間分配需要開銷

在Java中，數組是一種效率最高的存儲和隨機訪問對象的引用序列的方式。數組就是一個簡單的線性序列，這使得元素訪問非常快速。但是為這種速度所付出的代價是數組對象的大小被固定，並且在其生命周期中不可改變。你可能會建議使用 ArrayList，它可以通過創建一個新實例，然後把舊實例中所有的引用到移到新實例中，從而實現更多空間的自動分配。儘管通常應該首選 ArrayList 而不是數組、但是這種彈性需要開銷，因此，ArrayList 的效率比數組低很多。——Thinking in Java 第16章

1.2 集合框架體系結構

基本常見的集合框架就是下圖所示，還有一些特殊的沒寫出來，例如 ConcurrentHashMap 等等

簡單看一下其體系結構

Collection

Map

1.3 請說明Java集合類框架的基本介面有哪些？

首先集合類操作的對象，我們稱為元素，而集合類介面的每一種具體的實現類都可以選擇以它自己的方式對元素進行保存和排序。有的集合類允許重複的鍵，有的則不允許。

Java集合類裡面最基本的介面有：

• Collection：代表一組對象，每一個對象都是它的子元素。
• List：有順序的 collection，並且可以包含重複元素（順序）。
• Set：不保證有序，同時不包含重複元素的Collection（唯一）。
• Map：可以把 鍵(key) 映射到 值(value) 的對象，鍵不能重複（鍵值對）。

1.4 說一說 Java 常見集合的數據結構以及其特點

1.4.1 List

• ArrayList：Object 數組（查詢快，增刪慢，執行緒不安全，效率高 ）
• Vector： Object數組（查詢快，增刪慢，執行緒安全，效率低 ）
• LinkedList： 雙向鏈表，JDK1.6 之前是循環鏈表，JDK1.7 取消了循環（查詢慢，增刪快，執行緒不安全，效率高 ）

1.4.2 Map

• HashMap： JDK1.8 之前 HashMap 由數組+鏈表組成的，數組是 HashMap 存儲元素的主體，鏈表則是主要為了解決哈希衝突而存在的，即 「拉鏈法」 解決衝突。JDK1.8 以後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，以減少搜索時間（哈希表對鍵進行散列，Map結構即映射表存放鍵值對）
• LinkedHashMap： LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基於拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得鍵值對的插入順序以及訪問順序等邏輯可以得以實現。
• Hashtable： 數組 + 鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希衝突而存在的
• TreeMap： 紅黑樹（平衡二叉排序樹）

1.4.3 Set

• HashSet: 基於 HashMap 實現的，底層採用 HashMap 來保存元素（不保證有序，唯一）
• LinkedHashSet： LinkedHashSet 繼承與 HashSet，並且其內部是通過 LinkedHashMap 來實現的。有點類似於我們之前說的LinkedHashMap 其內部是基於 Hashmap 實現一樣，不過還是有一點點區別的。
• TreeSet： 紅黑樹，自平衡的排序二叉樹（可實現自然排序，例如 a-z）

1.5 Collection和Collections的區別

• Collection是集合的上級介面，繼承它的有 Set 和 List 介面
• Collections是集合的工具類，提供了一系列的靜態方法對集合的搜索、查找、同步等操作

1.6 請簡單說明一下什麼是迭代器？

Iterator 提供了遍歷及操作集合元素的介面，而 Collection介面實現 Iterable 介面，也就是說，每個集合都通過實現Iterable 介面中 iterator() 方法返回 Iterator 介面的實例，然後對集合的元素進行迭代操作。

有一點需要注意的是：在迭代元素的時候不能通過集合的方法刪除元素, 否則會拋出ConcurrentModificationException 異常. 但是可以通過 Iterator介面中的 remove() 方法進行刪除，同理想要增加元素，就可以使用 ListIterator 的 add 方法 （ListIterator 擁有 add、set、remove 方法，Iterator 擁有 remove 方法）

1.7 請你說說Iterator和ListIterator的區別？

Iterator 可用來遍歷 Set 和 List 集合，但是 ListIterator 只能用來遍歷List。

• Iterator只能 remove() 元素，而ListIterator可以 add()、set()、remove()
• Iterator只能使用 next() 順序的向後遍歷，ListIterator則向前 previous()和向後 next() 遍歷都可以
  • 還有一個額外的功能，ListIterator可以使用 nextIndex() 和 previousIndex() 取得當前游標位置的前後index位置，Iterator沒有此功能

可參考：Java – Iterator和ListIterator

2. List 介面

2.1 闡述 ArrayList 分別與 Vector、LinkedList 的異同點

2.1.1 ArrayList 與 Vector

ArrayList 是現在 List 的一種主要實現類，而 Vector 已經是過時的 Java 遺留容器

• 同：兩者都是使用 Object 數組方式存儲數據，均可以實現擴容且允許直接按序號查詢（索引）元素，但是插入元素要涉及數組元素移動等記憶體操作，所以兩者查詢數據快而插入數據慢

• 異：Vector中的方法由於添加了 synchronized 修飾，因此 Vector 是執行緒安全的容器，但性能上較 ArrayList 差

2.1.2 ArrayList 與 LinkedList

• 數據結構：ArrayList 是 Object 數組，LinkedList 是雙向鏈表（JDK1.6 之前是循環鏈表，JDK1.7 取消了循環）

  • 查詢效率：ArrayList 支援高效的隨機元素訪問，即通過下標快速獲取元素對象。而 LinkedList 不支援，所以 ArrayList 的查詢效率更高

  • 增刪效率：ArrayList 底層是數組存儲，所以插入和刪除元素的時間複雜度與元素插入的位置有關，因為會涉及到元素的移動問題，例如追加在末尾，則時間複雜度為 O(1) ，若在首部插入，則時間複雜度為 O(n)，中間任意位置插入，時間複雜度為，為 O((n - 1) / 2) ，平均時間複雜度還是 O(n) 而 LinkedList採用的是鏈表存儲，所以增刪不會涉及到元素的移動，只需要修改指針即可，時間複雜度可以簡單看為 O(1)，但是要是在指定位置增刪元素的話，需要先移動到指定位置再插入，以這個角度看時間複雜度為 O(n)

• 執行緒安全：ArrayList 和 LinkedListed 都是非執行緒安全的，如果遇到多個執行緒操作同一個容器的場景，則可以通過工具類 Collections 中的 synchronizedList 方法將其轉換成執行緒安全的容器後再使用（這是對裝潢模式的應用，將已有對象傳入另一個類的構造器中創建新的對象來增強實現）。

• 記憶體消耗：LinkedListed 每一個元素都需要存放前驅和後繼節點的地址，所以每一個元素都更加消耗空間，而 ArrayList 只要是在結尾會預留一定的容量空間，這是擴容所導致的不能充分填滿數組的情況（除非使用方法瘦身）

2.2 ArrayLsit 擴容機制和並發修改異常（請跳轉）

在 001-ArrayList源碼分析（含擴容機制等重點問題分析） 文章中，我做過詳細的分析，篇幅過長，可跳轉閱讀。

2.3 ArrayList集合加入指定大量數據，應該怎麼提高效率

ArrayList的默認初始容量為10，要插入大量數據的時候需要不斷擴容，而擴容是非常影響性能的，在已知數據量的情況下，可以直接在初始化的時候就設置ArrayList的容量，以提高效率。

3. Set 介面

3.1 Set 無序性是怎麼理解的

無序性是指存儲的數據在底層數組中並非按照數組索引的順序添加 ，而是根據數據的哈希值決定的。

具體分析可參考我在知乎的回答：Java遍歷HashSet為什麼輸出是有序的？@BWH_Steven 的答案

這個問題非常值得深入分析，對於 Set 和 Map 源碼的理解很有幫助！！！

3.2 1.4.4. HashSet 如何檢查重複

當你把對象加入 HashSet時，HashSet 會先計算對象的 hashcode值來判斷對象加入的位置，同時也會與其他加入的對象的 hashcode 值作比較，如果沒有相符的 hashcode ，HashSet 會假設對象沒有重複出現。但是如果發現有相同 hashcode 值的對象，這時會調用 equals() 方法來檢查 hashcode 相等的對象是否真的相同。如果兩者相同，HashSet 就不會讓加入操作成功。—— 《Head fist java》第二版

4. Map 介面

4.1 HashMap 與 HashTable 、HashSet、HashMap 等的區別

4.1.1 HashMap 與 HashTable

• 數據結構：HashMap JDK1.8 以後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，以減少搜索時間，不過在轉為紅黑樹前會判斷，如果數組長度小於 64，還是會優先進行數組擴容（哈希表對鍵進行散列，Map結構即映射表存放鍵值對），而 HashTable 沒有這種特殊的機構。

• 執行緒安全：HashMap 是非執行緒安全的，而 HashTable 屬於執行緒安全的（方法添加了 synchronized 修飾 ），因此，HashMap 效率也會略高，通常認為，HashTable 類似 Vector 是一個Java遺留類，基本不做使用。想保證執行緒安全，可以考慮使用 ConcurrentHashMap。

• Null 的處理：HashMap 的鍵和值都可以存儲為 null 的類型，但是只能有一個 null 類型的鍵，但是 null 類型的值可以有多個。HashTable 的鍵和值都不允許有 null 類型出現，否則會拋出空指針異常。

• 擴容機制：不指定初始值的時候，HashMap 初始值為 16，之後每次擴容，容量會成為原先的兩倍，HashTable 初始值為 11，擴容會使得容量成為原先的 2n + 1。若指定了初始值，HashMap 會將其擴充為 2 的冪次方大小，而 HashTable 會直接使用你給的初始值。

4.1.2 HashMap 與 HashSet

• HashMap 實現了 Map 介面，HashSet實現了 Set 介面。

• HashMap 儲存鍵值對，HashSet僅僅存儲對象。

• 使用 put() 方法將元素放入 map 中 使用 add() 方法將元素放入 set 中，但 add() 方法實際調用的還是 HashMap 中的 put() 方法。

• HashMap 中使用鍵對象來計算 hashcode 值 HashSet 使用成員對象來計算 hashcode 值，對於兩個對象來說hashcode 可能相同，所以 equals() 方法用來判斷對象的相等性，如果兩個對象不同的話，那麼返回 false。

• HashMap 比較快，因為是使用唯一的鍵來獲取對象，HashSet 較 HashMap 來說比較慢。

4.1.3 HashMap 與 TreeMap

• 順序問題：HashMap 中的元素是沒有順序的，TreeMap 中所有的元素都是有某一固定順序的。

• 執行緒安全：HashMap 和 TreeMap 都不是執行緒安全的

• 繼承問題：HashMap 繼承 AbstractMap 類；覆蓋了 hashcode() 和 equals() 方法，以確保兩個相等的映射返回相同的哈希值。TreeMap 繼承 SortedMap 類，保持鍵的有序順序。

• 調優問題：HashMap 基於哈希表實現的，使用HashMap要求添加的鍵類明確定義了 hashcode() 和 equals() （可以重寫該方法）；為了優化HashMap的空間使用，可以調優初始容量和負載因子。而 TreeMap 基於紅黑樹實現，所以TreeMap 就沒有調優選項，因為紅黑樹總是處於平衡的狀態。

• 適用場景：HashMap 適用於 Map 插入，刪除，定位元素，TreeMap適用於按自然順序或自定義順序遍歷鍵（key）。

4.2 HashMap 的長度為什麼是 2 的冪次方

HashSet因為底層使用哈希表（鏈表結合數組）實現，存儲時key通過一些運算後得出自己在數組中所處的位置。我們在hashCoe方法中返回到了一個等同於本身值的散列值，但是考慮到int類型數據的範圍：-2147483648~2147483647 ，著很顯然，這些散列值不能直接使用，因為記憶體是沒有辦法放得下，一個40億長度的數組的。所以它使用了對數組長度進行取模運算，得余後再作為其數組下標，indexFor( ) ——JDK7中，就這樣出現了，在JDK8中 indexFor()就消失了，而全部使用下面的語句代替，原理是一樣的。

// JDK8中
(tab.length - 1) & hash；

// JDK7中
bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
    return h & (length - 1);
}

可以看到其本質計算方法都是 (length - 1) & hash 提一句，為什麼取模運算時我們用 & 而不用 % 呢，因為位運算直接對記憶體數據進行操作，不需要轉成十進位，因此處理速度非常快，這樣就導致位運算 & 效率要比取模運算 % 高很多。

最關鍵的內容來了，如果我們用更容易理解的取余（%）， length % hash == (length - 1) & hash 這個公式想要成立的前提，就必須滿足 length 是 2 的 n 次方

簡單的說：HashMap 的長度為什麼是 2 的冪次方的原因就是，我們為了使用更加高效的 & 運算而不是 % 運算，但又為了保證運算的結果，仍然是取余操作。

4.3 hash() 中的擾動函數如何解決Hash衝突 ※

003-HashMap源碼分析（含散列表和紅黑樹介紹）

其中【 3.1 hash() 中的擾動函數如何解決Hash衝突 ※ 】詳細敘述了擾動函數的執行流程和作用，請跳轉查閱。

4.4 簡單談談 HashMap 中的底層原理

4.4.1 JDK 1.8 之前

JDK1.8 之前 HashMap 底層是數組 + 鏈表，HashMap 會使用 hashCode 以及擾動函數處理 key ，然後獲取一個hash 值，然後通過 (length- 1) & hash 判斷當前元素應該存放的位置，如果這個位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決衝突。

擾動函數在 4.3 中講述的應該很清楚了

拉鏈法的解釋，同樣可以參考 003-HashMap源碼分析（含散列表和紅黑樹介紹）

4.4.2 JDK 1.8

JDK 8 做了一些較大的調整，當數組中每個格子里的鏈表，長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，就可以大大的減少搜索時間，不過在轉為紅黑樹前會判斷，如果數組長度小於 64，還是會優先進行數組擴容。

4.5 HashMap 中載入因子的理解

• 載入因子就是表示哈希表中元素填滿的程度，當表中元素過多，超過載入因子的值時，哈希表會自動擴容，一般是一倍，這種行為可以稱作rehashing（再哈希）。
• 載入因子的值設置的越大，添加的元素就會越多，確實空間利用率的到了很大的提升，但是毫無疑問，就面臨著哈希衝突的可能性增大，反之，空間利用率造成了浪費，但哈希衝突也減少了，所以我們希望在空間利用率與哈希衝突之間找到一種我們所能接受的平衡，經過一些試驗，定在了0.75f。

4.6 ConcurrentHashMap 和 Hashtable 的區別

HashTable 雖然也滿足執行緒安全，但是類似 Vector， 是一個Java遺留類，基本不做使用。想保證執行緒安全，可以考慮使用 ConcurrentHashMap。

數據結構：JDK 1.7 中，ConcurrentHashMap 底層採用分段數組 + 鏈表實現，在 JDK 1.8 中，ConcurrentHashMap 中的數據結構與 HashMap 一致，都是數組 + 鏈表或紅黑樹。而 Hashtable 採用的是數組 + 鏈表的形式（數組為主體，鏈表用來解決哈希衝突）

執行緒安全：ConcurrentHashMap 在 JDK 1.7 的時候，有一個分段鎖的概念，也就是對整個數組進行分割開來（這就是 Segment 的概念），每一把鎖，只負責整個鎖分段中的一部分，而如果多執行緒訪問不同數據段的數據，鎖的競爭也就不存在了，訪問並法律也因此提高。而在 JDK 1.8 的時候，直接用 Node 數組 + 鏈表或紅黑樹實現，通過 synchronized（JDK 1.6 後優化了很多） 和 CAS 進行並發的控制。Hashtable 就是用一把鎖 synchronized 來保證執行緒安全，效率不是很高，多執行緒下，很可能會陷入阻塞輪詢狀態。

• 註：雖然 JDK 1.8 的源碼中還能看到 Segment ，但是主要也只是為了兼容舊版本了