連載Index（読む順・公開済リンクが最新）: S00_門前の誓い_総合Index

List<T> のままでも動きます。
ただ、存在確認・キー検索・更新を何度も回す処理は、コレクション選択だけで待ち時間が大きく変わります。

今回の 10 万件実測では、次の使い分けがかなりはっきり出ました。

やりたいこと	第一候補
あるかどうかを何度も調べる	`HashSet<T>`
キーで検索・更新する	`Dictionary<TKey, TValue>`
順序を保ったまま全件を扱う	`List<T>`

この記事では、Contains・検索・更新を 10 万件で比較し、どの処理で差が大きく出やすいか を確認します。
単に最速を決めるというより、実務でどれを先に見るか を判断しやすくするための比較です。

これは、検索や判定を何度も回す場面での話です。
件数が少ない、検索が 1 回だけ、順序そのものが大事、といった場面では結論が変わります。

検証環境

.NET 8
WinForms
Windows 11 Pro 24H2
CPU: Intel(R) Core(TM) Ultra 7 265U 2.10 GHz
RAM: 32 GB
ストレージ: SSD
対象件数: 100,000
反復回数: 3 回

計測では、各処理の前に 1 回だけウォームアップを流し、その後の平均を結果に使っています。
また、反復ごとに GC.Collect() と GC.WaitForPendingFinalizers() を入れています。

今回の比較は、コレクションの理論差だけを切り出したものではありません。
サンプルアプリに入れた 7 つの処理を、そのまま計測しています。
そのため、参照表を先に作る処理と、追加や更新まで含めて計測する処理が並びます。
この表は単純な順位表というより、どの処理で差が出やすいかを見る表として読むと追いやすくなります。

今回の比較条件

項目	内容
件数	100,000
反復回数	3 回
ウォームアップ	各処理の計測前に 1 回
ランダム照会件数	`max(5000, count / 5)`
重複取り込みデータ	`x / 2` で同じ ID が 2 回ずつ出る
除外対象件数	`max(3000, count / 10)`
更新対象件数	`max(5000, count / 5)`
計測対象	参照表生成を含むものと含まないものがあるため、各項目の注記を基準に見る

10 万件時の件数に直すと、ランダム照会は 20,000 件、更新対象も 20,000 件、除外対象は 10,000 件です。

まず全体結果

7 つの処理を並べると、List<T> が厳しくなりやすい場面と、Dictionary<TKey, TValue> / HashSet<T> を先に見る場面がかなりはっきり出ます。

No	処理名	List(ms)	Dictionary(ms)	HashSet(ms)	最速
1	末尾の会員番号を何度も探す	644.646	0.468	0.459	`HashSet<T>`
2	ランダムなIDを照会する	2227.772	0.627	0.314	`HashSet<T>`
3	重複行を除いて取り込む	149.183	2.278	1.911	`HashSet<T>`
4	退会者IDを除外して残す	51.131	2.639	2.360	`HashSet<T>`
5	2つの名簿で共通IDを探す	378.833	0.401	0.415	`Dictionary<TKey, TValue>`
6	更新対象IDを探して書き換える	15955.585	8.027	12.322	`Dictionary<TKey, TValue>`
7	明細ごとに会員か判定する	324.819	0.952	0.908	`HashSet<T>`

この表は、常に最速の型を決めるためではなく、処理の種類ごとにどこで差が大きく出やすいかを見るための表です。
項目ごとに計測範囲が少し違うため、単純な横並び比較というより、業務処理に近い流れで読むと差を追いやすくなります。

特に差が大きかったのは No.6 の更新処理で、List<T> 15955.585ms に対して Dictionary<TKey, TValue> は 8.027ms でした。

検証に使ったアプリとコード一式はこちらです。
対象件数や反復回数を変えて、同じ比較を手元で試せます。

GitHub リポジトリ

先に押さえたい見方

この結果を最初に読むときは、次の 3 点だけ押さえると判断しやすくなります。

Contains を何度も回すなら HashSet<T> を先に見る
ID から値を引いて更新まで進むなら Dictionary<TKey, TValue> を先に見る
順序を保ったまま全件を扱う処理は List<T> が自然

このあと各項目で、どの処理でその差が出たかを順に見ていきます。

特に差が大きかった 3 件

1. 更新対象IDを探して書き換える

今回いちばん差が大きかったのはここでした。
List<T> は更新対象ごとに一覧走査が発生しやすく、件数が増えると一気に重くなります。
Dictionary<TKey, TValue> は ID から対象へそのまま届くため、更新まで短く進めます。

2. ランダムなIDを照会する

問い合わせ回数が増えると、一覧検索の差がそのまま積み上がります。
今回のサンプルでは int の ID を受けて int の値を照会しているため、Dictionary<TKey, TValue> と HashSet<T> の TryGetValue をそのまま比べられます。

この結果は、ID と値が同じ単純な照会として読むと分かりやすくなります。
会員 ID から会員オブジェクトを取る場面なら、先に見るのは Dictionary<TKey, TValue> です。

3. 末尾の会員番号を何度も探す

同じ一覧に対して Contains を何度も回すと、List<T> はかなり厳しくなります。
値本体が不要で、あるかどうかだけ見たいなら HashSet<T> を先に見ます。

サンプルデータ

更新や取得の例では、ID を持つ簡単なデータを使います。

using System;
using System.Collections.Generic;

public class Member
{
    public int Id { get; set; }

    public string Name { get; set; } = string.Empty;

    public int Point { get; set; }
}

public static class SampleData
{
    public static List<Member> CreateMembers(int count)
    {
        var members = new List<Member>(count);

        for (int i = 0; i < count; i++)
        {
            members.Add(new Member
            {
                Id = i,
                Name = $"member-{i}",
                Point = i % 100
            });
        }

        return members;
    }
}

また、ランダム照会とランダム更新では、同じ seed の乱数で問い合わせ一覧を作っています。

using System;

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

1. 末尾の会員番号を何度も探す

ログイン可否、権限判定、重複確認のように、あるかどうかを何度も見る場面です。
今回のコードでは、末尾の値 count - 1 を count 回確認しています。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
644.646	0.468	0.459	`HashSet<T>`

計測範囲: 参照表を作った後の存在確認

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var target = count - 1;
var list = source.ToList();

var found = false;

for (var i = 0; i < count; i++)
{
    found ^= list.Contains(target);
}

Console.WriteLine(found);

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var target = count - 1;
var hashSet = source.ToHashSet();

var found = false;

for (var i = 0; i < count; i++)
{
    found ^= hashSet.Contains(target);
}

Console.WriteLine(found);

見直し候補

Contains がループ内にある
同じ一覧に対して何度も存在確認している
値本体は使わず、あるかどうかだけ見ている

2. ランダムなIDを照会する

ランダムな ID を受け取り、その ID が指す値を照会する処理です。
今回のサンプルでは値が int なので、Dictionary<TKey, TValue> も HashSet<T> も TryGetValue で値を取り出せます。
ただし、これは ID と値が同じ単純な照会 の比較です。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
2227.772	0.627	0.314	`HashSet<T>`

計測範囲: 参照表を作った後の照会処理

`List<T>` の例

using System;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var queries = BuildRandomQueries(count, Math.Max(5000, count / 5));
var list = source.ToList();

var total = 0;

foreach (var q in queries)
{
    total += list.FirstOrDefault(x => x == q);
}

Console.WriteLine(total);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

`Dictionary<TKey, TValue>` の例

using System;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var queries = BuildRandomQueries(count, Math.Max(5000, count / 5));
var dictionary = source.ToDictionary(x => x, x => x);

var total = 0;

foreach (var q in queries)
{
    if (dictionary.TryGetValue(q, out var value))
    {
        total += value;
    }
}

Console.WriteLine(total);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

`HashSet<T>` の例

using System;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var queries = BuildRandomQueries(count, Math.Max(5000, count / 5));
var hashSet = source.ToHashSet();

var total = 0;

foreach (var q in queries)
{
    if (hashSet.TryGetValue(q, out var value))
    {
        total += value;
    }
}

Console.WriteLine(total);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

補足

この項目は、ID と値が同じ単純な照会を比べています。
そのため、HashSet<T> の TryGetValue がかなり強く出ています。

ただ、業務で多いのは「ID からオブジェクトを取りたい」処理です。
その場合は、最初に見る候補は Dictionary<TKey, TValue> です。

var members = SampleData.CreateMembers(100000);
var memberMap = members.ToDictionary(x => x.Id);

if (memberMap.TryGetValue(99999, out var member))
{
    Console.WriteLine(member.Name);
}

見直し候補

FirstOrDefault(x => x.Id == id) が繰り返し出る
SingleOrDefault や Where(...).FirstOrDefault() を毎回呼んでいる
ID で探した後に、そのまま値を使っている

3. 重複行を除いて取り込む

CSV 取り込みや ID 一覧の生成で、同じ値は 1 回だけ残したい場面です。
今回のコードでは x / 2 を使い、同じ ID が 2 回ずつ出る入力を作っています。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
149.183	2.278	1.911	`HashSet<T>`

計測範囲: 重複確認と追加を含む

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).Select(x => x / 2).ToArray();
var list = new List<int>();

foreach (var item in source)
{
    if (!list.Contains(item))
    {
        list.Add(item);
    }
}

Console.WriteLine(list.Count);

`Dictionary<TKey, TValue>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).Select(x => x / 2).ToArray();
var dictionary = new Dictionary<int, int>();

foreach (var item in source)
{
    dictionary.TryAdd(item, item);
}

Console.WriteLine(dictionary.Count);

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).Select(x => x / 2).ToArray();
var hashSet = new HashSet<int>();

foreach (var item in source)
{
    hashSet.Add(item);
}

Console.WriteLine(hashSet.Count);

見直し候補

追加前に毎回 Contains
重複確認と追加を手で書いている
一意な値だけ残れば足りる

4. 退会者IDを除外して残す

除外対象の ID 一覧を見ながら、残す側だけを新しい一覧へ積む処理です。
今回のコードでは、除外対象は固定範囲ではなく、乱数で作った問い合わせ一覧です。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
51.131	2.639	2.360	`HashSet<T>`

計測範囲: 除外対象一覧の準備と、残す側の生成を含む

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var removeTargets = BuildRandomQueries(count, Math.Max(3000, count / 10));
var removeTargetList = removeTargets.ToList();

var active = new List<int>(count);

foreach (var item in source)
{
    if (!removeTargetList.Contains(item))
    {
        active.Add(item);
    }
}

Console.WriteLine(active.Count);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var source = Enumerable.Range(0, count).ToArray();
var removeTargets = BuildRandomQueries(count, Math.Max(3000, count / 10));
var removeTargetHashSet = removeTargets.ToHashSet();

var active = new List<int>(count);

foreach (var item in source)
{
    if (!removeTargetHashSet.Contains(item))
    {
        active.Add(item);
    }
}

Console.WriteLine(active.Count);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

見直し候補

除外一覧が List<T> のまま
ループ中に !Contains(...)
除外対象の件数が多い

5. 2つの名簿で共通IDを探す

左右の一覧を見比べて、両方にある ID だけ拾う処理です。
今回のコードでは、左を 0..count-1、右を count / 2..count + count / 2 - 1 で作っています。
10 万件なら、共通部分は後半 5 万件です。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
378.833	0.401	0.415	`Dictionary<TKey, TValue>`

計測範囲: 共通判定のみ

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var leftIds = Enumerable.Range(0, count).ToArray();
var rightIds = Enumerable.Range(count / 2, count).ToList();

var hit = 0;

foreach (var item in leftIds)
{
    if (rightIds.Contains(item))
    {
        hit++;
    }
}

Console.WriteLine(hit);

`Dictionary<TKey, TValue>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var leftIds = Enumerable.Range(0, count).ToArray();
var rightMap = Enumerable.Range(count / 2, count).ToDictionary(x => x, x => x);

var hit = 0;

foreach (var item in leftIds)
{
    if (rightMap.ContainsKey(item))
    {
        hit++;
    }
}

Console.WriteLine(hit);

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var leftIds = Enumerable.Range(0, count).ToArray();
var rightSet = Enumerable.Range(count / 2, count).ToHashSet();

var hit = 0;

foreach (var item in leftIds)
{
    if (rightSet.Contains(item))
    {
        hit++;
    }
}

Console.WriteLine(hit);

補足

この場面は HashSet<T> でも十分速く、実務でもかなり有力です。
今回の実行では Dictionary<TKey, TValue> がわずかに先でしたが、差はかなり小さめでした。
値本体を後ろで使うなら Dictionary<TKey, TValue>、判定だけなら HashSet<T> と見ると迷いにくくなります。

6. 更新対象IDを探して書き換える

更新対象の ID を受け取り、該当データを見つけて値を書き換える処理です。
今回のコードでは、更新対象は連番ではなく、乱数で作った問い合わせ一覧です。
10 万件ではここが最も差が大きく、List<T> 15955.585ms に対して Dictionary<TKey, TValue> は 8.027ms でした。
この比較は、「更新要求が何度も飛んでくる場面」として読むと実務に重ねやすくなります。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
15955.585	8.027	12.322	`Dictionary<TKey, TValue>`

計測範囲: 参照表の準備と、対象探索と更新を含む

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var baseItems = Enumerable.Range(0, count)
    .Select(x => new MutableItem { Id = x, Score = x })
    .ToArray();

var updates = BuildRandomQueries(count, Math.Max(5000, count / 5));
var list = baseItems.Select(x => new MutableItem { Id = x.Id, Score = x.Score }).ToList();

foreach (var id in updates)
{
    var item = list.FirstOrDefault(x => x.Id == id);
    if (item != null)
    {
        item.Score++;
    }
}

Console.WriteLine(list.Count);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

public sealed class MutableItem : IEquatable<MutableItem>
{
    // 同値判定の基準は Id
    public int Id { get; set; }

    public int Score { get; set; }

    public bool Equals(MutableItem? other)
    {
        if (other == null)
        {
            return false;
        }

        return Id == other.Id;
    }

    public override bool Equals(object? obj)
    {
        return Equals(obj as MutableItem);
    }

    public override int GetHashCode()
    {
        return Id;
    }
}

`Dictionary<TKey, TValue>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var baseItems = Enumerable.Range(0, count)
    .Select(x => new MutableItem { Id = x, Score = x })
    .ToArray();

var updates = BuildRandomQueries(count, Math.Max(5000, count / 5));
var dictionary = baseItems.ToDictionary(x => x.Id, x => new MutableItem { Id = x.Id, Score = x.Score });

foreach (var id in updates)
{
    if (dictionary.TryGetValue(id, out var item))
    {
        item.Score++;
    }
}

Console.WriteLine(dictionary.Count);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

public sealed class MutableItem : IEquatable<MutableItem>
{
    // 同値判定の基準は Id
    public int Id { get; set; }

    public int Score { get; set; }

    public bool Equals(MutableItem? other)
    {
        if (other == null)
        {
            return false;
        }

        return Id == other.Id;
    }

    public override bool Equals(object? obj)
    {
        return Equals(obj as MutableItem);
    }

    public override int GetHashCode()
    {
        return Id;
    }
}

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var baseItems = Enumerable.Range(0, count)
    .Select(x => new MutableItem { Id = x, Score = x })
    .ToArray();

var updates = BuildRandomQueries(count, Math.Max(5000, count / 5));
var hashSet = new HashSet<MutableItem>(baseItems.Select(x => new MutableItem { Id = x.Id, Score = x.Score }));

foreach (var id in updates)
{
    if (hashSet.TryGetValue(new MutableItem { Id = id }, out var item))
    {
        item.Score++;
    }
}

Console.WriteLine(hashSet.Count);

static int[] BuildRandomQueries(int count, int queryCount)
{
    var random = new Random(12345);
    var queries = new int[queryCount];

    for (var i = 0; i < queryCount; i++)
    {
        queries[i] = random.Next(0, count);
    }

    return queries;
}

public sealed class MutableItem : IEquatable<MutableItem>
{
    // 同値判定の基準は Id
    public int Id { get; set; }

    public int Score { get; set; }

    public bool Equals(MutableItem? other)
    {
        if (other == null)
        {
            return false;
        }

        return Id == other.Id;
    }

    public override bool Equals(object? obj)
    {
        return Equals(obj as MutableItem);
    }

    public override int GetHashCode()
    {
        return Id;
    }
}

補足

HashSet<T> でも、同値判定を ID にして TryGetValue を使えば要素を引けます。
ただし今回の結果では、更新対象を引いて書き換える処理は Dictionary<TKey, TValue> が先でした。
値の取り出しと更新まで一続きで見るなら、まず Dictionary<TKey, TValue> を見た方が判断しやすくなります。

見直し候補

更新対象 ID ごとに一覧を探している
FirstOrDefault の直後に値を書き換えている
一括更新なのに参照表を持っていない

7. 明細ごとに会員か判定する

明細を 1 件ずつ見ながら、その ID が会員一覧にあるか確認する処理です。
今回のコードでは、会員一覧は 3 の倍数だけで作り、明細側は奇数番だけ count / 3 を足して当たり外れを入れています。
単純な連番比較より、前処理の判定に近いデータです。

実測結果

List(ms)	Dictionary(ms)	HashSet(ms)	最速
324.819	0.952	0.908	`HashSet<T>`

計測範囲: 判定のみ

`List<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var members = Enumerable.Range(0, count).Where(x => x % 3 == 0).ToArray();
var details = Enumerable.Range(0, count).Select(x => x + (x % 2 == 0 ? 0 : count / 3)).ToArray();
var memberList = members.ToList();

var matched = 0;

foreach (var detail in details)
{
    if (memberList.Contains(detail))
    {
        matched++;
    }
}

Console.WriteLine(matched);

`HashSet<T>` の例

using System;
using System.Collections.Generic;
using System.Linq;

var count = 100000;
var members = Enumerable.Range(0, count).Where(x => x % 3 == 0).ToArray();
var details = Enumerable.Range(0, count).Select(x => x + (x % 2 == 0 ? 0 : count / 3)).ToArray();
var memberHashSet = members.ToHashSet();

var matched = 0;

foreach (var detail in details)
{
    if (memberHashSet.Contains(detail))
    {
        matched++;
    }
}

Console.WriteLine(matched);

見直し候補

明細ごとに会員判定している
値本体は使わない
判定だけ通れば足りる

まず見直すならこの順番

迷った時は、まず「ループの中で毎回探していないか」から見ると見つけやすくなります。

ループ内の Contains
FirstOrDefault(x => x.Id == id) の繰り返し
追加前の重複確認
除外一覧が List<T> のまま残っている箇所
更新対象ごとに一覧検索している箇所

この順で見ると、List<T> のままで重くなりやすい箇所を拾いやすくなります。

この比較をそのまま当てはめにくい場面

今回の結果は、検索や判定を何度も行う場面で差が見えやすい比較です。
次のような場面では別の見方が要ります。

件数がかなり少ない
1 回しか検索しない
順番そのものが大事
Dictionary<TKey, TValue> や HashSet<T> の生成コストの方が重い
comparer の実装差が大きい
ソート済み一覧に対して二分探索を使える

サンプルコード

検証に使ったアプリとコード一式はこちらです。
対象件数と反復回数を変えて、同じ比較を試せます。

GitHub リポジトリ

公式ドキュメント

細かい API は Microsoft Learn にまとまっています。

まとめ

今回の 10 万件比較では、コレクション名だけで決めるより、処理の中で何を何回しているかを先に見る方が判断しやすいことがはっきり出ました。

特に差が出やすかったのは次の場面です。

Contains を何度も回す
ランダムな ID を受けて値を照会する
重複を除いて取り込む
除外一覧を見ながら残す側を作る
更新対象を ID で探してそのまま書き換える

この条件が見えたら、List<T> のままでよいかを一度見直す価値があります。
判定だけなら HashSet<T>、ID から値を取って更新まで進むなら Dictionary<TKey, TValue> を先に見ると判断しやすくなります。

連載Index（読む順・公開済リンクが最新）: S00_門前の誓い_総合Index