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