• List, Set 都是继承自 Collection 接口

  • List 特点：元素有放入顺序，元素可重复。Set 特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在 set 中的位置是有该元素的 HashCode 决定的，其位置其实是固定的）

  • List 接口有三个实现类：LinkedList，ArrayList，Vector。Set 接口有两个实现类：HashSet(底层由 HashMap 实现)，LinkedHashSet

三条特点之外，真正决定选型的是底层数据结构带来的复杂度差异，以及”去重/判含”这类操作在两种集合里的成本天壤之别。本文按语义、实现、复杂度、选型四层展开。

语义差异：有序可重 vs 唯一性

  • List：序列语义。保留插入顺序、允许重复、支持按索引访问（get(i)）——对应”一批有先后关系的记录”
  • Set：集合语义。元素唯一、不承诺顺序（HashSet）、无索引访问——对应”一个成员资格集合”

“Set 无序但位置固定”那句注记的准确解释：HashSet 的迭代顺序由元素 hashCode 与桶分布决定，对同一组元素是稳定的，但对插入顺序不敏感；增删改元素后顺序可能变化，所以不能依赖它。

实现类与底层结构

实现 底层 顺序 备注
ArrayList 动态数组 插入序 随机访问 O(1)，尾部增删快，中部增删 O(n)
LinkedList 双向链表 插入序 头尾操作 O(1)，随机访问 O(n)，节点开销大
Vector 数组+方法同步 插入序 遗留类，用 Collections.synchronizedList 或并发集合替代
HashSet HashMap（值占位） 无 判含/增删 O(1)，依赖 equals+hashCode
LinkedHashSet LinkedHashMap 插入序 比 HashSet 多维护一条链表，代价少量内存
TreeSet 红黑树 排序序 范围查询/有序遍历，O(logN)

复杂度对比：判含是分水岭

List<String> list = new ArrayList<>(bigData);     // contains: O(n)
Set<String> set = new HashSet<>(bigData);         // contains: O(1)
  • list.contains(x) 线性扫描，10 万元素就是 10 万次 equals
  • set.contains(x) 一次哈希定位

去重与成员判断场景用 Set 是数量级差异；反过来”按位置取第 i 个””保留重复项””维护顺序遍历”是 List 的主场。循环里对 List 做 contains 是代码审查中最常见的性能坏味道之一，改 HashSet 往往直接消除 O(n²)。

去重保序的正确姿势

需求”去重且保留首次出现顺序”：

  • LinkedHashSet：构造即完成，O(n)
  • Stream：list.stream().distinct().collect(toList())（内部也是 LinkedHashSet）
  • 手动 List 判重：O(n²)，不要写

选型清单

  • 需要索引/重复/顺序遍历 → ArrayList（默认）；频繁头尾插入删除 → LinkedList 或 ArrayDeque
  • 去重、判含、交集并集（retainAll/addAll 语义清晰） → HashSet
  • 去重且保序 → LinkedHashSet
  • 需要排序与范围查询（topN、区间） → TreeSet
  • 并发场景 → CopyOnWriteArrayList / ConcurrentHashMap.newKeySet()，而非同步包装器

List 与 Set 的区别不止”有序可重 vs 无序唯一”两句特征，而是序列与集合两种数学结构在工程上的投影：选 List 是为顺序与位置付费，选 Set 是为唯一性与 O(1) 判含付费。按访问模式选型，特征表自然各归其位。