《JAVA八股真解》二、集合

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

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

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

核心接口说明：

• 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 会自动扩容至原容量的两倍。

扩容机制

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

链表与红黑树

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

为什么用红黑树？

• 红黑树是一种平衡二叉搜索树，保证了在最坏情况下查找时间复杂度为 O(log n)，而链表为 O(n)。
• 在高并发场景下，红黑树能显著提升性能。

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

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

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

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

4. HashMap 什么时候扩容？

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

1. JDK 1.7 及之前版本：

   • 当元素数量超过 threshold = capacity * loadFactor 时，触发扩容。
   • 默认初始容量为 16，负载因子为 0.75，首次扩容发生在第 13 个元素插入后。

2. JDK 1.8 及以后版本：

   • 同样基于 threshold 触发扩容。
   • 但新增了“树化”机制：当链表长度超过 8 且数组容量大于 64 时，链表转为红黑树。
   • 若链表长度小于 6，且数组容量小于 64，则不会触发扩容。

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

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

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

1. 优化哈希算法：

   • 使用位运算代替取模运算：(n - 1) & hash 相当于 hash % n。
   • 例如：若容量为 16（即 2^4），则 (15) & hash 能快速定位桶的位置。

2. 减少冲突：

   • 2 的幂次方可以均匀分布哈希值，降低碰撞概率。
   • 如果容量不是 2 的幂，可能导致某些桶被频繁访问，造成“热点”问题。

3. 便于扩容：

   • 每次扩容都是原容量的两倍，始终满足 2 的幂次方，简化了扩容逻辑。

示例：

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

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

6. HashMap 和 Hashtable 的区别

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

7. ConcurrentHashMap 和 HashMap 的区别

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

实现机制（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. 集合常见面试题汇总

1. ArrayList 和 LinkedList 的区别？

   • ArrayList：基于数组，随机访问快（O(1)），插入删除慢（O(n)）。
   • LinkedList：基于链表，插入删除快（O(1)），随机访问慢（O(n)）。

2. HashSet 和 TreeSet 的区别？

   • HashSet：无序，基于 HashMap 实现，允许 null。
   • TreeSet：有序，基于红黑树，不允许 null。

3. HashMap 的 put 方法流程？

   • 计算 hash 值 → 定位桶 → 若桶为空直接插入 → 若存在冲突判断是否为红黑树 → 插入链表或红黑树 → 若链表长度 > 8 且容量 > 64，则转为红黑树。

4. ConcurrentHashMap 的并发级别如何设置？

   • 并发级别决定了内部 segment 数量，默认为 16，可根据预期并发数调整。

5. HashMap 的扩容时机？

   • 当元素数量超过 threshold = capacity * loadFactor 时触发扩容。