《JAVA八股真解》二、集合

#JAVA##JAVA面经##JAVA内推#

1. Java 常用的集合、分类及涉及的接口

Java 集合主要分为四大类：List、Set、Map 和 Queue，它们都继承自 Collection 接口或 Map 接口。

类型	特性	实现类
List	有序，允许重复元素	`ArrayList`, `LinkedList`, `Vector`
Set	无序，不允许重复元素	`HashSet`, `TreeSet`, `LinkedHashSet`
Map	键值对存储，键唯一	`HashMap`, `TreeMap`, `LinkedHashMap`
Queue	队列结构，先进先出（FIFO）	`ArrayDeque`, `PriorityQueue`, `LinkedList`

核心接口说明：

Collection 接口：所有集合类的根接口，包含 add()、remove()、size() 等基本方法。
List 接口：按顺序存储元素，支持索引访问，常用实现有 ArrayList（动态数组）、LinkedList（双向链表）。
Set 接口：不包含重复元素，常用实现有 HashSet（基于哈希表）、TreeSet（基于红黑树，有序）。
Map 接口：存储键值对（key-value），通过键快速查找值，常用实现有 HashMap、TreeMap。
Iterator 接口：迭代器，用于遍历集合中的元素，可通过 iterator().next() 和 hasNext() 方法进行遍历。

提示：Iterator 是集合通用的遍历方式，适用于所有实现了 Iterable 接口的集合类。

2. HashMap 底层原理

从 JDK 1.8 开始，HashMap 的底层结构由“数组 + 链表”升级为“数组 + 链表 + 红黑树”。

基本结构

数组：存储桶（bucket），每个桶可以存放一个链表或红黑树。
链表/红黑树：当某个桶中元素过多时，会转换为红黑树以提高查询效率。

关键参数

默认负载因子（load factor）：0.75，表示当桶的数量达到容量的 75% 时触发扩容。
默认初始容量（capacity）：16，即数组大小为 16。
阈值（threshold）：capacity * load factor，即扩容临界点。

注意：当元素数量超过 threshold 时，HashMap 会自动扩容至原容量的两倍。

扩容机制

当元素数量达到 threshold 时，触发扩容。
创建新数组，大小为原数组的两倍。
将原有元素重新计算哈希值并插入新数组中。
这个过程称为“rehashing”，虽然耗时，但能有效提升性能。

链表与红黑树

链表：当桶中元素少于 8 个时，使用链表存储。
红黑树：当链表长度超过 8 且数组容量大于 64 时，链表转换为红黑树；反之则转回链表。

为什么用红黑树？

红黑树是一种平衡二叉搜索树，保证了在最坏情况下查找时间复杂度为 O(log n)，而链表为 O(n)。

在高并发场景下，红黑树能显著提升性能。

3. HashMap 为什么用红黑树不用 B 树？

尽管 B 树也是一种高效的平衡树，但 HashMap 选择红黑树的原因如下：

B 树的节点通常包含多个关键字，而红黑树每个节点只有一个关键字，更适合单键查找。
红黑树的插入、删除、查找平均时间复杂度均为 O(log n)，且实现相对简单。
B 树需要维护多个子节点指针，增加了内存开销和实现复杂度。
HashMap 主要用于单次查找，不需要频繁的范围查询，因此红黑树更合适。

结论：红黑树在插入、删除、查找上的综合表现优于 B 树，尤其适合 HashMap 的应用场景。

4. HashMap 什么时候扩容？

HashMap 的扩容发生在以下两种情况：

JDK 1.7 及之前版本：
- 当元素数量超过 threshold = capacity * loadFactor 时，触发扩容。
- 默认初始容量为 16，负载因子为 0.75，首次扩容发生在第 13 个元素插入后。
JDK 1.8 及以后版本：
- 同样基于 threshold 触发扩容。
- 但新增了“树化”机制：当链表长度超过 8 且数组容量大于 64 时，链表转为红黑树。
- 若链表长度小于 6，且数组容量小于 64，则不会触发扩容。

总结：扩容是为了避免哈希冲突过多导致性能下降，保持良好的查找效率。

5. HashMap 的长度为什么是 2 的 N 次方？

HashMap 的容量设计为 2 的幂次方，原因如下：

优化哈希算法：
- 使用位运算代替取模运算：(n - 1) & hash 相当于 hash % n。
- 例如：若容量为 16（即 2^4），则 (15) & hash 能快速定位桶的位置。
减少冲突：
- 2 的幂次方可以均匀分布哈希值，降低碰撞概率。
- 如果容量不是 2 的幂，可能导致某些桶被频繁访问，造成“热点”问题。
便于扩容：
- 每次扩容都是原容量的两倍，始终满足 2 的幂次方，简化了扩容逻辑。

示例：

int index = (table.length - 1) & hash;

此操作比 hash % table.length 更高效，且结果一致。

6. HashMap 和 Hashtable 的区别

对比项	HashMap	Hashtable
线程安全	不线程安全（非同步）	线程安全（同步）
null 值处理	允许 key 和 value 为 null	不允许任何 null 值
性能	性能更高，适合单线程环境	性能较低，因加锁机制
继承关系	继承自 `AbstractMap`	继承自 `Dictionary`（已废弃）

补充：Hashtable 是早期 Java 中的集合类，已被 ConcurrentHashMap 替代。

7. ConcurrentHashMap 和 HashMap 的区别

ConcurrentHashMap 是 HashMap 的线程安全版本，专为多线程环境设计。

对比项	ConcurrentHashMap	HashMap
线程安全性	线程安全，支持并发读写	非线程安全
锁粒度	分段锁（Segment）或 CAS + synchronized（JDK 8+）	无锁机制
性能	高并发下性能更好	单线程下性能优
null 值支持	不允许 null key 或 value	允许 null 值

实现机制（JDK 8+）

使用 CAS + synchronized 实现无锁操作。
数据结构仍为“数组 + 链表 + 红黑树”，但每个桶独立加锁。
支持并发读写，读操作无需等待，写操作通过 CAS 安全更新。

优势：相比 Hashtable 的全局锁，ConcurrentHashMap 提供更高的并发性能。

8. ConcurrentHashMap 和 Hashtable 如何保证线程安全？

ConcurrentHashMap

分段锁机制（JDK 7）：将整个 map 划分为多个 segment，每个 segment 独立加锁。
CAS + synchronized（JDK 8）：取消 segment，采用 CAS 操作配合 synchronized 保证原子性。
读写分离：读操作无锁，写操作仅对当前桶加锁，极大提升了并发能力。

Hashtable

全局锁：所有操作都需获取同一个锁，导致并发性能极低。
Synchronized 包装：每个方法都被 synchronized 修饰，阻塞其他线程。

结论：ConcurrentHashMap 通过细粒度锁和 CAS 技术，在保证线程安全的同时提供更高的并发性能。

9. 集合常见面试题汇总

ArrayList 和 LinkedList 的区别？
- ArrayList：基于数组，随机访问快（O(1)），插入删除慢（O(n)）。
- LinkedList：基于链表，插入删除快（O(1)），随机访问慢（O(n)）。
HashSet 和 TreeSet 的区别？
- HashSet：无序，基于 HashMap 实现，允许 null。
- TreeSet：有序，基于红黑树，不允许 null。
HashMap 的 put 方法流程？
- 计算 hash 值 → 定位桶 → 若桶为空直接插入 → 若存在冲突判断是否为红黑树 → 插入链表或红黑树 → 若链表长度 > 8 且容量 > 64，则转为红黑树。
ConcurrentHashMap 的并发级别如何设置？
- 并发级别决定了内部 segment 数量，默认为 16，可根据预期并发数调整。
HashMap 的扩容时机？
- 当元素数量超过 threshold = capacity * loadFactor 时触发扩容。