罗罗编程学习记录
本页内容 展开查看

04.1.1.3 集合:List、Set 与迭代

所属:全栈开发面试题库 / 04 后端语言与运行时 / 04.1 Java / 04.1.1 语言基础与现代特性

04.1.1.3-001 Java 集合体系的顶层结构是怎样的?

一句话结论

Collection 下分 List(有序可重复)、Set(不重复)、Queue(队列);Map 独立为键值对体系。

概念解释

  • List:ArrayList、LinkedList、Vector、CopyOnWriteArrayList。
  • Set:HashSet、TreeSet、LinkedHashSet。
  • Queue:ArrayDeque、PriorityQueue、BlockingQueue。
  • Map:HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap。

原理流程

集合按元素组织方式分流:单元素集合继承 Collection,键值对体系独立为 Map;选型先看有序性、唯一性、并发与排序需求。

代码或图示

本题无代码,顶层分类见概念解释。

常见误区

  • 以为 Map 继承 Collection:答:键值对语义与单元素集合不同,Map 是独立顶层接口。
  • 不看需求直接选实现类:答:应先确定有序/唯一/并发/排序要求再选。

追问

  • 为什么 Map 不继承 Collection?答:键值对语义与单元素集合不同。
  • 如何选集合?答:先看有序/唯一/并发/排序需求。

04.1.1.3-002 ArrayList 的扩容机制是怎样的?

一句话结论

默认容量 10(首次添加时分配),扩容为 oldCapacity + (oldCapacity >> 1),约 1.5 倍,然后复制元素到新数组。

概念解释

  • ensureCapacity 可预分配,减少多次扩容。
  • 扩容是 O(n) 复制,频繁添加大集合应预估容量。
  • trimToSize 可缩容到实际大小。

原理流程

添加元素前检查数组容量,不足时按约 1.5 倍新建数组,把原元素复制过去再替换内部数组引用;预分配容量可跳过多次扩容复制。

代码或图示

本题无代码,扩容步骤见原理流程。

常见误区

  • 以为扩容只是改长度:答:需新建更大数组并复制全部元素,成本 O(n)。
  • 以为 ArrayList 并发写安全:答:不安全,并发写需外部同步或并发容器。

追问

  • 为什么是 1.5 倍不是 2 倍?答:空间与复制次数的折中。
  • 扩容线程安全吗?答:不安全,并发写需外部同步或并发容器。

04.1.1.3-003 ArrayList 和 LinkedList 怎么选?

一句话结论

绝大多数场景选 ArrayList:随机访问 O(1)、内存连续、缓存友好;LinkedList 仅在已知节点位置频繁插入/删除时有优势,实际常被 ArrayDeque 替代。

概念解释

ArrayList 基于连续数组,LinkedList 基于双向链表;两者随机访问与插入删除成本不同。

原理流程

数组按下标直接定位;链表需从头或尾遍历到目标节点再改链。已知节点位置的链表插入只改指针,定位本身仍需遍历。

代码或图示

操作 ArrayList LinkedList
随机访问 O(1) O(n)
头部插入 O(n) O(1)
中间插入 O(n) O(n) 定位 + O(1) 改链
内存 连续数组 每节点额外指针

常见误区

  • 以为 LinkedList 插入删除总是 O(1):答:定位节点仍需遍历,整体未必快。
  • 用 LinkedList 做队列:答:ArrayDeque 通常内存与性能更优。

追问

  • LinkedList 的 O(1) 插入为什么不一定快?答:定位仍需遍历。
  • 队列用什么?答:ArrayDeque 通常优于 LinkedList。

04.1.1.3-004 Vector 和 ArrayList 有什么区别?

一句话结论

Vector 方法加 synchronized、线程安全但性能差、扩容默认 2 倍;ArrayList 非线程安全、扩容 1.5 倍。现代并发场景用 CopyOnWriteArrayList 或外部同步。

概念解释

Vector 是早期线程安全列表,每个方法加对象锁;ArrayList 不加锁,单线程下更轻量。

原理流程

Vector 所有读写方法在同一对象锁下串行执行,粒度为整个列表;扩容按约 2 倍复制。并发读多写少场景更适合 CopyOnWriteArrayList。

代码或图示

本题无代码,两者差异见概念解释与原理流程。

常见误区

  • 以为 Vector 是现代首选线程安全列表:答:全表锁粒度大、并发性能差,已少用。
  • 以为需要线程安全就用 Vector:答:可按场景选 Collections.synchronizedList 或读写分离的并发容器。

追问

  • Vector 为什么被淘汰?答:全表锁粒度大,并发性能差。
  • 如何让 ArrayList 线程安全?答:Collections.synchronizedList 或读写分离设计。

04.1.1.3-005 CopyOnWriteArrayList 的原理和适用场景?

一句话结论

写时复制:修改时复制整个数组,在新数组上改动后替换引用;读不加锁,适合读多写极少的场景。

概念解释

  • 读操作无锁、弱一致(可能读到旧数据)。
  • 写操作加锁,成本高、内存翻倍。
  • 适合监听器列表、配置快照,不适合频繁写。

原理流程

写操作先加锁,复制一份当前数组,在副本上修改后把内部引用指向新数组;读直接访问当前数组引用,不复制也不加锁。

代码或图示

本题无代码,写时复制流程见原理流程。

常见误区

  • 用它承载高频写入:答:每次写都复制整个数组,内存与 CPU 成本高。
  • 以为读到的一定是最新数据:答:弱一致,迭代期间可能基于旧快照。

追问

  • 为什么迭代器不会抛 ConcurrentModificationException?答:迭代的是旧数组快照。
  • 内存开销多大?答:每次写都复制整个数组。

04.1.1.3-006 HashSet 的去重原理是什么?

一句话结论

HashSet 内部用 HashMap,元素作为 key,value 是固定哑对象;先按 hashCode 定位桶,再用 equals 判断是否重复。

概念解释

  • 添加时 hash(key) 扰动,(n-1)&hash 定位。
  • 若 hash 冲突且 equals 不等,挂链表/红黑树。
  • 自定义对象必须正确重写 equals/hashCode。

原理流程

元素先算哈希定位桶;桶内已有元素时逐个 equals 比较,相等视为重复不加入,不等则挂到桶内链表/树结构。

代码或图示

本题无代码,去重流程见原理流程。

常见误区

  • 只重写 equals 不重写 hashCode:答:hash 不同会落到不同桶,无法去重。
  • 以为 HashSet 保证顺序:答:不保证,需要顺序用 LinkedHashSet/TreeSet。

追问

  • 为什么只重写 equals 不够?答:hash 不同会落到不同桶,无法去重。
  • HashSet 有序吗?答:不保证,需有序用 LinkedHashSet/TreeSet。

04.1.1.3-007 TreeSet 怎么排序?有什么要求?

一句话结论

TreeSet 基于 TreeMap(红黑树),按 Comparable 自然顺序或构造器传入 Comparator 排序;元素必须可比较,否则抛 ClassCastException。

概念解释

  • 插入/查找/删除 O(log n)。
  • 不允许 null(自然排序时)。
  • 判断重复用 compareTo == 0,不是 equals。

原理流程

元素按比较结果插入红黑树;比较返回 0 视为同一键,不再插入;比较器或自然排序决定树中顺序。

代码或图示

本题无代码,排序结构见原理流程。

常见误区

  • 以为重复判断用 equals:答:TreeSet 以 compareTo == 0 判定重复。
  • 比较器与 equals 不一致:答:可能出现“看似重复却加不进去”或顺序与预期不符。

追问

  • TreeSet 和 HashSet 怎么选?答:需要排序/范围查询用 TreeSet。
  • 比较器与 equals 不一致会怎样?答:可能出现“看似重复却加不进去”。

04.1.1.3-008 LinkedHashSet 有什么特点?

一句话结论

在 HashSet 基础上维护双向链表,保留插入顺序;迭代顺序可预测,性能略低于 HashSet。

概念解释

  • 适合需要去重且保持顺序的场景。
  • 不按访问顺序,LinkedHashMap 才支持 accessOrder。
  • 内部继承 HashSet,节点扩展 before/after。

原理流程

每个节点在哈希桶之外额外挂入双向链表,记录插入先后;迭代时沿链表遍历,因此顺序与插入一致。

代码或图示

本题无代码,链表维护方式见原理流程。

常见误区

  • 以为 LinkedHashSet 支持访问顺序排序:答:它只保留插入顺序,accessOrder 是 LinkedHashMap 的能力。
  • 以为它线程安全:答:不安全,并发需外部同步。

追问

  • 如何实现 LRU?答:用 LinkedHashMap 的 accessOrder + 重写 removeEldestEntry。
  • LinkedHashSet 线程安全吗?答:不安全。

04.1.1.3-009 什么是 fail-fast?哪些集合有?

一句话结论

迭代过程中集合结构被修改(增删,非 set 值),迭代器立即抛 ConcurrentModificationException,通过 modCount 检测。

概念解释

  • ArrayList、HashMap 等非并发集合都是 fail-fast。
  • 单线程中边迭代边 remove 也会触发,需用 Iterator.remove()。
  • 多线程并发修改只是“检测到就抛”,不保证一定检测到。

原理流程

集合维护结构修改计数 modCount,迭代器创建时记录期望值;每次迭代检查当前 modCount 是否一致,不一致即抛 CME。

代码或图示

本题无代码,检测机制见原理流程。

常见误区

  • 边迭代边用集合 remove:答:会改 modCount 触发 CME,应使用 iterator.remove()。
  • 以为 fail-fast 能保证检测到所有并发修改:答:只是检测到就抛,不保证每次都能发现。

追问

  • 为什么设计成 fail-fast?答:尽早暴露并发/逻辑错误。
  • 如何安全删除?答:iterator.remove() 或 removeIf。

04.1.1.3-010 fail-safe 迭代器是什么?

一句话结论

fail-safe(弱一致)迭代器基于快照或并发容器,迭代时允许并发修改,不抛 CME,但可能看不到最新数据。

概念解释

  • CopyOnWriteArrayList 迭代旧数组快照。
  • ConcurrentHashMap 迭代弱一致,不保证反映最新修改。
  • 适合并发读多写少场景。

原理流程

迭代器基于不可变快照或分段并发结构遍历,不记录 modCount 比对;并发写入反映在新结构上,旧迭代视图不受影响。

代码或图示

本题无代码,快照/弱一致机理见原理流程。

常见误区

  • 以为 fail-safe 就是数据强一致:答:只是不抛异常,可能读不到最新数据。
  • 以为 CHM 迭代器强一致:答:它是弱一致迭代。

追问

  • fail-safe 一定安全吗?答:只是不抛异常,数据一致性仍需业务保证。
  • CHM 的迭代器是强一致吗?答:不是。

04.1.1.3-011 Comparable 和 Comparator 有什么区别?

一句话结论

Comparable 是对象自身的自然排序能力(compareTo);Comparator 是外部比较器,可定义多种排序策略。

概念解释

Comparable 把排序规则写在类内部;Comparator 独立于被比较类,可按不同字段、不同方向定义多个策略。

原理流程

需要自然顺序时实现 Comparable.compareTo;需要多策略排序时传入 Comparator,比较器返回负数/0/正数表示小于/等于/大于。

代码或图示

class User implements Comparable<User> {
    public int compareTo(User o) { return Long.compare(id, o.id); }
}
Comparator<User> byName = Comparator.comparing(User::getName);

常见误区

  • 为多种排序反复改实体类:答:不应修改类,用外部 Comparator 组合策略。
  • 比较返回值随意约定:答:必须按负/0/正表示小于/等于/大于。

追问

  • 什么时候用 Comparator?答:不能修改类、需要多字段/多策略排序。
  • 比较返回值的含义?答:负数、0、正数表示小于、等于、大于。

04.1.1.3-012 Arrays.asList 有哪些坑?

一句话结论

返回的是固定大小的 Arrays$ArrayList 视图,不能 add/remove;对基本类型数组会整体作为一个元素;修改会写回原数组。

概念解释

返回列表直接包装原数组,不复制元素;因此结构变更受限,元素变更双向可见。

原理流程

列表内部引用原数组,set 直接写回数组;add/remove 因无法扩容底层数组而抛 UnsupportedOperationException;基本类型数组因泛型不能是基本类型,被整体当作一个对象元素。

代码或图示

List<Integer> list = Arrays.asList(1, 2, 3);
// list.add(4); // UnsupportedOperationException

int[] arr = {1,2,3};
List<int[]> wrong = Arrays.asList(arr); // size=1

常见误区

  • 把返回视图当可变列表使用:答:不能 add/remove,需要可变列表应再包一层 ArrayList。
  • 直接传基本类型数组:答:数组被当作单个元素,size 为 1。

追问

  • 如何得到可变 List?答:new ArrayList<>(Arrays.asList(...))。
  • 为什么基本类型数组会出错?答:泛型不能是基本类型,数组被当作一个对象。

04.1.1.3-013 集合转数组有哪些注意点?

一句话结论

用 toArray(new T[0]) 或 toArray(T[]::new),避免传入长度不足/共享数组;JDK 11+ 推荐数组构造器引用。

概念解释

无参 toArray() 返回 Object[],不能保证具体元素类型;带数组参数的重载按传入类型分配结果数组。

原理流程

传入长度足够的数组就写入该数组并返回;长度不足时新建同类型数组返回。new T[0] 由 JVM 优化分配,避免预分配大小估算错误。

代码或图示

String[] arr = list.toArray(new String[0]);
String[] arr2 = list.toArray(String[]::new);

常见误区

  • 强转无参 toArray() 结果:答:返回 Object[],强转可能抛 ClassCastException。
  • 复用一个外部数组反复传入:答:长度不足或被覆盖会产生意外结果。

追问

  • 为什么 toArray(new T[0]) 比 new T[size] 好?答:JVM 优化更好,无需预分配。
  • toArray() 返回 Object[] 能强转吗?答:不能保证具体类型,可能 ClassCastException。

04.1.1.3-014 常见并发集合有哪些?

一句话结论

ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentLinkedQueue、BlockingQueue 实现类。

概念解释

并发集合按并发结构与读写特征分流:哈希表分段/CAS、写时复制、无锁链表、阻塞队列。

原理流程

CHM 用分段/CAS 加桶锁;COW 写时复制;ConcurrentLinkedQueue 基于无锁链表;ArrayBlockingQueue 用有界队列做生产者消费者。

代码或图示

集合 特点 场景
CHM 分段/CAS + 桶锁 高并发 Map
COWArrayList 写时复制 读多写少
ConcurrentLinkedQueue 无锁队列 高并发队列
ArrayBlockingQueue 有界阻塞 生产者消费者

常见误区

  • 给 CHM 存 null 值:答:并发下无法区分“不存在”和“值为 null”,CHM 不允许 null。
  • 用默认无界阻塞队列防 OOM:答:LinkedBlockingQueue 默认无界,积压可致内存溢出。

追问

  • CHM 为什么不允许 null?答:避免并发下无法区分“不存在”和“值为 null”。
  • 阻塞队列怎么选?答:有界防 OOM,LinkedBlockingQueue 吞吐高但默认无界。

04.1.1.3-015 集合的初始容量怎么设置?

一句话结论

按预估元素数与负载因子反推:容量 = 元素数 / 0.75 + 1,避免频繁扩容与 rehash。

概念解释

哈希集合在元素数达到阈值(容量 × 负载因子)时扩容 rehash;初始容量应覆盖预估元素数。

原理流程

构造时按预估元素数除以负载因子(默认 0.75)向上取整设置容量,使元素在首次达到预估规模前不触发 rehash。

代码或图示

// 预计 1000 个元素
Map<String, User> map = new HashMap<>(1024);

常见误区

  • 直接把元素数当初始容量:答:未考虑负载因子,达到阈值仍会扩容。
  • 初始容量设得过大:答:浪费内存,遍历与扩容成本增加。

追问

  • 为什么不是直接传元素数?答:HashMap 会按阈值扩容。
  • 初始容量过大会怎样?答:浪费内存,遍历/扩容成本增加。

本节高频题

  • ArrayList 扩容(003-002)
  • ArrayList vs LinkedList(003-003)
  • HashSet 去重(003-006)
  • fail-fast 与安全删除(003-009)
  • Arrays.asList 坑(003-012)