專欄簡介

八股戰神篇專欄是基于各平臺共上千篇面經，上萬道面試題，進行綜合排序提煉出排序前百的高頻面試題，并對這些高頻八股進行關聯分析，將每個高頻面試題可能進行延伸的題目再次進行排序選出高頻延伸八股題。面試官都是以點破面從一個面試題不斷深入，目的是測試你的理解程度。本專欄將解決你的痛點，助你從容面對。本專欄已更新Java基礎高頻面試題、Java集合高頻面試題、MySQL高頻面試題，后續會更新JUC、JVM、Redis、操作系統、計算機網絡、設計模式、場景題等，計劃在七月前更新完畢（趕在大家高頻面試前）點此鏈接訂閱專欄“八股戰神篇”

一 常見的集合類型有哪些？

Java 集合框架分為單列集合和雙列集合兩大類。

首先是單列集合，它以 Collection 為核心接口，主要分為三種：

第一種是 List，用于存儲有序且可重復的元素，比如 ArrayList 基于動態數組，訪問快但插入刪除慢；LinkedList 基于雙向鏈表，插入刪除快但訪問慢；Vector 是線程安全的老版本實現。

第二種是 Set，用于存儲無序且不可重復的元素，比如 HashSet 基于哈希表，查找快但無序；LinkedHashSet 保留插入順序；TreeSet 基于紅黑樹，按順序存儲。

第三種是 Queue，用于隊列操作，比如 PriorityQueue 基于堆實現按優先級處理，ArrayDeque 是雙端隊列支持棧和隊列操作。

接下來是雙列集合，它以 Map 為核心接口，用于存儲鍵值對，比如：HashMap 基于哈希表，鍵無序且查找快；LinkedHashMap 保留插入順序；TreeMap 基于紅黑樹，按鍵的自然順序排序；Hashtable 是線程安全的老版本實現。

延伸

1，集合體系結構圖

為了更好理解，可以參考以下簡單的結構：

Collection|-- List| ? ? |-- ArrayList| ? ? |-- LinkedList|-- Set| ? ? |-- HashSet| ? ? |-- TreeSet|-- Queue|-- LinkedList|-- PriorityQueue
Map|-- HashMap|-- TreeMap|-- LinkedHashMap

2，集合的選擇

• 如果需要快速查詢：使用 HashSet 或 HashMap。

• 如果需要排序：使用 TreeSet 或 TreeMap。

• 如果需要保證插入順序：使用 LinkedHashSet 或 LinkedHashMap。

• 如果需要動態大小的數組：使用 ArrayList。

• 如果需要頻繁插入刪除：使用 LinkedList。

3，如果只有單列集合，沒有雙列集合，會發生什么？

雙列集合最核心的特性是以鍵值對形式存儲數據，每個鍵唯一且對應一個值。如果沒有雙列集合，會導致：

需要手動管理鍵值關系： 開發者需要用單列集合（如List）分別存儲鍵和值，自己維護它們的對應關系，增加了開發復雜度。

效率低下： 查找某個鍵對應的值需要遍歷整個鍵的集合，而不是像Map一樣通過哈希或排序快速定位。

二 ArrayList和LinkedList的區別？

ArrayList 和 LinkedList 是 Java 中常用的兩個 List 接口實現類。它們在底層數據結構和性能上有很大的區別，各有優缺點，適用于不同的場景。以下是它們詳細的區別。

第一點是底層實現不同

ArrayList：基于 動態數組 實現，元素連續存儲，支持通過索引直接訪問元素（隨機訪問），數組容量不足時會進行 動態擴容。

LinkedList：基于 雙向鏈表 實現，每個節點包含一個數據部分和兩個指針，分別指向前一個和后一個節點，不支持通過索引直接訪問，需要通過遍歷找到對應位置的元素。

第二點是訪問性能不同

ArrayList：隨機訪問性能優越，時間復雜度為 O(1)，因為可以直接通過索引訪問，適合頻繁讀取元素的場景，例如：根據索引獲取數據。

LinkedList：隨機訪問性能較差，時間復雜度為 O(n)，需要從頭或尾部開始遍歷才能找到對應的元素，不適合頻繁讀取或按索引訪問元素的場景。

第三點是插入和刪除性能不同

ArrayList：插入或刪除操作（非尾部）可能涉及大量數據的移動，時間復雜度為 O(n)，刪除或插入元素時，所有后續元素都需要移動，尤其是在列表中間插入或刪除元素時，在 尾部插入 元素的時間復雜度通常是 O(1)，但當數組容量不足時會觸發 擴容，導致性能下降。

LinkedList：插入或刪除操作性能更優（非索引訪問場景），時間復雜度為 O(1)，只需調整鏈表指針即可，但如果通過索引訪問位置后再插入或刪除，則時間復雜度為 O(n)，適合頻繁在列表頭部或中間插入和刪除元素的場景。

第四點是擴容效率的不同

ArrayList：插入時，如果空間不足需要擴容，擴容會新建一個更大的數組，并將舊數據復制過去，影響性能。

LinkedList：沒有容量的概念，插入時只需更新節點指針，不涉及擴容操作。

第五點是內存使用效率的不同

ArrayList：內存利用率較高，僅存儲實際數據，數組容量不足時會擴容（默認擴容為原容量的 1.5 倍），可能導致一定的內存浪費，擴容操作需要復制整個數組，會消耗時間和內存。

LinkedList：內存開銷較大，每個節點需要額外存儲兩個指針（prev 和 next），不會發生擴容問題，因為它是基于鏈表實現的，當數據量較大時，鏈表的額外指針開銷可能顯著增加內存使用。

第六點是使用場景的不同

場景	選擇
需要頻繁按索引訪問元素	ArrayList
需要頻繁在中間或兩端插入、刪除元素	LinkedList
數據量較大，內存效率要求高	ArrayList
數據量不大，頻繁插入刪除	LinkedList

代碼示例

1. 隨機訪問性能對比

import java.util.*;
?
public class AccessPerformanceTest {public static void main(String[] args) {List<Integer> arrayList = new ArrayList<>();List<Integer> linkedList = new LinkedList<>();
?// 初始化數據for (int i = 0; i < 100000; i++) {arrayList.add(i);linkedList.add(i);}
?// 測試 ArrayList 的隨機訪問性能long start = System.nanoTime();arrayList.get(50000);long end = System.nanoTime();System.out.println("ArrayList 隨機訪問時間: " + (end - start) + " ns");
?// 測試 LinkedList 的隨機訪問性能start = System.nanoTime();linkedList.get(50000);end = System.nanoTime();System.out.println("LinkedList 隨機訪問時間: " + (end - start) + " ns");}
}
輸出示例：ArrayList 隨機訪問時間: 100 ns
LinkedList 隨機訪問時間: 20000 ns

2. 插入和刪除性能對比

import java.util.*;
?
public class InsertPerformanceTest {public static void main(String[] args) {List<Integer> arrayList = new ArrayList<>();List<Integer> linkedList = new LinkedList<>();
?// 測試在頭部插入性能long start = System.nanoTime();for (int i = 0; i < 10000; i++) {arrayList.add(0, i);}long end = System.nanoTime();System.out.println("ArrayList 頭部插入時間: " + (end - start) + " ns");
?start = System.nanoTime();for (int i = 0; i < 10000; i++) {linkedList.add(0, i);}end = System.nanoTime();System.out.println("LinkedList 頭部插入時間: " + (end - start) + " ns");}
}
輸出示例：ArrayList 頭部插入時間: 50000000 ns
LinkedList 頭部插入時間: 2000000 ns

延伸

1，說一下ArrayList的默認大小？它是如何進行擴容的？
在 Java 中，ArrayList 的初始默認容量為 10。

當通過無參構造函數創建一個 ArrayList 時：

ArrayList?list = new ArrayList<>();
此時 ArrayList 的容量并未真正分配。

當第一次向 ArrayList 添加元素時（如 list.add(1)），它會分配默認大小為 10 的數組。
當 ArrayList 中的元素數量超過當前容量時，ArrayList 會自動擴容。當數組容量不足時，ArrayList 會將容量擴展為 原容量的 1.5 倍，創建一個新的更大的數組。將原數組中的元素拷貝到新數組中。

示例：

新容量計算公式：

newCapacity = oldCapacity + (oldCapacity >> 1);

初始容量為 10，當元素數量超過 10 時：

第一次擴容：容量從 10 擴展為 15。

第二次擴容：容量從 15 擴展為 22。

依此類推。

2，ArrayList是線程安全的嗎？為什么？

ArrayList?不是線程安全的。這是因為?ArrayList?的設計目標是為了在單線程環境下提供高性能，而沒有對多線程環境提供內置的線程同步機制。

因為?ArrayList?的底層結構是基于動態數組實現的，它的底層是一個?Object[]?數組，用來存儲元素。當需要添加、刪除或修改元素時，ArrayList?會直接操作這個數組。

• 在單線程環境下，這種設計性能高效。
• 但在多線程環境下，如果多個線程同時操作同一個?ArrayList?實例，可能會引發數據不一致或異常。

3，ArrayList是否有容量限制？

ArrayList?是 Java 中基于動態數組實現的列表。理論上，ArrayList?的容量限制取決于 JVM 所能分配的最大內存，具體限制與可用的堆內存大小和數組的實現有關。

理論限制：

• 最大容量為?Integer.MAX_VALUE - 8（即約 2^31 – 1 個元素，約 2.1 billion 個），這是由數組在 JVM 中的實現所決定的。
• 實際限制：受到可用內存的約束，通常在大量數據時可能會觸發?OutOfMemoryError。

三 HashMap的原理是什么？

HashMap 是一種基于哈希表的鍵值對存儲數據結構，它的查找很高效，存儲性能較好，被廣泛用于高效管理和訪問數據。HashMap 的實現基于數組和鏈表或紅黑樹，JDK 8之前是數組+鏈表，JDK 8及之后是數組+鏈表+紅?樹。接下來我會講述put方法和get方法的核心邏輯。

put方法：在 HashMap 中，put 方法的核心邏輯是將一個鍵值對插入到 HashMap 中。其執行流程主要包括以下步驟：

1. 計算鍵的哈希值 根據 hashCode() 方法計算鍵的哈希值，然后通過哈希值定位鍵值對應該存儲的桶（bucket）。

2. 定位桶位置 使用哈希值對數組的長度取模，確定鍵值對存儲的位置。

3. 檢查沖突（是否有相同哈希值的鍵）

   • 如果桶為空，直接插入鍵值對。

   • 如果桶中已有元素（發生哈希沖突），遍歷桶中的鏈表或樹結構：

     • 如果找到相同的鍵（通過 equals 方法判斷），則替換舊值為新值。

     • 如果未找到相同的鍵，則將鍵值對插入到鏈表末尾或樹中。

4. 樹化檢查 如果鏈表長度超過閾值（默認 8），鏈表會轉換為紅黑樹以提高性能。

5. 擴容檢查 如果插入新鍵值對后，HashMap 的實際元素數量超過了負載因子閾值（loadFactor），會觸發擴容（默認將容量翻倍）。

get方法：HashMap 的 get(Object key) 方法用于根據鍵（key）獲取對應的值（value）。其核心邏輯是：

1. 根據鍵的 hashCode() 計算哈希值，確定該鍵所在的桶（bucket）。

2. 遍歷該桶中的鏈表（或紅黑樹）來查找目標鍵。

3. 如果找到對應的鍵，返回其對應的值；否則返回 null。

延伸

1，鏈表到紅黑樹的轉換條件是什么？

默認鏈表長度超過 8 時轉換為紅黑樹，減少鏈表查找時間復雜度（從 O(n) 降到 O(log n)）。

2，HashMap為什么采用紅黑樹而不是采用B+樹？

在 HashMap 的實現中，鏈表長度超過一定閾值（默認 8）時會轉換為紅黑樹，而不是 B+ 樹，主要原因如下：

時間復雜度：紅黑樹是一種平衡二叉搜索樹，查找、插入、刪除的時間復雜度是 O(log n)。B+ 樹雖然在數據庫中有優勢，但其設計更適合磁盤存儲和范圍查詢，不適合頻繁的動態操作。

內存占用：紅黑樹的內存使用率較低，而 B+ 樹由于每個節點存儲更多指針，內存開銷較大，且不必要。

HashMap 的設計目標：HashMap 的目標是高效查找，而紅黑樹能很好地滿足這一點，并且它與內存結構更契合。B+ 樹則更適合大規模外存數據管理。

3，哈希沖突的解決辦法有哪些？

拉鏈法（Chaining）：將所有映射到同一哈希桶中的元素存儲為鏈表（或紅黑樹）。當沖突較少時，鏈表的查找復雜度為 O(n)，當鏈表轉為紅黑樹后復雜度降為 O(log n)。

開放地址法（Open Addressing）：如果一個位置已經被占用，嘗試探查其他位置存儲沖突的元素。線性探測，依次檢查下一個位置。二次探測，按平方步長檢查下一個位置。雙哈希，使用第二個哈希函數計算探測步長。

再哈希（Rehashing）：當哈希表負載因子過高時，擴容并重新計算所有鍵的哈希值，減少沖突。

四 HashMap如何擴容？

HashMap 在存儲過程中可能會遇到哈希沖突，因此需要使用鏈表或紅黑樹來解決這些沖突。然而，隨著數據量的增加，沖突可能會加劇，導致訪問的時間復雜度無法維持在 O(1) 的水平。此時，就需要進行擴容。擴容的過程包括分配新的數組和重新哈希舊數組中的鍵值對。

HashMap 擴容主要有下面四個核心步驟：

1. 觸發條件 擴容發生在插入新元素時，如果當前元素數量超過了 閾值，則觸發擴容。

2. 容量翻倍 擴容時HashMap 會先新建一個數組，新數組的大小是老數組的兩倍。

3. 重新哈希（Rehashing） 將舊數組中的鍵值對重新分配到新數組中，重新計算每個鍵值對在新數組中的位置。在JDK 1.8 及之后對擴容進行了改進，通過位運算判斷新下標位置，而不需要每個節點都重新計算哈希值，提高了效率。

4. 性能影響 擴容是一種代價較高的操作，需要分配新內存并重新計算所有鍵值對的位置，因此應盡量避免頻繁擴容。

延伸

1.為什么采用2倍擴容，而不是1.5倍或者3倍擴容？

HashMap 采用 2 倍擴容，是為了性能優化、空間利用率和實現簡單性的綜合平衡，避免了 1.5 倍或 3 倍擴容帶來的復雜性和資源浪費問題。

（1）保持哈希分布均勻性

HashMap 擴容后需要重新計算鍵值對的位置。如果新數組大小是 2 的冪，則通過位運算（key.hash & (newCapacity - 1)）來定位數組索引。這種位運算是非常高效的，避免了取模運算（%）的性能開銷。如果選擇其他擴容倍數（如 1.5 倍或 3 倍），就無法簡單通過位運算完成定位，計算索引的效率會降低。

（2）節約內存碎片，防止浪費空間

1.5 倍擴容：擴容后的數組大小無法保證是 2 的冪。這樣 HashMap 的存儲空間利用率可能下降，影響鍵值對的哈希分布，增加哈希沖突。

3 倍擴容：雖然可以減少擴容的頻率，但擴容時占用內存會瞬間大幅增加，浪費內存空間。尤其在數據量大的情況下，內存分配的壓力會顯著增加。

（3）減少擴容頻率與內存占用的平衡

擴容過小（如 1.5 倍）會導致頻繁擴容，而擴容過大（如 3 倍）會導致一次性占用過多內存。2 倍擴容在擴容頻率和擴容成本之間取得了一個平衡：擴容后內存增長速度適中，只需重新分配內存并搬移數據，避免了頻繁擴容的性能開銷。

（4） 兼容性與實現簡單性

Java 中 HashMap 的容量始終是 2 的冪次方。2 倍擴容后，容量仍然是 2 的冪，哈希計算和分布規則無需額外調整。如果使用 1.5 倍或 3 倍擴容，則數組長度不再是 2 的冪，導致實現變得復雜。比如，哈希計算的規則需要調整，哈希分布也可能變得不均勻。

五 Java 8中，HashMap有哪些重要的改進？

在 Java 8 中，HashMap 的實現進行了重要的優化，主要集中在性能提升和處理哈希沖突的改進。以下是關鍵的改進點：

1，數據結構的改進

在 JDK 1.7 及之前，HashMap 的數據結構是“數組+鏈表”。當發生哈希沖突時，多個鍵值對以鏈表形式存儲在同一個“桶”中。 在 JDK 1.8 中，引入了紅黑樹優化。當鏈表長度超過 8 時，會自動轉換為紅黑樹，這將時間復雜度從 O(n) 降低到 O(logN)，大幅提高查找效率。

2，哈希算法的改進

在JDK 1.7時直接使用 hashCode 的低位進行哈希運算，這樣當 table 長度較小時，高位沒有參與計算，導致哈希分布不均。Java 8 使用了一種新的哈希函數實現（基于 MurmurHash 的思想），以減少哈希沖突的概率。這個優化使鍵的分布更加均勻，即使是質量較差的哈希碼也能避免集中到某些桶中。

3，擴容位置改進

在 Java 7 中，擴容時需要重新計算每個元素的哈希值。 在 Java 8 中，擴容優化為利用位運算快速判斷新位置：每個元素的哈希值只需要檢查高位變化即可決定分配到新桶或保留在原桶中。例如，當容量從 16 擴展到 32 時，桶的數量翻倍，每個元素的位置只需要通過 (hash & (newCapacity - 1)) 判斷是否需要遷移。這種優化減少了擴容時的計算開銷。

4，擴容觸發機制改進

在JDK 1.7中擴容是“先擴容后插入”，無論是否發生哈希沖突，都會執行擴容操作，可能導致無效擴容。在JDK 1.8中擴容變為“先插入再擴容”，僅在插入后元素總量超過閾值，或某條鏈表因哈希沖突長度超過 8 且當前數組容量未達到 64 時，才會觸發擴容，減少了不必要的操作。

延伸

1，改進的哈希算法詳解

在 Java 8 中，HashMap 的哈希函數對鍵的哈希碼做了更多處理，以減少沖突。它通過高位和低位的混合（h ^ (h >>> 16)）來避免低質量的哈希函數導致的沖突。

示例：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

這種設計使得高位和低位都能參與哈希桶的定位，減少了哈希沖突的概率，尤其是對于哈希值分布不均的鍵。

2，與 Java 7 HashMap 的對比

特性	Java 7	Java 8
沖突處理	鏈表	鏈表 + 紅黑樹
時間復雜度（最壞情況）	O(n)	O(log n)（鏈表轉紅黑樹后）
哈希算法	哈希碼簡單混合	哈希碼高位與低位的混合
擴容機制	重新計算哈希值	基于高位判斷新桶位置

示例對比

Java 7 性能退化示例：

import java.util.HashMap;
?
public class HashMapTest {public static void main(String[] args) {HashMap<Integer, String> map = new HashMap<>();for (int i = 0; i < 1000; i++) {map.put(i * 16, "value" + i); // 強制讓哈希沖突}System.out.println(map); // 性能會退化為 O(n)}
}

Java 8 的改進： 在相同情況下，Java 8 中鏈表會轉化為紅黑樹，從而避免退化問題。

3，HashMap能不能無限擴容？

HashMap 的擴容最終受限于 JVM 所能提供的內存。當 HashMap 的容量增長到超過 JVM 可用的堆內存大小時，擴容操作將無法成功，可能會導致 OutOfMemoryError。適用于中小規模的數據存儲，實際開發中，由于 HashMap 的擴容和 rehashing 都是相對昂貴的操作，大量的元素插入可能會導致系統性能的顯著下降。

4，樹化后刪除元素能不能回退成鏈表？

當紅黑樹中的元素數量減少到 6 時，HashMap 會將紅黑樹退化回鏈表，紅黑樹的結構維護成本較高，涉及復雜的旋轉和調整操作。如果元素數量較少，鏈表反而更加高效。

六 HashMap是否是線程安全的？

HashMap 是非線程安全的。HashMap 是 Java 中的一個常用集合類，用于存儲鍵值對。由于它在設計時沒有考慮線程安全問題，所以在多線程環境中，多個線程同時對 HashMap 進行讀寫操作可能導致數據不一致、死循環等問題。

延伸

1. 為什么 HashMap 不是線程安全的

HashMap 的非線程安全性主要體現在以下幾個方面：

1. 并發修改導致數據不一致：

   • 多個線程同時對 HashMap 進行修改（如 put()、remove() 等），可能導致數據被覆蓋或丟失，最終狀態不可預測。

   • 示例問題：線程 A 和線程 B 同時向 HashMap 中插入數據，線程 A 可能會覆蓋線程 B 的修改，導致丟失線程 B 的數據。

2. 擴容操作的線程安全問題：

   • 當 HashMap 的容量達到閾值時，會觸發擴容（rehash），即將元素重新分布到新的數組中。

   • 如果在多線程環境中發生擴容操作，可能導致死循環或數據丟失。

   • 原因：擴容過程中，HashMap 會通過鏈表的遍歷重新分配元素。如果多個線程同時執行擴容操作，鏈表的結構可能被破壞，導致循環引用。

3. 無同步機制：

   • HashMap 的方法（如 put()、get() 等）沒有任何同步措施，不會主動加鎖，因此多個線程同時訪問共享的 HashMap 會導致線程安全問題。

2.如何使HashMap變得線程安全？

HashMap 本身不是線程安全的，如果在多線程環境下使用可能會出現數據不一致、死循環等問題。要使 HashMap 線程安全，可以采用以下幾種方法：

1. 使用 Collections.synchronizedMap

• 將HashMap包裝成線程安全的同步Map。

• 示例代碼：

  Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

• 這種方式會為所有操作加鎖，適合簡單的多線程訪問，但性能較低。

2.使用 ConcurrentHashMap

• ConcurrentHashMap 是 Java 提供的線程安全實現，采用分段鎖機制（Java 8 后基于 CAS 和分段鎖結合）。

• 示例代碼：

  Map<String, String> concurrentMap = new ConcurrentHashMap<>();

• ConcurrentHashMap 提供更高的并發性能，是線程安全的推薦選擇。

3.手動加鎖

• 可以使用 synchronized 或 ReentrantLock 在關鍵代碼塊上加鎖。

• 示例代碼：

  Map<String, String> map = new HashMap<>();
  synchronized (map) {
  map.put("key", "value");
  }

• 這種方式適合特定場景，但需要自行管理鎖，代碼復雜且容易出錯。