ScalaのListMapは挿入順序を保持しない

はじめに

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)
の箇所で処理結果を末尾に追加しているため順序がずれているようです。

参考記事
https://www.techscore.com/blog/2015/06/15/scala_mutable_listmap/

immutableなListMap

あとで書く
（現状自分のレベル低くて追えなかった・・・w）