➡️
Mapの挿入順を保持する言語

2025/08/28に公開
 C#とDartの例Dart2.0ではMapの取り出す際の順序が挿入順と同じらしいです。挿入順を保持しないと勝手に思っていたので、これを知るまでDartで順番を確認する無駄なロジックを書いていたみたいです。
ただ、この勘違いは私だけではない気がしています。他のプログラミング言語に馴染みがある人は似たような経験があるのではないでしょうか。例えばC#のDictionaryはloopを回して取り出すと、必ずしも挿入時と同じ順番で返ってくるとは限りません。
using System;
using System.Collections.Generic;

public class DictionaryOrderExample
{
    public static void Main(string[] args)
    {
        var names = new Dictionary<string, string>();
        names.Add("A", "Alice");
        names.Add("B", "Bob");
		names.Remove("A");
        names.Add("C", "Charlie");
        Console.WriteLine(string.Join(" ", names.Values)); // "Charlie Bob"
    }
}
なぜこのようなことが起きるかというと、内部ではhash tableをデータ構造として使っているからです。本来はFIFOで挿入していきますが、Aliceを削除したので、もともとAliceがあったエントリーを初期化します。Charlieが追加されるときは一番最初に初期化されたAliceのエントリーに上書きされます。このような挙動をするため、C#のDictionaryは挿入時の順番を保証していないと言えます。
.NET9から追加されたGenericのOrderedDictionaryを利用すると、挿入時の順番を保持してくれます。Dictionaryのhash tableに加え、順番を記録するキーを配列で保存しているため、上記のようなことは発生しません。ただ、データの挿入・削除をする際にhash tableとキーの両方を操作する必要があり、場合によっては時間・空間パフォーマンスがリニアに増える弱点があります。
話をDartに戻します。DartのMapでは、全く同じ実装をしても上記のような問題は発生しません。
void main() {
  Map<String, String> names = {
    'A': 'Alice',
    'B': 'Bob',
  };
  
  names.remove('A');
  names['C'] = 'Charlie';
  
  names.forEach((key, value) {
    print(value); // "Bob Charlie"
  });
}
Dart2.0以降のMapは内部的にはLinkedHashMapを実装しています。キーバーリューのマッピングをhash tableで実装している点はC#のOrderedDictionaryと似ていますが、インデックスをするデータ構造が配列ではなくDoubly Linked Listで実装されているのが違います。上記のケースだと、エントリーが削除されるときに前後のノードからも消された状態で初期化され、次に追加するキーを最後尾に追加することで挿入順の確約を実現できているみたいです。
空間パフォーマンス的には全てのノードでポインターを2つ使う点を考えると、C#のDictionaryと比べ見劣りします。線形に増えていくのでデータの規模が大きくなると悪化しますが、後述するようにDartのユースケースでは大した差は生まれないのかな、位に思っています。

 他の言語と比べてみる調べてみると、ビルトインでよく使われるMapなりdictionaryが挿入時の順番を守るかどうかはかなり分かれるみたいです。（注意：私は以下のすべての言語を使っているわけではないので、間違ってたらすいません）
順番を確約
python3
javascript/typescript
swift (keyvaluepair)
ruby
dart
順番が確約されていない
c#
java/kotlin
golang
c++
rust
これらを見ると、スクリプト言語やGUIと相性の良い言語は順番を確約し、システム言語やトラフィックの多いバックエンドに使われる言語は順番を確約しない傾向がありそうです。個人的に興味深いと思ったのは”新しい”言語が必ずしもどちらかに寄るわけではなくて、例えば比較的新しいdartは順番を確約しつつrustは順番を確約しません。golangに至っては取り出す順番をわざとランダムにしているらしいです。
それぞれの特徴を比較して、上記のような言語設計・データ構造がその言語のユースケースを生むかを決めていそうだと思いました。先ほど「◯◯のような言語は順番を確約する/しない」と言いましたが、実は「順番を確約する/しないから、この言語はこのようなユースケースが多い」のほうが正しい因果関係じゃないか、と言いたいです。
挿入時の順番を揃えてくれるのは開発者としては仕事がしやすくて嬉しいですが、キーのコリジョンが起きるような入力を多数されると挿入・取り出しの最悪時間がO(n)まで下がります。トラフィックの多いシステムではMapが大きくなった場合コリジョンが起きやすくなりますし、わざとパフォーマンスを落とす入力を仕掛けてくるものがいるかもしれません。小さな個人開発程度でしたらほとんど気づかないレベルですが、エンタープライス開発ではリスクになり得ます。
golangではキーをわざとランダムにしたり、javaはキーをツリー化することで挿入・取り出しのパフォーマンスを下げない工夫をしているらしいです。このような言語がバックエンド開発で好まれるのはよくわかります。
その点GUIではあまり大きいデータを扱うことはなさそうですし、ほとんどの場合人類が感知できないレベルのレイテンシーは気にしません。逆にmapが挿入順で保持されているとかえって嬉しい事がよくあります。例えばフォーム入力などメールアドレス→パスワードなど知覚的に正しい順序というのがあり、同時にキーバリューペアで保存したい場合はデフォルトのmapが挿入順で保持されていたほうが操作がしやすいです。なので、順番を保持する言語はGUIを触る言語に好まれやすい気がします。
スクリプト言語に関しては、短い開発時間・短い行数で早く実行したい場合においては、もし順番が保持されていないとわざわざ別のデータ構造を用意して挿入順を記録したりする手間が増えて不便です。こちらもやはり、順番を確約するような言語設計に軍配が上がります。
パフォーマンスと利便性というのは当然トレードオフなのですが、言語によってそのトレードオフがどのようにして現れるのかきっぱり分かれるのが面白いです。もちろんこのカテゴリに当てはまらない言語もあってツッコまれそうな気もしますが、私が観測できる限りで面白い結論を作りたいと思ったのでそういう結論を作ってみました。
C#とDartの例

他の言語と比べてみる

Discussion
