在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]{valresultListBuffer[Int]()for(x-list){if(!result.contains(x)){resultx}}result.toList}这个逻辑很直白遍历原列表如果结果里没有这个元素就加进去。但问题在哪result.contains(x)是O(n)的——因为result是List你要从头扫到尾才能找到这个元素。整个函数的复杂度就是O(n²)。数据量小的时候没感觉十万条数据就是一百亿次比较。这就是为什么那个UV统计任务跑了半小时——它本质上就是一个O(n²)的去重。怎么优化很简单把List换成Set// 写法二用Set去重defdistinct(list:List[Int]):List[Int]{valseenscala.collection.mutable.Set[Int]()valresultListBuffer[Int]()for(x-list){if(!seen.contains(x)){seenx resultx}}result.toList}现在seen.contains(x)是O(1)的——因为Set是基于哈希表实现的。整个函数的复杂度就变成了O(n)。从半小时降到30秒就是这一行改动的差别。这就是Set的价值它用O(1)的contains换来了O(n)的去重。Set不是去重的列表它是数学上的集合很多人对Set的理解停留在自动去重的列表。这个理解太浅了。List是什么List是有序的序列——你关心的是每个元素在第几个位置你关心的是元素之间的顺序。Set是什么Set是数学上的集合——你关心的是某个元素在不在里面你根本不关心它在第几个位置。这两个东西的设计目标完全不一样维度ListSet核心问题这个元素在第几个位置这个元素在不在里面containsO(n)O(1)有序有序无序HashSet重复元素允许不允许典型操作get(i)、indexOf(i)add、remove、contains典型场景遍历、按位置访问、保持顺序去重、成员判断、集合运算看出来了吗Set和List不是同一个东西的不同变体而是解决不同问题的两种数据结构。你做用户去重本质问题是这个用户在不在已经见过的集合里——这就是Set的主场。你要按时间顺序输出日志那就是List的主场。搞清楚你要解决的核心问题是什么比你记住多少个API都重要。Scala Set的底层实现不是一个东西是一套体系很多人以为Scala的Set就是一个类就像Java的HashSet那样。其实不是——Scala的Set是一整套体系不同的实现对应不同的场景。HashSet最常用的Setimportscala.collection.immutable.HashSetvalsetHashSet(1,2,3,4,5)set.contains(3)// trueO(1)HashSet是最常用的Set实现底层是基于哈希表的——你调用add的时候它会算这个元素的hashCode然后存到对应的桶里。你调用contains的时候它直接算hashCode去对应的桶里找——所以是O(1)。这就是为什么Set的contains这么快——它不是遍历一遍找而是直接算出来在哪然后去拿。TreeSet有序的Setimportscala.collection.immutable.TreeSetvalsetTreeSet(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保持插入顺序的Setimportscala.collection.mutable.LinkedHashSetvalsetLinkedHashSet[Int]()set3set1set2// LinkedHashSet(3, 1, 2) —— 保持插入顺序有时候你既要去重又要保持元素的插入顺序——这时候用LinkedHashSet。它底层是哈希表加链表既能O(1)查找又能保持插入顺序。经验法则场景用什么Set只需要去重、成员判断不需要顺序HashSet需要元素按大小排序TreeSet需要保持插入顺序LinkedHashSet数据量很小十几个元素随便用哪个差别不大很多人不管什么场景都用默认的HashSet其实在需要有序的场景下TreeSet能帮你省掉排序的步骤。不可变Set vs 可变SetScala的老传统和List一样Scala的Set也分不可变和可变两套。// 不可变Setvalset1Set(1,2,3)valset2set14// 返回新Setset1不变// 可变Setimportscala.collection.mutable.SetvalbufSet(1,2,3)buf4// 原地修改这个设计哲学和List是一样的对外暴露不可变Set内部用可变Set构建。但Set有个和List不一样的地方——不可变Set的性能其实没那么差。为什么因为Set的核心操作是contains是基于哈希的O(1)操作。即使你每次add都返回一个新Setadd操作本身也是O(1)平均情况。所以在Set这个场景下可变和不可变的性能差距没有List那么大。很多时候你直接用不可变Set就够了不需要特意搞个可变Set来构建。// 直接用不可变Set就行不用搞个可变SetvalsetSet(1,2,3)456这也是为什么很多人觉得Scala的Set比List好用——因为不可变Set的性能足够好你不需要像List那样纠结我到底该不该用ListBuffer。Set的核心操作不只是add和remove很多人用Set就只会add、remove、contains这三个操作。其实Set真正强大的地方是它的集合运算——这是数学上的集合不是列表。并集、交集、差集valaSet(1,2,3,4)valbSet(3,4,5,6)// 并集两个集合合在一起去重ab// Set(1, 2, 3, 4, 5, 6)a union b// 同上// 交集两个集合都有的元素a intersect b// Set(3, 4)ab// 同上// 差集在a里但不在b里的元素a diff b// Set(1, 2)a--b// 同上这三个操作在大数据开发里太常用了。比如你要算上周活跃但这周不活跃的用户——这就是差集。你要算两周都活跃的用户——这就是交集。你要算累计用户总数——这就是并集。这些操作用List写都是O(n²)的灾难。用Set写都是O(n)的高效操作。子集判断valallUsersSet(u1,u2,u3,u4,u5)valpaidUsersSet(u1,u3)// paidUsers是不是allUsers的子集paidUsers.subsetOf(allUsers)// true这个操作做权限判断、做范围校验的时候特别好用。什么时候该用Set什么时候该用List这是最常见的困惑。我给一个简单的判断标准你关心的是元素在不在里面还是元素在第几个位置关心在不在 → 用Set关心第几个位置 → 用List具体到实际场景用Set的场景去重你有一堆数据要去掉重复的成员判断你要频繁判断某个元素在不在里面集合运算并集、交集、差集缓存索引你要快速查找某个key是否存在用List的场景按顺序输出你要按时间顺序、按插入顺序输出元素按位置访问你经常要get(i)拿第i个元素保持顺序的去重你要去重但还要保持原来的顺序这时候用LinkedHashSet或者ListSet配合遍历处理你要逐个遍历元素做处理而且元素顺序很重要一个最常见的错误很多人做去重的时候直接把List转成Set然后就完事了。// 错误顺序没了vallistList(3,1,2,1,3)valdistinctlist.toSet.toList// List(1, 2, 3) —— 顺序变了如果你只是要去重不在乎顺序这么写没问题。但如果你要保持原来的顺序——比如你要按时间顺序输出不重复的事件——那这么写就错了。正确的做法是用LinkedHashSet或者ListSet配合// 正确去重并保持插入顺序vallistList(3,1,2,1,3)valseenscala.collection.mutable.Set[Int]()valresultListBuffer[Int]()for(x-list){if(!seen(x)){seenx resultx}}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。这个选择做对了你的代码性能至少提升一个数量级。
