跳至主要内容

Java集合

IT枫斗者大约 8 分钟Java八股文Java八股文Java集合

阅读提示

建议先看题目目录，再按“概念 -> 原理 -> 场景 -> 优化”顺序复习。
每题先讲结论，再补关键机制和项目实践，回答会更稳。

回答提示：是一种比较通俗的解释，比较好理解，如果‘参考答案’不太好记住，可以直接复习回答提示也可以。

适用版本：本文以 Java SE 21 API 为准；ArrayList 容量增长细节以 OpenJDK 21 实现为例，属于实现细节而非接口保证。历史实现差异另行标注。

1、Java中的集合类有哪些？如何分类的？(此问题基本不会被问到，但是要大体理解整个集合的内容，如果能记住此问题（灵活记住），面试集合的基础问题基本都可以回答)

回答提示：

  • List（列表）：List接口及其实现类用于存储一组有序的元素。元素可以重复，且可以通过索引访问。常见的List实现类有ArrayList、LinkedList等。ArrayList基于动态数组实现，访问元素速度快；LinkedList基于双向链表实现，已定位节点或操作两端时插删为 O(1)，按索引定位仍需 O(n)。
  • Set（集合）：Set接口及其实现类用于存储不重复的元素；是否有确定遍历顺序取决于实现。Set不允许出现重复元素，因此常用于去重操作。常见的Set实现类有HashSet、TreeSet等。HashSet基于哈希表实现，不保证遍历顺序；LinkedHashSet 通常按插入顺序遍历；TreeSet基于红黑树实现，元素会按照自然顺序或者自定义顺序排序。
  • Queue（队列）：Queue接口及其实现类用于在处理前保存元素，出队顺序由实现决定，通常是 FIFO，但优先队列并非如此。常见的Queue实现类有LinkedList（也实现了List接口）、PriorityQueue等。LinkedList可以用作双端队列；PriorityQueue是一个基于优先级堆的无界队列，元素的排序方式可以通过比较器来定义。
  • Map（映射）：Map接口及其实现类用于存储键值对。键是唯一的，每个键都映射到一个值。常见的Map实现类有HashMap、TreeMap等。HashMap基于哈希表实现，键值对存储无序；TreeMap基于红黑树实现，键会按照自然顺序或者自定义顺序排序。

参考回答：

  • 集合类存放于 java.util 包中，常见接口包括 List（列表）、Set（集）、Queue（队列）和 Map（映射）。List、Set、Queue 都属于 Collection 体系；Queue 不是 List 的子接口，Map 是独立体系。
  • Collection：Collection 是集合 List、Set、Queue 的最基本的接口。
  • Iterator：迭代器，可以通过迭代器遍历集合中的数据
  • Map：是映射表的基础接口
img
img
  • 上图可辅助理解；接口关系以文字和官方 API 为准。Java 21 还引入了表达确定遍历顺序的 SequencedCollection、SequencedSet、SequencedMap 等接口。ArrayList 常见扩容约为 1.5 倍，具体边界见第 3 题。

官方资料：Collection、Set、Queue。

2、那些集合是线程安全的？

参考回答：

  1. Vector：一个线程安全的List实现，它的大部分方法都是同步的，因此可以在多线程环境中使用。不过，由于同步操作会带来性能开销，所以在不需要线程安全的场合，建议使用ArrayList。
  2. Hashtable：一个线程安全的Map实现，它同样是同步的，可以在多线程环境中使用。与HashMap相比，Hashtable的性能可能稍差一些，因为同步操作会增加额外的开销。
  3. Stack：一个线程安全的栈实现，它也是同步的，可以在多线程环境中使用。单线程栈通常优先使用 Deque 的实现（如 ArrayDeque）；ArrayDeque 本身不保证线程安全。
  4. ConcurrentHashMap：线程安全的 Map 实现（不是 HashMap 的子类）。OpenJDK 7 使用 Segment 分段锁；OpenJDK 8 起主要使用 CAS 和桶级 synchronized 协调更新，普通 get 通常不加锁。不允许 null 键或值，不能把吞吐量优势视为所有负载下的保证。
  5. CopyOnWriteArrayList：一个线程安全的List实现，它通过在写操作时复制整个数组来实现线程安全。这种策略适用于读多写少的场景，因为写操作会涉及到复制整个数组，所以性能开销较大。

线程安全的方法不等于任意复合操作都原子化。例如 if (!map.containsKey(k)) map.put(k, v) 有检查与写入之间的竞争窗口，可使用 ConcurrentHashMap.putIfAbsent(k, v) 完成原子条件插入。多键操作仍不构成事务。

官方资料：ConcurrentHashMap、Stack。

3、ArrayList的扩容机制是什么？

回答提示：

  • 初始容量：OpenJDK 21 的无参构造器使用共享空数组，首次添加时通常分配容量 10；new ArrayList<>(n) 则按显式容量处理，不能混为一谈。
  • 扩容触发：当向ArrayList中添加元素，且当前元素数量达到容量上限时，就会触发扩容操作。
  • 扩容策略：ArrayList的扩容策略是增长大约50%的容量。
  • 数组复制：扩容过程中，ArrayList会创建一个新的、更大容量的数组，并将原有数组中的所有元素复制到新数组中。

参考回答：

  • 以 OpenJDK 21 为例，容量不足时，优先增长量是 oldCapacity >> 1，新容量还必须满足本次操作的最小需求，并处理数组长度上限。批量添加时，最小需求可能超过约 1.5 倍的容量。增长策略属于 JDK 类库实现细节，不能归因于 JVM 随意选择倍数。
  • 扩容会分配新数组并复制已有元素引用，不会克隆元素对象。一次扩容需要 O(n) 复制，连续尾部添加的均摊时间复杂度为 O(1)。size 是实际元素个数，capacity 是内部数组长度。
无参构造：size=0，内部空数组
首次 add：size=1，capacity=10
第 11 次逐个 add：容量 10 → 15，复制原有引用后写入
第 16 次逐个 add：容量 15 → 22（15 + (15 >> 1)）

这是根据源码推导的普通逐个追加示意，假定中途未调用 ensureCapacity、trimToSize 等方法，不是运行测量结果。

官方资料：OpenJDK 21 ArrayList 源码（构造器、grow、add）。

4、ArrayList和linkedList的区别？

回答提示：

  • 内部实现：ArrayList是基于动态数组实现的，底层数组存放连续的元素引用，引用指向的对象不保证连续；而LinkedList则是基于双向链表实现，元素通过指针相互连接。
  • 随机访问：ArrayList支持快速随机访问，时间复杂度为O(1)；LinkedList则需要遍历，时间复杂度为O(n)。
  • 内存占用：LinkedList每个节点除了存储数据外，还需要存储指向前一个和后一个节点的指针，因此比ArrayList更占内存。
  • 使用场景：ArrayList适用于需要频繁进行随机访问的场景；LinkedList 的优势限于两端操作或已通过迭代器定位后的局部插删；按索引插删仍有 O(n) 的定位成本。

参考回答：

  • ArrayList：基于动态数组，适合按下标访问；中间插删需移动后续引用，通常为 O(n)。预估元素数量并指定合理容量可以减少扩容，但是否快于其他结构应结合实际负载判断。
  • LinkedList：基于双向链表，按索引访问会从较近的一端遍历。两端插删或迭代器已定位后的插删为 O(1)，按索引插删整体通常仍为 O(n)。
  • 遍历 LinkedList 可使用增强 for、iterator 或 listIterator，总体为 O(n)。应避免 for (int i = 0; i < list.size(); i++) list.get(i)，反复按索引定位会使整体退化为 O(n²)。问题在于 get(i)，并不是 for 语法本身。indexOf 同样需要线性查找，找不到时返回 -1。

官方资料：LinkedList（实现与索引访问说明）。

5、HashMap和HashTable有什么区别？

回答提示：

  • 线程安全性：HashMap是非线程安全的，而HashTable是线程安全的。HashTable通过synchronized关键字实现同步，但可能导致性能下降。
  • null值处理：HashMap允许null作为键和值，而HashTable不允许。
  • 性能：由于HashMap不需要考虑线程同步，通常性能更高。

参考回答：

区别 ：

线程安全性

  • HashMap方法没有synchronized修饰，线程非安全，HashTable线程安全；

空键和空值：

  • HashMap允许key和value为null，而HashTable不允许

历史遗留：（了解）

  • Hashtable 是 Java 1.0 中的遗留类，虽然仍然可以使用，但通常建议使用 HashMap，并结合 java.util.concurrent 包中的现代并发类来处理多线程问题。
  • HashMap 是在 Java 2 中引入的，设计更现代化，使用也更加灵活。

迭代器：(了解)

  • HashMap 使用的是快速失败（fail-fast）的迭代器，如果在创建迭代器后对集合进行了结构上的修改（除了使用迭代器自身的 remove 方法外），迭代器可能抛出 ConcurrentModificationException；fail-fast 只是尽力检测错误，不能作为并发正确性的保证。
  • Hashtable 的 keySet()、entrySet() 等集合视图也提供 fail-fast 迭代器；只有 keys()、elements() 返回的旧式 Enumeration 不是 fail-fast。枚举期间结构被修改，结果未定义，并不意味着枚举可安全并发使用。

性能：（了解）

  • 在没有线程安全需求的场景中，HashMap 通常比 Hashtable 性能更高，因为它没有同步的开销。

官方资料：Hashtable（迭代器、Enumeration 与线程安全）。