performance - 为什么 Map 实现应该覆盖 foreach？

Question

documentation对于 scala.collection.mutable.Map 来说。

It is also good idea to override methods foreach and size for efficiency.

覆盖size(可能)是O(n)到O(1)的改进。

但是重写 foreach 的值(value)是什么？

Answer 1

scala.collection.immutable.MapLike 中 foreach 的默认实现使用迭代器来实现 foreach。此实现继承自 IterableLike 。

def foreach[U](f: A => U): Unit =
  iterator.foreach(f)

但是实现迭代器通常比实现 foreach 复杂得多。迭代器必须显式地跟踪当前位置，这需要状态，并且在树状结构的情况下可能需要大量逻辑，例如什么用于不可变的 HashMap。以下是当前集合库中不可变 HashMap 和 HashSet 的迭代器作为示例 TrieIterator 。并不简单，对吧？

另一方面，foreach 方法使用调用堆栈来跟踪当前位置，因此实现起来非常简单且高效。二叉树的 foreach 方法就是 left.foreach(f); right.foreach(f)。

因此，根据映射的迭代器的复杂程度，单独实现 foreach 可能确实是一个好主意，以提高性能。