Java集合面試題看這篇就夠了

備戰實習，會定期的總結常考的面試題，大家一起加油！ 🎯

往期文章：

• 【面試題】計算機網路篇-10道常見面試題p1
• 【面試題】JVM篇-10道常見面試題p1
• 【面試題】Java并發篇-10道常見面試題p1
• 【面試題】Java基礎篇-常見面試題總結p1
• 【面試題】Java基礎篇-常見面試題總結p2
• 【面試題】MySQL常見面試題合集
• 【面試題】Java基礎篇-常見面試題總結p3

注意：

如果本文中有錯誤的地方，歡迎評論區指正！🍭

1.說說Java中常用的容器有哪些？

容器主要包括 Collection 和 Map 兩種，Collection 存盤著物件的集合，而 Map 存盤著鍵值對(兩個物件)的映射表，

如圖：

👨?💻面試官追問：說說集合有哪些類及他們各自的區別和特點？

• Set
  • TreeSet 基于紅黑樹實作，支持有序性操作，例如根據一個范圍查找元素的操作，但是查找效率不如 HashSet，HashSet 查找的時間復雜度為 O(1)，TreeSet 則為 O(logN)，
  • HashSet 基于HashMap實作，支持快速查找，但不支持有序性操作，并且失去了元素的插入順序資訊，也就是說使用 Iterator 遍歷 HashSet 得到的結果是不確定的，
  • LinkedHashSet 是 HashSet 的子類，并且其內部是通過 LinkedHashMap 來實作的，內部使用雙向鏈表維護元素的插入順序，
• List
  • ArrayList 基于動態陣列實作，支持隨機訪問，
  • Vector 和 ArrayList 類似，但它是執行緒安全的，
  • LinkedList 基于雙向鏈表實作，只能順序訪問，但是可以快速地在鏈表中間插入和洗掉元素，不僅如此，LinkedList 還可以用作堆疊、佇列和雙向佇列，
• Queue
  • LinkedList 可以用它來實作雙向佇列，
  • PriorityQueue 基于堆結構實作，可以用它來實作優先佇列，
  • ArrayQueue基于陣列實作，可以用它實作雙端佇列，也可以作為堆疊，

👨?💻面試官追問：說說Map有哪些類及他們各自的區別和特點？

• TreeMap 基于紅黑樹實作，
• HashMap 1.7基于陣列+鏈表實作，1.8基于陣列+鏈表+紅黑樹，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突），JDK1.8 以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷，如果當前陣列的長度小于 64，那么會選擇先進行陣列擴容，而不是轉換為紅黑樹）時，將鏈表轉化為紅黑樹，以減少搜索時間，
• HashTable 和 HashMap 類似，但它是執行緒安全的，這意味著同一時刻多個執行緒可以同時寫入 HashTable 并且不會導致資料不一致，它是遺留類，不應該去使用它，（現在可以使用 ConcurrentHashMap 來支持執行緒安全，并且 ConcurrentHashMap 的效率會更高(1.7 ConcurrentHashMap 引入了分段鎖, 1.8 引入了紅黑樹)，）
• LinkedHashMap繼承自 HashMap，使用雙向鏈表來維護元素的順序，順序為插入順序或者最近最少使用(LRU)順序，

2.詳細說說 Arraylist 和 LinkedList的區別?

• ArrayList：底層是基于陣列實作的，查找快，增刪較慢，LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持，快速隨機訪問就是通過元素的序號快速獲取元素物件(對應于get(int index)方法)，
• LinkedList：底層是基于鏈表實作的，確切的說是回圈雙向鏈表(JDK1.6之前是雙向回圈鏈表、JDK1.7之后取消了回圈)，查找慢、增刪快，LinkedList鏈表由一系串列項連接而成，一個表項包含3個部分︰元素內容、前驅表和后驅表，因此記憶體空間占用比ArrayList 更多，

👨?💻面試官追問：ArrayList的增刪一定比LinkedList要慢嗎？

不一定的，

1. 如果增刪都是在末尾來操作（每次呼叫的都是 remove() 和 add()），此時 ArrayList就不需要移動和復制陣列來進行操作了，如果資料量有百萬級的時，速度是會比 LinkedList 要快的，
2. 如果洗掉操作的位置是在中間，由于LinkedList的消耗主要是在遍歷上，ArrayList的消耗主要是在移動和復制上(底層呼叫的是arrayCopy()方法，是native方法)，LinkedList 的遍歷速度是要慢于ArrayList的復制移動速度的，如果資料量有百萬級的時，還是ArrayList要快，

3.ArrayList實作 RandomAccess介面有何作用？

public interface RandomAccess {
}

查看原始碼我們發現實際上 RandomAccess 介面中什么都沒有定義，

從原始碼可以看出RandomAccess 介面只是一個標志介面，只要List集合實作這個介面，就能支持快速隨機訪問，通過查看Collections類中的binarySearch()方法，可以看出，判斷List是否實作RandomAccess介面來實行indexedBinarySerach(list, key)或 iteratorBinarySerach(list, key)方法，再通過查看這兩個方法的原始碼發現：實作RandomAccess介面的List集合采用一般的 for回圈遍歷，而未實作這介面則采用迭代器，即ArrayList 一般采用for回圈遍歷，而 LinkedList 一般采用迭代器遍歷

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);
}

👨?💻面試官追問：為何LinkedList卻沒實作這個介面？

ArrayList 底層是陣列，而 LinkedList 底層是鏈表，

陣列天然支持隨機訪問，時間復雜度為 O(1)，所以稱為快速隨機訪問，鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間復雜度為 O(n)，所以不支持快速隨機訪問，

ArrayList 實作了 RandomAccess 介面，就表明了他具有快速隨機訪問功能， RandomAccess 介面只是標識，并不是說 ArrayList 實作 RandomAccess 介面才具有快速隨機訪問功能的！

4.說一說Vector 和 ArrayList 的區別？

他們兩個都實作了List介面，底層資料結構都是陣列，

不同的是：

1. vector通過remove、add等方法加上synchronized關鍵字實作執行緒同步，所以是執行緒安全的，而ArrayList是執行緒不安全的
2. 由于vector使用了synchronized進行加鎖，所以性能不如ArrayList
3. Vector 擴容時，如果未指定擴容遞增值capacityIncrement，或該值不大于 0 時，每次擴容為原來的 2 倍，否則擴容量為capacityIncrement的值，ArrayList每次擴容為舊容量的1.5倍

5.說說ArrayList 的擴容機制？

1. 當使用add方法的時候首先呼叫ensureCapacityInternal方法，傳入 size+1進去，檢查是否需要擴容

2. 如果空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化為默認大小10，獲取“默認的容量”和要擴容的大小兩者之間的最大值

3. 和當前陣列長度比較，如果 if (minCapacity - elementData.length > 0)執行grow擴容方法

4. 將陣列擴容為原來的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);

5. 檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當作陣列的新容量

6. 再檢查新容量newCapacity 是否超出了ArrayList所定義的最大容量，若超出了，則呼叫hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE，如果minCapacity大于MAX_ARRAY_SIZE，則新容量則為Interger.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）

7. ArrayList 中copy陣列的核心就是System.arraycopy方法，將original陣列的所有資料復制到copy陣列中，這是一個本地方法

詳細的擴容原始碼可以參考：https://blog.csdn.net/qq_45966440/article/details/122270715?spm=1001.2014.3001.5501

6.Array和ArrayList有何區別？

• Array可以容納基本型別和物件，而ArrayList只能容納物件
• Array是指定大小的，ArrayList 的容量是根據需求自動擴展
• ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等

👨?💻面試官追問：什么時候更適合使用Array？

1. 如果串列的大小已經指定，大部分情況下是存盤和遍歷它們可以使用Array
2. 對于基本型別資料，ArrayList 使用自動裝箱來減少編碼作業量；而當處理固定大小的基本資料型別的時候，這種方式相對比較慢，這時候應該使用Array
3. 如果你要使用多維陣列，使用[][]比 List更容易

7.遍歷一個List有哪些不同的方式？

先說一下常見的元素在記憶體中的存盤方式，主要有兩種:

1. 順序存盤(Random Access)：相鄰的資料元素在記憶體中的位置也是相鄰的，可以根據元素的位置讀取元素，
2. 鏈式存盤(Sequential Access)：每個資料元素包含它下一個元素的記憶體地址，在記憶體中不要求相鄰，例如LinkedList，

主要的遍歷方式主要有三種：

1. for回圈遍歷：遍歷者自己在集合外部維護一個計數器，依次讀取每一個位置的元素
2. Iterator遍歷：基于順序存盤集合的Iterator可以直接按位置訪問資料，基于鏈式存盤集合的Iterator，需要保存當前遍歷的位置，然后根據當前位置來向前或者向后移動指標
3. foreach遍歷：也就是增強for回圈，foreach內部也是采用了Iterator的方式實作，但使用時不需要顯示地宣告Iterator

代碼如下：

public class TestLinkedList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        //for回圈遍歷
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        //Iterator遍歷
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        //foreach遍歷
        for (String s : list) {
            System.out.println(s);
        }
    }
}

👨?💻面試官追問：那么對于以上三種遍歷方式應該如何選取呢？

在Java集合框架中，提供了一個RandomAccess介面，該介面沒有方法，只是一個標記，通常用來標記List的實作是否支持RandomAccess，所以在遍歷時，可以先判斷是否支持RandomAccess ( list instanceof RandomAccess)，如果支持可用for回圈遍歷，否則建議用Iterator或 foreach遍歷，

8.comparable和comparator的區別？

• comparable介面出自java.lang包，可以理解為一個內比較器，因為實作了comparable介面的類可以和自己比較，要和其他實作了Comparable介面類比較，可以使用compareTo(objectobj)方法，compareTo方法的回傳值是int，有三種情況：
  1. 回傳正整數（比較者大于被比較者）
  2. 回傳0（比較者等于被比較者）
  3. 回傳負整數（比較者小于被比較者）
• comparator介面出自java.util包，它有一個compare(object obj1，object obj2)方法用來排序，回傳值同樣是int，有三種情況，和compareTo類似，

它們之間的區別：

1. 很多包裝類都實作了comparable介面，像Integer、string等，所以直接呼叫co1lections.sort()直接可以使用，如果對類里面自帶的自然排序不滿意，而又不能修改其源代碼的情況下，使用comparator就比較合適，
2. 此外使用comparator可以避免添加額外的代碼與我們的目標類耦合，同時可以定義多種排序規則，這一點是comparable介面沒法做到的
3. 從靈活性和擴展性講Comparator更優，故在面對自定義排序的需求時，可以優先考慮使用comparator介面，

9.Collection和Collections有什么區別？

• Collection：是最基本的集合介面，它提供了對集合物件進行基本操作的通用介面方法，一個Collection代表一組Object，即Collection的元素，它的直接繼承介面有List，Set 和Queue，
• Collections：是不屬于Java的集合框架的，它是集合類的一個工具類，此類不能被實體化，服務于Java的Collection框架，它包含有關集合操作的靜態多型方法，實作對各種集合的搜索、排序、執行緒安全等操作，

10.說一下PriorityQueue？

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

它有這些特點：

• PriorityQueue 利用了二叉堆的資料結構來實作的，底層使用可變長的陣列來存盤資料，
• PriorityQueue 通過堆元素的上浮和下沉，實作了在 O(logn) 的時間復雜度內插入元素和洗掉堆頂元素，
• PriorityQueue 是非執行緒安全的，且不支持存盤 NULL 和 non-comparable 的物件，
• PriorityQueue 默認是小頂堆，但可以接收一個 Comparator 作為構造引數，從而來自定義元素優先級的先后，
• 默認容量是11，當陣列比較小（小于64）的時候每次擴容容量翻倍，當陣列比較大（大于等于64）的時候每次擴容只增加一半的容量，
• PriorityQueue不是有序的，只有堆頂存盤著最小的元素

可以參考PriorityQueue原始碼：https://blog.csdn.net/qq_45966440/article/details/122273598?spm=1001.2014.3001.5501

11.說一下HashSet的實作原理？

HashSet 的實作是依賴于HashMap的，HashSet 的值都是存盤在HashMap中的，在 HashSet 的構造法中會初始化一個HashMap物件，HashSet 不允許值重復，因此，HashSet的值是作為HashMap的key存盤在HashMap 中的，當存盤的值已經存在時回傳false，

👨?💻面試官追問：HashSet有哪些特點？

• 無序性（存盤元素無序）
• 唯一性（允許使用null）本質上，HashSet的值是作為HashMap的key存盤在HashMap 中的，因此保證唯一性
• HashSet沒有提供get()方法，同HashMap一樣，因為Set內部是無序的，所以只能通過迭代的方式獲得

12.HashMap的實作原理/底層資料結構？

• JDK1.7：陣列 + 鏈表
• JDK1.8：陣列 + （鏈表 | 紅黑樹）

HashMap 通過 key 的 hashCode 經過擾動函式處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當前元素存放的位置（這里的 n 指的是陣列的長度），如果當前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆寫，不相同就通過拉鏈法解決沖突，

所謂擾動函式指的就是 HashMap 的 hash 方法，使用 hash 方法也就是擾動函式是為了防止一些實作比較差的 hashCode() 方法 換句話說使用擾動函式之后可以減少碰撞，

JDK1.8的hash方法：

static final int hash(Object key) {
    int h;
    // key.hashCode()：回傳散列值也就是hashcode
    // ^ ：按位異或
    // >>>:無符號右移，忽略符號位，空位都以0補齊
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

JDK1.7的hash方法：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

從原始碼可以看出JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加簡化，但是原理不變，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次，

13.HashMap 的長度為什么是 2 的冪次方？

1. 計算索引時效率更高：hash % tab.length，而計算機中直接求余運算效率不如位移運算，所以原始碼中做了優化，使用 hash & (tab.length- 1)來尋找桶位，而實際上 hash % length 等于 hash & ( length - 1) 的前提是 length 必須為 2 的 n 次冪
2. 擴容時重新計算索引效率更高： hash & oldCap == 0 的元素留在原來位置 ，否則新位置 = 舊位置 + oldCap
3. 當根據 key 的 hash 值尋址計算確定桶位下標 index 時，如果HashMap 的陣列長度 tab.length 是 2 的 n 次冪數，那么就可以保證新插入陣列中的資料均勻分布，每個桶位都有可能分配到資料，而如果陣列長度不是 2 的 n 次冪數，那么就可能導致一些桶位上永遠不會被插入到資料，反而有些桶位頻繁發生 hash 沖突，導致陣列空間浪費，沖hash 突概率增加，

14.說說HashMap的put方法執行流程？

1. 計算key的hash值
2. 如果桶（陣列）數量為0，則初始化桶
3. 如果key所在的桶沒有元素，則直接插入
4. 如果key所在的桶中的第一個元素的key與待插入的key相同，說明找到了元素，轉后續流程（9）處理
5. 如果第一個元素是樹節點，則呼叫樹節點的putTreeVal()尋找元素或插入樹節點
6. 如果不是以上三種情況，則遍歷桶對應的鏈表查找key是否存在于鏈表中
7. 如果找到了對應key的元素，則轉后續流程（9）處理
8. 如果沒找到對應key的元素，則在鏈表最后插入一個新節點并判斷是否需要樹化
9. 如果找到了對應key的元素，則判斷是否需要替換舊值，并直接回傳舊值
10. 如果插入了元素，則數量加1并判斷是否需要擴容

詳細的HashMap方法執行程序可以參考：【JDK原始碼】HashMap原始碼分析（附常見面試題）

15.說說HashMap的get方法執行流程？

1. 計算key的hash值
2. 找到key所在的桶及其第一個元素
3. 如果第一個元素的key等于待查找的key，直接回傳
4. 如果第一個元素是樹節點就按樹的方式來查找
5. 否則就按鏈表方式查找
6. 如果都沒有，回傳null

16.說說HashMap的resize方法執行程序？

1. 如果使用是默認構造方法，則第一次插入元素時初始化為默認值，容量為16，擴容門檻為12
2. 如果使用的是非默認構造方法，則第一次插入元素時初始化容量等于擴容門檻，擴容門檻在構造方法里等于傳入容量向上最近的2的n次方
3. 如果舊容量大于0，則新容量等于舊容量的2倍，但不超過最大容量2的30次方，新擴容門檻為舊擴容門檻的2倍
4. 創建一個新容量的桶
5. 搬移元素，原鏈表分化成兩個鏈表，低位鏈表存盤在原來桶的位置，高位鏈表搬移到原來桶的位置加舊容量的位置

關于這部分建議詳細看看原始碼：【JDK原始碼】HashMap原始碼分析（附常見面試題）

17.HashMap什么時候會樹化？

必須滿足兩個條件：

• 鏈表長度超過樹化閾值>8
• 陣列容量>=64

當鏈表長度超過樹化閾值 8 時，先嘗試擴容來減少鏈表長度，如果陣列容量已經 >=64，才會進行樹化，

👨?💻面試官追問：那什么時候樹化退化？

• 情況1：在擴容時如果拆分樹時，樹元素個數 <= 6 則會退化鏈表
• 情況2：移除之前，remove 樹節點時，若 root、root.left、root.right、root.left.left 有一個為 null ，也會退化為鏈表

18.HashMap底層為什么選擇紅黑樹而不用其他樹，比如二叉查找樹？

二叉查找樹在特殊情況下也會變成一條線性結構，和原先的長鏈表存在一樣的深度遍歷問題，查找性能慢，如圖：

使用紅黑樹主要是為了提升查找資料的速度，紅黑樹是平衡二叉樹的一種，插入新資料（新資料初始是紅色結點插入）后會通過左旋，右旋，變色等操作來保持平衡，解決單鏈表查詢深度的問題，

👨?💻面試官追問：那為什么要將鏈表中轉紅黑樹的閾值設為8？

之所以以 8 為樹化門檻，是因為經過大量測驗，8 這個值是最合適的，理想情況下，使用隨機的哈希碼，節點分布在 hash 桶中的頻率遵循泊松分布，按照泊松分布的公式計算，長度超過 8 的鏈表出現概率是 0.00000006，樹化閾值選擇 8 就是為了讓樹化幾率足夠小

👨?💻面試官繼續追問：那為什么不一開始直接使用紅黑樹？

• 當鏈表資料量少的時候，遍歷線性鏈表比遍歷紅黑樹消耗的資源少 (因為少量資料，紅黑樹本身自選、變色保持平衡也是需要消耗資源的)，所以前期使用線性表，
• 然后TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用鏈表

19.HashMap擴容（加載）因子為何默認是 0.75f？

1. 在空間占用與查詢時間之間取得較好的權衡
2. 大于這個值，空間節省了，但鏈表就會比較長影響性能
3. 小于這個值，沖突減少了，但擴容就會更頻繁，空間占用也更多

20.HashMap怎么計算 key 的 hash 值的？

我們先看原始碼：

static final int hash(Object key) {
    int h;
    //key==null直接回傳0
    //1、否則呼叫key的hashCode()方法計算出key的哈希值然后賦值給h,
    //2、h >>> 16，后與h無符號右移16位后的二進制進行按位異或得到最后的hash值,
    //3、這樣做是為了使計算出的hash更分散，讓高16位可以參與（低16位具有高16位的特征）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以看出：

1. 首先，計算物件的 hashCode()
2. 然后將 key 的 hashCode 的高 16 位和 hashCode 低 16 位 進行異或（XOR）運算，最終得到新的 hash 值，二次 hash() 是為了綜合高位資料，讓哈希分布更為均勻

關于第二點，這里舉個例子就知道了：

我們知道，HashMap 新插入的資料需要經過尋址演算法 index = hash & (tab.length - 1)來確定桶位下標，tab.length就是陣列長度，我們這里設其為 n，

如果當 n 即陣列長度很小，假設是 n = 16 的話，那么 n - 1 是 15 ，其二進制數為 1111 ，這樣的值和 hashCode 直接做按位與操作，實際上只使用了哈希值的后 4 位，如果當哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，所以這里把高低位都利用起來，從而解決了這個問題

我們來看一個分析圖：

由上圖，可以知道如果只使用 key.hashCode()方法計算得到的 hash 值，那么當 hash 值高位變化較大，而低位變化較小時，通過尋址演算法 hash & (tab.length - 1) 得到的桶位下標 index 就更容易出現 hash 沖突了！

21.HashMap是怎么解決哈希沖突的？

哈希沖突：hashMap在存盤元素時會先計算key的hash值來確定存盤位置，因為key的hash值計算最后有個對陣列長度取余的操作，所以即使不同的key也可能計算出相同的hash值，這樣就引起了hash沖突，hashMap的底層結構中的鏈表/紅黑樹就是用來解決這個問題的，

HashMap中的哈希沖突解決方式可以主要從三方面考慮（以JDK1.8為背景)

1. 拉鏈法
   HasMap中的資料結構為陣列+鏈表/紅黑樹，當不同的key計算出的hash值相同時，就用鏈表的形式將Node結點（沖突的key及key對應的value)掛在陣列后面，
2. hash函式
   key的hash值經過兩次擾動， key的hashcode值與key的hashcode值的右移16位進行異或，然后對陣列的長度取余（實際為了提高性能用的是位運算，但目的和取余一樣)，這樣做可以讓hashcode取值出的高位也參與運算，進一步降低hash沖突的概率，使得資料分布更平均，
3. 紅黑樹
   在拉鏈法中，如果hash沖突特別嚴重，則會導致陣列上掛的鏈表長度過長，性能變差，因此在鏈表長度大于8時，將鏈表轉化為紅黑樹，可以提高遍歷鏈表的速度，

22.HashMap多執行緒操作導致死回圈問題知道嗎?

在jdk1.7之前，主要原因在于并發下的 Rehash 會造成元素之間會形成一個回圈鏈表，不過，jdk 1.8 后解決了這個問題，但是還是不建議在多執行緒下使用 HashMap,因為多執行緒下使用 HashMap 還是會存在其他問題比如資料丟失，并發環境下推薦使用 ConcurrentHashMap ，

這部分建議詳細參考：hashmap擴容時死回圈問題

23.說說LinkedHashMap 的實作原理？

• LinkedHashMap也是基于HashMap 實作的，不同的是它定義了一個Entry header，這個header不是放在Table里，它是額外獨立出來的，LinkedHashMap通過繼承hashMap 中的Entry，并添加兩個屬性Entrybefore，after和 header結合起來組成一個雙向鏈表，來實作按插入順序或訪問順序排序，
• LinkedHashMap定義了排序模式 accessOrder，該屬性為boolean型變數，對于訪問順序，為true，對于插入順序，則為false，一般情況下，不必指定排序模式，其迭代順序即為默認為插入順序，

24.說說HashMap 和 HashSet 區別？

HashSet 底層就是基于 HashMap 實作的，兩者主要區別：

25.說下HashMap 和 Hashtable 的區別？

1. 執行緒是否安全： HashMap 是非執行緒安全的，Hashtable 是執行緒安全的,因為 Hashtable 內部的方法基本都經過synchronized 修飾，（如果你要保證執行緒安全的話就使用 ConcurrentHashMap 吧！）

2. **效率：**因為Hashtable加了synchronized鎖，所以HashMap 要比 Hashtable 效率高一點，另外，Hashtable 基本被淘汰，不要在代碼中使用它

3. 對 Null key 和 Null value 的支持： HashMap 可以存盤 null 的 key 和 value，但 null 作為鍵只能有一個，null 作為值可以有多個；Hashtable 不允許有 null 鍵和 null 值，否則會拋出 NullPointerException，

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

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

   ② 創建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為 2 的冪次方大小，也就是說 HashMap 總是使用 2 的冪作為哈希表的大小，

5. 底層資料結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷，如果當前陣列的長度小于 64，那么會選擇先進行陣列擴容，而不是轉換為紅黑樹）時，將鏈表轉化為紅黑樹，以減少搜索時間，Hashtable 沒有這樣的機制，

26.說一下HashMap 和 TreeMap 區別？

TreeMap 和HashMap 都繼承自AbstractMap ，但是需要注意的是TreeMap它還實作了NavigableMap介面和SortedMap 介面，

• 實作 NavigableMap 介面讓 TreeMap 有了對集合內元素的搜索的能力，
• 實作SortedMap介面讓 TreeMap 有了對集合中的元素根據鍵排序的能力，默認是按 key 的升序排序，不過我們也可以指定排序的比較器，

示例代碼如下：

/**
 * @author xppll
 * @date 2022/1/1 21:35
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }

    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>((o1, o2) -> {
            return Integer.compare(o1.getAge() - o2.getAge(), 0);
        });
        treeMap.put(new Person(2), "person1");
        treeMap.put(new Person(42), "person2");
        treeMap.put(new Person(22), "person3");
        treeMap.put(new Person(10), "person4");
        treeMap.forEach((key, value) -> System.out.println(value));
    }
}
//輸出：
person1
person4
person3
person2

可以看出，TreeMap 中的元素已經是按照 Person 的 age 欄位的升序來排列了，

綜上，相比于HashMap來說 TreeMap 主要多了對集合中的元素根據鍵排序的能力以及對集合內元素的搜索的能力

27.為什么HashMap中String、Integer這樣的包裝類適合作為Key?

1. 這些包裝類都是final修飾，是不可變性的，保證了key的不可更改性，不會出現放入和獲取時哈希值不同的情況，
2. 它們內部已經重寫過hashcode() ， equal()等方法，

👨?💻面試官追問：如果使用Object作為HashMap的Key，應該怎么辦呢？

1. 重寫hashcode()方法，因為需要計算hash值確定存盤位置
2. 重寫equals()方法，因為需要保證key的唯一性

👨?💻面試官繼續追問：能否使用任何類作為Map 的key？

可以，但要注意以下兩點:

1. 如果類重寫了equals()方法，也應該重寫hashcode()方法，
2. 最好定義key類是不可變的，這樣key對應的hashcode()值可以被快取起來，性能更好，這也是為什么string特別適合作為HashMap 的key ，

28.說一下Queue 與 Deque 的區別？

Queue 是單端佇列，只能從一端插入元素，另一端洗掉元素，實作上一般遵循 先進先出（FIFO） 規則，Queue 擴展了 Collection 的介面，根據 因為容量問題而導致操作失敗后處理方式的不同 可以分為兩類方法: 一種在操作失敗后會拋出例外，另一種則會回傳特殊值，

Deque 是雙端佇列，在佇列的兩端均可以插入或洗掉元素，Deque 擴展了 Queue 的介面, 增加了在隊首和隊尾進行插入和洗掉的方法，同樣根據失敗后處理方式的不同分為兩類：

除此之外，Deque 還提供有 push() 和 pop() 等其他方法，可用于模擬堆疊，

29.說說ArrayDeque 與 LinkedList 的區別？

ArrayDeque 和 LinkedList 都實作了 Deque 介面，兩者都具有佇列的功能，也都可以實作堆疊，連著區別：

• ArrayDeque 是基于可變長的陣列和雙指標來實作，而 LinkedList 則通過鏈表來實作，
• ArrayDeque 不支持存盤 NULL 資料，但 LinkedList 支持，
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 時就已經存在，
• ArrayDeque 插入時可能存在擴容程序, 不過均攤后的插入操作依然為 O(1)，雖然 LinkedList 不需要擴容，但是每次插入資料時均需要申請新的堆空間，均攤性能相比更慢，

從性能的角度上，選用 ArrayDeque 來實作佇列要比 LinkedList 更好，

ArrayDeque 原始碼可以參考：【JDK原始碼】ArrayDeque原始碼分析

LinkedList 原始碼可以參考：【JDK原始碼】LinkedList原始碼分析

30.說一下 HashSet、LinkedHashSet 和 TreeSet 三者的異同？

HashSet、LinkedHashSet 和 TreeSet 都是 Set 介面的實作類，都能保證元素唯一，并且都不是執行緒安全的，他們的不同點：

• HashSet、LinkedHashSet 和 TreeSet 的主要區別在于底層資料結構不同：
  1. HashSet 的底層資料結構是哈希表（基于 HashMap 實作）
  2. LinkedHashSet 的底層資料結構是鏈表和哈希表，元素的插入和取出順序滿足 FIFO
  3. TreeSet 底層資料結構是紅黑樹，元素是有序的，排序的方式有自然排序和定制排序
• 底層資料結構不同又導致這三者的應用場景不同：
  1. HashSet 用于不需要保證元素插入和取出順序的場景
  2. LinkedHashSet 用于保證元素的插入和取出順序滿足 FIFO 的場景
  3. TreeSet 用于支持對元素自定義排序規則的場景

參考文章：

• https://blog.csdn.net/qq_45966440/category_10889559.html
• https://blog.csdn.net/weixin_43591980/category_10638797.html?spm=1001.2014.3001.5515
• https://javaguide.cn/java/basis/java%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93/
• https://pdai.tech/