scala - 何时使用 Scala TreeMap？

Question

给定以下 TreeMap 的示例:

scala> import scala.collection.immutable.TreeMap
import scala.collection.immutable.TreeMap

scala> val tm = TreeMap( ("foo" -> List(2,1) ) )
tm: scala.collection.immutable.TreeMap[String,List[Int]] = Map(foo -> List(2, 1))

scala> tm + ("bar" -> List(300, 4) )
res0: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), foo -> List(2, 1))

scala> res0 + ("bippy" -> List(4) )
res1: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), bippy -> List(4), foo -> List(2, 1))

我不清楚何时使用 TreeMap 优于 Map .什么时候？

Answer 1

TreeMap 保证 map 中的条目使用键按排序顺序排列，而 Map 不提供任何此类保证。

因此，如果您想要在 map 中对键进行排序，请使用 TreeMap 否则普通 map 就足够了。我使用 TreeMap 的地方正在为 Twitter's API 生成 token .要创建 token ，需要使用按字典顺序排序的 url 参数创建字符串。我在 map 中获取 url 参数，然后将其放入 TreeMap 中以对其进行排序。

有点深-

Scala 使用 Hash Tries创建一个 HashMap(这是 Map 的默认实现)，其中数据结构是 Trie 并且键是散列的。此外，当大小小于 5( source ) 时，Scala 会优化 HashMap。它在正常情况下提供恒定的查找和插入成本。

另一方面，TreeMap 是使用 Red Black trees 构建的.红黑树的查找和插入成本为 O(ln n)。

因此，当您不想对键进行排序以获得更好的性能时，请使用 Map。

更多详情在收藏docs