Java 集合常見知識點&面試題總結(上)，2022 最新版！

你好，我是 Guide。秋招即將到來（提前批已經開始），我對 JavaGuide 的內容進行了重構完善，公眾號同步一下最新更新，希望能夠幫助你。

你也可以在網站(javaguide.cn)上在線閲讀，閲讀體驗會更好！

前 3 篇：

• Java 基礎常見知識點&面試題總結(上)，2022 最新版！
• Java 基礎常見知識點&面試題總結(中)，2022 最新版
• Java 基礎常見知識點&面試題總結(下)，2022 最新版！

集合概述

Java 集合概覽

Java 集合， 也叫作容器，主要是由兩大接口派生而來：一個是 Collection接口，主要用於存放單一元素；另一個是 Map 接口，主要用於存放鍵值對。對於Collection 接口，下面又有三個主要的子接口：List、Set 和 Queue。

Java 集合框架如下圖所示：

注：圖中只列舉了主要的繼承派生關係，並沒有列舉所有關係。比方省略了AbstractList, NavigableSet等抽象類以及其他的一些輔助類，如想深入瞭解，可自行查看源碼。

説説 List, Set, Queue, Map 四者的區別？

• List(對付順序的好幫手): 存儲的元素是有序的、可重複的。
• Set(注重獨一無二的性質): 存儲的元素是無序的、不可重複的。
• Queue(實現排隊功能的叫號機): 按特定的排隊規則來確定先後順序，存儲的元素是有序的、可重複的。
• Map(用 key 來搜索的專家): 使用鍵值對（key-value）存儲，類似於數學上的函數 y=f(x)，"x" 代表 key，"y" 代表 value，key 是無序的、不可重複的，value 是無序的、可重複的，每個鍵最多映射到一個值。

集合框架底層數據結構總結

先來看一下 Collection 接口下面的集合。

List

• Arraylist： Object[] 數組
• Vector：Object[] 數組
• LinkedList： 雙向鏈表(JDK1.6 之前為循環鏈表，JDK1.7 取消了循環)

Set

• HashSet(無序，唯一): 基於 HashMap 實現的，底層採用 HashMap 來保存元素
• LinkedHashSet: LinkedHashSet 是 HashSet 的子類，並且其內部是通過 LinkedHashMap 來實現的。有點類似於我們之前説的 LinkedHashMap 其內部是基於 HashMap 實現一樣，不過還是有一點點區別的
• TreeSet(有序，唯一): 紅黑樹(自平衡的排序二叉樹)

Queue

• PriorityQueue: Object[] 數組來實現二叉堆
• ArrayQueue: Object[] 數組 + 雙指針

再來看看 Map 接口下面的集合。

Map

• HashMap： JDK1.8 之前 HashMap 由數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希衝突而存在的（“拉鍊法”解決衝突）。JDK1.8 以後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷，如果當前數組的長度小於 64，那麼會選擇先進行數組擴容，而不是轉換為紅黑樹）時，將鏈表轉化為紅黑樹，以減少搜索時間
• LinkedHashMap： LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基於拉鍊式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》
• Hashtable： 數組+鏈表組成的，數組是 Hashtable 的主體，鏈表則是主要為了解決哈希衝突而存在的
• TreeMap： 紅黑樹（自平衡的排序二叉樹）

如何選用集合?

主要根據集合的特點來選用，比如我們需要根據鍵值獲取到元素值時就選用 Map 接口下的集合，需要排序時選擇 TreeMap,不需要排序時就選擇 HashMap,需要保證線程安全就選用 ConcurrentHashMap。

當我們只需要存放元素值時，就選擇實現Collection 接口的集合，需要保證元素唯一時選擇實現 Set 接口的集合比如 TreeSet 或 HashSet，不需要就選擇實現 List 接口的比如 ArrayList 或 LinkedList，然後再根據實現這些接口的集合的特點來選用。

為什麼要使用集合？

當我們需要保存一組類型相同的數據的時候，我們應該是用一個容器來保存，這個容器就是數組，但是，使用數組存儲對象具有一定的弊端， 因為我們在實際開發中，存儲的數據的類型是多種多樣的，於是，就出現了“集合”，集合同樣也是用來存儲多個數據的。

數組的缺點是一旦聲明之後，長度就不可變了；同時，聲明數組時的數據類型也決定了該數組存儲的數據的類型；而且，數組存儲的數據是有序的、可重複的，特點單一。 但是集合提高了數據存儲的靈活性，Java 集合不僅可以用來存儲不同類型不同數量的對象，還可以保存具有映射關係的數據。

Collection 子接口之 List

Arraylist 和 Vector 的區別?

• ArrayList 是 List 的主要實現類，底層使用 Object[ ]存儲，適用於頻繁的查找工作，線程不安全 ；
• Vector 是 List 的古老實現類，底層使用Object[ ] 存儲，線程安全的。

Arraylist 與 LinkedList 區別?

1. 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
2. 底層數據結構： Arraylist 底層使用的是 Object 數組；LinkedList 底層使用的是 雙向鏈表 數據結構（JDK1.6 之前為循環鏈表，JDK1.7 取消了循環。注意雙向鏈表和雙向循環鏈表的區別，下面有介紹到！）
3. 插入和刪除是否受元素位置的影響：
4. ArrayList 採用數組存儲，所以插入和刪除元素的時間複雜度受元素位置的影響。 比如：執行add(E e)方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間複雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間複雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之後的(n-i)個元素都要執行向後位/向前移一位的操作。
5. LinkedList 採用鏈表存儲，所以，如果是在頭尾插入或者刪除元素不受元素位置的影響（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），時間複雜度為 O(1)，如果是要在指定位置 i 插入和刪除元素的話（add(int index, E element)，remove(Object o)）， 時間複雜度為 O(n) ，因為需要先移動到指定位置再插入。
6. 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應於get(int index)方法)。
7. 內存空間佔用： ArrayList 的空 間浪費主要體現在在 list 列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接後繼和直接前驅以及數據）。

我們在項目中一般是不會使用到 LinkedList 的，需要用到 LinkedList 的場景幾乎都可以使用 ArrayList 來代替，並且，性能通常會更好！就連 LinkedList 的作者約書亞 · 布洛克（Josh Bloch）自己都説從來不會使用 LinkedList 。

另外，不要下意識地認為 LinkedList 作為鏈表就最適合元素增刪的場景。我在上面也説了，LinkedList 僅僅在頭尾插入或者刪除元素的時候時間複雜度近似 O(1)，其他情況增刪元素的時間複雜度都是 O(n) 。

補充內容:雙向鏈表和雙向循環鏈表

雙向鏈表： 包含兩個指針，一個 prev 指向前一個節點，一個 next 指向後一個節點。

另外推薦一篇把雙向鏈表講清楚的文章：http://juejin.cn/post/6844903648154271757

雙向循環鏈表： 最後一個節點的 next 指向 head，而 head 的 prev 指向最後一個節點，構成一個環。

補充內容:RandomAccess 接口

java public interface RandomAccess { }

查看源碼我們發現實際上 RandomAccess 接口中什麼都沒有定義。所以，在我看來 RandomAccess 接口不過是一個標識罷了。標識什麼？ 標識實現這個接口的類具有隨機訪問功能。

在 binarySearch（) 方法中，它要判斷傳入的 list 是否 RandomAccess 的實例，如果是，調用indexedBinarySearch()方法，如果不是，那麼調用iteratorBinarySearch()方法

java public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }

ArrayList 實現了 RandomAccess 接口， 而 LinkedList 沒有實現。為什麼呢？我覺得還是和底層數據結構有關！ArrayList 底層是數組，而 LinkedList 底層是鏈表。數組天然支持隨機訪問，時間複雜度為 O(1)，所以稱為快速隨機訪問。鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間複雜度為 O(n)，所以不支持快速隨機訪問。，ArrayList 實現了 RandomAccess 接口，就表明了他具有快速隨機訪問功能。 RandomAccess 接口只是標識，並不是説 ArrayList 實現 RandomAccess 接口才具有快速隨機訪問功能的！

説一説 ArrayList 的擴容機制吧

詳見筆主的這篇文章:ArrayList 擴容機制分析

Collection 子接口之 Set

comparable 和 Comparator 的區別

• comparable 接口實際上是出自java.lang包 它有一個 compareTo(Object obj)方法用來排序
• comparator接口實際上是出自 java.util 包它有一個compare(Object obj1, Object obj2)方法用來排序

一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo()方法或compare()方法，當我們需要對某一個集合實現兩種排序方式，比如一個 song 對象中的歌名和歌手名分別採用一種排序方法的話，我們可以重寫compareTo()方法和使用自制的Comparator方法或者以兩個 Comparator 來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的 Collections.sort().

Comparator 定製排序

```java ArrayList arrayList = new ArrayList(); arrayList.add(-1); arrayList.add(3); arrayList.add(3); arrayList.add(-5); arrayList.add(7); arrayList.add(4); arrayList.add(-9); arrayList.add(-7); System.out.println("原始數組:"); System.out.println(arrayList); // void reverse(List list)：反轉 Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):"); System.out.println(arrayList);

    // void sort(List list),按自然排序的升序排序
    Collections.sort(arrayList);
    System.out.println("Collections.sort(arrayList):");
    System.out.println(arrayList);
    // 定製排序的用法
    Collections.sort(arrayList, new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    System.out.println("定製排序後：");
    System.out.println(arrayList);

```

Output:

原始數組: [-1, 3, 3, -5, 7, 4, -9, -7] Collections.reverse(arrayList): [-7, -9, 4, 7, -5, 3, 3, -1] Collections.sort(arrayList): [-9, -7, -5, -1, 3, 3, 4, 7] 定製排序後： [7, 4, 3, 3, -1, -5, -7, -9]

重寫 compareTo 方法實現按年齡來排序

```java // person對象沒有實現Comparable接口，所以必須實現，這樣才不會出錯，才可以使treemap中的數據按順序排列 // 前面一個例子的String類已經默認實現了Comparable接口，詳細可以查看String類的API文檔，另外其他 // 像Integer類等都已經實現了Comparable接口，所以不需要另外實現了 public class Person implements Comparable { private String name; private int age;

public Person(String name, int age) {
    super();
    this.name = name;
    this.age = age;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public int getAge() {
    return age;
}

public void setAge(int age) {
    this.age = age;
}

/**
 * T重寫compareTo方法實現按年齡來排序
 */
@Override
public int compareTo(Person o) {
    if (this.age > o.getAge()) {
        return 1;
    }
    if (this.age < o.getAge()) {
        return -1;
    }
    return 0;
}

}

```

```java public static void main(String[] args) { TreeMap pdata = new TreeMap(); pdata.put(new Person("張三", 30), "zhangsan"); pdata.put(new Person("李四", 20), "lisi"); pdata.put(new Person("王五", 10), "wangwu"); pdata.put(new Person("小紅", 5), "xiaohong"); // 得到key的值的同時得到key所對應的值 Set keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName());

    }
}

```

Output：

5-小紅 10-王五 20-李四 30-張三

無序性和不可重複性的含義是什麼

1、什麼是無序性？無序性不等於隨機性 ，無序性是指存儲的數據在底層數組中並非按照數組索引的順序添加 ，而是根據數據的哈希值決定的。

2、什麼是不可重複性？不可重複性是指添加的元素按照 equals()判斷時 ，返回 false，需要同時重寫 equals()方法和 HashCode()方法。

比較 HashSet、LinkedHashSet 和 TreeSet 三者的異同

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的實現類，都能保證元素唯一，並且都不是線程安全的。
• HashSet、LinkedHashSet 和 TreeSet 的主要區別在於底層數據結構不同。HashSet 的底層數據結構是哈希表（基於 HashMap 實現）。LinkedHashSet 的底層數據結構是鏈表和哈希表，元素的插入和取出順序滿足 FIFO。TreeSet 底層數據結構是紅黑樹，元素是有序的，排序的方式有自然排序和定製排序。
• 底層數據結構不同又導致這三者的應用場景不同。HashSet 用於不需要保證元素插入和取出順序的場景，LinkedHashSet 用於保證元素的插入和取出順序滿足 FIFO 的場景，TreeSet 用於支持對元素自定義排序規則的場景。

Collection 子接口之 Queue

Queue 與 Deque 的區別

Queue 是單端隊列，只能從一端插入元素，另一端刪除元素，實現上一般遵循 先進先出（FIFO） 規則。

Queue 擴展了 Collection 的接口，根據 因為容量問題而導致操作失敗後處理方式的不同 可以分為兩類方法: 一種在操作失敗後會拋出異常，另一種則會返回特殊值。

| Queue 接口 | 拋出異常 | 返回特殊值 | | ------------ | --------- | ---------- | | 插入隊尾 | add(E e) | offer(E e) | | 刪除隊首 | remove() | poll() | | 查詢隊首元素 | element() | peek() |

Deque 是雙端隊列，在隊列的兩端均可以插入或刪除元素。

Deque 擴展了 Queue 的接口, 增加了在隊首和隊尾進行插入和刪除的方法，同樣根據失敗後處理方式的不同分為兩類：

| Deque 接口 | 拋出異常 | 返回特殊值 | | ------------ | ------------- | --------------- | | 插入隊首 | addFirst(E e) | offerFirst(E e) | | 插入隊尾 | addLast(E e) | offerLast(E e) | | 刪除隊首 | removeFirst() | pollFirst() | | 刪除隊尾 | removeLast() | pollLast() | | 查詢隊首元素 | getFirst() | peekFirst() | | 查詢隊尾元素 | getLast() | peekLast() |

事實上，Deque 還提供有 push() 和 pop() 等其他方法，可用於模擬棧。

ArrayDeque 與 LinkedList 的區別

ArrayDeque 和 LinkedList 都實現了 Deque 接口，兩者都具有隊列的功能，但兩者有什麼區別呢？

• ArrayDeque 是基於可變長的數組和雙指針來實現，而 LinkedList 則通過鏈表來實現。

• ArrayDeque 不支持存儲 NULL 數據，但 LinkedList 支持。

• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 時就已經存在。

• ArrayDeque 插入時可能存在擴容過程, 不過均攤後的插入操作依然為 O(1)。雖然 LinkedList 不需要擴容，但是每次插入數據時均需要申請新的堆空間，均攤性能相比更慢。

從性能的角度上，選用 ArrayDeque 來實現隊列要比 LinkedList 更好。此外，ArrayDeque 也可以用於實現棧。

説一説 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其與 Queue 的區別在於元素出隊順序是與優先級相關的，即總是優先級最高的元素先出隊。

這裏列舉其相關的一些要點：

• PriorityQueue 利用了二叉堆的數據結構來實現的，底層使用可變長的數組來存儲數據
• PriorityQueue 通過堆元素的上浮和下沉，實現了在 O(logn) 的時間複雜度內插入元素和刪除堆頂元素。
• PriorityQueue 是非線程安全的，且不支持存儲 NULL 和 non-comparable 的對象。
• PriorityQueue 默認是小頂堆，但可以接收一個 Comparator 作為構造參數，從而來自定義元素優先級的先後。

PriorityQueue 在面試中可能更多的會出現在手撕算法的時候，典型例題包括堆排序、求第K大的數、帶權圖的遍歷等，所以需要會熟練使用才行。

後記

專注 Java 原創乾貨分享，大三開源 JavaGuide （「Java學習+面試指南」一份涵蓋大部分 Java 程序員所需要掌握的核心知識。準備 Java 面試，首選 JavaGuide！），目前已經 120k+ Star。

原創不易，歡迎點贊分享，歡迎關注我在掘金的賬號，我會持續分享原創乾貨！加油，衝！

如果本文對你有幫助的話，歡迎點贊分享，這對我繼續分享&創作優質文章非常重要。感謝 🙏🏻