List、Set、Map：先看业务，再选集合

选集合，先看你准备怎样存和找数据：要保留重复项和位置，用 List；只关心有没有某一项并希望去重，用 Set；要凭商品编号查数量，用 Map。Set 按自己的相等规则判断重复。Map 保存键和对应的值，同一个键再次写入通常会更新值；它不是 Collection 的子接口，不能只把三者理解成快慢不同的容器。

例如，订单明细用 List 保留每一行，已处理的任务编号用 Set 检查是否出现过，购物车用 Map 记录商品编号和数量。还要说清“有顺序”指什么：按位置、按首次加入、按最近访问，还是按大小排序。HashMap 不保证遍历顺序；LinkedHashMap 和 TreeMap 也有不同规则。测试应检查文档承诺的顺序，不能依赖某次碰巧看到的输出。

选择哪种实现，会影响每次操作要做多少工作。ArrayList 可以直接按下标读取；从空列表连续在尾部追加时，总花费通常与追加次数成正比，平均每次是固定量级，这叫摊还常数，但某次扩容可能较慢。

中间插删则要移动后续元素。LinkedList 如果迭代器已经到达操作位置，改变链接较便宜；但按下标找位置仍要逐项走过去。不能只比较插入那一步而忽略查找位置的花费。日常顺序存储通常先选简单实现，再根据实际怎样读取和修改数据调整。

把业务需要转成操作组合，比背单个方法复杂度更有用。若任务是对每个左侧编号检查右侧是否存在，右侧用 List.contains 会反复线性查找，两个输入规模相乘；先把右侧建成 HashSet 通常能把重复扫描换成快速成员判断，但要付出额外存储和构建成本。

动态数组里，size 是已有元素数，capacity 是底层数组目前能装多少项。追加时还有空位就直接写，没有才建更大的数组并搬过去。若每次按一定比例增加容量，昂贵的搬运不会每次发生，连续追加的总成本可以保持较低；这就是摊还分析。反过来，每次只多开一个空位，就要反复搬动所有旧元素，总搬运量会增长到平方级。

遍历时怎样删除也要遵守集合规则。迭代器支持的 remove 或 removeIf 可以按规则删除；一边遍历，一边随意从原集合增删，可能触发快速失败异常。这类异常用于尽早暴露错误，不是线程安全保障，也不保证发现所有并发问题。并发容器、加锁包装和不可修改快照在遍历时各有规则，需要分别核对。

本机 ArrayList.grow 根据旧容量、最小所需增长和偏好增长调用 ArraysSupport.newLength，再通过 Arrays.copyOf 搬运。普通路径的偏好增长约为旧容量的一半，但实际结果还受最小需求与大数组边界影响。模型采用类似几何增长并设置教学上限，不声称完整复现 JDK 的容量策略。

逻辑大小与容量必须分开。容量多出的槽位是为未来追加准备的空间，不是已经属于列表的元素；get 和迭代应依据 size，而不是底层数组长度。模型只实现 add 和 size，故意不提供完整 List 接口，避免让几行代码被误认为可直接替代生产集合。

数组扩容要复制已有元素，元素越多，这一次 add 就可能越慢，达到线性时间。摊还分析看的不是某一次，而是从空列表开始连续追加的总花费：容量按一定比例增大时，历次搬运量形成几何级数，总量与最终元素数同阶。所以平均到这一串追加上很省，并不保证每次追加一样快，也不是按随机输入概率求平均。

具体扩大多少是实现细节，不宜用反射读取私有数组后依赖精确容量。提前知道数量时，可以合理设置初始容量来减少搬运，但估得太大会多占内存。长期设计更应依赖公开 API 说明的行为和成本，而不是某个补丁版本内部的常量。

输入两个非空引用的 Integer 列表，元素不得为 null。返回同时出现在两侧的编号，每个编号只出现一次，顺序按左侧首次出现。空列表合法，输入不被修改。

右侧只需要回答是否存在，不需要保留重复次数与原始顺序，因此先建 HashSet。左侧决定输出顺序，按原顺序扫描；命中右侧集合后放入 LinkedHashSet，既能去重又保持第一次加入的先后。两种集合分别承担不同职责，而不是随意堆叠容器。

如果用普通 HashSet 保存结果，内容虽然可能正确，顺序却没有保证；如果直接往 ArrayList 添加每次命中项，又会保留左侧重复。也可以使用额外已输出集合加结果列表，实现同一语义。选择最能直接表达契约的组合，有助于读者从类型看到算法意图。

两侧都要完整验证 null 元素，即使另一侧为空也不应跳过接口约定。最后创建 ArrayList 作为结果容器，调用者修改输出不会改变输入。算法只复制 Integer 引用，但 Integer 是不可变值包装类型，因此这里无需进一步复制元素；换成可变实体时必须重新评估隔离要求。

右侧 m 项构建成员表，左侧 n 项各做固定次数成员和去重操作，最后复制 k 项输出；哈希操作成本前提需明确。

数据规模小且逻辑简单时，不必为省一次线性扫描引入复杂索引。建立集合有内存、分配与哈希计算成本；大量重复查询时才更容易摊薄构建成本。评估时记录数据量、重复率、查询次数与是否需要顺序，避免用孤立微基准给所有场景下结论。

不可修改集合与不可变快照需要区分。List.of 禁止结构修改并拒绝 null，但元素可能仍可变；包装已有列表也可能继续观察到底层变化。把集合返回给其它模块前，明确容器所有权与元素可变性，不能用方法返回类型 List 就暗示它可写或不可写。

换成 ConcurrentHashMap 后，仍要检查完整操作是否允许被别的线程插入。例如先 containsKey 再 put，并不会自动成为一次不可拆开的操作；可按需求使用 putIfAbsent、compute，或在更大范围同步。先写清必须保证的业务规则，再选集合，不能看到 Concurrent 就认定整条流程都正确。