【C#】HashSet完全ガイド｜内部構造・集合演算・IEqualityComparer・SortedSet・FrozenSet・スレッドセーフまで

// ① デフォルト初期化
var tags = new HashSet<string>();

// ② コレクション初期化子
var primes = new HashSet<int> { 2, 3, 5, 7, 11, 13 };

// ③ 既存コレクションから作成（重複は自動的に排除される）
var numbers = new[] { 1, 2, 2, 3, 3, 3, 4 };
var unique  = new HashSet<int>(numbers); // { 1, 2, 3, 4 }

// ④ 初期容量を指定（リサイズコストを抑制）
var largeSet = new HashSet<int>(capacity: 10_000);

// ⑤ EnsureCapacity（.NET 5+）— 必要な容量を予約
var cache = new HashSet<string>();
cache.EnsureCapacity(50_000);

// ⑥ TrimExcess — 余分な容量を切り詰める
cache.TrimExcess(); // 内部配列を実要素数に合わせて縮小

// ⑦ LINQ ToHashSet（.NET Core 2.0+ / .NET Standard 2.1+）
var fromLinq = Enumerable.Range(1, 100).ToHashSet();

var fruits = new HashSet<string>();

// ① Add: 戻り値 bool（追加できたか = 重複していなかったか）
bool added1 = fruits.Add("Apple");   // true
bool added2 = fruits.Add("Apple");   // false（重複は無視されて false）
bool added3 = fruits.Add("Banana");  // true

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

// ② Contains: O(1) の高速判定
bool hasApple = fruits.Contains("Apple");   // true
bool hasGrape = fruits.Contains("Grape");   // false

// ③ Remove: 戻り値 bool（削除できたか）
bool removed = fruits.Remove("Banana");     // true
bool removed2 = fruits.Remove("NotExist");  // false

// ④ TryGetValue（.NET Core 2.0+）— 「正規化された値」を取り出すパターン
// 大文字小文字を無視して保存している場合に元のケースを取得できる
var caseInsensitive = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { "Apple" };
if (caseInsensitive.TryGetValue("APPLE", out string? canonicalName))
    Console.WriteLine(canonicalName); // "Apple"（最初に追加された形）

// ⑤ Clear: 全要素削除
fruits.Clear();
Console.WriteLine(fruits.Count); // 0

// ⑥ RemoveWhere: 条件に合う要素を一括削除
var numbers = new HashSet<int> { 1, 2, 3, 4, 5, 6 };
int removedCount = numbers.RemoveWhere(n => n % 2 == 0);
Console.WriteLine(removedCount);  // 3（2,4,6 が削除）

var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };

// 元の集合を変更せずに演算するパターン → コピーを作る
var union        = new HashSet<int>(a); union.UnionWith(b);              // {1,2,3,4,5,6}
var intersection = new HashSet<int>(a); intersection.IntersectWith(b);   // {3,4}
var difference   = new HashSet<int>(a); difference.ExceptWith(b);        // {1,2}
var symDiff      = new HashSet<int>(a); symDiff.SymmetricExceptWith(b);  // {1,2,5,6}

// 引数は IEnumerable<T> でも受け付ける（HashSet 以外も渡せる）
var listB = new List<int> { 3, 4, 5, 6 };
var union2 = new HashSet<int>(a);
union2.UnionWith(listB); // OK

var subset    = new HashSet<int> { 1, 2 };
var full      = new HashSet<int> { 1, 2, 3, 4 };
var disjoint  = new HashSet<int> { 7, 8 };

// IsSubsetOf: subset が full に完全に含まれるか
Console.WriteLine(subset.IsSubsetOf(full));        // true

// IsProperSubsetOf: 真部分集合（subset != full かつ subset ⊂ full）
Console.WriteLine(subset.IsProperSubsetOf(full));  // true
Console.WriteLine(full.IsProperSubsetOf(full));    // false（同じ集合）

// IsSupersetOf: full が subset を完全に含むか
Console.WriteLine(full.IsSupersetOf(subset));      // true

// IsProperSupersetOf: 真上位集合
Console.WriteLine(full.IsProperSupersetOf(subset)); // true

// Overlaps: 1要素でも共通があるか（O(min(n,m)) で高速）
Console.WriteLine(full.Overlaps(subset));          // true
Console.WriteLine(full.Overlaps(disjoint));        // false

// SetEquals: 順序を無視して同じ集合か
var s1 = new HashSet<int> { 3, 1, 2 };
var s2 = new HashSet<int> { 1, 2, 3 };
Console.WriteLine(s1.SetEquals(s2));               // true

// デフォルト: 大文字小文字を区別する
var caseSensitive = new HashSet<string> { "Apple", "apple" };
Console.WriteLine(caseSensitive.Count); // 2（別要素として扱われる）

// OrdinalIgnoreCase: ASCII 範囲の大文字小文字を無視（最速）
var tags = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "C#", "JavaScript", "Python"
};
Console.WriteLine(tags.Contains("c#"));        // true
Console.WriteLine(tags.Add("CSHARP"));         // true（"C#" とは別キーなので追加される）
Console.WriteLine(tags.Add("c#"));             // false（"C#" と等価で重複扱い）

// InvariantCultureIgnoreCase: カルチャ中立の大文字小文字無視
var globalTags = new HashSet<string>(StringComparer.InvariantCultureIgnoreCase);

// CurrentCultureIgnoreCase: 実行環境のカルチャに依存
var localTags = new HashSet<string>(StringComparer.CurrentCultureIgnoreCase);

// 用途別の選び方:
// 内部識別子（ヘッダー名・タグ・ID）         → OrdinalIgnoreCase
// ユーザー入力（言語非依存）                  → InvariantCultureIgnoreCase
// ユーザー入力（実行環境のロケールに従う）    → CurrentCultureIgnoreCase

// 顧客 ID で重複判定したい User クラス
public sealed class User
{
    public int Id { get; init; }
    public string Name { get; init; } = "";
    public string Email { get; init; } = "";
}

// IEqualityComparer<User>: ID のみで等価判定
public sealed class UserByIdComparer : IEqualityComparer<User>
{
    public bool Equals(User? x, User? y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (x is null || y is null) return false;
        return x.Id == y.Id;
    }

    public int GetHashCode(User obj) => obj.Id.GetHashCode();
}

var users = new HashSet<User>(new UserByIdComparer())
{
    new User { Id = 1, Name = "Alice" },
    new User { Id = 2, Name = "Bob" },
};

// Id=1 の別インスタンスは重複扱い
bool added = users.Add(new User { Id = 1, Name = "Alice 2" });
Console.WriteLine(added);          // false
Console.WriteLine(users.Count);    // 2

// レコード型を使えば Equals/GetHashCode が自動生成され、比較器が不要
public sealed record UserRecord(int Id, string Name, string Email);
var recordSet = new HashSet<UserRecord>
{
    new(1, "Alice", "a@example.com"),
    new(1, "Alice", "a@example.com"), // 全プロパティ一致 → 重複扱い
};
Console.WriteLine(recordSet.Count); // 1

var orders = new[]
{
    new { UserId = 1, Item = "Book" },
    new { UserId = 2, Item = "Pen" },
    new { UserId = 1, Item = "Notebook" },
    new { UserId = 3, Item = "Eraser" },
};

// ① ユーザー ID の重複を排除したリストが欲しい（プリミティブ）
List<int> uniqueUsers = orders.Select(o => o.UserId).Distinct().ToList();
// → [1, 2, 3]

// ② 重複排除した結果を再利用（O(1) で含まれるか判定したい）
HashSet<int> userSet = orders.Select(o => o.UserId).ToHashSet();
if (userSet.Contains(2)) Console.WriteLine("User 2 exists"); // O(1)

// ③ オブジェクトのプロパティで重複排除（.NET 6+）
var distinctOrders = orders.DistinctBy(o => o.UserId).ToList();
// → 各 UserId の最初の注文だけを残す

// ④ パフォーマンス比較: 1万件中の重複チェック
var data = Enumerable.Range(1, 10_000).ToList();
var lookup = new[] { 100, 5_000, 9_999 };

// NG: List.Contains は O(n) → 3 × 10,000 = 30,000 回の比較
foreach (var x in lookup)
    if (data.Contains(x)) Console.WriteLine($"{x} found");

// OK: HashSet にして O(1) → 3 × 1 = 3 回の比較
var dataSet = data.ToHashSet();
foreach (var x in lookup)
    if (dataSet.Contains(x)) Console.WriteLine($"{x} found");

var sorted = new SortedSet<int> { 5, 1, 3, 8, 2 };
foreach (var n in sorted) Console.Write($"{n} ");
// 1 2 3 5 8（自動的に昇順）

// Min / Max がプロパティで取得できる（HashSet にはない）
Console.WriteLine(sorted.Min); // 1
Console.WriteLine(sorted.Max); // 8

// GetViewBetween: 範囲ビュー（範囲内の要素のみを SortedSet として取得）
SortedSet<int> view = sorted.GetViewBetween(2, 5); // 2..5 を含む
Console.WriteLine(string.Join(",", view)); // 2,3,5

// ビューに対する変更は元の SortedSet にも反映される
view.Add(4); // 元の sorted にも 4 が追加される
Console.WriteLine(sorted.Contains(4)); // true

// Reverse: 逆順列挙（IEnumerable<T>）
foreach (var n in sorted.Reverse()) Console.Write($"{n} ");
// 8 5 4 3 2 1

// カスタム比較器で降順 SortedSet
var desc = new SortedSet<int>(Comparer<int>.Create((a, b) => b.CompareTo(a)))
    { 5, 1, 3, 8, 2 };
// 列挙すると 8, 5, 3, 2, 1

using System.Collections.Immutable;

// ImmutableHashSet: 一度作ったら変更できない
// → 変更操作は新しいインスタンスを返す（元は変更されない）
ImmutableHashSet<string> roles = ImmutableHashSet<string>.Empty
    .Add("admin")
    .Add("editor");

// Add は新しいインスタンスを返す
var withViewer = roles.Add("viewer");
Console.WriteLine(roles.Count);      // 2（変わらない）
Console.WriteLine(withViewer.Count); // 3

// Builder: 大量に追加するときはまとめてビルドする（効率的）
var builder = ImmutableHashSet.CreateBuilder<string>();
foreach (var role in GetRolesFromDb())
    builder.Add(role);
ImmutableHashSet<string> immutable = builder.ToImmutable();

// スレッドセーフなスナップショット共有
private static ImmutableHashSet<string> _allowedIps =
    ImmutableHashSet<string>.Empty;

public static void AddAllowedIp(string ip)
{
    // Interlocked.CompareExchange でロックフリーな更新
    ImmutableHashSet<string> original, updated;
    do
    {
        original = _allowedIps;
        updated  = original.Add(ip);
    } while (Interlocked.CompareExchange(ref _allowedIps, updated, original) != original);
}

using System.Collections.Frozen;

// FrozenSet: 作成後は変更不可・読み取りが HashSet より高速
// → 起動時に一度だけ作って使い回す予約語リスト・許可ロール表などに最適

// 通常のコレクションから作成
string[] csharpKeywords =
{
    "if", "else", "while", "for", "foreach",
    "class", "interface", "namespace", "using"
};
FrozenSet<string> keywordSet = csharpKeywords.ToFrozenSet();

// 使い方は HashSet と同じ
bool isKeyword = keywordSet.Contains("class"); // true

// StringComparer も指定可能
FrozenSet<string> caseInsensitive = csharpKeywords
    .ToFrozenSet(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(caseInsensitive.Contains("CLASS")); // true

// 注: 構築コストは HashSet より高い（入力データに最適化された内部構造を選ぶため）
//     1度作って何度も読むユースケース専用

using System.Collections.Concurrent;

// ConcurrentDictionary のキーだけを使うパターン（最も一般的な代替）
// 値の型は何でもよい（byte が最小）
var safeSet = new ConcurrentDictionary<string, byte>();

// 追加: TryAdd（既に存在すれば false）
bool added1 = safeSet.TryAdd("user1", 0); // true
bool added2 = safeSet.TryAdd("user1", 0); // false（重複）

// 存在確認: ContainsKey（O(1) スレッドセーフ）
bool exists = safeSet.ContainsKey("user1");

// 削除: TryRemove
safeSet.TryRemove("user1", out _);

// 列挙: スナップショット型（列挙中の変更で例外は起きないが、新規追加は見える保証なし）
foreach (var key in safeSet.Keys) Console.WriteLine(key);

// HashSet のような拡張メソッド
public static class ConcurrentSetExt
{
    public static bool Add<T>(this ConcurrentDictionary<T, byte> set, T item)
        where T : notnull => set.TryAdd(item, 0);

    public static bool Remove<T>(this ConcurrentDictionary<T, byte> set, T item)
        where T : notnull => set.TryRemove(item, out _);
}

public sealed class ThreadSafeSet<T>
{
    private readonly HashSet<T> _set;
    private readonly object _lock = new();

    public ThreadSafeSet(IEqualityComparer<T>? comparer = null)
        => _set = new HashSet<T>(comparer);

    public bool Add(T item)
    {
        lock (_lock) return _set.Add(item);
    }

    public bool Contains(T item)
    {
        lock (_lock) return _set.Contains(item);
    }

    public bool Remove(T item)
    {
        lock (_lock) return _set.Remove(item);
    }

    // 列挙はスナップショットを返す（ロック中に foreach すると他スレッドがブロックされる）
    public List<T> Snapshot()
    {
        lock (_lock) return new List<T>(_set);
    }
}

// IReadOnlySet<T>（.NET 5+）— 読み取り専用集合の汎用インターフェース
// HashSet<T> も SortedSet<T> も ImmutableHashSet<T> も実装している

public sealed class TagRegistry
{
    private readonly HashSet<string> _tags = new(StringComparer.OrdinalIgnoreCase);

    // 公開 API は IReadOnlySet で書き込みを禁止する
    public IReadOnlySet<string> Tags => _tags;

    public void RegisterTag(string tag) => _tags.Add(tag);
}

var registry = new TagRegistry();
registry.RegisterTag("csharp");

// 呼び出し側は読み取りだけ可能
IReadOnlySet<string> tags = registry.Tags;
bool exists = tags.Contains("CSHARP"); // true（OrdinalIgnoreCase）

// tags.Add(...) はコンパイルエラー（IReadOnlySet には Add がない）

// ReadOnlySet<T>（.NET 9+）— HashSet を完全にラップする読み取り専用ラッパー
// 単に IReadOnlySet を返すよりもキャストして書き換えられるリスクをさらに抑制できる
// var readOnly = new ReadOnlySet<string>(_tags);

// 参照型を入れた後に GetHashCode に影響するフィールドを変更すると
// 「入れたはずの要素が見つからない」状態になる

public sealed class MutableTag
{
    public string Name { get; set; } = ""; // mutable!
    public override int GetHashCode() => Name.GetHashCode();
    public override bool Equals(object? obj) =>
        obj is MutableTag t && t.Name == Name;
}

var tag = new MutableTag { Name = "Old" };
var set = new HashSet<MutableTag> { tag };

Console.WriteLine(set.Contains(tag)); // true（Name="Old" のハッシュで格納）

tag.Name = "New"; // ハッシュが変わってしまう
Console.WriteLine(set.Contains(tag)); // false（探すバケットが変わって見つからない）

// 対策: HashSet に入れる型は immutable にする
public sealed record ImmutableTag(string Name); // record は init オンリーで安全

var set = new HashSet<int> { 1, 2, 3, 4, 5 };

// NG: foreach 中に Remove → InvalidOperationException
foreach (var x in set)
{
    if (x % 2 == 0) set.Remove(x); // 例外！
}

// OK ①: RemoveWhere を使う（最も簡潔）
set.RemoveWhere(x => x % 2 == 0);

// OK ②: ToList でスナップショット化してから列挙
foreach (var x in set.ToList())
{
    if (x > 3) set.Remove(x);
}

// OK ③: 削除対象を別コレクションに集めてから一括削除
var toRemove = new List<int>();
foreach (var x in set) if (x > 3) toRemove.Add(x);
foreach (var x in toRemove) set.Remove(x);

// 参照型の HashSet は null を1つだけ含めることができる
var set = new HashSet<string?> { "a", "b", null };
Console.WriteLine(set.Count);          // 3
Console.WriteLine(set.Contains(null)); // true

bool added = set.Add(null); // false（既に null が含まれているので重複扱い）

// 一方、Dictionary のキーは null を許さない（ArgumentNullException）
// HashSet と Dictionary でこの仕様が異なるので注意

var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };

// NG: a が破壊される（after の状態を期待していると不具合に）
a.IntersectWith(b);
Console.WriteLine(string.Join(",", a)); // "3,4"（元の {1,2,3,4} は失われた）

// OK: 元を保ちたいならコピーを作ってから操作する
var aOriginal = new HashSet<int> { 1, 2, 3, 4 };
var intersection = new HashSet<int>(aOriginal);
intersection.IntersectWith(b);
Console.WriteLine(string.Join(",", aOriginal));    // "1,2,3,4"（保たれている）
Console.WriteLine(string.Join(",", intersection)); // "3,4"