为什么可变和不可变 ListMap 在 Scala 中具有不同的顺序？

Question

为什么ListMap的不可变版本按升序存储，而可变版本按降序存储？

如果您有 scalatest-1.6.1.jar 和 junit-4.9.jar，您可以使用以下测试

  @Test def StackoverflowQuestion()
  {
    val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18)
    val sortedIMMUTABLEMap = collection.immutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedIMMUTABLEMap.head._2)
    println("last : " + sortedIMMUTABLEMap.last._2)
    sortedIMMUTABLEMap.foreach(X => println(X))
    assert(sortedIMMUTABLEMap.head._2 < sortedIMMUTABLEMap.last._2)

    val sortedMUTABLEMap = collection.mutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedMUTABLEMap.head._2)
    println("last : " + sortedMUTABLEMap.last._2)
    sortedMUTABLEMap.foreach(X => println(X))
    assert(sortedMUTABLEMap.head._2 > sortedMUTABLEMap.last._2)
  }

： 这是 PASSING 测试的输出：

head : 2
last : 18
(C,2)
(A,5)
(D,9)
(B,12)
(E,18)
head : 18
last : 2
(E,18)
(B,12)
(D,9)
(A,5)
(C,2)

Answer 1

症状可以简化为：

scala> collection.mutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(2,two)
(1,one)

scala> collection.immutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(1,one)
(2,two)

代码中的“排序”不是问题的核心，您对 ListMap 的调用正在使用来自同伴的 ListMap.apply 调用构造由可变或不可变列表支持的列表映射的对象。规则是插入顺序将被保留。

区别似乎在于可变列表由不可变列表支持，并且插入发生在前面。这就是为什么在迭代时会出现后进先出行为。我仍在寻找不可变的，但我打赌插入实际上在后面。编辑，我改变主意：插入可能在前面，但似乎 immutable.ListMap.iterator 方法决定使用 toList.reverseIterator 反转结果在返回的迭代器上。我认为值得将其放入邮件列表中。

文档可以更好吗？当然。有痛吗？不是真的，我不会让它发生。如果文档不完整，明智的做法是在选择一种结构与另一种结构之前测试其行为或查找源代码。

实际上，如果 Scala 团队决定稍后改变行为并且认为他们可以，因为该行为实际上没有记录并且没有合同，那么可能会很痛苦。

---

为了解决评论中解释的用例，假设您已经在映射（可变或不可变）中收集了字符串频率计数：

val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18, "B" -> 5)

由于您只需要在最后排序一次，因此您可以将元组从映射转换为seq 然后排序：

map.toSeq.sortBy(_._2)
// Seq[(java.lang.String, Int)] = ArrayBuffer((C,2), (A,5), (B,5), (D,9), (E,18))

Answer 2

据我所知，ListMap 都没有声称是排序的映射，而只是用列表实现的映射。事实上，我在他们的合同中没有看到任何关于保留插入顺序的内容。

Scala 编程解释说，如果早期元素更有可能被访问，则 ListMap 可能有用，但除此之外它与 Map 相比几乎没有优势。

Answer 3

不要对订单建立任何期望，它没有声明，并且在 Scala 版本之间会有所不同。

例如：

import scala.collection.mutable.{ListMap => MutableListMap}

MutableListMap("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18).foreach(println)

在 2.9.1 上给出：
（E，18）
(D,9)
(C,2)
（乙，12）
(A,5)

但在 2.11.6 上给出：
（E，18）
(C,2)
(A,5)
（乙，12）
(D,9)