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).

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