文日小栈
← 返回文章

集合

发布于 2026/10/19
Java

1. 完整回答

Java 集合框架（Java Collections Framework）是 Java 提供的一套统一的数据存储和操作机制，主要解决对象的存储、查找、去重、排序和遍历等问题。

整个框架主要分为 Collection 和 Map 两大体系。

Collection 主要管理单个元素，包括 List、Set 和 Queue。List 支持重复元素和按索引访问，常用 ArrayList；Set 用于元素去重，常用 HashSet；Queue 用于队列处理，常用 ArrayDeque 和 BlockingQueue。

Map 用于存储键值对，常用的是 HashMap，它通过哈希表实现快速查找，正常情况下，插入和查询的时间复杂度接近 O(1)。

这些集合的主要区别来自底层数据结构。比如 ArrayList 基于动态数组，随机访问效率高；LinkedList 基于双向链表，适合已定位节点后的插入和删除；HashMap 基于哈希表，通过哈希值定位元素，发生哈希冲突时通过链表或红黑树处理。

另外，线程安全和顺序保证也是集合选型的重要因素。比如 HashMap 不保证遍历顺序，也不支持无同步的并发修改；LinkedHashMap 可以维护插入顺序或访问顺序；ConcurrentHashMap 适合多线程共享键值数据。

2. 核心原理与关键概念

2.1 核心原理

Java 集合的核心是统一接口、不同数据结构实现，以及根据使用场景选择合适的时间和空间开销。

  1. 集合的接口设计

通过接口定义统一操作，再由不同实现类提供具体的数据存储方式。

  • Collection → List、Set、Queue

  • Queue → Deque

  • Map → HashMap、LinkedHashMap、TreeMap

Map 是独立接口，没有继承 Collection。

  1. 动态数组机制

以 ArrayList 为例：

添加元素 → 检查数组容量 → 容量不足时扩容并复制数据 → 写入新元素。

数组支持通过索引直接定位，因此随机访问是 O(1)。中间插入或删除通常需要移动元素，时间复杂度是 O(n)。

  1. 哈希表机制

以 HashMap 为例：

计算 Key 的 hashCode() → 扰动处理并定位数组桶 → 比较桶内 Key → 更新已有值或插入新节点 → 必要时扩容。

在 Java 8 及后续常见 JDK 实现中，哈希冲突主要通过链表和红黑树处理。正常情况下，哈希分布比较均匀，查找效率接近 O(1)。

  1. 集合的并发机制

普通集合通常需要外部同步来处理并发修改。

并发集合会使用适合自身场景的线程安全机制：

  • ConcurrentHashMap：通过 CAS、局部加锁等机制协调并发更新。

  • CopyOnWriteArrayList：写入时复制底层数组，读取和遍历使用稳定的数组。

  • BlockingQueue：通过线程安全的队列操作和阻塞等待实现生产者与消费者之间的数据传递。

2.2 关键概念

概念 含义
有序性 集合是否保证特定的遍历顺序，例如插入顺序或排序顺序
唯一性 Set 元素不能重复，Map 的 Key 不能重复
哈希冲突 不同 Key 经过哈希定位后落到同一个桶
负载因子 控制哈希表空间利用率和扩容时机，HashMap 默认是 0.75
扩容 容量不足时扩大底层存储空间，可能涉及数据复制或重新分布
线程安全 多线程访问和修改集合时，能否保证操作符合规定的并发语义

这里有一个容易混淆的地方：有序需要明确具体含义。List 保证元素的位置顺序，LinkedHashMap 可以保证插入顺序，TreeMap 保证按照 Key 的比较规则排序。

3. 高频面试追问

3.1 Collection、Collections 和 Map 有什么区别？

Collection 和 Map 是集合框架中的两类核心接口，Collections 是集合工具类。

Collection 定义了单个元素集合的通用操作，比如添加、删除、遍历和判断是否包含元素。List、Set、Queue 都继承了 Collection。

Map 用于存储 Key-Value 映射，Key 唯一，可以通过 Key 查找对应的 Value。它提供 put()、get()、remove() 等操作，还能通过 keySet() 和 entrySet() 获取集合视图。

Collections 则提供集合相关的工具方法，比如排序、反转，以及创建同步包装集合、不可修改的集合视图等。

它们各自承担不同职责，也体现了 Java 集合框架面向接口编程的设计方式。

3.2 ArrayList 和 LinkedList 有什么区别？为什么通常优先选择 ArrayList？

ArrayList 基于动态数组，LinkedList 基于双向链表。大多数普通列表场景，我会优先使用 ArrayList。

ArrayList 的元素通过数组连续存放引用，因此按索引访问是 O(1)，尾部添加的均摊复杂度也是 O(1)。如果在中间插入或删除元素，需要移动后续元素，复杂度是 O(n)。

LinkedList 通过前后节点引用维护数据，首尾插入和删除是 O(1)。但按索引访问需要遍历链表，复杂度是 O(n)。

虽然 LinkedList 的节点插入和删除很快，但如果需要先查找位置，整体仍然可能是 O(n)。而且 LinkedList 的节点对象存在额外内存开销，访问时的缓存局部性也较差。

所以普通的业务列表、查询结果和频繁遍历的场景，我通常选择 ArrayList。需要频繁操作两端时，可以考虑 ArrayDeque。

3.3 HashMap 的底层结构是什么？put 和 get 是怎么实现的？

HashMap 底层采用哈希表，在常见的 Java 8 及后续 JDK 实现中，主要由数组、链表和红黑树组成。

执行 put() 时，首先计算 Key 的哈希值，再经过扰动处理，通过数组长度定位到对应的桶。

如果桶为空，就直接插入；如果桶内已经存在元素，就比较哈希值和 Key 是否相等。如果找到相同的 Key，就更新 Value；否则添加新的节点。

当同一个桶中的节点数量较多，并且数组容量满足条件时，链表可以转换为红黑树，从而降低大量哈希冲突造成的查找成本。

get() 的过程类似：计算哈希值 → 定位桶 → 在桶内查找匹配的 Key → 返回 Value。

正常情况下，HashMap 的插入和查询效率接近 O(1)。如果哈希冲突严重，性能就会下降。

继续追问：HashMap 的 get() 返回 null，就说明 Key 不存在吗？

不能直接这样判断。HashMap 允许一个 null Key，也允许多个 null Value。如果 Key 对应的 Value 本来就是 null，get() 同样返回 null。需要明确判断 Key 是否存在时，可以使用 containsKey()。

3.4 HashMap 为什么要扩容？为什么默认负载因子是 0.75？

HashMap 扩容主要是为了控制哈希冲突，默认负载因子 0.75 是时间效率和空间利用率之间的折中。

HashMap 的默认初始容量是 16，默认负载因子是 0.75。

它通过容量和负载因子计算扩容阈值。比如容量为 16 时，阈值是 12，当插入新元素导致数量超过 12，就会触发扩容。

在常见 JDK 实现中，扩容通常会把桶数组容量扩大为原来的两倍，并重新分布已有节点。

负载因子太高，桶内冲突可能增多，查询性能下降；负载因子太低，会浪费空间。

另外，扩容需要重新分布数据，会带来额外开销。所以如果提前知道数据规模，我会合理设置初始容量，减少不必要的扩容。

3.5 为什么 HashMap 的 Key 要同时重写 equals() 和 hashCode()？

因为 HashMap 通过 hashCode() 定位元素，再通过 equals() 判断 Key 是否相等，两者必须满足一致性约定。

hashCode() 主要负责计算哈希值，帮助定位桶；equals() 负责判断两个 Key 在业务意义上是否相等。

如果两个对象通过 equals 判断相等，它们的 hashCode 必须相同；但 hashCode 相同的对象，equals 不一定返回 true，因为可能发生哈希冲突。

如果只重写 equals，没有同步重写 hashCode，就可能出现两个逻辑相等的 Key 被放在不同桶里，导致查询失败或重复存储。

还有一个问题是可变 Key。比如把用户对象作为 Key，放入 HashMap 后修改了参与 hashCode 计算的用户 ID，就可能无法通过这个对象正常查找到原来的数据。

所以我通常优先使用 String、Integer 等不可变对象作为 Key，自定义 Key 也会尽量让参与相等性判断的字段保持不变。

3.6 HashSet 为什么能去重？它和 TreeSet 有什么区别？

HashSet 通过 HashMap 实现元素唯一性，TreeSet 则通过比较规则判断元素是否重复，并维护排序顺序。

HashSet 底层使用 HashMap，把 Set 中的元素作为 Map 的 Key，Value 使用固定的占位对象。

添加元素时，先根据 hashCode 定位，再通过 equals 判断是否已经存在相同元素。存在就不再添加。

TreeSet 底层基于 TreeMap，采用红黑树结构。它通过自然排序或者 Comparator 比较元素，当比较结果为 0 时，就认为元素在集合中已经存在。

所以 HashSet 适合普通去重，平均增删查复杂度是 O(1)；TreeSet 适合去重后还需要排序、范围查询的场景，基本操作是 O(log n)。

使用 TreeSet 时，我会保证比较规则与 equals 尽量一致，避免业务上不同的对象因为比较结果为 0 而被当成重复元素。

3.7 HashMap、LinkedHashMap 和 TreeMap 应该怎么选择？

主要看是否需要顺序，以及需要什么类型的顺序。

HashMap 基于哈希表，平均查询效率高，不保证遍历顺序，适合普通的键值查询。

LinkedHashMap 在哈希表基础上维护双向链表，默认保持插入顺序，也可以配置为访问顺序。基本操作平均仍接近 O(1)，但需要额外维护链表。

TreeMap 基于红黑树，可以按照 Key 的自然顺序或者指定比较器进行排序，查询、插入和删除的时间复杂度都是 O(log n)。

项目里，如果只需要通过 ID 查询对象，我会用 HashMap；如果接口返回数据需要保持固定的插入顺序，我会用 LinkedHashMap；如果要按时间或数值范围查找，就会考虑 TreeMap。

LinkedHashMap 还有一个典型用途，就是实现简单的 LRU 缓存。配置访问顺序后，最近访问的元素会移动到链表后面，再结合淘汰最旧元素的机制，就可以实现最近最少使用策略。

3.8 HashMap 为什么线程不安全？ConcurrentHashMap 怎么实现线程安全？

HashMap 没有提供并发读写的同步保障，ConcurrentHashMap 通过线程安全的并发访问机制解决了这个问题。

多个线程同时修改 HashMap 时，可能因为缺少同步产生更新丢失、数据状态不一致等问题，扩容和节点修改也可能发生竞争。

ConcurrentHashMap 针对并发访问做了专门设计。在 Java 8 及后续常见实现中，它通过 CAS 和桶级别的同步机制等协调更新，读取通常不需要加锁，从而减少线程之间的竞争。

它还提供 putIfAbsent()、compute()、merge() 等支持原子更新的方法，适合并发更新单个 Key 的场景。

但需要注意，ConcurrentHashMap 的单个线程安全方法，并不意味着多个方法组合后自动具有原子性。比如先 get() 再 put()，仍然可能发生并发竞争。

另外，ConcurrentHashMap 不允许 null Key 和 null Value，这样可以避免并发场景中对 null 返回值的歧义。

继续追问：两个线程同时对同一个 Key 进行计数，应该怎么处理？

我会使用 compute() 或 merge() 完成原子更新。如果是高并发计数场景，也可以让 ConcurrentHashMap 的 Value 使用 LongAdder，通过 computeIfAbsent() 初始化计数器后执行 increment()，减少计数更新时的竞争。

3.9 什么是 ConcurrentModificationException？遍历集合时怎么安全删除元素？

ConcurrentModificationException 通常表示迭代期间检测到了不符合迭代规则的结构性修改。

像 ArrayList、HashMap 这样的集合，迭代器一般采用快速失败机制，也就是 fail-fast。

迭代器会检测集合的结构性修改。如果遍历过程中直接通过集合对象添加或删除元素，后续迭代操作可能抛出 ConcurrentModificationException。

这种异常即使在单线程环境下也可能出现，而且检测属于尽力而为，不能依靠它保证线程安全。

如果要边遍历边删除，我会优先使用 Iterator.remove()，或者使用集合提供的 removeIf()。

如果需要支持并发遍历和修改，可以根据场景选择 ConcurrentHashMap 或 CopyOnWriteArrayList。

其中 CopyOnWriteArrayList 的迭代器读取创建时的数组快照，后续修改不会影响当前遍历；ConcurrentHashMap 使用弱一致性遍历，可能观察到部分并发更新。两者的遍历语义不同。

3.10 Queue、Deque 和 BlockingQueue 有什么区别？项目中怎么选？

Queue 负责队列操作，Deque 支持两端操作，BlockingQueue 进一步提供线程安全和阻塞等待能力。

Queue 定义了入队、出队和查看队头的通用接口，典型方法包括 offer()、poll()、peek()。

Deque 是双端队列，可以在队头和队尾添加或删除元素，因此也可以实现栈。

如果是单线程下的普通先进先出队列，或者需要实现栈，我通常使用 ArrayDeque。

如果任务需要按照优先级执行，可以使用 PriorityQueue。它基于堆实现，入队和出队通常是 O(log n)，每次取出的都是当前优先级最高的元素，但直接遍历不保证排序顺序。

如果是多线程生产者消费者模型，我会使用 LinkedBlockingQueue 等阻塞队列。比如任务生产者调用 put() 放入任务，消费者调用 take() 获取任务，队列为空时消费者可以阻塞等待，省去了手动轮询。

4. 易混淆概念对比

4.1 Collection、Collections、Map

对比项 Collection Collections Map
类型 接口 工具类 接口
作用 定义元素集合操作 提供集合相关工具方法 定义键值映射操作
典型操作 add、remove、contains sort、reverse、synchronizedList put、get、containsKey
代表实现 ArrayList、HashSet 无需实现 HashMap、TreeMap

4.2 ArrayList 与 LinkedList

对比项 ArrayList LinkedList
底层结构 动态数组 双向链表
按索引访问 O(1) O(n)
尾部添加 均摊 O(1) O(1)
头部插入 O(n) O(1)
中间插入 O(n)，需要移动元素 查找位置 O(n)，定位后插入 O(1)
内存开销 较低，可能存在预留容量 较高，每个节点保存前后引用
适用场景 随机访问、遍历、普通列表 频繁操作首尾节点

4.3 HashMap、LinkedHashMap、TreeMap

对比项 HashMap LinkedHashMap TreeMap
底层结构 哈希表 哈希表 + 双向链表 红黑树
遍历顺序 不保证 插入顺序或访问顺序 按 Key 排序
查询复杂度 平均 O(1) 平均 O(1) O(log n)
线程安全 否 否 否
典型场景 快速键值查询 保序数据、简单 LRU 缓存 有序查询、范围查询

4.4 HashMap、Hashtable、ConcurrentHashMap

对比项 HashMap Hashtable ConcurrentHashMap
线程安全 否 是 是
同步方式 无内置同步 方法级 synchronized CAS、局部同步等机制
并发性能 需外部同步 锁竞争相对明显 适合高并发访问
null Key 允许一个 不允许 不允许
null Value 允许 不允许 不允许
使用场景 普通单线程数据处理 旧系统兼容 多线程共享 Map

4.5 快速失败、快照遍历、弱一致性遍历

对比项 快速失败 快照遍历 弱一致性遍历
典型集合 ArrayList、HashMap CopyOnWriteArrayList ConcurrentHashMap
检测结构修改 尝试抛出异常 不抛出该修改异常 不抛出该修改异常
遍历期间修改 可能触发 ConcurrentModificationException 当前迭代器保持原快照 可能看到部分新数据
核心特点 尽力检测错误修改 遍历结果稳定 支持并发访问
主要限制 无法用于保证线程安全 写入复制成本较高 不提供整个 Map 的一致快照

5. 总结

Java 集合框架主要用于管理对象的存储、查找、去重、排序和遍历，通过统一接口提供不同的数据结构实现。

它主要包括 Collection 和 Map 两个体系，Collection 下面有 List、Set、Queue 等接口，Map 用于管理键值对。

从底层机制看，ArrayList 使用动态数组，适合随机访问；HashMap 使用哈希表，正常情况下可以实现接近 O(1) 的查询；TreeMap 使用红黑树，适合有序查询。

实际开发中，我会根据数据是否重复、是否需要顺序、访问和修改频率，以及线程安全要求来选择实现。普通列表优先考虑 ArrayList，键值查询使用 HashMap，需要排序时考虑 TreeMap，多线程共享映射使用 ConcurrentHashMap。集合的选择最终还是要结合操作成本和业务场景，避免只根据某一个操作的时间复杂度来判断。