保留插入顺序的不可变 Scala Map 实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9313866/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Immutable Scala Map implementation that preserves insertion order
提问by Matroska
LinkedHashMapis used to preserve insertion order in the map, but this only works for mutable maps. Which is the immutable Mapimplementation that preserves insertion order?
LinkedHashMap用于保留地图中的插入顺序，但这仅适用于可变地图。哪个是Map保留插入顺序的不可变实现？
回答by missingfaktor
ListMapimplements an immutable map using a list-based data structure, and thus preserves insertion order.
ListMap使用基于列表的数据结构实现不可变映射，从而保留插入顺序。
scala> import collection.immutable.ListMap
import collection.immutable.ListMap
scala> ListMap(1 -> 2) + (3 -> 4)
res31: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4)
scala> res31 + (6 -> 9)
res32: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4, 6 -> 9)
The following extension method - Seq#toListMapcan be quite useful when working with ListMaps.
以下扩展方法 -Seq#toListMap在使用ListMaps时非常有用。
scala> import scalaz._, Scalaz._, Liskov._
import scalaz._
import Scalaz._
import Liskov._
scala> :paste
// Entering paste mode (ctrl-D to finish)
implicit def seqW[A](xs: Seq[A]) = new SeqW(xs)
class SeqW[A](xs: Seq[A]) {
def toListMap[B, C](implicit ev: A <~< (B, C)): ListMap[B, C] = {
ListMap(co[Seq, A, (B, C)](ev)(xs) : _*)
}
}
// Exiting paste mode, now interpreting.
seqW: [A](xs: Seq[A])SeqW[A]
defined class SeqW
scala> Seq((2, 4), (11, 89)).toListMap
res33: scala.collection.immutable.ListMap[Int,Int] = Map(2 -> 4, 11 -> 89)
回答by axel22
While ListMapwill preserve insertion order, it is not very efficient - e.g. lookup time is linear. I suggest you create a new collection class which wraps both the immutable.HashMapand the immutable.TreeMap. The immutable map should be parametrized as immutable.HashMap[Key, (Value, Long)], where the Longin the tuple gives you the pointer to the corresponding entry in the TreeMap[Long, Key]. You then keep an entry counter on the side. This tree map will sort the entries according to the insertion order.
虽然ListMap会保留插入顺序，但效率不是很高——例如查找时间是线性的。我建议您创建一个新的集合类，它同时immutable.HashMap包含immutable.TreeMap. 不可变映射应参数化为immutable.HashMap[Key, (Value, Long)]，其中Long元组中的 为您提供指向TreeMap[Long, Key]. 然后，您将入口柜台放在一边。此树图将根据插入顺序对条目进行排序。
You implement insertion and lookup in the straightforward way - increment the counter, insert into the hash map and insert to the the counter-key pair into the treemap. You use the hash map for the lookup.
您以简单的方式实现插入和查找 - 增加计数器，插入哈希映射并将计数器键对插入到树映射中。您使用哈希映射进行查找。
You implement iteration by using the tree map.
您可以使用树图实现迭代。
To implement remove, you have to remove the key-value pair from the hash map and use the index from the tuple to remove the corresponding entry from the tree map.
要实现删除，您必须从哈希映射中删除键值对，并使用元组中的索引从树映射中删除相应的条目。
