Implementación inamovible de Scala Map que conserva el orden de inserción

Question

LinkedHashMap se utiliza para conservar el orden de inserción en el mapa, pero esto solo funciona para mapas mutables. ¿Cuál es la implementación inmutable de Map que preserva el orden de inserción?

Answer 1

ListMap implementa un mapa inmutable utilizando una estructura de datos basada en listas, y así conserva el orden de inserción.

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) 

El siguiente método de extensión - Seq#toListMap pueden ser muy útiles cuando se trabaja con 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

Mientras ListMap se preservar el orden de inserción, no es muy eficiente - por ejemplo, el tiempo de búsqueda es lineal. Le sugiero que cree una nueva clase de colección que incluya tanto el immutable.HashMap como el immutable.TreeMap. El mapa inmutable debe parametrizarse como immutable.HashMap[Key, (Value, Long)], donde Long en la tupla le proporciona el puntero a la entrada correspondiente en el TreeMap[Long, Key]. A continuación, mantenga un contador de entrada en el lateral. Este mapa de árbol ordenará las entradas de acuerdo con el orden de inserción.

Implementa la inserción y la búsqueda de la manera directa: incremente el contador, inserte en el mapa hash e inserte en el par de contra-teclas en el mapa de árbol. Utiliza el mapa hash para la búsqueda.

Implementa la iteración usando el mapa de árbol.

Para implementar eliminar, debe eliminar el par de clave-valor del mapa de hash y usar el índice de la tupla para eliminar la entrada correspondiente del mapa de árbol.