保留插入顺序的不可变的Scala Map实现

LinkedHashMap用于在地图中保留插入顺序，但是这只适用于可变映射。 哪个是保留插入顺序的不可变Map实现？

Answer 1

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) 

以下扩展方法Seq#toListMap在处理Seq#toListMap时非常有用。

 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) 

Answer 2

虽然ListMap将保留插入顺序，但效率不高 – 例如查找时间是线性的。 我build议你创build一个新的集合类，它包装了immutable.HashMap和immutable.TreeMap 。 不可变映射应该参数化为immutable.HashMap[Key, (Value, Long)] ，其中元组中的Long给你指向TreeMap[Long, Key]相应条目的指针。 然后你在旁边保留一个进入柜台。 此树形图将根据插入顺序对条目进行sorting。

您可以直接实现插入和查找 – 增加计数器，插入散列映射并将其插入到树形映射中。 您使用哈希映射进行查找。

您可以使用树形图来实现迭代。

要实现remove，必须从哈希映射中删除键值对，并使用元组中的索引从树映射中删除相应的条目。