，保留插入顺序

Question

LinkedHashMap不可改变的Scala Map实现用于在地图保留插入顺序，但这只适用于可变地图。哪一个是不变的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可以ListMap s工作时是非常有用的。

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]相应的条目。然后你在旁边保留一个进入计数器。此树形图将根据插入顺序对条目进行排序。

您可以实现以直接的方式插入和查找 - 增加计数器，插入到哈希表，并插入到反密钥对成树状图。您使用哈希映射进行查找。

您可以通过使用树地图实现迭代。

要实现删除，你必须删除从哈希表的键值对，并使用该指数从数组中删除从树图的对应条目。