Java集合面试总结（题目来源JavaGuide）

问题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）。
- 不允许 null key 和 null value。
- 查询、插入、删除 O(1)。
- 效率较低（同步开销大）。
适用场景：
- 需要线程安全的 Map（但通常用 ConcurrentHashMap 替代）。

（5）ConcurrentHashMap

底层数据结构：分段锁 + 哈希表（JDK 1.7），CAS + 哈希表 + 红黑树（JDK 1.8）
特点：
- 线程安全，高效（分段锁 / CAS 机制）。
- 不允许 null key 和 null value。
- 查询、插入、删除比 Hashtable 快（O(1)）。
适用场景：
- 高并发环境下的 Map，如缓存存储。

总结

类型	实现类	底层数据结构	主要特点	适用场景
List	`ArrayList`	动态数组	查询快，增删慢	读多写少
	`LinkedList`	双向链表	插入/删除快，查询慢	频繁增删
	`Vector`	动态数组	线程安全	多线程
Set	`HashSet`	哈希表	无序，不重复	唯一集合
	`LinkedHashSet`	哈希表 + 双向链表	插入顺序	唯一且有序
	`TreeSet`	红黑树	自动排序	唯一且排序
Map	`HashMap`	数组 + 链表 + 红黑树	无序，查询快	快速查找
	`LinkedHashMap`	哈希表 + 双向链表	按插入顺序	LRU缓存
	`TreeMap`	红黑树	Key 自动排序	需要排序
	`Hashtable`	哈希表	线程安全，低效	线程安全（少用）
	`ConcurrentHashMap`	哈希表 + CAS	高并发	并发环境

问题3：有哪些集合是线程不安全的？怎么解决呢？

1. 线程不安全的集合

（1）ArrayList（线程不安全）

底层数据结构：动态数组
问题：多线程环境下，多个线程同时 add() 可能导致 数据覆盖、数组扩容时的数据丢失。
解决方案：
1. 使用 Vector（线程安全，但性能较低）
2. 使用 Collections.synchronizedList(new ArrayList<>())
3. 使用 CopyOnWriteArrayList（适用于读多写少的场景）

（2）HashMap（线程不安全）

底层数据结构：数组 + 链表（JDK 1.7），数组 + 链表 + 红黑树（JDK 1.8）
问题：
- JDK 1.7 多线程 put() 时可能引发死循环（rehash 过程中链表反转）。
- JDK 1.8 仍然是线程不安全的，多线程 put() 可能会丢数据。
解决方案：
1. 使用 ConcurrentHashMap（高性能并发 Map，推荐）
2. 使用 Collections.synchronizedMap(new HashMap<>())（性能较低）
3. 使用 Hashtable（线程安全但性能差，较少使用）

2. ArrayList vs. Vector（高频对比）

对比项	`ArrayList`	`Vector`
线程安全	❌ 非线程安全	✅ 线程安全（synchronized）
底层数据结构	动态数组	动态数组
扩容方式	`1.5x` 扩容	`2x` 扩容
性能	高（无锁）	低（同步开销大）
适用场景	单线程	多线程（但 `CopyOnWriteArrayList` 更推荐）

💡 为什么 Vector 不推荐？

Vector 的方法使用 synchronized 关键字，导致所有方法都串行执行，性能较低。
多线程环境下，更推荐 CopyOnWriteArrayList 或 Collections.synchronizedList(new ArrayList<>())。

3. HashMap vs. ConcurrentHashMap（高频对比）

对比项	`HashMap`	`ConcurrentHashMap`
线程安全	❌ 非线程安全	✅ 线程安全
底层数据结构	数组 + 链表（JDK 1.7）数组 + 链表 + 红黑树（JDK 1.8）	JDK 1.7：分段锁 + 哈希表（Segment 机制） JDK 1.8：CAS + `synchronized` + 红黑树
`null` Key / Value	✅ 允许 `null` Key 和 `null` Value	❌ 不允许 `null` Key 和 `null` Value
并发性能	低（多线程可能出错）	高（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 结构类似。
核心优化：
1. CAS（Compare-And-Swap）机制：插入新元素时，先尝试用 CAS 方式写入，失败再加锁。
2. synchronized 代替 ReentrantLock：JDK 1.8 采用 Node 级别加锁，仅在 Hash 冲突时加锁，降低锁竞争。
3. 红黑树优化：当链表长度超过 8 时，转换为红黑树，提高查询性能。

💡 为什么 ConcurrentHashMap 性能更好？

HashTable 是全表锁，每次访问都需要 synchronized，性能低。
ConcurrentHashMap 采用 CAS + 局部锁，大幅提升并发性能。

5. 线程安全的解决方案（汇总）

线程不安全集合	线程安全替代方案
`ArrayList`	`CopyOnWriteArrayList` / `Collections.synchronizedList(new ArrayList<>())`
`HashSet`	`Collections.synchronizedSet(new HashSet<>())`
`HashMap`	`ConcurrentHashMap` / `Collections.synchronizedMap(new HashMap<>())`
`LinkedList`	`BlockingQueue`（如 `LinkedBlockingQueue`）

6. 总结

ArrayList vs. Vector
- ArrayList 非线程安全，性能高。
- Vector 线程安全，但同步开销大，不推荐。
- 推荐：CopyOnWriteArrayList（读多写少）。
HashMap vs. 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. 复杂度总结

操作	平均时间复杂度	最坏时间复杂度（链表）	最坏时间复杂度（红黑树）
`get(key)` 查询	`O(1)`	`O(n)`	`O(log n)`
`remove(key)` 删除	`O(1)`	`O(n)`	`O(log n)`

🔹 面试重点：

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
底层数据结构	哈希表（`HashMap`）	哈希表 + 双向链表	红黑树（`TreeMap`）
元素存储顺序	无序	按照插入顺序	自动排序（默认升序，可自定义）
是否排序	❌ 不排序	❌ 不排序（但保持插入顺序）	✅ 排序（按 `compareTo()` 规则）
允许 `null`	✅ 允许 1 个 `null`	✅ 允许 1 个 `null`	❌ 不允许 `null`
查询性能	🚀 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. 选择建议（如何选择？）

场景	推荐使用
需要去重，不关心顺序，查询性能最高	`HashSet`（最快）
需要去重，且保持插入顺序	`LinkedHashSet`
需要去重，且按大小排序	`TreeSet`

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`	哈希表（`HashMap`）	无序	🚀 `O(1)`	🚀 `O(1)`	❌
`LinkedHashSet`	哈希表 + 双向链表（`LinkedHashMap`）	插入顺序	🚀 `O(1)`	🚀 `O(1)`	❌
`TreeSet`	红黑树（`TreeMap`）	排序	🐌 `O(log n)`	🐌 `O(log n)`	✅

🔹 总结

HashSet 最快，但无序。
LinkedHashSet 有序，比 HashSet 稍慢。
TreeSet 自动排序，但性能最慢（O(log n)）。

问题8： HashMap 和 Hashtable 的区别？HashMap 和 HashSet 区别？HashMap 和 TreeMap 区别？ ConcurrentHashMap 和 Hashtable 的区别？

1. HashMap vs. Hashtable（区别）

对比项	HashMap	Hashtable
线程安全	❌ 非线程安全	✅ 线程安全（方法使用 `synchronized` 修饰）
底层数据结构	数组 + 链表（JDK 1.7）数组 + 链表 + 红黑树（JDK 1.8）	数组 + 链表
性能	🚀 高（无锁）	🐌 低（全表锁）
`null` 是否允许	✅ 允许 `null` key 和 `null` value	❌ 不允许 `null` key 和 `null` value
扩容方式	`capacity * 2`（翻倍扩容）	`capacity * 2 + 1`
适用场景	单线程或高并发（推荐使用 `ConcurrentHashMap`）	低并发场景（通常不推荐）

✅ 总结：

HashMap 性能更高，适用于 单线程或并发环境（推荐 ConcurrentHashMap）。
Hashtable 所有方法加锁，线程安全但性能低，一般不推荐使用。

💡 面试问法：

为什么 Hashtable 不推荐使用？
- Hashtable 全表锁，并发效率低，通常使用 ConcurrentHashMap 替代。

2. HashMap vs. HashSet（区别）

对比项	HashMap	HashSet
实现接口	`Map<K, V>`	`Set<E>`
数据存储方式	`key-value` 形式	仅存 `key`，值始终为 `new Object()`
底层数据结构	数组 + 链表 + 红黑树（JDK 1.8）	基于 `HashMap`，`value` 是固定对象
是否允许重复	❌ `key` 唯一，`value` 可重复	❌ 不允许重复元素
`null` 是否允许	✅ `key` 允许一个 `null`，`value` 可多个 `null`	✅ 允许一个 `null`
查询性能	🚀 `O(1)`	🚀 `O(1)`
适用场景	需要存储键值对（如用户 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
底层数据结构	数组 + 链表 + 红黑树	红黑树（`TreeMap`）
排序方式	❌ 无序	✅ 自动排序（默认升序）
查询性能	🚀 `O(1)`（无冲突）	🐌 `O(log n)`（红黑树）
`null` 是否允许	✅ `key` 允许 `null`	❌ `key` 不允许 `null`
适用场景	需要快速查找的键值对	需要排序的键值对（如排行榜）

✅ 总结：

HashMap 查询快（O(1)），无序，适合快速存取数据。
TreeMap 自动排序（O(log n)），适用于需要排序的场景。

💡 面试问法：

如果 HashMap 需要排序怎么办？
- 使用 TreeMap 或者 LinkedHashMap。

4. ConcurrentHashMap vs. Hashtable（区别）

对比项	ConcurrentHashMap（推荐）	Hashtable（已淘汰）
底层数据结构	JDK 1.7：分段锁（`Segment`） JDK 1.8：CAS + `synchronized`（红黑树）	哈希表 + 全表锁
锁的粒度	局部锁（高并发）	全表锁（低效）
查询性能	🚀 高（读 `O(1)`，写 `O(1)` ~ `O(log n)`)	🐌 低（所有方法 `synchronized`）
`null` 是否允许	❌ 不允许 `null` key/value	❌ 不允许 `null` key/value
适用场景	高并发环境（推荐）	低并发环境（已淘汰）

✅ 总结：

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 + `synchronized`（JDK 1.8）
查询性能	🚀 `O(1)` vs. 🐌 `O(1)`（但有锁）	🚀 `O(1)` vs. 🚀 `O(1)`	🚀 `O(1)` vs. 🐌 `O(log n)`	🚀 `O(1)` vs. 🐌 `O(1)`（但有锁）
是否排序	❌ 都无序	❌ 都无序	❌ HashMap 无序，✅ TreeMap 排序	❌ 都无序
null 允许性	HashMap 允许 `null` key/value，Hashtable 不允许 `null`	✅ HashSet 允许一个 `null`	❌ TreeMap 不允许 `null` key	❌ ConcurrentHashMap 不允许 `null`

🚀 面试重点：

高并发环境：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 操作 保证线程安全。