Java 集合学习 01：线性表、Set 与 Map 的选择

ArrayList 和 LinkedList 的比较经常被简化成一句话：数组查询快，链表插入快。它没有错，但放进真实代码里远远不够。决定容器是否合适的，不是“某个操作的理论复杂度”，而是数据从哪里来、要移动多少元素，以及 CPU 实际如何访问这些内存。

ArrayList 扩容过程

ArrayList 的底层是连续的对象引用数组。JDK 8 之后，无参构造不会立刻分配长度为 10 的数组；第一次添加元素时才初始化。容量不足时，会创建更大的数组，并把旧数组内容复制过去，新的容量通常约为旧容量的 1.5 倍。

这意味着尾部追加的摊销成本接近 O(1)，但一次扩容本身是 O(n)。如果业务能估到数量，直接声明容量会比事后“优化扩容”更有价值：

List<Event> events = new ArrayList<>(expectedEventCount);

在批量读取、构建响应列表、缓存查询结果这类路径上，ArrayList 往往也有额外优势：连续内存带来更好的缓存局部性，遍历时较少发生指针跳转。

ArrayList 和 LinkedList 的区别

链表在“已经拿到目标节点”的前提下，链接或摘除节点可以是 O(1)。但 Java 的 LinkedList 通常先要根据下标从头或尾走到该节点；所以按位置插入、删除仍然包含 O(n) 的定位成本。

这也是为什么下面的直觉经常误导人：

我经常在中间插入元素，所以应该用 LinkedList。

如果插入位置是下标、元素数量并不小，LinkedList 并不会自动胜出。多数业务最终是“按下标访问 + 顺序遍历 + 尾部追加”，ArrayList 更接近默认解。只有双端队列语义明确时，才应优先考虑 ArrayDeque；只有确实持有节点引用、频繁在局部重连时，链表的优势才更具体。

ArrayList 和 LinkedList 如何选择

场景	更合适的起点	原因
结果集、DTO 列表、批量遍历	ArrayList	连续访问，尾插友好
栈、队列、双端操作	ArrayDeque	避免链表节点额外开销
已知规模的大批量装载	ArrayList<>(n)	避免多次扩容复制
需要稳定按键排序	TreeMap / 排序后列表	容器语义更贴近需求

选择容器前，我会先问三个问题：会不会随机访问？数据量是否可预估？“插入”前是否仍需要遍历定位？这三个答案通常比背诵复杂度更能决定实现质量。

HashSet、LinkedHashSet 和 TreeSet 的区别

当需求从“保存一批元素”变成“去重”，应该先切换到 Set 的语义。HashSet 依赖 HashMap 保存 key，强调平均查找性能；LinkedHashSet 在此基础上保留插入顺序；TreeSet 则用红黑树维持排序，适合范围查询与有序输出。

三者都不是并发容器，也都不应该只因“看起来高级”而被使用。要顺序就明确选择 LinkedHashSet，要排序或区间就选择 TreeSet；否则普通 HashSet 已经是最小、清楚的表达。

HashMap、LinkedHashMap 和 TreeMap 如何选择

HashMap 是多数键值查找的默认实现；需要保持插入顺序时可以用 LinkedHashMap；需要按 key 的顺序遍历、做范围检索时才用 TreeMap。这比只记“HashMap 无序、TreeMap 有序”更接近代码评审时应问的问题：顺序是否属于业务语义？排序成本是否值得？

迭代集合时还需要注意 fail-fast 机制。普通集合的迭代器会通过修改计数尽早发现结构性并发修改，抛出 ConcurrentModificationException；它是 bug 探测器，不是并发控制方案。多线程读写需要同步、并发集合，或在明确快照语义的前提下复制数据。

集合遍历时为什么会抛 ConcurrentModificationException

集合 API 容易让人快速写出代码，也容易掩盖数据建模的问题。先定义“是否允许重复、是否要求顺序、是否需要范围查询、读写是否并发”，再让容器成为该语义的实现。这样以后替换实现时，业务代码不会被某一种数据结构绑死。

Array 和 ArrayList 的区别

Java 数组的长度在创建后不可变，它既可以保存基本类型，也可以保存对象引用。ArrayList 则只保存对象引用；基本类型会通过包装类型进入集合。这个区别看起来基础，却会影响两类代码：一类是对内存布局敏感的高频路径，另一类是需要借助泛型把类型约束放到编译期的业务代码。

数组适合长度稳定、下标语义很强的场景，例如固定大小的缓冲区、协议字段表或算法中的临时工作区。ArrayList 适合长度会增长、需要大量集合 API 的普通业务数据。不要因为 ArrayList 可以扩容，就把任何本可固定的结构都变成动态列表；同样，也不要为了“性能”提前手写数组管理逻辑，除非剖析结果证实集合对象本身就是瓶颈。

ArrayList 的扩容过程可以拆成四步：发现最小所需容量超过当前数组长度；计算新容量；申请新数组并复制旧引用；令 elementData 指向新数组。最昂贵的是复制，因此预估容量的收益来自避免多次完整数组复制，而不是某个神秘的构造器优化。1.5 倍是扩容频率与闲置空间之间的折中：增长太慢会频繁复制，增长太快会让暂时不用的引用槽位占据更多堆空间。

这里还要分清“容量”和“元素个数”。size() 只表示有效元素数量，容量属于实现细节。业务代码不应该依赖默认容量，也不应该把 ensureCapacity 当成通用优化手段；当调用方能合理估计数据规模时，在构造时给容量通常更清楚。

LinkedList 的底层结构和时间复杂度

Java 的 LinkedList 是双向链表。它维护头尾节点，因此在队首、队尾插入或删除时，不需要搬移整段数组；但每个元素都要额外保存前后引用，内存开销、对象分配和指针跳转也随之而来。

“中间插入 O(1)”必须补全为“已经拿到节点时”。LinkedList 的公开 API 以索引和元素为主，定位第 k 个元素仍要沿链表走过去，平均需要遍历一部分链。因此 add(index, value) 并不是在所有情况下比 ArrayList 快。若每次都从列表外部用下标操作，定位成本往往比数组搬移更显著。

更重要的是 CPU 并不只按大 O 运行。连续数组有更好的缓存局部性，顺序遍历时预取有效；链表节点散落在堆上，遍历会产生更多间接寻址。结果是，在常见的“读多、顺序遍历、偶尔尾插”的 Web 后端场景里，ArrayList 几乎总是更自然的默认值。

如果需求本质是栈、队列或双端队列，应优先表达为 Deque，通常选 ArrayDeque。它避免了 LinkedList 的节点对象开销，也避免了传统 Stack 的历史包袱。只有当算法已经持有节点、确实需要局部重连，或数据访问模式天然是链式时，链表才是更有说服力的选择。

Set 的底层结构与使用场景

Set 的共同语义是元素唯一，但“唯一”背后依赖不同机制。

实现	主要结构	遍历特征	适合的问题
HashSet	基于哈希表	不承诺顺序	快速去重、成员判断
LinkedHashSet	哈希表加链接	保留插入顺序	去重后仍要按输入顺序输出
TreeSet	红黑树	按自然顺序或比较器排序	有序去重、范围判断

HashSet 的元素实际上作为内部 HashMap 的 key 保存，value 只是一个占位对象。它能否正确去重，仍取决于元素的 equals 和 hashCode。可变对象尤其危险：对象放入集合后若修改了参与 hash 或相等判断的字段，元素可能还在集合里，却再也无法按预期找到或删除。

LinkedHashSet 不是“更快的 HashSet”，它换来的是顺序语义；TreeSet 也不是“自动帮忙排序的 Set”，其比较器必须与业务等价关系相协调。若比较器把两个不同对象比较为 0，集合会把它们视为同一个元素。这是比语法更重要的集合契约。

fail-fast 和 fail-safe 是什么

普通集合的迭代器通常具备 fail-fast 行为：迭代期间发生结构性修改，修改计数与迭代器预期不一致时，尽早抛出 ConcurrentModificationException。它的目标是快速暴露错误，而不是在多线程下提供安全保证；检测也不是绝对可靠的同步协议。

因此有三种不同处理方式。第一，在单线程中通过迭代器自身的 remove 修改；第二，先收集要删的元素，迭代结束后统一变更；第三，在并发环境中使用合适的同步或并发集合。CopyOnWriteArrayList 的迭代器看到的是快照，适合读远多于写的配置、监听器等场景；写入会复制底层数组，绝不适合高频写路径。ConcurrentHashMap 提供弱一致迭代，不承诺遍历时看到一个静止世界，但允许并发操作继续进行。

面试总结

集合选择不是背诵类名，而是把业务问题翻译成数据结构约束：是否允许重复、是否需要稳定顺序、是否要求按范围查找、是否会并发访问、规模是否可预估。只有把这些约束写清楚，ArrayList、HashSet、TreeMap 等实现才会成为可替换的细节，而不是埋在业务代码里的偶然选择。

ArrayList 为什么扩容 1.5 倍，不是 2 倍

扩容倍数没有脱离业务场景的绝对答案。倍数太小，数组很快再次不够用，复制次数增多；倍数太大，列表在增长阶段会保留更多暂时空闲的引用槽位。JDK 的 1.5 倍是空间利用率与复制频率的折中，并利用简单移位计算新容量。它并不意味着业务侧应当把任何容量都交给默认策略：已知批量导入规模时，提前传入容量通常比研究默认倍数更有效。

ArrayList 和 LinkedList 是线程安全的吗

两者都不是线程安全集合。给列表加一个 synchronized 包装或使用 Collections.synchronizedList 只能提供单次方法调用的互斥；迭代时仍需在外部同步。读多写少又需要迭代快照时，CopyOnWriteArrayList 可以考虑；普通共享状态则应重新审视是否真的需要多个线程直接操作同一列表。

集合类的选择原则

先选接口语义，再选实现：线性顺序用 List，唯一性用 Set，键值映射用 Map，双端出入用 Deque。如果代码变量直接声明为具体实现类，后续替换成本会更高；若声明为接口又依赖实现特有行为，例如依赖 HashMap 的偶然遍历顺序，同样会留下隐患。接口应表达业务不变量，实现则根据访问模式、数据量和并发边界决定。