performance - Scala 最高效的 Map 实现

Question

在单个线程中创建和使用 Scala Map 时，最好的选择是什么？ (就像在 StringBuffer 与 StringBuilder 上构造字符串的 java 类似的最佳赌注)。

选择 Map 的约束类型是:

map 创建一次，对可能的现有键进行多次添加/更新

map 中没有删除任何内容 - 因此可能不需要这种操作

map 可能有数千个值(不是很大)

用法来自同一个线程(因此不必担心并行访问/更新 map )

map 的签名可能是 Map[String,T]。如果有理由可以使用 Map[Int/Long,T]。

我调查过

collection.immutable.Map(最初有效 优化 用于几个键)

collection.immutable.HashMap

collection.mutable.OpenHashMap

collection.mutable.HashMap

测试表明，50000 个 key 没有明显的赢家。
我找到了一些

simple microbenchmarks comparing Scala vs Java mutable map performance - 201这表明 OpenHashMap 可能是一个不错的选择

New collections in Scala 2.7.2 - 2008

官方scaladoc Performance Characteristics除了所有 Map 实现都采用 之外，不提供方向eC - 有效恒定时间 用于查找和添加。

然而，问题是在这种情况下，一般来说什么是最安全的赌注，为什么？

Answer 1

如果您的 map 不是非常小也不是很大，并且您的 key 是 String ，然后 collection.mutable.AnyRefMap是个好赌注。 collection.mutable.LongMap如果您可以拥有 Long 甚至更快键。它们存在的原因正是为了快速处理常见用例。

如果大多数 map 都非常小(0-4 个元素)，那么 LinkedHashMap往往是最好的，因为它避免了哈希表的开销。 (不可变映射在 4 个或更少元素时也不错。)

如果映射真的很大(数以百万计的键/值对)，那么标准 collection.mutable.HashMap是要走的路，因为当您用完单独键的空间时，性能会稍微降低一点。