삽입 순서를 유지하는 불규칙 스칼라 맵 구현

Question

LinkedHashMap은 삽입 순서를지도에 유지하는 데 사용되지만 변경 가능한지도에서만 작동합니다. 게재 신청서를 유지하는 불변의 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) 

다음 확장 메서드

- ListMap의 작업을 할 때 Seq#toListMap은 매우 유용 할 수 있습니다.

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]에있는 해당 항목에 대한 포인터를 제공합니다. 그런 다음 옆에 진입 카운터를 두십시오. 이 트리 맵은 게재 신청서에 따라 항목을 정렬합니다.

삽입 및 조회는 간단한 방법으로 구현합니다. 즉, 카운터를 증가시키고, 해시 맵에 삽입하고 카운터 키 쌍을 트리 맵에 삽입합니다. 검색을 위해 해시 맵을 사용합니다.

트리 맵을 사용하여 반복을 구현합니다.

제거를 구현하려면 해시 맵에서 키 - 값 쌍을 제거하고 튜플의 인덱스를 사용하여 트리 맵에서 해당 항목을 제거해야합니다.