実行できるC#ドキュメント: HashSet

Q: C#のHashSetとは何ですか？

HashSet は、順序の定まっていない一意な要素のコレクションです。すでにある要素を追加しても何も起きず、Contains は集合がどれだけ大きくてもほぼ定数時間で答えます。要素が Dictionary のキーと同じくハッシュコードで保存されているからです。

Q: HashSet.Addは何を返しますか？

Add は、要素が追加されたときに true、すでに集合にあったときに false を返します。そのため if (!seen.Add(x)) は1行の重複チェックになります。1回の呼び出しで、新しい要素を追加し、繰り返し現れた要素を教えてくれます。

Q: C#のListから重複を取り除くには？

list.Distinct().ToList() は重複のない新しいリストを返し、各要素の最初の出現を元の順序で残します。new HashSet (list) でも重複は取り除けますが、集合には保証された順序がありません。その場で重複を取り除くには var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x)); を使います。

Q: ListではなくHashSetを使うべきなのはどんなときですか？

主に「この要素はコレクションにあるか」を尋ねる場合や、要素が一意である必要がある場合は HashSet を使います。List .Contains はすべての要素を走査するのでリストが大きくなるほど遅くなりますが、HashSet .Contains は遅くなりません。順序、重複、インデックスによるアクセスが重要なら List を使います。

Q: HashSetに重複したオブジェクトが入ってしまうのはなぜですか？

クラスが Equals と GetHashCode をオーバーライドしていないので、集合が参照を比較し、フィールドの値が同じ2つのオブジェクトを別物とみなすからです。両方のメソッドを（必ずセットで）オーバーライドするか、集合のコンストラクターに IEqualityComparer を渡します。

HashSet<T> は、どの要素も最大1回しか現れないコレクションです。インデックスも保証された順序もありませんが、その代わりに、所属しているかどうかをほぼ定数時間で確認できます。100万個の中から1つのタグを見つけるのに、10個の中から見つけるのとほぼ同じ時間しかかかりません。

要素の追加：Addはboolを返す

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

出力：

True
False
3
True
True
False
2

重複の追加はエラーではありません。Add は単に false を返し、集合は変わりません。この戻り値こそ、このメソッドで最も役に立つ点です。「これを見たことがあるか」と「覚えておく」を1回の呼び出しにまとめられます。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

出力：

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Containsが速い理由

List<T>.Contains は値を各要素と順に比較するので、コストはリストの大きさに比例して増えます。HashSet<T> は要素のハッシュコードを計算し、そのコードのバケットに移動して、そこに保存されている少数の要素とだけ比較します。ループの中での所属判定なら、O(n)の処理がO(1)になり、2つのリストに対する二重ループが1回の走査になります。

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

集合を作るにはリストを1回走査するコストがかかるので、得になるのは、数回を超えて検索する場合だけです。

リストから重複を取り除く

よく使われる方法は3つあり、順序がどうなるかが異なります。

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

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

出力：

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

リストとして結果が欲しいなら、Distinct が標準的な選択です。その場で取り除く版が動くのは、RemoveAll が要素ごとに順に述語を1回呼ぶからです。2つ目以降のコピーでは seen.Add が false を返すので、ちょうどそれらが削除されます。

集合演算：和、積、差

HashSet<T> には集合論の演算があります。...With メソッドは呼び出された集合そのものを変更し、何も返しません。

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

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

出力：

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

引数は、配列、リスト、別の集合など、任意の IEnumerable<T> にできます。SetEquals は引数の順序と重複を無視します。集合の列挙順序は当てにすべきものではないので、Show ヘルパーは表示の前に並べ替えています。

LINQ には、新しいシーケンスを返して入力には触れない対応するメソッドがあります：monday.Union(tuesday)、monday.Intersect(tuesday)、monday.Except(tuesday)。集合を変更したくない場合や、入力がリストの場合はこちらを使います。

自分で作ったクラスの独自の等価性

集合は GetHashCode と Equals で「同じ要素」かどうかを決めます。それらをオーバーライドしていないクラスでは、どちらもオブジェクトの同一性に基づくので、フィールドが等しい2つのオブジェクトは2つの別々の要素になります。

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

出力：

2
1
True

ルール：Equals で等しいオブジェクトは、同じ GetHashCode を返さなければなりません。Equals だけをオーバーライドすると、集合は間違ったバケットを探し、重複を報告し続けます。.NET Core 2.1以降では、HashCode.Combine(X, Y) を使えば、手書きの計算なしで良いハッシュコードを作れます。

クラスを変更できない場合や、ある集合でだけ別の「同じ」の基準が必要な場合は、コンストラクターに IEqualityComparer<T> を渡します。文字列には既製の比較子があります。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

出力：

True
False
2

C# 9以降では、record が値に基づく Equals と GetHashCode を生成してくれるので、record Point(int X, int Y); は追加のコードなしで集合に使えます。

オブジェクトが集合に入っている間は、GetHashCode の元になるフィールドを決して変更してはいけません。オブジェクトは古いハッシュのバケットに残るので、Contains と Remove がそれを見つけられなくなります。

順序とSortedSet

HashSet<T> の列挙順序は任意とみなすべきです。要素を並べ替えた状態で扱いたいなら、表示するときに並べ替える（set.OrderBy(x => x)）か、常に要素を順序どおりに保ち、1回の操作あたりO(log n)で Min、Max、範囲の問い合わせを提供する SortedSet<T> を使います。

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet、List、Dictionaryの比較

必要なこと	使うもの
一意な要素、高速な「含まれているか」	`HashSet<T>`
一意な要素、常にソート済み	`SortedSet<T>`
順序、重複、インデックスによるアクセス	`List<T>`
キーごとに値を保存する	`Dictionary<TKey, TValue>`

集合は、値のないキーだけの辞書です。所属を追跡するためだけに Dictionary<string, bool> を書いているなら、HashSet<string> のほうが同じことをより明確に表せます。

よくある間違い

順序を期待する。 集合には当てにできる順序がありません。並べ替えるか、SortedSet<T> を使います。
Equals と GetHashCode のない独自のクラス。 等しく見えるオブジェクトが別々の要素になります。
Equals だけをオーバーライドする。 必ず GetHashCode も一緒にオーバーライドします。
追加した後に要素を変更する。 集合がそれを見つけられなくなります。
集合にインデックスでアクセスする。 set[0] はコンパイルできません。インデックスはないので、位置が必要なら ToList() で変換します。

よくある質問

C#のHashSetとは何ですか？

HashSet<T> は、順序の定まっていない一意な要素のコレクションです。すでにある要素を追加しても何も起きず、Contains は集合がどれだけ大きくてもほぼ定数時間で答えます。要素が Dictionary のキーと同じくハッシュコードで保存されているからです。

HashSet.Addは何を返しますか？

Add は、要素が追加されたときに true、すでに集合にあったときに false を返します。そのため if (!seen.Add(x)) は1行の重複チェックになります。1回の呼び出しで、新しい要素を追加し、繰り返し現れた要素を教えてくれます。

C#のListから重複を取り除くには？

list.Distinct().ToList() は重複のない新しいリストを返し、各要素の最初の出現を元の順序で残します。new HashSet<T>(list) でも重複は取り除けますが、集合には保証された順序がありません。その場で重複を取り除くには var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x)); を使います。

ListではなくHashSetを使うべきなのはどんなときですか？

主に「この要素はコレクションにあるか」を尋ねる場合や、要素が一意である必要がある場合は HashSet<T> を使います。List<T>.Contains はすべての要素を走査するのでリストが大きくなるほど遅くなりますが、HashSet<T>.Contains は遅くなりません。順序、重複、インデックスによるアクセスが重要なら List<T> を使います。

HashSetに重複したオブジェクトが入ってしまうのはなぜですか？

クラスが Equals と GetHashCode をオーバーライドしていないので、集合が参照を比較し、フィールドの値が同じ2つのオブジェクトを別物とみなすからです。両方のメソッドを（必ずセットで）オーバーライドするか、集合のコンストラクターに IEqualityComparer<T> を渡します。