bucket-sort logo bucket-sort

プログラミングとインフラエンジニアリングの覚え書き

[C#] HashSet<T>の使い方

C# , .NET bucket-sort

HashSet<T> は、.NET のコレクションの中でも「重複を許さない集合」を扱いたいときに非常に便利なクラスです。List<T> は何でも順番に入れていける汎用的なコレクションですが、「同じものを二重に入れたくない」「この値が含まれているかを高速に調べたい」といった場面では、HashSet<T> の方が適しています。

一言で言えば、HashSet<T> は 重複なし・高速検索のためのコレクション です。

HashSetとは何か

まず、HashSet<T> の基本的な性質を整理すると次のようになります。

基本特徴

  • 同じ要素は1つしか入らない
  • 要素の順序は保証されない
  • 存在チェックが高速
  • 集合演算がしやすい

たとえば次のコードでは、2 を2回追加していますが、実際には1つしか保持されません。

var set = new HashSet<int>();

set.Add(1);
set.Add(2);
set.Add(2);

Console.WriteLine(set.Count); // 2

この「重複を自動的に排除してくれる」という性質が、HashSet<T> の最も分かりやすい特徴です。

何がうれしいのか

HashSet<T> が役に立つのは、単に重複を防ぎたいときだけではありません。もう一つ大きいのが、存在チェックが速いことです。

if (set.Contains(1))
{
    // 存在する
}

List<T> でも Contains は使えますが、内部的には先頭から順番に探すため、要素数が増えるほど時間がかかります。一方 HashSet<T> はハッシュテーブルを使っているため、平均的には O(1) に近いコストで存在チェックできます。

つまり、

  • 「重複を入れたくない」
  • 「含まれているかを何度も調べたい」

という2つの条件が揃ったとき、HashSet<T> はかなり強力です。

Listとの違い

使い分けを考えるうえで、List<T> との違いははっきり押さえておいた方がよいです。

項目 HashSet List
重複 不可 可
検索 高速 遅め
順序 保証なし 保証あり
インデックスアクセス なし あり

この表から分かる通り、HashSet<T> は「順番」や「添字」を扱うコレクションではありません。 その代わり、「集合であること」そのものに価値があります。

向いている用途

  • 重複排除
  • 高速な存在チェック
  • 集合演算

向いていない用途

  • 表示順を維持したい
  • n番目の要素を取りたい
  • 登録順に意味がある

内部構造が速さの理由

HashSet<T> が高速なのは、内部で ハッシュテーブル を使っているからです。

イメージとしては、

値 → ハッシュ関数 → バケット

という形です。

たとえば "apple" と "banana" に対してハッシュ値を計算し、それぞれ対応する場所に格納します。こうすることで、「ある値が存在するか」を調べるときに、すべてを順に比較するのではなく、候補となる場所に直接近い形でアクセスできます。

もちろん、ハッシュ衝突といって別の値が同じバケットに入ることはありますが、その場合も内部で適切に処理されます。

よく使う操作

基本操作は非常にシンプルです。

追加

set.Add(10);

Add は bool を返します。

  • true → 新しく追加された
  • false → すでに存在していた

この戻り値は意外と便利で、「初めて見た値だけ処理する」といったコードが書きやすくなります。

削除

set.Remove(10);

クリア

set.Clear();

存在確認

if (set.Contains(10))
{
    // ある
}

集合演算がとても強い

HashSet<T> の魅力は、単なる「重複なしコレクション」で終わらないところです。集合演算が直接サポートされているため、数学やSQLの集合操作に近い感覚で扱えます。

和集合

setA.UnionWith(setB);

積集合

setA.IntersectWith(setB);

差集合

setA.ExceptWith(setB);

対称差

setA.SymmetricExceptWith(setB);

このあたりは List<T> でもLINQで書けますが、HashSet<T> は最初から「集合」として設計されているため、意図がそのまま表現できます。

実務で重要：Equals と GetHashCode

HashSet<T> を使うとき、実務で一番大事なのはここです。 要素の「同じ／違う」は、Equals と GetHashCode で決まります。

たとえば次のようなクラスを考えます。

class Person
{
    public string Name { get; set; }
}

この状態で、

set.Add(new Person { Name = "A" });
set.Add(new Person { Name = "A" });

とすると、普通は両方入ります。 なぜなら、別インスタンスであり、既定の比較では「別物」とみなされるからです。

つまり、HashSet<T> で「同じ人なら1件にしたい」と考えるなら、

  • Equals / GetHashCode をオーバーライドする
  • IEqualityComparer<T> を渡す

といった対応が必要になります。

var set = new HashSet<Person>(new PersonComparer());

この部分を理解していないと、「HashSetなのに重複が入った」と感じやすいので注意が必要です。

注意点

順序は保証されない

HashSet<T> は集合なので、順番を前提にしてはいけません。

foreach (var item in set)
{
    // 順番は不定
}

「今はたまたまこの順で出ている」ということはあっても、それに依存するコードは避けるべきです。

スレッドセーフではない

複数スレッドから同時に更新する用途には、そのままでは向きません。必要ならロックなどの排他制御が要ります。

典型的な使いどころ

HashSet<T> は、意外といろいろなところで役に立ちます。

よくある用途

  • 重複排除
  • visited管理
  • 許可一覧／禁止一覧
  • 集合計算
  • 高速な会員チェックやID存在確認

たとえばグラフ探索や再帰処理で「訪問済みノード」を管理するのは定番です。

if (visited.Contains(node))
{
    return;
}
visited.Add(node);

まとめ

HashSet<T> は、重複を許さず、高速な存在チェックができる集合コレクションです。List<T> と比べると順序や添字は扱えませんが、その代わり「集合」としての性質に特化しています。

特に重要なのは次の3点です。

押さえておきたいポイント

  • 重複排除と存在チェックに強い
  • 順序を持たない
  • 比較の基準は Equals と GetHashCode

「順番はいらないが、含まれているかは素早く知りたい」という場面では、まず HashSet<T> を検討するとよいと思います。

Related Posts