Implémentation Scala Map immuable qui préserve l'ordre d'insertion

Question

Je sais que LinkedHashMap est utilisé pour préserver l'ordre d'insertion dans la carte, mais cela ne fonctionne que pour les cartes mutables. Quelle est l'implémentation immuable de Map qui préserve l'ordre d'insertion?

Merci

Answer 1

ListMap implémente une carte immuable à l'aide d'une structure de données basée sur une liste et préserve ainsi l'ordre d'insertion.

 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)
 

La méthode d'extension suivante - Seq#toListMap peut être très utile lorsque vous travaillez avec 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

Alors qu' ListMap permettra de préserver l'ordre d'insertion, il n'est pas très efficace - par exemple la recherche du temps est linéaire. Je vous suggère de créer une nouvelle classe de collection qui englobe à la fois l' immutable.HashMap et de la immutable.TreeMap. Les lois immuables de la carte doivent être paramétrés en tant que immutable.HashMap[Key, (Value, Long)], où l' Long dans le tuple vous donne le pointeur sur l'entrée correspondante dans l' TreeMap[Long, Key]. Ensuite, vous gardez une entrée de compteur sur le côté. Cet arbre de la carte va trier les entrées, selon l'ordre d'insertion.

Vous mettre en œuvre l'insertion et de la recherche dans la façon simple - incrémenter le compteur, l'insérer dans le hachage de la carte et insérez-la dans la contre-paire de clés dans le treemap. Vous utilisez la carte de hachage pour la recherche.

Vous mettre en œuvre par itération à l'aide de l'arborescence de la carte.

Pour mettre en œuvre les supprimer, vous devez supprimer la paire clé-valeur de hachage de la carte et utiliser l'index à partir de la n-uplet pour supprimer l'entrée correspondante dans l'arborescence de la carte.