Niezmienna Scala Implementacja mapy, która zachowuje zamówienie reklamowe

Question

LinkedHashMap służy do zachowania kolejności reklamacji na mapie, ale działa to tylko w przypadku map zmiennych. Która z niezmiennych implementacji Map zachowuje porządek reklamowy?

Answer 1

ListMap implementuje niezmienną mapę przy użyciu struktury danych opartej na listach, a tym samym zachowuje zamówienie reklamowe.

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) 

następującą metodę rozszerzenia - Seq#toListMap może być bardzo przydatna podczas pracy z 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

Podczas ListMap zachowuje kolejność wstawiania nie jest bardzo skuteczny - np czas wyszukiwania jest liniowy. Proponuję utworzyć nową klasę kolekcji, która otoczy zarówno immutable.HashMap, jak i immutable.TreeMap. Niezmienna mapa powinna być sparametryzowana jako immutable.HashMap[Key, (Value, Long)], gdzie Long w krotce daje wskaźnik do odpowiedniego wpisu w TreeMap[Long, Key]. Następnie trzymasz licznik wpisów na boku. Ta mapa drzewa posortuje wpisy zgodnie ze zleceniem reklamowym.

Implementację wstawia się i przeszukuje w prosty sposób - zwiększa licznik, wstawia do mapy mieszania i wstawia do pary liczników w treemap. Do wyszukiwania używasz mapy mieszania.

Wykonujesz iterację za pomocą drzewa mapy.

Aby zaimplementować usunięcie, musisz usunąć parę klucz-wartość z mapy skrótu i ​​użyć indeksu z krotki, aby usunąć odpowiedni wpis z drzewa mapy.