《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 树，尤其适合 的应用场景。