filterKeys会导致堆栈溢出吗？

Question

据我了解，MapLike 的方法 filterKeys 在原始地图上创建了一个包装器。因此，如果我执行下面的代码 m 将是一串 10K 包装器和原始地图。

var m = Map(1 -> "one", 2 -> "two")
for(1 <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

现在我认为调用 m.contains 导致了堆栈溢出，但它并没有发生。您能解释一下这个案例中发生了什么吗？

Answer 1

我无法重现堆栈溢出，但发生的情况如下：

override def filterKeys(p: A => Boolean): Map[A, B] = new DefaultMap[A, B] {
  override def foreach[C](f: ((A, B)) => C): Unit = for (kv <- self) if (p(kv._1)) f(kv)
  def iterator = self.iterator.filter(kv => p(kv._1))
  override def contains(key: A) = self.contains(key) && p(key)
  def get(key: A) = if (!p(key)) None else self.get(key)
}

请注意，没有复制值：新类只是向四个方法添加规则，这将改变它们的工作方式以反映您添加的过滤器。由于您重复应用 filterKeys （10000 次），这意味着您有 10000 个类，每个类都指向前一个类，第一个类则指向您的原始地图。

因此，在最终类上（直接或间接）调用上述方法之一将调用 10000 个嵌套方法，如果堆栈足够小，这肯定会产生堆栈溢出。

Answer 2

我能够像这样导致堆栈溢出（Scala 2.9.1），

scala> var m = Map(1 -> "one", 2 -> "two")
scala> for (_ <- 0 until 1000000) { m = m.filterKeys(_ % 2 == 0) }
scala> m.contains(1)
huge stack trace

当然，您可以通过强制 filterKeys 在每一步实际执行其工作来避免堆栈跟踪：

scala> var m = Map(1 -> "one", 2 -> "two")
scala> for (_ <- 0 until 1000000) { m = Map() ++ m.filterKeys(_ % 2 == 0) }
scala> m.contains(1)
res1: Boolean = false

Answer 3

如果我逐字复制，你的循环只执行1次。因此，您只创建了一个包装器，因此原本打算成为 10000 个包装器的链实际上只是 1 的链。这可能是一个拼写错误，但循环

for(1 <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

可能应该是

for(i <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

除此之外，丹尼尔是对的； fitlerKeys 确实产生了本质上是包装器的东西。我花了超过 10k 次迭代，但我确实成功创建了一个 StackOverflowError。