Zenn
🎃

【C#データ構造】C#の集合とは？HashSetとSortedSetについて解説

2024/11/06に公開
C#
set
tech

初めに

C#のSetとは集合を表します。大きくHashSetとSortedSetがあるのでこれらについて説明を行います．

HashSet

  • 特性: HashSetはハッシュベースのアルゴリズムを用いており、要素の順序を保持しません。そのため、要素を挿入する順序や、HashSetを列挙する順序に一貫性はありません。
  • パフォーマンス: 要素の追加、削除、検索が平均的にO(1)の時間で実行されるため、頻繁な検索や挿入操作に最適です。
  • 使用シーン: 大量のデータから重複の排除や、高速な検索を行いたい場合に適しています。

SortedSet

  • 特性: SortedSetはソートされた順序を保持するため、要素が常に昇順で並びます。IComparerインターフェースを実装することで独自のソート基準を設定することも可能です。
  • パフォーマンス: 内部で二分木を使用しており、要素の追加、削除、検索はO(log n)の時間がかかります。要素の順序を考慮する必要がある場合に適しています。
  • 使用シーン: ソート済みの一意なコレクションが必要な場合や、最小・最大要素へのアクセスが必要な場合に適しています。

具体例

次に、それぞれの特性を示す具体例を挙げます。

HashSet の例

csharp
コードをコピーする
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        HashSet<int> hashSet = new HashSet<int>();
        hashSet.Add(3);
        hashSet.Add(1);
        hashSet.Add(4);
        hashSet.Add(1); // 重複要素、追加されない
        hashSet.Add(2);

        Console.WriteLine("HashSet の内容:");
        foreach (int item in hashSet)
        {
            Console.WriteLine(item); // 順序は保証されない
        }
    }
}

SortedSet の例

csharp
コードをコピーする
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        SortedSet<int> sortedSet = new SortedSet<int>();
        sortedSet.Add(3);
        sortedSet.Add(1);
        sortedSet.Add(4);
        sortedSet.Add(1); // 重複要素、追加されない
        sortedSet.Add(2);

        Console.WriteLine("SortedSet の内容:");
        foreach (int item in sortedSet)
        {
            Console.WriteLine(item); // 常に昇順で表示される
        }
    }
}

出力結果

HashSetの場合:

コードをコピーする
HashSet の内容:
3
1
4
2

（順序は保証されません）

SortedSetの場合:

コードをコピーする
SortedSet の内容:
1
2
3
4

（昇順で並び替えられています）

まとめ

  • 要素の順序を気にしない場合や高速な操作を求める場合はHashSetを使用。
  • 常にソートされた順序が必要な場合はSortedSetを使用。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

Discussion