Question

1. Map 是由键值对组成的 Iterable 。 scala 的 Predef 类提供了一个隐式转化， 让我们可以用 key -> value 这样的写法来表示 (key, value) 这样的 pair 。 因此 Map ( "x" -> 1, "y" -> 2) 和 Map(("x",1), ("y",2)) 的含义完全 相同， 但是前者更易读。

2. 与Set 类似，Scala 也提供了可变、不可变版本的Map 。Set(),mutable.Set(),Map(),mutable.Map() 等工厂方法返回的Set 和 Map 其实都是不同的类型。

   • 对于可变的 mutable.Set() 工厂方法，它返回的是mutable.HashSet 对象。

   • 对于可变的 mutable.Map() 工厂方法，它返回的是 mutable.HashMap 对象。

   • 不可变的 Set() 工厂方法返回的类型取决于我们传入多少个元素。对于少于五个元素的Set，有专门特定大小的类与之对应从而达到最佳性能；大于等于五个元素的 Set 返回的是 HashSet 类型。

     • 零个元素：immutable.EmptySet 。
     • 一个元素：immutable.Set1 。
     • 二个元素：immutable.Set2 。
     • 三个元素：immutable.Set3 。
     • 四个元素：immutable.Set4 。
     • 五个或更多元素：immutable.HashSet。

   • 同理，不可变的 Map() 工厂方法返回的类型取决于我们传入多少个元素。对于少于五个元素的Map，有专门特定大小的类与之对应从而达到最佳性能；大于等于五个元素的 Map 返回的是 HashMap 类型。

     • 零个：immutable.EmptyMap 。
     • 一个：immutable.Map1. 。
     • 二个：immutable.Map2 。
     • 三个：immutable.Map3 。
     • 四个：immutable.Map4 。
     • 五个或更多：immutable.HashMap。

   默认的不可变实现可以提供最佳性能。另外，如果添加一个元素到 EmptySet，则返回一个 Set1 对象。如果从 Set1 对象移除一个元素，则得到一个 EmptySet 对象。

3. 可以通过 += 和 -> 来向Map 中添加键值对。

   
   xxxxxxxxxx
   import scala.collection.mutable
   val map1 = mutable.Map[Int,String]()
   map1 += (1 ->"1")
   map1 += (2 ->"2")

   • 1 -> "1" 转换成标准的方法调用，即1.->("1")。

     你可以在任何对象上调用-> 方法，它返回的是一个二元元组。

   • += 将调用map1 对象的.+=() 方法，向map1 中添加键值对。

4. Map 特质和操作和 Set 类似：

   • 查找：

     • ms get k ： 以 Option 表示的、ms 中跟键k 关联的值， 如果没有对应的 k 则返回 None 。
     • ms(k) ： 返回 ms 中跟键 k 关联的值， 如果没有对应的 k 则抛出异常。
     • ms apply k ： 等价于 ms(k)。
     • ms getOrElse(k,d) ： 返回 ms 中跟键 k 关联的值， 如果没有对应的 k 则返回 d 。
     • ms contains k： 测试 ms 中是否包含键 k。
     • ms isDefinedAt k ： 等价于 ms contains k 。

   • 添加和更新：

     • ms + (k -> v) ： 创建一个包含 ms 和给定 k -> v 键值对的新的 Map。
     • ms + (k -> v, w-> u)： 创建一个包含 ms 和给定 k -> v， w -> u 键值对的新的 Map 。
     • ms + kvs ： 创建一个包含 ms 和给定 kvs 包含的所有键值对的新的 Map 。
     • ms updated(k,v) ： 等价于 ms + (k -> v)

   • 移除：

     • ms - k ： 创建一个包含 ms 所有映射关系、但不包含键 k 的新的 Map 。
     • ms - (k,l,m)： 创建一个包含 ms 所有映射关系、但不包含键 k,l,m 的新的 Map 。
     • ms -- ks ： 创建一个包含 ms 所有映射关系、但不包含 ks 中所有键的新的 Map 。

   • 子集合：

     • ms.keys ： 返回 ms 中所有键的 Iterable 。
     • ms.keySet： 返回 ms 中所有键的 Set。
     • ms.keysIterator ： 返回一个迭代器， 该迭代器迭代时交出 ms 中每个键。
     • ms.values ： 返回ms 中所有值的 Iterable。
     • ms.valuesIterator ： 返回一个迭代器， 该迭代器迭代时交出 ms 中每个值。

   • 变换 transform：

     • ms filterKeys p ： 只包含 ms 中那些键满足条件 p 的映射关系的 Map 视图。
     • ms mapValues f： 通过对 ms 中每个value 应用函数 f 得到的 Map 视图。

5. mutable.Map 特质的操作：

   • 添加和更新：

     • ms(k) = v ： 以副作用将 k -> v 映射关系添加到 ms ， 或者更新 ms 的键k 对应的值。 也可以写作 ms.update(k, v)。
     • ms += (k -> v) ： 以副作用的方式将 k -> v 映射关系添加到 ms ， 返回 ms 本身。
     • ms += (k1 -> v1, k2 -> v2) ： 以副作用的方式将 k1 -> v1, k2 -> v2 映射关系添加到 ms ， 返回 ms 本身。
     • ms ++= kvs ： 以副作用的方式将 kvs 中的映射关系添加到 ms ， 并返回 ms 本身。
     • ms put (k, v) ： 将 k -> v 映射关系添加到 ms 中， 并以Option 的方式返回之前与 k 关联的值。
     • ms getOrElseUpdate(k, d)： 如果键 k 在 ms 中有定义， 则返回关联的值。否则用 k -> d 更新 ms 并返回 d 。

   • 移除：

     • ms -= k ： 以副作用的方式移除键 k 的映射关系， 并返回 ms 本身。
     • ms -= (l, k, m) ： 以副作用的方式从 ms 移除给定键的映射关系， 并返回 ms 本身。
     • ms --= ks ： 以副作用的方式从 ms 移除 ks 中所有键的映射关系， 并返回 ms 本身。
     • ms remove k ： 从 ms 中移除键 k 的映射关系并以 Option 的形式返回键k 之前关联的值。
     • ms retrain p ： 仅保留 ms 中那些键满足条件 p 的映射关系。
     • ms.clear() ： 从 ms 中移除所有的映射关系。

   • 变换和克隆

     • ms transform f ： 用函数 f 变化 ms 中所有关联的 key-value 的 pair 对。f 的输入包括key 和 value 。
     • ms.clone ： 返回跟 ms 包含相同映射关系的新的可变映射。

6. 和 Set 一样， Map 的添加和移除操作涉及到对象的拷贝， 因此不常用。相比之下， mutable.Map 的添加和移除使用得更多。

7. mutable.Map.getOrElseUpdate 适合用作对cache 的映射的访问：

   
   xxxxxxxxxx
   def f(x :String) :String = {
     .... // 这里需要经历一个开销巨大的计算， 如连接数据库或者发送网络请求
   }
   val cache = collection.mutable.Map[String, String]()
   def cachedF(s : String) = cache.getOrElseUpdate(s, f(s))

   注意： getOrElseUpdate 方法的第二个参数是传名by-name 的， 因此只有当 getOrElseUpdate 需要第二个参数的值时， f(s) 的计算才会真正执行。

8. 有时候我们需要迭代器按照特定顺序迭代的Set 或 Map，对此 Scala 提供了 SortedSet 和 SortedMap 这两个 Trait 。这些Trait 被 TreeSet 和 TreeMap 类实现，这些实现采用红黑树来保持元素（对于 TreeSet ）或者键（对于Map）的顺序，具体顺序由 Ordered Trait 决定，Set 元素的类型或者 Map 键的类型必须都混入了 Ordered Trait 或者能够被隐式转换为 Ordered 。

   这两个类只有不可变的版本。

   
   xxxxxxxxxx
   import scala.collection.immutable.{TreeSet，TreeMap}
   val ts = TreeSet(1,9,2,4,8)
   val tm = TreeMap(1 -> "a",9 -> "b", 2 -> "c")

9. 可变集合类型和不可变集合类型的选择：

   • 通常首选采用不可变集，因为不可变集合容易理解和使用。

   • 在元素不多的情况下，不可变集合通常比可变集合更紧凑。

     • 一个空的可变Map，如果按照默认的 HashMap 实现，会占用80 字节，每增加一项需要额外的 1.6字节。
     • 而一个空的不可变 Map 是个单例对象，它被所有引用共享，因此使用它本质上只需要一个指针的大小。

     因此对于小型的 Map 和 Set，不可变版本比可变版本紧凑的多，可以节省大量空间，并带来重要的性能优势。

   • Scala 提供了一些语法糖来让不可变 Set 和可变 Set 的切换更加容易。

     如：虽然不可变 Set 不支持 += 操作，但是 Scala 提供了一个变通途径：只要看到 a += b 而 a 并不支持 += 方法，则 Scala 尝试将其解读为 a = a + b。此时 a 必须被声明为 var 而不是 val 。

     
     xxxxxxxxxx
     val a = Set(1,2,3)
     var c = Set(1,2,3)
     a + = 4 // 不支持
     c + = 4 // 等价于 c = c + 4， c 指向一个新的 Set

     同样的思想适合所有以 = 结尾的方法。 这时候只需要将 Set 替换为 mutable.Set 就能够用很小的代价来替换到可变Set 的版本。

     这样的特殊语法不仅适合于Set，它也适合于Map 、以及所有的值类型。