什么更新了PrefixMap继承的Map？

Question

运行《Scala 编程》第 3 版中的 PrefixMap 示例来自 The Architecture of Scala Collections 一章，我不明白在调用更新时更新 PrefixMap 的继承 Map 是什么。这是代码：

import collection._

class PrefixMap[T]
  extends mutable.Map[String, T]
    with mutable.MapLike[String, T, PrefixMap[T]] {

  val id: Long = PrefixMap.nextId
  var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
  var value: Option[T] = None

  def get(s: String): Option[T] =
    if (s.isEmpty) value
    else suffixes get s(0) flatMap (_.get(s substring 1))

  def withPrefix(s: String): PrefixMap[T] =
    if (s.isEmpty) this
    else {
      val leading = s(0)
      suffixes get leading match {
        case None =>
          suffixes = suffixes + (leading -> empty)
        case _ =>
      }
      val ret = suffixes(leading) withPrefix (s substring 1)
      println("withPrefix: ends with: id="+this.id+", size="+this.size+", this="+this)
      ret
    }

  override def update(s: String, elem: T) = {
    println("update: this before withPrefix: id="+this.id+", size="+this.size+", return="+this)
    val pm = withPrefix(s)
    println("update: withPrefix returned to update: id="+pm.id+", size="+pm.size+", return="+pm)
    println("===> update: this after withPrefix and before assignment to pm.value : id="+this.id+", size="+this.size+", return="+this)
    pm.value = Some(elem)
    println("===> update: this after assinment to pm.value: id="+this.id+", size="+this.size+", return="+this)
  }

  override def remove(s: String): Option[T] =
    if (s.isEmpty) { val prev = value; value = None; prev }
    else suffixes get s(0) flatMap (_.remove(s substring 1))

  def iterator: Iterator[(String, T)] =
    (for (v <- value.iterator) yield ("", v)) ++
      (for ((chr, m) <- suffixes.iterator;
            (s, v) <- m.iterator) yield (chr +: s, v))

  def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }

  def -= (s: String): this.type  = { remove(s); this }

  override def empty = new PrefixMap[T]
}

object PrefixMap {
  var ids: Long = 0
  def nextId: Long = { PrefixMap.ids+=1; ids }
}

object MyApp extends App {
  val pm = new PrefixMap[Int]
  pm.update("a", 0)
  println(pm)

}

输出为：

更新：在 withPrefix 之前：id=1，size=0，return=Map()

withPrefix: 结束于: id=1, size=0, this=Map()

更新：withPrefix return更新：id=2，size=0，return=Map()

===> 更新：在 withPrefix 之后和分配给 pm.value 之前：id=1，size=0，return=Map()

===> 更新：在对 pm.value 进行分类之后：id=1，size=1，return=Map(a -> 0)

地图（a -> 0）

所以问题是：update方法中带"pm.value = Some(elem)"的那一行怎么可能导致继承的PrefixMap的Map更新为(a -> 0)?

Answer 1

不清楚你所说的“继承 PrefixMap的映射”是什么意思。 Map 是一个 trait，如果你来自 Java 世界，它类似于 interface。这意味着 Map 本身没有任何价值，它只是指定契约并通过 "core" 方法（您在 PrefixMap 中实现的方法提供各种便利方法的一些默认实现).

至于整个数据结构的工作原理，您应该将此 PrefixMap 实现想象成 "tree"。从逻辑上讲，每条边都有一个字符（在前缀序列中），每个节点可能对应于一个字符串的值，该字符串是通过累积从根到当前节点的路径上的所有字符创建的。

因此，如果您有一个具有 "ab" -> 12 键值的地图，树将如下所示：

如果你把 "ac" -> 123 添加到树中，它将变成

最后，如果您将 "a" -> 1 添加到树中，它将变为：

这里的重要观察是，如果您将 "a" 节点作为根节点，您将得到一个有效的前缀树，所有字符串都被该 "a" 前缀缩短。

物理布局有点不同：

有根节点是PrefixMap[T]，从外面看是Map[String,T]，还有一个空字符串key的节点。
value + suffixes 的内部节点，即可选值和合并的子节点列表及其边缘上的相应字符到 Map[Char, PrefixMap[T]]

如您所见，update 实现是通过 withPrefix 调用有效地查找内容，然后为其赋值。那么 withPrefix 方法的作用是什么？虽然它是递归实现的，但以迭代的方式考虑它可能更容易。从这个角度来看，它逐一遍历给定 String 的字符，并在树中导航，创建缺失的节点，参见

 case None =>
      suffixes = suffixes + (leading -> empty)

最后 returns 对应于整个 String 的节点（即 this 在最深递归的情况下 s.isEmpty）

方法 get 的实现实际上与 withPrefix 非常相似：它递归地遍历给定的字符串并在树中导航，但它更简单，因为它不必创建缺失的节点。因为子节点实际上也存储在 Map 它的 get 方法 returns Option 中 PrefixMap 应该 return Option.所以你可以只使用 flatMap 如果在某个级别没有这样的子节点它会工作正常。

最后 iterator 创建它的迭代器作为

的并集

value.iterator（幸运的是 Option 在 Scala 中实现 iterator return 只是 1 或 0 个元素，具体取决于是否有值）
所有子节点的所有 iterators 只是将自己的字符作为前缀添加到它们的键中。

所以当你这样做时

val pm = new PrefixMap[Int]
pm.update("a", 0)
println(pm)

update 在树中创建节点并存储值。 pm.toString 实际上使用 iterate 来构建字符串表示。因此它遍历树集合所有节点中非空 value Options 中的所有值。

什么更新了PrefixMap继承的Map？

What updates the inherited Map of PrefixMap?

scala

scala-collections