C#コレクションの選び方：Dictionary・HashSet・FrozenDictionaryを実測

2026年11月改訂： この記事は2021年7月19日に韓国語で書いたものを、日本語向けに書き直したものです。元の記事は同じ月の「コレクション入門」と内容（ArrayList・Queue・Stack・Hashtable）がほぼ重なっていて、例のうち3つは .NET 10 でコンパイルできませんでした（2.3 f による error CS1003、Colsole の打ち間違いによる error CS0103）。そこでこの記事は範囲を変え、今使うべきコレクションからどれを選ぶかを扱います。旧式の4クラスとボックス化のコストは入門の記事へ、List<T> の内部構造は「Listの内部」へ移しました。

List<T> と Dictionary は使っているけれど、HashSet、SortedDictionary、PriorityQueue、FrozenDictionary、ImmutableArray をいつ選べばいいのか迷う人向けの記事です。先に結論を書くと、キーで引くなら Dictionary／HashSet、起動後に変わらないなら FrozenDictionary／FrozenSet、キー順がずっと必要なときだけ SortedDictionary です。文字列キー1万件で検索速度と構築コストを測り、この判断の裏付けにしました。

2021年版で直したところ

ArrayList・Queue・Stack の3つの例は、実数リテラルとサフィックスの間に空白があり、構文解析の段階で止まりました。

Program.cs(11,32): error CS1003: 構文エラーです。',' が必要です

2.3 f を 2.3f に直すと、今度は Console の打ち間違いが出てきます。

Program.cs(16,17): error CS0103: 現在のコンテキストに 'Colsole' という名前は存在しません
Program.cs(17,17): error CS0103: 現在のコンテキストに 'Colsole' という名前は存在しません

両方を直すと、コメントのとおりに動きました。ArrayList は 10 / 2.3 / 30 のあとに韓国語のあいさつ文字列2つ、Queue は 30 / 4.4 / ABC、Stack は ABC / 4.4 / 10 を出力しました。Hashtable の例はもともとコンパイルでき、キーを直接指定して3つの値を順に出力していました（列挙ではないので順番の問題はありません）。

本文の説明も3か所直します。

• 「C# が提供するすべてのコレクションはどんな型の変数でも入れられる」は、System.Collections の非ジェネリッククラスにしか当てはまりません。List<int> に文字列を入れると error CS1503 でコンパイルできません。
• 「ハッシュテーブルのキーにはどんな型でも使える」には条件があります。null はキーにできず（ArgumentNullException）、自作の型は Equals と GetHashCode を両方オーバーライドしないと、等しいキーが別物として扱われます。
• 最後の「ヘルプ」（C言語のスタック・ヒープ・データ領域）はテーマから外れるので削りました。そこでは「int i = 10; int array[i]; はコンパイラが処理できない」とありましたが、C99 以降は可変長配列としてコンパイルできます（clang -std=c99 で sizeof array は40）。C89 でコンパイルしたときだけ warning: variable length arrays are a C99 feature が出ます。
• 元記事のキュー・スタック・ハッシュテーブル・ボックス化の図4枚は、ほかの資料から持ってきたものに見えたため、著作権上の問題を避けて外しました。キューとスタックの動きは「コレクション入門」で実際の出力として示し、この記事の図はすべて自作です。

Dictionary と HashSet：まずはこれ

キーで値を引くなら Dictionary<TKey, TValue>、入っているかどうかだけ知りたいなら HashSet<T> が基本です。どちらもハッシュベースなので、件数が増えても検索時間はほぼ一定です。

HashSet<string> a = ["ios", "android", "web"];   // C# 12 のコレクション式
HashSet<string> b = ["web", "desktop"];
a.IntersectWith(b);
Console.WriteLine("HashSet Add dup -> " + b.Add("web") + ", intersect: " + string.Join(",", a));

HashSet Add dup -> False, intersect: web

HashSet.Add はすでにあれば例外ではなく false を返すので、「初めて見たものだけ処理する」という重複排除にそのまま使えます。IntersectWith、UnionWith、ExceptWith などの集合演算もあります。

気をつけたいのは列挙の順番です。Dictionary は追加するだけなら入れた順に列挙されるように見えますが、削除した場所は再利用されます。

var d = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2, ["c"] = 3 };
d.Remove("a"); d["d"] = 4;
Console.WriteLine(string.Join(",", d.Keys));

d,b,c

d が先頭に来ました。仕様上、順番は定義されていないので、順番が必要なら次の SortedDictionary を使うか、明示的に並べ替えます。

SortedDictionary・LinkedList・PriorityQueue

SortedDictionary<TKey, TValue> は、キーを常に並べた状態で持ちます（中身は平衡二分探索木）。

SortedDictionary: apple,fig,pear

pear、apple、fig の順に入れてもキー順で出てきます。代わりに、検索はハッシュより遅くなります（後の実測）。

LinkedList<T> は双方向連結リストで、手元にあるノード（LinkedListNode<T>）の前後への挿入・削除が定数時間です。値で探す Find は先頭からたどるので、ノードへの参照を持ち回る場面（LRU キャッシュの実装など）でなければ List<T> のほうが向いています。

var ll = new LinkedList<int>([1, 2, 4]);
ll.AddAfter(ll.Find(2)!, 3);   // 1,2,3,4

PriorityQueue<TElement, TPriority> は .NET 6 で追加されました。元記事を書いた2021年7月時点の最新だった .NET 5 にはありません。優先度の値が小さいものから出てきます。

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 5); pq.Enqueue("urgent", 1); pq.Enqueue("normal", 3);
while (pq.TryDequeue(out var job, out var pri)) Console.Write($"{job}({pri}) ");

urgent(1) normal(3) low(5) 

Microsoft Learn のドキュメントによると、優先度が同じ要素どうしの順番は保証されず、UnorderedItems で列挙しても優先度順にはなりません。ジョブのスケジューリングやダイクストラ法の最短経路のように、「次にいちばん急ぐもの」を繰り返し取り出す場面で使います。

FrozenDictionary・FrozenSet と ImmutableArray

FrozenDictionary／FrozenSet（.NET 8、System.Collections.Frozen）は作ったあと変更できない代わりに、作る時点でキーを分析して検索方法を選びます。できたオブジェクトの型を出してみると、キーの性質によって実装が変わることがわかります。

Frozen: 2 True LengthBucketsFrozenDictionary`1

キーが "ko"、"ja"、"en" のように短いと長さ別バケットの実装が、下の計測の user-000123-… のようなキーでは OrdinalStringFrozenDictionary_LeftJustifiedSubstring が選ばれました。キーの一部の文字だけをハッシュして時間を減らす方式です。インターフェース経由で Add を呼ぶと NotSupportedException になります。

ImmutableArray<T>（System.Collections.Immutable）は変更できない配列です。Add は元をそのまま残し、新しい配列を返します。

ImmutableArray<int> ia = [1, 2, 3];
var ib = ia.Add(4);   // ia = 1,2,3   ib = 1,2,3,4

ImmutableArray は構造体なので、default のままだと中の配列がありません。IsDefault が True になり、その状態で Length を読むと NullReferenceException が出ました。フィールドに持つときは [] か ImmutableArray<int>.Empty で初期化しておきます。

よく混同されるのが読み取り専用ラッパーです。

var src = new List<int> { 1, 2 };
IReadOnlyList<int> ro = src.AsReadOnly();
src.Add(3);
Console.WriteLine(ro.Count);   // 3

AsReadOnly() は元のリストをのぞく窓にすぎないので、元が変われば一緒に変わります。「受け取った側が書き換えられない」ならラッパーで足り、「誰も書き換えられない」なら Immutable か Frozen が必要です。

検索速度の実測：文字列キー1万件

user-000123-1a2b3c4d の形の文字列キー1万件を各コレクションに入れ、あらかじめランダムに選んでおいたキー500万個（すべて存在するキー）で検索しました。どの方式も同じ形のラムダ経由で呼んでいるので、呼び出しのオーバーヘッドは全行で同じです。.NET 10.0.14、Release ビルド、Apple Silicon Mac、ウォームアップ後3回計測した最後の値です。

Dictionary は実行ごとに18〜33nsの幅でぶれ、ほかは回ごとの差が小さめでした。読み取れることは3つです。

• Frozen は検索が約1.5倍速いが、構築は約8倍高い。 1万件で1.8msなので起動時に1回なら問題ありませんが、リクエストごとに作ると損をします。
• ImmutableDictionary は Dictionary の4倍以上遅かった。 中身が木構造だからです。少しずつ変えた版を複数持ちたいとき（スナップショットの共有）に使うもので、単に「変わらない表」なら FrozenDictionary が合っています。
• List.IndexOf は約11μsで、Dictionary の約500倍。 1万件を先頭から比べるためです。リストに対して Contains を繰り返しているコードは、真っ先に HashSet に変える候補です。

判断図：いつ何を使うか

旧式の ArrayList・Hashtable をこの表の型に移す手順は「コレクション入門」に、これらのコレクションを絞り込んだりまとめたりする方法は「LINQ入門」に続きます。

確認環境：.NET SDK 10.0.403 / ランタイム 10.0.14、C# 14（net10.0 の既定値）、macOS（Apple Silicon Mac）。C の例は Apple clang。