問題1：說說 List,Set,Map 三者的區別？
在 Java 中，List、Set 和 Map 是最常用的集合框架（Collection Framework）接口，它們的主要區別如下：
1. List（列表）
-
特點：
- 允許存儲 重復元素。
- 保持插入順序，即元素的存儲順序與遍歷順序一致。
- 允許null值（可存多個）。
- 提供索引訪問，可以使用索引(
get(int index))獲取元素。
-
常見實現類：
ArrayList（基于數組，查詢快，增刪慢）LinkedList（基于雙向鏈表，查詢慢，增刪快）Vector（線程安全的ArrayList，但性能較低）
-
使用場景：
- 需要有序存儲元素，并且可能有重復值，例如存儲一系列日志記錄、待辦事項等。
2. Set（集合）
-
特點：
- 不允許存儲重復元素。
- 無法通過索引訪問元素（沒有
get(int index)方法）。 - 默認情況下不保證元素的存儲順序（
TreeSet除外）。 - 允許最多一個 null 值（
HashSet允許，TreeSet不允許）。
-
常見實現類：
HashSet（基于哈希表，存取快，但無序）LinkedHashSet（有序的 HashSet，按插入順序存儲）TreeSet（基于紅黑樹，自動排序，不允許null）
-
使用場景：
- 需要存儲唯一的元素集合，例如存儲用戶ID、標簽等。
3. Map（映射）
-
特點：
- 以 鍵值對 (key-value) 形式存儲數據。
- Key 不可重復，但 Value 可以重復。
- 允許最多一個
null鍵，多值null值（TreeMap不允許null鍵）。
-
常見實現類：
HashMap（無序，基于哈希表，存取快，線程不安全）LinkedHashMap（有序的 HashMap，按插入順序存儲）TreeMap（排序的 Map，基于紅黑樹，按 Key 排序）
-
使用場景：
- 需要存儲鍵值映射，如學生學號-姓名、配置項鍵值對等。
總結對比
| 特性 | List | Set | Map |
|---|---|---|---|
| 是否允許重復元素 | 允許 | 不允許 | Key 不允許重復，Value 允許 |
| 是否保證順序 | 保證插入順序 | HashSet 無序，LinkedHashSet 保證插入順序，TreeSet 排序 | HashMap 無序，LinkedHashMap 保持插入順序，TreeMap 按 key 排序 |
是否可存 null | 允許多個 | 僅 HashSet 允許一個 | HashMap 允許一個 null Key，多 null Value，TreeMap 不允許 null Key |
| 訪問方式 | 通過索引 (get(int index)) | 迭代器 (Iterator) | 通過 Key (get(K key)) |
| 適用場景 | 需要有序存儲并允許重復，如購物車、任務列表 | 需要唯一元素，如用戶ID | 需要鍵值映射，如用戶信息 |
簡單記憶：
List適合 有序、可重復 場景。Set適合 唯一、無序（或排序） 場景。Map適合 鍵值映射 場景。
問題2：?List,Set,Map 在 Java 中分別由哪些對應的實現類？底層的數據結構？
在 Java 中，List、Set 和 Map 各自有多個常見的實現類，它們的底層數據結構不同，適用于不同的場景。下面詳細分析各自的實現類及其底層結構。
1. List（列表）
List 主要有以下幾個實現類：
（1）ArrayList
-
底層數據結構：動態數組
-
特點：
-
查詢速度快（基于數組，通過索引訪問，
O(1)）。 -
插入和刪除慢（涉及數據移動，
O(n)）。 -
允許
null元素，允許重復元素。 -
線程不安全。
-
-
適用場景：
-
讀操作多，寫操作少的場景，如緩存數據、搜索結果等。
-
（2）LinkedList
-
底層數據結構：雙向鏈表
-
特點：
-
查詢速度慢（鏈表遍歷，
O(n)）。 -
插入、刪除速度快（
O(1)，不涉及數據移動）。 -
允許
null元素，允許重復元素。 -
線程不安全。
-
-
適用場景：
-
頻繁插入、刪除元素，如任務隊列、消息隊列等。
-
（3）Vector
-
底層數據結構：動態數組
-
特點：
-
與
ArrayList類似，但線程安全（方法加了synchronized）。 -
查詢快，插入刪除慢。
-
允許
null元素，允許重復元素。
-
-
適用場景：
-
多線程環境下，需要線程安全的
List。
-
2. Set（集合）
Set 主要有以下幾個實現類：
（1）HashSet
-
底層數據結構：哈希表（基于
HashMap實現，值存HashMap的 key） -
特點：
-
無序存儲元素（元素順序可能變化）。
-
不允許重復元素。
-
允許
null值（但只能有一個）。 -
查詢、插入、刪除速度快（平均
O(1)）。
-
-
適用場景：
-
需要去重的集合，如存儲唯一用戶ID。
-
（2）LinkedHashSet
-
底層數據結構：哈希表 + 雙向鏈表
-
特點：
-
有序（按照插入順序存儲）。
-
不允許重復元素。
-
查詢、插入、刪除速度比
HashSet略慢（受鏈表影響）。
-
-
適用場景：
-
既需要去重，又要保持插入順序的場景，如LRU緩存。
-
（3）TreeSet
-
底層數據結構：紅黑樹（自平衡二叉搜索樹）
-
特點：
-
自動排序（默認按升序排序，可自定義
Comparator）。 -
不允許重復元素。
-
不允許
null。 -
查詢、插入、刪除速度
O(log n)（比HashSet慢）。
-
-
適用場景：
-
需要排序且去重的集合，如排行榜、時間排序數據。
-
3. Map（映射）
Map 主要有以下幾個實現類：
（1）HashMap
-
底層數據結構：數組 + 單鏈表 + 紅黑樹（JDK 1.8 之后）
-
特點：
-
Key無序存儲，不允許重復，允許null（最多一個）。 -
Value允許重復，允許null。 -
查詢、插入、刪除快（
O(1)，最壞O(log n)）。 -
線程不安全。
-
-
適用場景：
-
需要快速查找
key-value數據，如緩存、配置項存儲。
-
（2）LinkedHashMap
-
底層數據結構：哈希表 + 雙向鏈表
-
特點：
-
按插入順序存儲（可以用
accessOrder=true變成 LRU 訪問順序）。 -
查詢、插入、刪除速度略低于
HashMap（受鏈表影響）。
-
-
適用場景：
-
需要按插入順序遍歷的
Map，如緩存實現。
-
（3）TreeMap
-
底層數據結構：紅黑樹
-
特點：
-
Key 自動排序（默認升序，可自定義
Comparator）。 -
Key 不允許
null（Value 允許）。 -
查詢、插入、刪除
O(log n)。
-
-
適用場景：
-
需要按 key 排序的
Map，如時間戳排序的日志數據。
-
（4）Hashtable
-
底層數據結構：哈希表
-
特點：
-
線程安全（方法加
synchronized）。 -
不允許
nullkey 和nullvalue。 -
查詢、插入、刪除
O(1)。 -
效率較低（同步開銷大）。
-
-
適用場景：
-
需要線程安全的
Map（但通常用ConcurrentHashMap替代）。
-
（5）ConcurrentHashMap
-
底層數據結構：分段鎖 + 哈希表（JDK 1.7），CAS + 哈希表 + 紅黑樹（JDK 1.8）
-
特點：
-
線程安全，高效（分段鎖 / CAS 機制）。
-
不允許
nullkey 和nullvalue。 -
查詢、插入、刪除比
Hashtable快（O(1)）。
-
-
適用場景：
-
高并發環境下的
Map，如緩存存儲。
-
總結
| 類型 | 實現類 | 底層數據結構 | 主要特點 | 適用場景 |
|---|---|---|---|---|
| List |
| 動態數組 | 查詢快，增刪慢 | 讀多寫少 |
|
| 雙向鏈表 | 插入/刪除快，查詢慢 | 頻繁增刪 | |
|
| 動態數組 | 線程安全 | 多線程 | |
| Set |
| 哈希表 | 無序，不重復 | 唯一集合 |
|
| 哈希表 + 雙向鏈表 | 插入順序 | 唯一且有序 | |
|
| 紅黑樹 | 自動排序 | 唯一且排序 | |
| Map |
| 數組 + 鏈表 + 紅黑樹 | 無序，查詢快 | 快速查找 |
|
| 哈希表 + 雙向鏈表 | 按插入順序 | LRU緩存 | |
|
| 紅黑樹 | Key 自動排序 | 需要排序 | |
|
| 哈希表 | 線程安全，低效 | 線程安全（少用） | |
|
| 哈希表 + CAS | 高并發 | 并發環境 |
?問題3：有哪些集合是線程不安全的？怎么解決呢？
1. 線程不安全的集合
（1）ArrayList（線程不安全）
-
底層數據結構：動態數組
-
問題：多線程環境下，多個線程同時
add()可能導致 數據覆蓋、數組擴容時的數據丟失。 -
解決方案：
-
使用
Vector（線程安全，但性能較低） -
使用
Collections.synchronizedList(new ArrayList<>()) -
使用
CopyOnWriteArrayList（適用于讀多寫少的場景）
-
（2）HashMap（線程不安全）
-
底層數據結構：數組 + 鏈表（JDK 1.7），數組 + 鏈表 + 紅黑樹（JDK 1.8）
-
問題：
-
JDK 1.7 多線程
put()時可能引發死循環（rehash 過程中鏈表反轉）。 -
JDK 1.8 仍然是線程不安全的，多線程
put()可能會丟數據。
-
-
解決方案：
-
使用
ConcurrentHashMap（高性能并發 Map，推薦） -
使用
Collections.synchronizedMap(new HashMap<>())（性能較低） -
使用
Hashtable（線程安全但性能差，較少使用）
-
2. ArrayList vs. Vector（高頻對比）
| 對比項 |
|
|
|---|---|---|
| 線程安全 | ? 非線程安全 | ? 線程安全（synchronized） |
| 底層數據結構 | 動態數組 | 動態數組 |
| 擴容方式 |
|
|
| 性能 | 高（無鎖） | 低（同步開銷大） |
| 適用場景 | 單線程 | 多線程（但 |
💡 為什么 Vector 不推薦？
-
Vector的方法使用synchronized關鍵字，導致所有方法都串行執行，性能較低。 -
多線程環境下，更推薦
CopyOnWriteArrayList或Collections.synchronizedList(new ArrayList<>())。
3. HashMap vs. ConcurrentHashMap（高頻對比）
| 對比項 |
|
|
|---|---|---|
| 線程安全 | ? 非線程安全 | ? 線程安全 |
| 底層數據結構 | 數組 + 鏈表（JDK 1.7） | JDK 1.7：分段鎖 + 哈希表（Segment 機制） |
|
| ? 允許 | ? 不允許 |
| 并發性能 | 低（多線程可能出錯） | 高（JDK 1.8 采用 CAS 機制，提高并發性能） |
| 適用場景 | 單線程 | 高并發環境 |
4. ConcurrentHashMap 如何保證線程安全？
🔹 JDK 1.7（Segment 分段鎖）
-
ConcurrentHashMap采用 Segment + HashEntry 結構，將整個 Map 分成多個Segment（默認 16 個）。 -
每個
Segment維護自己的鎖，只有訪問相同Segment的線程才會競爭鎖，大大提高并發性。 -
缺點：
Segment結構較復雜，鎖的粒度仍然較大。
🔹 JDK 1.8（CAS + synchronized + 紅黑樹）
-
取消了
Segment，改為 數組 + 鏈表 + 紅黑樹 結構，與HashMap結構類似。 -
核心優化：
-
CAS（Compare-And-Swap）機制：插入新元素時，先嘗試用 CAS 方式寫入，失敗再加鎖。
-
synchronized代替ReentrantLock：JDK 1.8 采用 Node 級別加鎖，僅在 Hash 沖突時加鎖，降低鎖競爭。 -
紅黑樹優化：當鏈表長度超過 8 時，轉換為紅黑樹，提高查詢性能。
-
💡 為什么 ConcurrentHashMap 性能更好？
-
HashTable是全表鎖，每次訪問都需要synchronized，性能低。 -
ConcurrentHashMap采用 CAS + 局部鎖，大幅提升并發性能。
5. 線程安全的解決方案（匯總）
| 線程不安全集合 | 線程安全替代方案 |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
6. 總結
-
ArrayListvs.Vector-
ArrayList非線程安全，性能高。 -
Vector線程安全，但同步開銷大，不推薦。 -
推薦：
CopyOnWriteArrayList（讀多寫少）。
-
-
HashMapvs.ConcurrentHashMap-
HashMap非線程安全，多線程環境下可能丟數據。 -
ConcurrentHashMap采用 CAS +synchronized保證線程安全，高并發推薦。
-
-
ConcurrentHashMap 如何保證線程安全？
-
JDK 1.7：
Segment分段鎖（16 個小鎖）。 -
JDK 1.8：
CAS +synchronized` + 紅黑樹（更高效）。
-
如果你在面試中被問到： 👉 ArrayList 和 Vector 的區別？
-
Vector 是同步的，ArrayList 不是，性能上 ArrayList 更好。
-
現在不推薦 Vector，而是使用
CopyOnWriteArrayList。
👉 HashMap 和 ConcurrentHashMap 的區別？
-
HashMap非線程安全，ConcurrentHashMap線程安全，高并發推薦。 -
JDK 1.8
ConcurrentHashMap采用 CAS +synchronized，比 JDK 1.7 更高效。
問題4：?HashMap 查詢，刪除的時間復雜度
1. HashMap 底層數據結構（JDK 1.8 之后）
HashMap 采用 數組 + 鏈表 + 紅黑樹 作為底層數據結構：
-
當沒有哈希沖突時（即均勻分布的情況下）：時間復雜度為
O(1)。 -
當發生哈希沖突時：
-
鏈表存儲：查找或刪除需要遍歷鏈表，最壞時間復雜度
O(n)。 -
紅黑樹存儲（鏈表長度 ≥ 8 時轉換為紅黑樹）：查詢、刪除的時間復雜度降為
O(log n)。
-
2. HashMap 查詢的時間復雜度
-
理想情況下（無哈希沖突）：
-
通過
key計算hash值，找到數組索引，直接返回值，時間復雜度O(1)。
-
-
最壞情況（所有
key哈希沖突，存儲為鏈表）：-
需要遍歷整個鏈表，時間復雜度
O(n)。
-
-
優化后（鏈表轉紅黑樹）：
-
當鏈表長度 >= 8 時，自動轉為紅黑樹，查詢復雜度降為
O(log n)。
-
? 最終查詢時間復雜度：
-
平均情況：
O(1) -
最壞情況（鏈表）：
O(n) -
最壞情況（紅黑樹）：
O(log n)
示例：
Map<Integer, String> map = new HashMap<>();
map.put(1, "A");
map.put(2, "B");
String value = map.get(1); // O(1)（理想情況）
3. HashMap 刪除的時間復雜度
-
理想情況下（無哈希沖突）：
-
remove(key)計算hash，直接刪除，時間復雜度O(1)。
-
-
最壞情況（哈希沖突，鏈表存儲）：
-
需要遍歷鏈表找到
key并刪除，時間復雜度O(n)。
-
-
優化后（鏈表轉紅黑樹）：
-
刪除操作
O(log n)。
-
? 最終刪除時間復雜度：
-
平均情況：
O(1) -
最壞情況（鏈表）：
O(n) -
最壞情況（紅黑樹）：
O(log n)
示例：
map.remove(1); // O(1)（理想情況）
4. 復雜度總結
| 操作 | 平均時間復雜度 | 最壞時間復雜度（鏈表） | 最壞時間復雜度（紅黑樹） |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
🔹 面試重點：
-
JDK 1.8 之前：查詢、刪除最壞情況
O(n)（哈希沖突形成鏈表）。 -
JDK 1.8 之后：鏈表長度 ≥ 8 時轉為紅黑樹，優化為
O(log n)。
問題5：?HashMap 的底層實現
JDK1.8 之前 ： 數組和鏈表
JDK1.8 之后 ： 多了紅黑樹
問題6：?HashMap 的長度為什么是 2 的冪次方？
| 問題 | 答案 |
|---|---|
為什么 HashMap 長度是 2 的冪？ | 為了 優化索引計算，減少哈希沖突 |
| 如何計算索引？ | index = hash & (table.length - 1) |
為什么用 & (length - 1) 而不是 % length？ | 位運算比取模運算更快 |
如果 length 不是 2 的冪，會怎樣？ | 索引分布不均，哈希沖突增加，性能下降 |
HashMap 如何保證 length 是 2 的冪？ | tableSizeFor(cap) 方法，自動調整 capacity |
問題7：?比較 HashSet、LinkedHashSet 和 TreeSet 三者的異同
1. 共同點（相同點）
? 1.1. 都實現了 Set 接口
-
不允許存儲重復元素，如果嘗試添加相同元素，新的數據會被忽略。
? 1.2. 允許 null 值
-
HashSet和LinkedHashSet允許存儲一個null值。 -
TreeSet不允許null（因為TreeSet依賴compareTo()進行排序，null無法比較）。
? 1.3. 不是線程安全的
-
三者都不是線程安全的，若在多線程環境下使用，需要使用
Collections.synchronizedSet()或ConcurrentSkipListSet。
Set<Integer> set = Collections.synchronizedSet(new HashSet<>());? 1.4. 不能通過索引訪問元素
-
Set沒有get(int index)方法，不能像List那樣通過索引訪問。
2. 不同點（區別）
| 對比項 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底層數據結構 | 哈希表（ | 哈希表 + 雙向鏈表 | 紅黑樹（ |
| 元素存儲順序 | 無序 | 按照插入順序 | 自動排序（默認升序，可自定義） |
| 是否排序 | ? 不排序 | ? 不排序（但保持插入順序） | ? 排序（按 |
| 允許 | ? 允許 1 個 | ? 允許 1 個 | ? 不允許 |
| 查詢性能 | 🚀 O(1)（哈希存儲，最快） | 🚀 O(1)（哈希存儲） | 🐌 O(log n)（紅黑樹，較慢） |
| 插入性能 | 🚀 O(1)（哈希存儲） | 🚀 O(1)（哈希存儲） | 🐌 O(log n)（紅黑樹，較慢） |
| 刪除性能 | 🚀 O(1) | 🚀 O(1) | 🐌 O(log n) |
| 適用場景 | 需要快速查找的集合 | 需要保留插入順序的集合 | 需要排序的集合 |
3. 三者的底層實現
（1）HashSet
-
底層使用
HashMap，Set的值存儲在HashMap的 key 中，所有 value 設為Object類型的固定值。 -
元素無序存儲，無法保證插入順序。
public HashSet() {map = new HashMap<>();
}
public boolean add(E e) {return map.put(e, PRESENT) == null;
}
? 適用場景：需要快速去重，不關心元素順序。
（2）LinkedHashSet
-
底層使用
LinkedHashMap，通過雙向鏈表維護插入順序。 -
保證遍歷順序與插入順序一致。
public LinkedHashSet() {super(16, .75f, true); // 繼承 LinkedHashMap }
? 適用場景：去重但保持插入順序，如 LRU 緩存。
（3）TreeSet
-
底層使用
TreeMap，基于紅黑樹存儲。 -
按
compareTo()結果自動排序，默認升序。 -
不允許
null，因為null無法參與比較。public TreeSet() {this(new TreeMap<>()); }
? 適用場景：需要排序的集合，如排行榜、時間排序的日志。
4. 示例代碼
（1）HashSet
Set<String> hashSet = new HashSet<>();
hashSet.add("B");
hashSet.add("A");
hashSet.add("C");
System.out.println(hashSet); // 輸出無序：[A, C, B]（順序可能不同）
（2）LinkedHashSet
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("B");
linkedHashSet.add("A");
linkedHashSet.add("C");
System.out.println(linkedHashSet); // 輸出順序：["B", "A", "C"]
（3）TreeSet
Set<String> treeSet = new TreeSet<>();
treeSet.add("B");
treeSet.add("A");
treeSet.add("C");
System.out.println(treeSet); // 輸出順序：["A", "B", "C"]（自動排序）
5. 選擇建議（如何選擇？）
| 場景 | 推薦使用 |
|---|---|
| 需要去重，不關心順序，查詢性能最高 |
|
| 需要去重，且保持插入順序 |
|
| 需要去重，且按大小排序 |
|
6. 重點面試問題
💡 1. HashSet、LinkedHashSet、TreeSet 的區別？
-
HashSet：基于HashMap，無序存儲，O(1) 查詢 -
LinkedHashSet：基于LinkedHashMap，有序存儲 -
TreeSet：基于TreeMap，自動排序，O(log n) 查詢
💡 2. HashSet 為什么查詢快？
-
HashSet基于HashMap，使用hashCode()計算索引，查詢平均 O(1)。
💡 3. TreeSet 為什么不允許 null？
-
TreeSet依賴compareTo()進行排序，而null不能比較。
💡 4. TreeSet 是如何排序的？
-
通過
Comparable接口 (compareTo()) 或Comparator自定義排序規則。
7. 總結
| Set 類型 | 底層數據結構 | 順序 | 查詢性能 | 插入/刪除性能 | 是否排序 |
|---|---|---|---|---|---|
|
| 哈希表（ | 無序 | 🚀 | 🚀 | ? |
|
| 哈希表 + 雙向鏈表（ | 插入順序 | 🚀 | 🚀 | ? |
|
| 紅黑樹（ | 排序 | 🐌 | 🐌 | ? |
🔹 總結
-
HashSet最快，但無序。 -
LinkedHashSet有序，比HashSet稍慢。 -
TreeSet自動排序，但性能最慢（O(log n)）。
問題8：?HashMap 和 Hashtable 的區別？HashMap 和 HashSet 區別？HashMap 和 TreeMap 區別？ ConcurrentHashMap 和 Hashtable 的區別？
1. HashMap vs. Hashtable（區別）
| 對比項 | HashMap | Hashtable |
|---|---|---|
| 線程安全 | ? 非線程安全 | ? 線程安全（方法使用 |
| 底層數據結構 | 數組 + 鏈表（JDK 1.7） | 數組 + 鏈表 |
| 性能 | 🚀 高（無鎖） | 🐌 低（全表鎖） |
|
| ? 允許 | ? 不允許 |
| 擴容方式 |
|
|
| 適用場景 | 單線程或高并發（推薦使用 | 低并發場景（通常不推薦） |
? 總結：
-
HashMap性能更高，適用于 單線程或并發環境（推薦ConcurrentHashMap）。 -
Hashtable所有方法加鎖，線程安全但性能低，一般不推薦使用。
💡 面試問法：
-
為什么
Hashtable不推薦使用？-
Hashtable全表鎖，并發效率低，通常使用ConcurrentHashMap替代。
-
2. HashMap vs. HashSet（區別）
| 對比項 | HashMap | HashSet |
|---|---|---|
| 實現接口 |
|
|
| 數據存儲方式 |
| 僅存 |
| 底層數據結構 | 數組 + 鏈表 + 紅黑樹（JDK 1.8） | 基于 |
| 是否允許重復 | ? | ? 不允許重復元素 |
|
| ? | ? 允許一個 |
| 查詢性能 | 🚀 | 🚀 |
| 適用場景 | 需要存儲鍵值對（如用戶 ID -> 用戶信息） | 需要存儲唯一元素集合（如用戶 ID 集合） |
? 總結：
-
HashMap存儲鍵值對，HashSet僅存儲 key（基于HashMap實現）。 -
HashSet去重能力基于HashMap的key唯一性。
💡 面試問法：
-
HashSet 為什么是基于 HashMap 實現的？
-
HashSet本質上就是HashMap，value始終存一個固定對象。
-
public boolean add(E e) {return map.put(e, PRESENT) == null;
}
3. HashMap vs. TreeMap（區別）
| 對比項 | HashMap | TreeMap |
|---|---|---|
| 底層數據結構 | 數組 + 鏈表 + 紅黑樹 | 紅黑樹（ |
| 排序方式 | ? 無序 | ? 自動排序（默認升序） |
| 查詢性能 | 🚀 | 🐌 |
|
| ? | ? |
| 適用場景 | 需要快速查找的鍵值對 | 需要排序的鍵值對（如排行榜） |
? 總結：
-
HashMap查詢快（O(1)），無序，適合快速存取數據。 -
TreeMap自動排序（O(log n)），適用于需要排序的場景。
💡 面試問法：
-
如果 HashMap 需要排序怎么辦？
-
使用
TreeMap或者LinkedHashMap。
-
4. ConcurrentHashMap vs. Hashtable（區別）
| 對比項 | ConcurrentHashMap（推薦） | Hashtable（已淘汰） |
|---|---|---|
| 底層數據結構 | JDK 1.7：分段鎖（ | 哈希表 + 全表鎖 |
| 鎖的粒度 | 局部鎖（高并發） | 全表鎖（低效） |
| 查詢性能 | 🚀 高（讀 | 🐌 低（所有方法 |
|
| ? 不允許 | ? 不允許 |
| 適用場景 | 高并發環境（推薦） | 低并發環境（已淘汰） |
? 總結：
-
ConcurrentHashMap替代Hashtable，采用 CAS + 局部鎖，更高效。 -
Hashtable線程安全但性能低，一般不再使用。
💡 面試問法：
-
ConcurrentHashMap 如何保證線程安全？
-
JDK 1.7：
Segment分段鎖（16 個小鎖，提高并發性能）。 -
JDK 1.8：
CAS +synchronized` + 紅黑樹（更高效）。
-
5. 總結
| 對比項 | HashMap vs. Hashtable | HashMap vs. HashSet | HashMap vs. TreeMap | ConcurrentHashMap vs. Hashtable |
|---|---|---|---|---|
| 線程安全 | ? HashMap 非線程安全，? Hashtable 線程安全（但慢） | HashMap 存 key-value，HashSet 只存 key | HashMap 無序，TreeMap 排序 | ConcurrentHashMap 更高效（局部鎖），Hashtable 全表鎖（淘汰） |
| 底層結構 | HashMap：哈希表，Hashtable：哈希表（帶鎖） | HashSet 基于 HashMap | HashMap 哈希表，TreeMap 紅黑樹 | ConcurrentHashMap 分段鎖（JDK 1.7） / CAS + |
| 查詢性能 | 🚀 | 🚀 | 🚀 | 🚀 |
| 是否排序 | ? 都無序 | ? 都無序 | ? HashMap 無序，? TreeMap 排序 | ? 都無序 |
| null 允許性 | HashMap 允許 | ? HashSet 允許一個 | ? TreeMap 不允許 | ? ConcurrentHashMap 不允許 |
🚀 面試重點：
-
高并發環境：
ConcurrentHashMap代替Hashtable -
需要排序：用
TreeMap -
去重：用
HashSet（基于HashMap）
?問題9：ConcurrentHashMap 線程安全的具體實現方式/底層具體實現
1. JDK 1.7 中的實現（分段鎖）
在 JDK 1.7 中，ConcurrentHashMap 采用了 分段鎖（Segment Locking） 機制。HashMap 的每個**桶（Segment）**都是獨立加鎖的，允許多個線程并發操作不同的段，但同一段內的操作需要加鎖。
1.1. 分段鎖模型
-
ConcurrentHashMap會把整個 map 劃分為多個 段（Segment），每個段內部維護一個HashMap，并且每個段有一個鎖。 -
每個段都可以并發操作，不同段之間的鎖是獨立的，這就避免了全表鎖定，從而大大提高了并發性能。
-
每個段的默認大小是 16（即 16 個桶），并且段數可以動態調整。
1.2. 鎖粒度
-
鎖定段： 每次只能鎖住某個段（而不是整個
ConcurrentHashMap）。 -
不同段的并發訪問： 不同線程可以并發地對不同段進行
get、put等操作。 -
同一段的并發訪問： 如果多個線程訪問同一段的不同元素，則這些線程會被阻塞，直到持有該段鎖的線程釋放鎖。
1.3. 分段鎖的代碼示例
public class ConcurrentHashMap<K, V> {static final int MAX_SEGMENT = 16; // 默認分成16個段final Segment<K, V>[] segments;// Segment 內部結構static final class Segment<K, V> extends ReentrantLock implements Serializable {transient volatile HashEntry<K, V>[] table;transient volatile int count;final float loadFactor;Segment(int initialCapacity, float loadFactor) {this.loadFactor = loadFactor;// Initialize the segment's hash table with the given capacity}// Segment 內部的操作方法（put、get 等）public V get(Object key) {// 獲取 key 對應的 value}public void put(K key, V value) {// 將 key-value 對存入當前段的 table 中}}// 主 Map 操作，基于多個 Segment 來完成public V get(Object key) {int hash = key.hashCode();Segment<K, V> segment = segmentFor(hash);return segment.get(key);}public void put(K key, V value) {int hash = key.hashCode();Segment<K, V> segment = segmentFor(hash);segment.put(key, value);}private Segment<K, V> segmentFor(int hash) {return segments[(hash >>> 16) & (segments.length - 1)];}
}
1.4. 分段鎖模型的優缺點
優點：
-
細粒度鎖：只鎖住某一段，多個線程可以并行操作不同的段，并行度較高。
-
線程安全：每個段是獨立加鎖的，避免了全表加鎖帶來的性能瓶頸。
缺點：
-
內存占用高：每個段內部都是一個完整的
HashMap，在大數據量時可能會占用較多內存。 -
鎖競爭：如果多個線程訪問同一段，仍然會發生阻塞。
2. JDK 1.8 中的實現（CAS + synchronized）
在 JDK 1.8 中，ConcurrentHashMap 做了重大優化，去除了分段鎖，改用 CAS（Compare-And-Swap） 和 synchronized 來實現線程安全。其底層不再使用多個段，而是直接將數據存儲在一個 桶數組（數組 + 鏈表 + 紅黑樹） 中，通過 分段鎖和局部鎖 的方式來提供高并發性。
2.1. CAS 和 synchronized 的組合
-
CAS：
ConcurrentHashMap采用 樂觀鎖，在更新數據時首先通過 CAS 操作嘗試更新，如果失敗（例如并發更新），則進行重試。 -
synchronized：對于需要一致性的操作（如擴容），采用synchronized鎖定局部區域（如某個桶），保證數據一致性。
2.2. JDK 1.8 的底層結構
-
桶數組：和
HashMap類似，ConcurrentHashMap內部使用數組來存儲鍵值對。每個桶可以是 鏈表（哈希沖突時）或 紅黑樹（當鏈表過長時轉換為紅黑樹）。 -
每個桶的操作：
-
使用
synchronized鎖定某個桶的插入、刪除、查找操作。 -
對于普通操作（如插入、查詢），采用 CAS 來保證數據的一致性。
-
-
擴容：當負載因子超過一定閾值時，
ConcurrentHashMap會進行擴容（桶數翻倍），這時需要用synchronized來保護擴容過程。
2.3. JDK 1.8 代碼示例
public class ConcurrentHashMap<K, V> {// 存儲數據的桶數組transient volatile Node<K, V>[] table;private final float loadFactor = 0.75f;private transient volatile int sizeCtl;// 鎖定某個桶public V get(Object key) {int hash = hash(key);Node<K, V> e;if ((e = table[hash & (table.length - 1)]) != null) {// 通過鏈表查找，若鏈表長度大于閾值轉為紅黑樹synchronized (e) {// 查找并返回}}return null;}// 使用 CAS 更新值public boolean putIfAbsent(K key, V value) {int hash = hash(key);Node<K, V> e;if ((e = table[hash & (table.length - 1)]) != null) {// 使用 CAS 更新，如果失敗則重試}return true;}// 擴容private void resize() {synchronized (this) {// 擴容并重置桶數組}}// hash 計算（保證一致性）private int hash(Object key) {return key.hashCode();}
}
2.4. JDK 1.8 實現的優缺點
優點：
-
更高效：通過 CAS 和局部鎖提高了并發性能，不需要全表加鎖。
-
擴展性強：自動擴容時，通過同步鎖保護內存，避免了擴容過程中的數據不一致。
-
支持高并發：多個線程可以在不同桶上并行操作，極大提高了吞吐量。
缺點：
-
復雜度高：相比 JDK 1.7，JDK 1.8 的實現更加復雜，使用了 CAS 和
synchronized等技術，需要處理各種競爭條件。 -
內存開銷：每個桶存儲的是
Node，這比HashMap更占用內存。
3. 線程安全的關鍵點
-
CAS（Compare-And-Swap）：樂觀鎖的一種實現方式，通過原子操作檢查和更新數據。如果當前數據符合預期，則修改數據；否則重試。
-
synchronized：用于保護需要保證一致性的關鍵操作（如擴容、遷移）。 -
紅黑樹優化：當鏈表的長度超過一定閾值（8），
HashMap會將鏈表轉換為紅黑樹，優化查詢性能。
4. 總結
-
JDK 1.7：使用 分段鎖，將
ConcurrentHashMap劃分為多個段，每個段有一個獨立的鎖，多個線程可以并行操作不同的段。 -
JDK 1.8：采用 CAS +
synchronized技術，使用桶數組（數組 + 鏈表 + 紅黑樹）來存儲數據。通過局部鎖和 CAS 實現高并發。 -
線程安全性：
ConcurrentHashMap通過 細粒度鎖（桶級別、段級別鎖）和 CAS 操作 保證線程安全。
ConcurrentHashMap 是高并發場景下非常常用的工具，在需要線程安全的并發環境下，它是 Hashtable 和 synchronizedMap 的更好替代品。
