Implementazione di Scala Scala immutabile che conserva l'ordine di inserimento

Question

LinkedHashMap viene utilizzato per conservare l'ordine di inserimento nella mappa, ma funziona solo per mappe mutabili. Qual è l'implementazione immutabile Map che conserva l'ordine di inserimento?

Answer 1

ListMap implementa una mappa immutabile utilizzando una struttura di dati basata su elenchi e quindi conserva l'ordine di inserimento.

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) 

Il seguente metodo di estensione - Seq#toListMap può essere molto utile quando si lavora 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

Mentre ListMap conserveranno ordine di inserimento, non è molto efficiente - esempio il tempo di ricerca è lineare. Ti suggerisco di creare una nuova classe di raccolta che comprenda sia lo immutable.HashMap sia lo immutable.TreeMap. La mappa immutabile deve essere parametrizzata come immutable.HashMap[Key, (Value, Long)], dove lo Long nella tupla fornisce il puntatore alla voce corrispondente nello TreeMap[Long, Key]. Quindi tieni un contatore di entrata sul lato. Questa mappa albero ordinerà le voci in base all'ordine di inserimento.

Si implementa l'inserimento e la ricerca in modo diretto - incrementare il contatore, inserire nella mappa hash e inserire la coppia di chiavi in ​​chiave nella mappa dei tre. Si utilizza la mappa hash per la ricerca.

Si implementa l'iterazione utilizzando la mappa ad albero.

Per implementare la rimozione, è necessario rimuovere la coppia chiave-valore dalla mappa hash e utilizzare l'indice dalla tupla per rimuovere la voce corrispondente dalla mappa dell'albero.