Scala의 ListMap은 삽입 순서를 유지하지 않습니다.

8146 단어 컬렉션Scala

소개



ListMap(mutable인)은 이름적으로 순서를 보관 유지한 Map를 만들어 준다고 생각해 구현하고 있었습니다만,
사실은 아니었기 때문에 공부를 위해 구현을 쫓아보기로했습니다.
※ 아직 Scala 처음으로 일주일 정도이므로 잘못되어 있으면 죄송합니다.

결론



immutable ListMap은 삽입 순서를 유지하지만 mutable ListMap은 삽입 순서를 유지하지 않는다는 것을 배웠습니다.
import scala.collection.mutable

import collection.immutable.ListMap

object Untitled {
  def main(args: Array[String]) {
    val iListMap = ListMap[Int, String]()
    val iRes = iListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
    println("immutable:",iRes)

    val mListMap = mutable.ListMap[Int,String]()
    val mRes = mListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
    println("mutable",mRes)
  }
}

// output
//(immutable:,ListMap(1 -> 一郎, 2 -> 二郎, 3 -> 三郎, 4 -> 四郎))
//(mutable,Map(4 -> 四郎, 2 -> 二郎, 3 -> 三郎, 1 -> 一郎))

구현을 쫓아보기



mutable ListMap



updated 는 내부에서는 map() += map() 를 실시하고 있습니다.
그래서 mutable.ListMap의 다음 메소드에서 해독을 시작합니다.

+=


  def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this }

kv는 순차 map을 저장하고 A는 key를, B는 Value를 저장합니다.
elems는 remove의 결과를 포함합니다. (remove의 내용에 대해서는 아래에서 설명)
마지막으로 kv를 remove 결과의 시작 부분에 저장합니다.

remove


  @tailrec
  private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = {
    if (elems.isEmpty) acc
    else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail }
    else remove(key, elems.tail, elems.head :: acc)
  }

elems 는 선두 요소를 제외한 List 를 재귀적으로 받아, acc 에는 최종적인 처리 결과를 포함하고 있습니다.
remove if 에서 elems가 비어있을 때 acc를 반환

remove의 else if 의 처리에서는, 동일한 key를 가지는 원의 map의 요소를 없애고, 새로운 요소를 선두에 추가하고 있습니다.
예: map(1 -> "hoge") += map(1 -> "fuga") 는 map(1 -> "fuga")

재귀 적으로 호출하는 else remove의 부분에서, 처리 결과의 전에 선두 요소를 추가하고 있습니다.
@tailrec

실제로 디버그로 접었더니 다음과 같이 되었습니다.


remove(key, elems.tail, elems.head :: acc)의 개소에서 처리 결과를 말미에 추가하고 있기 때문에 순서가 어긋나 있는 것 같습니다.

참고 기사
htps //w w. chs 이것. 이 m/bぉg/2015/06/15/s ぁ_무타 bぇ_ぃst마 p/

immutable ListMap



나중에 쓰다
(현재 자신의 레벨 낮아서 쫓지 않았다···w)

좋은 웹페이지 즐겨찾기