Scala 可变 Set 操作：从性能问题到最佳实践

上一篇我们聊了不可变Set——它O(1)的contains、它的集合运算在大数据开发里无处不在。但有个问题如果你要在一个循环里不断往Set里加元素用不可变Set就会很别扭。这时候你需要的就是可变Set。很多人学Scala的时候记住了不可变优先这个原则然后就走到另一个极端——什么都用不可变Set。直到有一天他写了这么一段代码// 用不可变Set动态收集数据varseenSet.empty[String]for(line-lines){if(needProcess(line)){seenseenline}}看起来没问题对吧每次seen line返回一个新Set然后重新赋值给seen。但当seen里有十万个元素的时候每次操作都要重新构建整个哈希表——这个性能开销你品你细品。这时候你就需要可变Set了。这篇文章不讲可变Set是什么这种入门废话直接说干货为什么不可变Set在动态收集场景下不够用可变Set的底层是怎么实现的什么时候你该用可变Set而不是不可变Set先从一个性能问题说起假设你要写一个函数给定一个文件的所有行返回不重复的行集合。用不可变Set怎么写// 写法一用不可变SetvarseenSet.empty[String]for(line-lines){seenseenline}seen逻辑很直白遍历每一行如果不在集合里就加进去。但问题在哪seen line是O(n)的——因为不可变Set每次add都要创建一个新的哈希表结构把旧元素复制过去。十万行数据就是一百亿次操作。怎么优化把var换成val把不可变Set换成可变Set// 写法二用可变Setimportscala.collection.mutablevalseenmutable.Set.empty[String]for(line-lines){seenline}seen.toSet// 最后转成不可变Set输出现在seen line是摊销O(1)的——因为可变Set是原地修改哈希表不需要复制整个结构。整个函数的复杂度就变成了O(n)。从几分钟降到几秒就是这一行改动的差别。这就是可变Set存在的意义在需要动态收集数据的场景下可变Set的性能远好于不可变Set。可变Set的底层它就是个可变的哈希表很多人以为可变Set和不可变Set是两种完全不同的东西。其实它们的底层思路是一样的——都是基于哈希表。区别在于不可变Set每次add都返回一个新Set内部会尽量复用旧结构结构共享但在动态添加场景下复用效果有限可变Set直接在原哈希表上修改add/remove都是原地操作importscala.collection.mutable// 创建可变HashSetvalsetmutable.HashSet(1,2,3,4,5)// add原地添加set6// HashSet(1, 2, 3, 4, 5, 6)// remove原地删除set-3// HashSet(1, 2, 4, 5, 6)// contains和不可变Set一样O(1)set.contains(4)// true看出来了吗可变Set的API和不可变Set几乎一样——都是、-、contains。区别就是可变Set是原地修改不可变Set是返回新对象。这也是为什么Scala的集合体系这么优雅——不管可变还是不可变它们共享同一套API。你学会了一个就学会了所有。可变Set的几种实现和不可变Set一样可变Set也有几种不同的实现对应不同的场景。HashSet最常用的可变Setimportscala.collection.mutable.HashSetvalsetHashSet(1,2,3)set4最常用的可变Set底层就是个可变哈希表。add/remove/contains都是摊销O(1)。99%的场景用它就够了。LinkedHashSet保持插入顺序importscala.collection.mutable.LinkedHashSetvalsetLinkedHashSet[String]()setcsetasetb// LinkedHashSet(c, a, b) —— 保持插入顺序有时候你既要去重又要保持元素的插入顺序——这时候用LinkedHashSet。它底层是哈希表加链表既能O(1)查找又能保持插入顺序。这个在做日志解析、做事件追踪的时候特别好用——你既要去重又要保持事件的发生顺序。可变Set vs 不可变Set怎么选这是最常见的困惑。我给一个简单的判断标准你是在构建一个Set还是在使用一个Set在构建——数据是动态收集的你不知道最终有多少元素——用可变Set在使用——数据已经有了你要做查找、做集合运算——用不可变Set具体到实际场景场景用什么循环里动态收集元素可变Set构建一个Set后要在多个地方传递不可变Set需要频繁add/remove可变Set做并集/交集/差集不可变Set方法参数传入的Set不可变Set别假设它是可变的方法返回的Set不可变Set对外暴露不可变的最佳实践可变构建不可变输出这是Scala集合体系的老传统了内部用可变Set构建对外用不可变Set输出。defprocessLines(lines:List[String]):Set[String]{valseenmutable.HashSet[String]()for(line-lines){if(needProcess(line)){seenline}}seen.toSet// 最后转成不可变Set输出}这个模式的好处是内部高效用可变Set构建性能好外部安全对外暴露不可变Set调用方拿到的是线程安全的边界清晰可变的东西只在方法内部不会泄露出去这和ListBuffer的模式是一模一样的——可变收集不可变输出。和Java HashSet对比Java也有HashSet也有LinkedHashSet。那Scala的可变Set和Java的HashSet到底差在哪1. 运算符风格// JavaSetStringsetnewHashSet();set.add(a);set.remove(a);set.contains(a);// Scalaimportscala.collection.mutablevalsetmutable.Set[String]()setaset-aset.contains(a)写法上的差别只是表面。真正的差别在这几点2. 和Scala集合体系无缝互转Java的HashSet要转成List、转成数组都得自己折腾。Scala的可变Set和不可变Set、List、Array之间互转都是一行代码的事。3. 默认是不可变的Java里你new的HashSet默认就是可变的。你要想要不可变的得自己用Collections.unmodifiableSet()包一层——而且这只是个视图你拿着原始引用还是能改。Scala里默认的Set就是不可变的。你要可变的得显式importmutable.Set。这个设计哲学的差别和List是一样的把可变性上升到类型层面编译器帮你检查。几个真正影响性能的细节1. toSet是O(n)不是O(1)和ListBuffer的toList不一样可变Set的toSet不是零拷贝的——它需要把可变哈希表复制成一个不可变Set。所以如果你最后不需要转成不可变Set那就别转。但大多数情况下这个复制的开销是值得的——因为你对外暴露不可变Set调用方用起来更安全。2. 可变Set不是线程安全的这个不用多说了可变集合都不是线程安全的。如果你在多线程环境下需要共享Set要么用不可变Set要么自己加锁要么用并发集合。3. 大数据量下Set的内存开销比List大Set要维护哈希表内存开销比List大。如果你的数据量特别大——比如几百万个元素——那Set的内存占用可能是List的好几倍。这时候你要权衡你要O(1)的contains还是要省内存写在最后我写这篇文章的时候特意没罗列可变Set有多少个方法——因为那些东西官方文档都有查一下就行。真正值得花时间理解的是为什么需要可变Set不是因为它就是Java HashSet的Scala版而是因为在动态收集数据的场景下不可变Set的性能不够好。你要在循环里不断往Set里加元素用不可变Set就是O(n²)的灾难用可变Set就是O(n)的高效。但可变Set也不是万能的。它只适合构建场景——你在一个方法内部动态收集一批数据最后输出一个不可变Set。一旦数据收集完了你就该把它转成不可变Set在系统里安全地传递。这就是Scala集合体系的核心哲学可变用于构建不可变用于传递。理解了这个你就理解了Scala集合设计的精髓。你不会再纠结为什么不直接用Java的HashSet——因为你知道这不是哪个更好的问题而是设计哲学的区别。Java的集合是命令式的你有一个可变容器你往里面加东西、删东西容器一直在变。Scala的集合是函数式的数据是不可变的你操作数据的时候会生成新的数据。而在这个过程中如果你真的需要一个可变的临时容器Scala也给你准备好了——就是可变Set。它不是更好的HashSet它是函数式编程世界里那个让你可以安全地作弊的小窗口。平时你守规矩用不可变Set但当你真的需要动态构建数据的时候可变Set给你提供了一个高效的临时工作台。