从 mutable.Map 到 immutable.Map 的 O(1) 转换？

Question

有没有办法在 O(1) 时间内将可变 Map 转换（包装）为不可变（也就是说，不是通过复制值，而是类似于 JavaConversions 中所做的）

Answer 1

正如 Thomas 指出的，只读视图的复杂度为 O(1)。但只读并不等于不变性。

这种差异在“对抗位腐烂中得到了很好的描述”论文：

所有集合类都保存在
包 scala.collection。这个套餐
具有三个子包：mutable、
不可变的、通用的。最多
集合以三种形式存在，
取决于它们的可变性。

封装中的集合
scala.collection.immutable 是
保证不可变
每个人。这意味着人们可以信赖
访问相同的事实
收藏价值随着时间的推移永远
产生具有相同的集合
元素。包装中的集合
scala.collection.mutable 已知
有一些改变的操作
收集到位。

封装中的集合
scala.collection 可以是可变的
或不可变。例如，
collection.Seq[T] 是以下的超类
collection.immutable.Seq[T] 和
集合.mutable.Seq[T]。一般来说，
scala 包中的根集合。
集合定义相同的接口
作为不可变集合，以及
包中的可变集合
scala.collection.mutable 通常添加
一些破坏性的修改
对此不可变的操作
界面。 之间的区别
根集合和不可变
集合是一个用户
不可变集合有保证
没有人可以改变集合，
而根集合的用户有
承担他人的修改，
即使他们无能为力
自行修改。

也许这只是简单的向上转换。

scala> val mm = collection.mutable.Map(1 -> 2)
mm: scala.collection.mutable.Map[Int,Int] = Map(1 -> 2)

scala> val readOnly = mm : collection.Map[Int, Int]
readOnly: scala.collection.Map[Int,Int] = Map(1 -> 2)

Answer 2

有一个只读投影 对于可变映射。

scala> collection.mutable.Map(1->2).readOnly
res0: scala.collection.Map[Int,Int] = ro-Map(1 -> 2)

正如 oxbow_lakes 指出 底层 Map 是仍然可变，并且在只读投影发布给客户端后可能会发生变化。不变性的错觉必须在管理地图的代码中解决。

Answer 3

您所要求的本质上是不安全的。您可以将 mutable.Map 作为不可变的 collection.Map 传递，但使用此表单的“客户端”无法确定他们的视图不会从他们下面改变。

Answer 4

原则上可以向可变数据结构添加一种“冻结”方法，以防止进一步的突变。这是唯一稍微安全的包装方法。 （只有一点点，因为之后当你尝试改变它时，你必须抛出异常。）但是，Scala 的可变集合不具备此功能。人们可以通过覆盖所有变异方法（update、+=、++= 等）将其添加到例如 mutable.HashMap 中，但是这将是一项相当大的工作。

Answer 5

Philipp Haller 在独特性和借用能力方面的工作与此相关。在通过类型系统强制执行“所有权”领域还有很多其他工作，但 Philipp 实际上为 Scala 编译器提供了一个可用的插件。

Answer 6

类似这样的事情应该做，它类似于 ArraySeq.unsafeWrapArray 。

class UnsafeWrappedMap[K, V](underlying: mutable.Map[K, V]) extends Map[K, V] with StrictOptimizedMapOps[K, V, Map, Map[K, V]] {
  def removed(key: K) = underlying.iterator.filter(_._1 != key).toMap

  def updated[V1 >: V](key: K, value: V1) = {
    underlying.iterator.map {
      case (`key`, _) => (key, value)
      case kv => kv
    }.toMap
  }

  def get(key: K) = underlying.get(key)

  def iterator = underlying.iterator
}

object UnsafeWrappedMap {
  def apply[K, V](underlying: mutable.Map[K, V]) = new UnsafeWrappedMap(underlying)
}

显然，在创建此映射后，您一定不能触摸可变映射！

一个更雄心勃勃的解决方案可能是创建一个映射，一旦创建了副本，就会设置一个内部标志，并且任何未来的突变都将导致可变实例在执行突变之前复制其内部状态。