List.Contains と HashSet.Containsってどのくらい性能差があるのか検証してみた

はじめに

とあるプロジェクトにて、とあるデータのコレクションをListで扱っていたのですが、
今後の性能を考えHashSetとして扱うか・・・コレクション順序をどうするか・・・
など設計を再検討する機会がありました。

実装上Containsを多用していたため、
List.Contains と HashSet.Containsってどのくらい性能差があるのか
を実際に検証してみることにしました。

前提として、メカニズムには以下の違いがあり、HashSetが高速です。

ListとHashSetのcontainsメソッドの速度差は、要素数によって異なりますが、一般的にはHashSetの方が高速です。
これは、HashSetがハッシュテーブルを使用しており、要素の検索に平均O(1)の時間がかかる一方で、Listの場合は要素を順番に比較する必要があり、平均O(n)の時間がかかるためです。

検証コード

※コレクション要素を全検索します。

Console.WriteLine("please enter the int number");
var count = int.Parse(Console.ReadLine());

var userList = CreateUserList(count);
Measure(() =>
{
    foreach (var user in userList)
    {
        userList.Contains(user);
    }
}, "List");

var userHash = CreateUserHash(count);
Measure(() =>
{
    foreach (var user in userHash)
    {
        userHash.Contains(user);
    }
}, "HaseSet");

return;

void Measure(Action action, string type)
{
    var sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    action();
    sw.Stop();
    Console.WriteLine($"{type}:{sw.ElapsedMilliseconds}msec");
}

IList<User> CreateUserList(int count)
{
    var users = new List<User>();
    for (var i = 1; i <= count; i++)
    {
        users.Add(new User(i));
    }
    return users;
}

HashSet<User> CreateUserHash(int count)
{
    var users = new HashSet<User>();
    for (var i = 1; i <= count; i++)
    {
        users.Add(new User(i));
    }
    return users;
}

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

    public User(int id)
    {
        Id = id;
    }
}

結果

please enter the int number
1000
List:2msec
HaseSet:0msec

please enter the int number
10000
List:81msec
HaseSet:1msec

please enter the int number
100000
List:2816msec
HaseSet:5msec

GitHub