HashSet C#: Item Unik, Contains dan Operasi Set

HashSet<T> adalah koleksi tempat setiap item muncul paling banyak satu kali. Koleksi ini tidak punya indeks dan tidak punya urutan yang dijamin, dan sebagai gantinya ia memeriksa keanggotaan dalam waktu yang kurang lebih konstan: mencari satu tag di antara sejuta tag butuh waktu kira-kira sama dengan mencarinya di antara sepuluh tag.

Menambahkan item: Add mengembalikan 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);
    }
}

Output:

True
False
3
True
True
False
2

Menambahkan duplikat bukan sebuah error; Add hanya mengembalikan false dan set-nya tidak berubah. Nilai kembalian itulah hal paling berguna dari method ini. Ia menggabungkan "apakah aku sudah pernah melihat ini?" dan "ingat item ini" dalam satu pemanggilan:

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");
    }
}

Output:

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

Kenapa Contains cepat

List<T>.Contains membandingkan nilai dengan setiap elemen satu per satu, jadi biayanya bertambah seiring panjang list. HashSet<T> menghitung hash code item, langsung menuju bucket untuk kode tersebut, dan hanya membandingkan sedikit item yang tersimpan di sana. Untuk pemeriksaan keanggotaan di dalam loop, langkah O(n) berubah menjadi langkah O(1), dan loop bersarang pada dua list berubah menjadi satu kali jalan:

// 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));

Membuat set butuh satu kali jalan pada list, jadi cara ini baru menguntungkan kalau kamu melakukan pencarian lebih dari beberapa kali.

Menghapus duplikat dari list

Ada tiga cara yang umum, dan ketiganya berbeda dalam hal apa yang terjadi pada urutan:

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));
    }
}

Output:

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

Distinct adalah pilihan default yang tepat saat kamu ingin hasilnya berupa list. Versi yang langsung mengubah list bekerja karena RemoveAll memanggil predicate sekali untuk setiap elemen secara berurutan: seen.Add mengembalikan false untuk salinan kedua dan seterusnya, jadi tepat salinan-salinan itulah yang dihapus.

Operasi set: union, intersection, selisih

HashSet<T> punya operasi dari teori himpunan. Method ...With mengubah set tempat method itu dipanggil dan tidak mengembalikan apa pun.

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 }));
    }
}

Output:

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

Argumennya bisa berupa IEnumerable<T> apa saja: array, list atau set lain. SetEquals mengabaikan urutan dan duplikat pada argumennya. Fungsi bantu Show mengurutkan sebelum mencetak karena urutan enumerasi sebuah set bukan sesuatu yang bisa diandalkan.

LINQ punya method padanannya yang mengembalikan urutan baru dan tidak mengubah input-nya: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Pakai method-method itu saat kamu tidak ingin mengubah sebuah set, atau saat input-nya berupa list.

Kesamaan kustom untuk class buatanmu

Sebuah set menentukan "item yang sama" dengan GetHashCode dan Equals. Untuk class yang tidak meng-override keduanya, keduanya didasarkan pada identitas objek, jadi dua objek dengan field yang sama dianggap dua item yang berbeda:

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)));
    }
}

Output:

2
1
True

Aturannya: objek yang Equals harus mengembalikan GetHashCode yang sama. Kalau kamu hanya meng-override Equals, set akan mencari di bucket yang salah dan tetap melaporkan duplikat. Di .NET Core 2.1 ke atas, HashCode.Combine(X, Y) membuat hash code yang baik tanpa perhitungan yang ditulis manual.

Saat kamu tidak bisa mengubah class-nya, atau butuh pengertian "sama" yang berbeda untuk satu set, kirim sebuah IEqualityComparer<T> ke constructor-nya. String sudah dilengkapi comparer siap pakai:

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);
    }
}

Output:

True
False
2

Di C# 9 ke atas, record membuatkan Equals dan GetHashCode berbasis nilai untukmu, jadi record Point(int X, int Y); bisa dipakai di set tanpa kode tambahan.

Jangan pernah mengubah field yang dipakai oleh GetHashCode saat objeknya ada di dalam set. Objek itu tetap berada di bucket untuk hash lamanya, jadi Contains dan Remove tidak bisa menemukannya lagi.

Urutan dan SortedSet

HashSet<T> melakukan enumerasi dalam urutan yang sebaiknya kamu anggap acak. Kalau kamu butuh item yang terurut, urutkan saat mencetak (set.OrderBy(x => x)) atau pakai SortedSet<T>, yang selalu menjaga item tetap terurut dan menambahkan Min, Max dan query rentang dengan biaya O(log n) per operasi:

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

HashSet vs List vs Dictionary

Set adalah dictionary yang punya key tapi tidak punya value. Kalau kamu menulis Dictionary<string, bool> hanya untuk mencatat keanggotaan, HashSet<string> menyampaikan hal yang sama dengan lebih jelas.

Kesalahan yang sering terjadi

• Mengharapkan urutan. Set tidak punya urutan yang bisa diandalkan; urutkan, atau pakai SortedSet<T>.
• Class kustom tanpa Equals dan GetHashCode. Objek yang terlihat sama menjadi item yang terpisah.
• Hanya meng-override Equals. Selalu override GetHashCode bersamanya.
• Mengubah item setelah ditambahkan. Set tidak bisa lagi menemukannya.
• Mengakses set lewat indeks. set[0] tidak bisa di-compile; set tidak punya indeks. Konversi dengan ToList() kalau kamu butuh posisi.