はじめに

Scalaのお話です。
Mapで情報を管理しつつ、要素の挿入順序も保持したいという欲求にかられました。
２年ほど前に一度使ったな、確か要素の挿入順序を保持してくれたっけな、という曖昧な記憶のもとに可変ListMap（mutable.ListMap）を使いました。

mutable.ListMapのAPIリファレンスには

A simple mutable map backed by a list.

としか書かれてませんが、「ああ、内部実装はListなのね。じゃあ入れた順に並ぶんだね」と安直に考えてしまいました。
それが間違いの始まりでした。

可変ListMapに要素を入れてみる

現時点の最新のScala 2.11.6でやってみます。

まず、バージョン確認から。

最新になっています。
インスタンスを用意して、要素を２つほど入れます。要素の追加には「+=」を使います。

挿入順序の逆順になっています。さらに要素を入れていきます。

あれ？順序が乱れていますね。もうひとつ要素を入れてみます。

？？？
どういうことでしょう。

ソースを見てみよう

mutable.ListMapのソースを読んでみます。必要な箇所のみ抜粋します。

+= 関数は54行目です。
まず、要素を保持するmutable.Listであるelems（47行目）からキー（kv._1）に該当する要素を削除（remove）します。
次に、elemsの先頭にキーと値（kv）を追加します。

ここは問題なさそうです。最後に追加した要素が先頭にくるんですね。

では、次に remove 関数（60行目）を見てみます。
accumulator を使って処理結果を引き継いでいくというよくある実装です。
61行目：elemsが空の場合（つまり最後まで処理した場合）は、accumulator（それまでの処理結果）を返す。
62行目：elemsの先頭がキーに一致する場合、accumulator（それまでの処理結果）の後ろに、elemsの先頭を除いたものを追加して返す。
63行目：それ以外（elemsの先頭がキーに一致しない）場合、elemsの先頭を除いたものからキーを remove する。それまでの処理結果の前にelemsの先頭を追加したものを、ここまでの処理結果とする。

あ、63行目ですね。ここで順序が逆になっています。
「それまでの処理結果の前にelemsの先頭を追加したものを、ここまでの処理結果とする」ではなく、
「それまでの処理結果の後にelemsの先頭を追加したものを、ここまでの処理結果とする」であれば、挿入順序は保持されます。
つまり、

とすれば挿入順序は保持されるのですが、Listの最後尾に要素を追加するのはコストが高いので、このような実装になっているのでしょう。
「挿入順序は保持される」と仕様に書かれているわけではないですし．．．。

古いバージョンのScalaで試してみる

でもやっぱり気になります。昔は確か挿入順序が保持されていたような．．．。
どこかで実装が変更になったんでしょうか。githubの履歴を辿ってみると、ありました。

SI-6853 changed private method remove to be tail recursive.
Operations += and -= on mutable.ListMap rely on the private method remove to perform. This methods was implemented using recursion, but it was not tail recursive. When the ListMap got too big the += caused a StackOverflowError.

「removeは再帰関数だけど末尾再帰ではないので、大きなものを処理するとStackOverflowErrorになる」ので修正したとのことです。

Scala 2.10.1 以降で変更になっているようですので、その一つ前のバージョンのScala 2.9.3で試してみます。

こちらだと、逆順ですが挿入順序は保持されます。
ソースはここにあります。

+= 関数（47行目）は変わってないですが、remove 関数（50行目）の実装が変わっています。
確かにこの実装だと挿入順序が保持されますね。

おわりに

ライブラリの仕様を確認せずに思い込みで使っていたら、ライブラリのバージョンが上がったら挙動が変わっていて慌てました、というありがちなお話です。
mutable.ListMapは実装がシンプルだし、動作確認しても以前は大丈夫だったので、順序保証されると思い込んでしまいましたが、仕様にはそんなこと一言も書いてありません。
書いてあるのは、ただ「実装がListである」だけ。
仕様を読むときに「こうだったらいいな」という希望が「こうに違いない」という予断に変わり、誤った理解をしてしまったんだと反省します。

ライブラリの仕様を読むときは「ほんとにそう？」と疑ってかかりましょう。

おまけ

挿入順序を保持したい場合はmutable.LinkedHashMapを使うのがいいですね。
APIリファレンスには、

This class implements mutable maps using a hashtable. The iterator and all traversal methods of this class visit elements in the order they were inserted.

「挿入順序を保持する」とちゃんと書かれています。