【Dart】Mapの順番（HashMap, LinkedHashMap, SplayTreeMap）

様々な言語によくあるハッシュマップでは順番の概念がなく、その一方で、PHP（連想配列）など一部の言語の実装では順番があったりします。 言語を切り替えて開発したりしばらく使わなかったりすると混乱する部分です。

Dart の Map についてはどうなっているのか知らなかったので調べてみました。

いきなり結論

• Map　順番あり
• LinkedHashMap　順番あり
• HashMap　順番なし
• SplayTreeMap　順番あり（追加順ではなくキーの順）

Map は基本的に LinkedHashMap と同じになるようです。
参考にしたのは次の情報です。

Does dart automatically determine which map type to use? - Stack Overflow

If you navigate to our docs:

• https://api.dartlang.org/dev
• dart:core (https://api.dartlang.org/dev/dart-core/dart-core-library.html)
• Map (https://api.dartlang.org/dev/dart-core/Map-class.html)

You'll see the following description:

Maps, and their keys and values, can be iterated. The order of iteration is defined by the individual type of map.

And for the default constructor (the one used for {} syntax, as well):

Creates a LinkedHashMap instance that contains all key/value pairs of other.

検証

Map

void main() {
  final Map m = {
    3: 'orange',
    2: 'apple',
    1: 'banana'
  };

  m.forEach((k, v) => print('$k: $v'));
}

3: orange
2: apple
1: banana

記述したとおりの順番になっています。

LinkedHashMap

dart:collection のインポートが必要です。

import 'dart:collection';

void main() {
  final m = LinkedHashMap();
// final m = Map();  // これに変えても同じ結果になる
  m[3] = 'orange';
  m[2] = 'apple';
  m[1] = 'banana';

  m.forEach((k, v) => print('$k: $v'));
}

3: orange
2: apple
1: banana

追加順のままになりました。

HashMap

dart:collection のインポートが必要です。

import 'dart:collection';

void main() {
  final m = HashMap();
  m[3] = 'orange';
  m[2] = 'apple';
  m[1] = 'banana';

  m.forEach((k, v) => print('$k: $v'));
}

1: banana
2: apple
3: orange

任意の順番になりました（たまたまキーの順番に並んでいますが、常にそうなるとは限らないはずです）。
他の言語でよくあるハッシュマップと同じですね。

SplayTreeMap

四種類の中で SplayTreeMap は一番わかりにくいと思います。
探した情報の中では次の解説が明解でした。

What are the differences between the different Map implementations in Dart? - Stack Overflow

A splay tree is a good choice for data that is stored and accessed frequently, like caches. The reason is that they use tree rotations to bring up an element to the root for better frequent accesses. The performance comes from the self-optimization of the tree. That is, frequently accessed elements are moved nearer to the top. If however, the tree is equally often accessed all around, then there's little point of using a splay tree map.

頻繁にアクセスする要素を木構造のルートのほうに寄せる最適化をしてくれるので、要素のアクセス頻度に偏りがある用途ではこれを使うと効率が良さそうです。
そうでない場合にはメリットが少ないようです。

追記（2020-1-30）

SplayTreeMap にはもう一つ大事な特徴があることがわかりました。

Dart/Flutter Map, HashMap Tutorial with Examples - BezKoder

SplayTreeMap iterates the keys in sorted order.

キーの順にイテレートしてくれるとのことです。
これは活用できそうな機能ですね。

試してみると、キーと無関係な順序（3, 2, 1）で要素を追加しても、イテレーションは確かにキーの順になりました（1, 2, 3）。

import 'dart:collection';

void main() {
  final m = SplayTreeMap();
  m[3] = 'orange';
  m[2] = 'apple';
  m[1] = 'banana';

  m.forEach((k, v) => print('$k: $v'));
}

1: banana
2: apple
3: orange

公式ドキュメント にも順序のことが書かれていますが、アクセス頻度によってツリー内の最適な位置に配置される件と混同していました。
読み直すと、順序や同一性判定のための比較関数をコンストラクタに渡せる旨も書かれていました。

Keys of the map are compared using the compare function passed in the constructor, both for ordering and for equality.

パフォーマンスについては、先ほどの Stack Overflow ではどの操作も O(log n) の計算量で済むことが説明されていて、この情報が正しければ効率はなかなか良いと言えます。

It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time.