在Spark里做用户去重，你会用什么？在Flink里做实时UV统计，你会用什么？在ETL里做维度关联，你会用什么？答案都是Set。但很多人用了几年Set，对它的认知还停留在"去重的列表"。

我在做一个实时数仓项目的时候，遇到过一个很诡异的性能问题：一个简单的UV统计任务，跑了半小时还没出结果。一开始以为是数据倾斜，后来profile了一下，发现瓶颈全在一个List.contains(userId)上——每次判断用户是否来过，都要遍历整个List，数据量一大，就是O(n²)的灾难。

改成Set之后，性能直接从半小时降到了30秒。

这不是什么高深的优化，就是最基础的数据结构选择问题。但为什么这么简单的问题，会有这么多人踩坑？因为大多数人学Set的时候，学的都是"Set是什么"，而不是"Set为什么是这样设计的"。

这篇文章不罗列Set有哪些方法——那些官方文档都有。我想聊几个真正值得思考的问题：Scala的Set底层是怎么实现的？为什么contains是O(1)？为什么大数据开发离不开Set？什么时候你真的该用Set而不是List？

先从一个真实的性能问题说起

假设你要写一个函数：给定一个List[Int]，返回去重后的列表。

用List怎么写？

// 写法一：用List.contains逐个判断defdistinct(list:List[Int]):List[Int]={valresult=ListBuffer[Int]()for(x<-list){if(!result.contains(x)){result+=x}}result.toList}

这个逻辑很直白：遍历原列表，如果结果里没有这个元素，就加进去。

但问题在哪？result.contains(x)是O(n)的——因为result是List，你要从头扫到尾才能找到这个元素。整个函数的复杂度就是O(n²)。

数据量小的时候没感觉，十万条数据，就是一百亿次比较。这就是为什么那个UV统计任务跑了半小时——它本质上就是一个O(n²)的去重。

怎么优化？很简单，把List换成Set：

// 写法二：用Set去重defdistinct(list:List[Int]):List[Int]={valseen=scala.collection.mutable.Set[Int]()valresult=ListBuffer[Int]()for(x<-list){if(!seen.contains(x)){seen+=x result+=x}}result.toList}

现在seen.contains(x)是O(1)的——因为Set是基于哈希表实现的。整个函数的复杂度就变成了O(n)。

从半小时降到30秒，就是这一行改动的差别。

这就是Set的价值：它用O(1)的contains，换来了O(n)的去重。

Set不是"去重的列表"，它是数学上的集合

很多人对Set的理解停留在"自动去重的列表"。这个理解太浅了。

List是什么？List是"有序的序列"——你关心的是每个元素在第几个位置，你关心的是元素之间的顺序。

Set是什么？Set是"数学上的集合"——你关心的是"某个元素在不在里面"，你根本不关心它在第几个位置。

这两个东西的设计目标完全不一样：

看出来了吗？Set和List不是"同一个东西的不同变体"，而是解决不同问题的两种数据结构。

你做用户去重，本质问题是"这个用户在不在已经见过的集合里"——这就是Set的主场。你要按时间顺序输出日志，那就是List的主场。

搞清楚你要解决的核心问题是什么，比你记住多少个API都重要。

Scala Set的底层实现：不是一个东西，是一套体系

很多人以为Scala的Set就是一个类，就像Java的HashSet那样。其实不是——Scala的Set是一整套体系，不同的实现对应不同的场景。

HashSet：最常用的Set

importscala.collection.immutable.HashSetvalset=HashSet(1,2,3,4,5)set.contains(3)// true，O(1)

HashSet是最常用的Set实现，底层是基于哈希表的——你调用add的时候，它会算这个元素的hashCode，然后存到对应的桶里。你调用contains的时候，它直接算hashCode，去对应的桶里找——所以是O(1)。

这就是为什么Set的contains这么快——它不是"遍历一遍找"，而是"直接算出来在哪，然后去拿"。

TreeSet：有序的Set

importscala.collection.immutable.TreeSetvalset=TreeSet(5,3,1,4,2)// TreeSet(1, 2, 3, 4, 5) —— 自动排序了set.min// 1set.max// 5

如果你需要Set是有序的——比如你要按从小到大的顺序输出元素——那就用TreeSet。它底层是红黑树，添加和查找都是O(log n)，比HashSet的O(1)慢一点，但它是有序的。

LinkedHashSet：保持插入顺序的Set

importscala.collection.mutable.LinkedHashSetvalset=LinkedHashSet[Int]()set+=3set+=1set+=2// LinkedHashSet(3, 1, 2) —— 保持插入顺序

有时候你既要去重，又要保持元素的插入顺序——这时候用LinkedHashSet。它底层是哈希表加链表，既能O(1)查找，又能保持插入顺序。

经验法则

很多人不管什么场景都用默认的HashSet，其实在需要有序的场景下，TreeSet能帮你省掉排序的步骤。

不可变Set vs 可变Set：Scala的老传统

和List一样，Scala的Set也分不可变和可变两套。

// 不可变Setvalset1=Set(1,2,3)valset2=set1+4// 返回新Set，set1不变// 可变Setimportscala.collection.mutable.Setvalbuf=Set(1,2,3)buf+=4// 原地修改

这个设计哲学和List是一样的：对外暴露不可变Set，内部用可变Set构建。

但Set有个和List不一样的地方——不可变Set的性能其实没那么差。为什么？因为Set的核心操作是contains，是基于哈希的O(1)操作。即使你每次add都返回一个新Set，add操作本身也是O(1)（平均情况）。

所以在Set这个场景下，可变和不可变的性能差距没有List那么大。很多时候你直接用不可变Set就够了，不需要特意搞个可变Set来构建。

// 直接用不可变Set就行，不用搞个可变Setvalset=Set(1,2,3)+4+5+6

这也是为什么很多人觉得Scala的Set比List好用——因为不可变Set的性能足够好，你不需要像List那样纠结"我到底该不该用ListBuffer"。

Set的核心操作：不只是add和remove

很多人用Set，就只会add、remove、contains这三个操作。其实Set真正强大的地方，是它的集合运算——这是数学上的集合，不是列表。

并集、交集、差集

vala=Set(1,2,3,4)valb=Set(3,4,5,6)// 并集：两个集合合在一起，去重a++b// Set(1, 2, 3, 4, 5, 6)a union b// 同上// 交集：两个集合都有的元素a intersect b// Set(3, 4)a&b// 同上// 差集：在a里但不在b里的元素a diff b// Set(1, 2)a--b// 同上

这三个操作，在大数据开发里太常用了。

比如你要算"上周活跃但这周不活跃的用户"——这就是差集。你要算"两周都活跃的用户"——这就是交集。你要算"累计用户总数"——这就是并集。

这些操作用List写，都是O(n²)的灾难。用Set写，都是O(n)的高效操作。

子集判断

valallUsers=Set("u1","u2","u3","u4","u5")valpaidUsers=Set("u1","u3")// paidUsers是不是allUsers的子集？paidUsers.subsetOf(allUsers)// true

这个操作做权限判断、做范围校验的时候特别好用。

什么时候该用Set，什么时候该用List？

这是最常见的困惑。我给一个简单的判断标准：

你关心的是"元素在不在里面"，还是"元素在第几个位置"？

• 关心"在不在" → 用Set
• 关心"第几个位置" → 用List

具体到实际场景：

用Set的场景

1. 去重：你有一堆数据，要去掉重复的
2. 成员判断：你要频繁判断"某个元素在不在里面"
3. 集合运算：并集、交集、差集
4. 缓存索引：你要快速查找某个key是否存在

用List的场景

1. 按顺序输出：你要按时间顺序、按插入顺序输出元素
2. 按位置访问：你经常要get(i)拿第i个元素
3. 保持顺序的去重：你要去重，但还要保持原来的顺序（这时候用LinkedHashSet，或者List+Set配合）
4. 遍历处理：你要逐个遍历元素做处理，而且元素顺序很重要

一个最常见的错误

很多人做去重的时候，直接把List转成Set，然后就完事了。

// 错误：顺序没了vallist=List(3,1,2,1,3)valdistinct=list.toSet.toList// List(1, 2, 3) —— 顺序变了！

如果你只是要去重，不在乎顺序，这么写没问题。但如果你要保持原来的顺序——比如你要按时间顺序输出不重复的事件——那这么写就错了。

正确的做法是用LinkedHashSet，或者List+Set配合：

// 正确：去重并保持插入顺序vallist=List(3,1,2,1,3)valseen=scala.collection.mutable.Set[Int]()valresult=ListBuffer[Int]()for(x<-list){if(!seen(x)){seen+=x result+=x}}result.toList// List(3, 1, 2) —— 顺序保持了

这个坑我见过无数人踩——包括很多工作了好几年的老程序员。

与Java Set对比：到底差在哪

Java也有Set，也有HashSet、TreeSet、LinkedHashSet。那Scala的Set和Java的Set到底有什么区别？

1. 不可变Set是默认的

Java里，你new的HashSet默认就是可变的。你要想要不可变的，得自己用Collections.unmodifiableSet()包一层——而且这只是个"视图"，你拿着原始引用还是能改。

Scala里，默认的Set就是不可变的。你要可变的，得显式importscala.collection.mutable.Set。

这个设计哲学的差别和List是一样的：把可变性上升到类型层面，编译器帮你检查。

你拿到一个Set，就放心用，没人能改它。你拿到一个mutable.Set，就知道这是个临时变量，别往方法外面传。

2. 集合运算原生支持

Java的Set要做并集、交集、差集，得自己写addAll、retainAll、removeAll，写起来很啰嗦。

Scala的Set原生就有++、&、--这些运算符，一行代码搞定。

3. 和集合体系无缝互转

Java的Set要转成List、转成数组，都得自己折腾。Scala的Set和List、Array、Map之间互转都是一行代码的事。

几个真正影响性能的细节

1. contains的性能，取决于元素的hashCode质量

Set的contains是O(1)——前提是hashCode分布均匀。如果你用的元素类型hashCode实现得很差，所有元素的hashCode都一样，那Set就退化成了链表，contains就是O(n)。

最常见的坑：你自己写了一个类，但没好好实现hashCode和equals。结果所有实例的hashCode都一样，Set就变成了O(n)的灾难。

经验法则：你放进Set里的类，必须同时正确实现equals和hashCode。两个方法要保持一致——相等的对象必须有相同的hashCode。

2. 大数据量下，HashSet的内存开销比List大

Set要维护哈希表，内存开销比List大。如果你的数据量特别大——比如几百万个元素——那Set的内存占用可能是List的好几倍。

这时候你要权衡：你要O(1)的contains，还是要省内存？很多时候，这个取舍是很现实的。

3. TreeSet比HashSet慢，但它是有序的

TreeSet的add和contains都是O(log n)，比HashSet的O(1)慢一点。但它是有序的——如果你需要有序的Set，这个代价是值得的。

别在不需要有序的场景下用TreeSet——纯浪费性能。

写在最后

我写这篇文章的时候，特意没罗列Set有多少个方法——因为那些东西官方文档都有，查一下就行。

真正值得花时间理解的是：Set到底解决了什么问题？

它不是"去重的列表"，它是一个专门为"成员判断"和"集合运算"设计的数据结构。它用哈希表的O(1)查找，换来了去重、成员判断、集合运算的高效。

在大数据开发里，Set无处不在——用户去重、UV统计、维度关联、权限判断、实时计算的状态管理。理解了Set，你就理解了大数据处理里最核心的几个操作：去重、join、聚合。

很多人用了几年Set，还停留在"new一个HashSet，然后add add add"的阶段。这不是Set的正确打开方式。Set的真正威力在于它的集合运算——并集、交集、差集、子集判断。这些操作用List写都是O(n²)，用Set写都是O(n)。

当你下次要写一个去重函数的时候，先想想：我是在解决"成员判断"的问题，还是在解决"顺序遍历"的问题？如果是前者，用Set。如果是后者，用List。

这个选择做对了，你的代码性能至少提升一个数量级。