集合框架的选择与复杂度

集合选择首先是业务语义，其次才是性能。若业务需要去重却使用 List，调用方迟早会在不同位置写出不同的去重规则。

Open Table of contents

用四个问题选择集合
运行订单去重示例
看懂时间复杂度
避免可变键
下一步

用四个问题选择集合

元素是否有稳定顺序？有顺序优先考虑 List。
元素是否必须唯一？唯一集合使用 Set。
是否通过键查找值？使用 Map。
是否按进入顺序或优先级处理？使用 Queue 或 Deque。

ArrayList 适合按索引读取和尾部追加；HashSet 表达无重复成员；HashMap 表达键值映射；ArrayDeque 适合作为队列或栈。通常不要用旧的 Vector 和 Stack。

运行订单去重示例

import java.util.*;

public class 订单索引 {
    record 订单(String id, String customerId) {}

    public static void main(String[] args) {
        var orders = List.of(new 订单("O-1", "C-1"), new 订单("O-2", "C-1"));
        var byId = new LinkedHashMap<String, 订单>();
        var customers = new HashSet<String>();

        for (var order : orders) {
            if (byId.putIfAbsent(order.id(), order) != null) {
                throw new IllegalArgumentException("订单号重复: " + order.id());
            }
            customers.add(order.customerId());
        }
        System.out.println(byId.keySet());       // 保持插入顺序
        System.out.println(customers.size());   // 唯一客户数
    }
}

LinkedHashMap 比 HashMap 多维护一条链表，因此能保持插入顺序，也需要额外内存。只有输出顺序属于契约时才支付这项成本。

看懂时间复杂度

时间复杂度描述输入规模增长时，操作次数如何增长。O(1) 表示平均操作次数不随元素数量线性增长；O(n) 表示可能扫描全部元素。

操作	常见集合	平均复杂度	注意
按索引读取	`ArrayList`	`O(1)`	中间插入需移动元素
判断包含	`HashSet`	`O(1)`	依赖正确的 `equals/hashCode`
按键查找	`HashMap`	`O(1)`	哈希冲突和扩容有成本
保持排序	`TreeMap`	`O(log n)`	比哈希映射更慢但有序
头尾入队	`ArrayDeque`	`O(1)`	不允许 `null`

复杂度不是耗时。缓存局部性、对象分配、数据规模和并发竞争都可能改变实际结果；性能结论需要基准测试。

避免可变键

放入 HashMap 的键如果参与 hashCode() 的字段随后改变，条目可能再也查不到。优先用不可变 record 作为键，并保证 equals() 与 hashCode() 使用同一组字段。

返回集合时明确所有权：List.copyOf(values) 创建不可变快照；Collections.unmodifiableList(values) 只是只读视图，底层列表变化仍会反映出来。

下一步

阅读泛型、边界与类型擦除，为集合 API 增加编译期类型安全。