《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 树，尤其适合 的应用场景。
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
【八股真解】精炼最新高频面经 文章被收录于专栏
本专栏在精不在多，内容分为八股文、大厂真实面经，面试通过后将offer和面试题私发给我，可退还专栏的收益部分费用。欢迎大家共建专栏
