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

Question

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在使用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)

Answer 2

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

您可以直接的方式实现插入和查找 - 递增计数器,插入哈希映射并插入到树形图中的计数器密钥对.您使用哈希映射进行查找.

您可以使用树映射来实现迭代.

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