Çalıştırılabilir C# Dokümanları: HashSet

Q: C#'ta HashSet nedir?

HashSet , tanımlı bir sırası olmayan benzersiz öğelerden oluşan bir koleksiyondur. Zaten var olan bir öğeyi eklemek hiçbir şey yapmaz ve küme ne kadar büyük olursa olsun Contains kabaca sabit zamanda cevap verir, çünkü öğeler bir Dictionary'nin anahtarları gibi hash koduna göre saklanır.

Q: HashSet.Add ne döndürür?

Add, öğe eklendiğinde true, zaten kümedeyse false döndürür. Bu da if (!seen.Add(x))'i tek satırlık bir tekrar kontrolü yapar: yeni öğeleri ekler ve tekrarlananları aynı çağrıda size bildirir.

Q: C#'ta bir List'ten tekrarlar nasıl silinir?

list.Distinct().ToList() tekrarsız yeni bir liste döndürür ve her öğenin ilk geçişini orijinal sırasında tutar. new HashSet (list) de tekrarları siler, ama bir kümenin garanti edilmiş bir sırası yoktur. Yerinde tekrar silmek için var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x)); kullanın.

Q: HashSet'im neden tekrar eden nesneler içeriyor?

Sınıfınız Equals ve GetHashCode'u override etmiyor, bu yüzden küme referansları karşılaştırıyor ve alan değerleri aynı olan iki nesne farklı sayılıyor. İki metodu da override edin (her zaman birlikte) ya da kümenin constructor'ına bir IEqualityComparer verin.

Bir HashSet<T>, her öğenin en fazla bir kez göründüğü bir koleksiyondur. İndeksi ve garanti edilmiş bir sırası yoktur; karşılığında üyeliği kabaca sabit zamanda kontrol eder: bir milyon etiket arasında birini bulmak, on etiket arasında bulmak kadar sürer.

Öğe eklemek: Add bool döndürür

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

Çıktı:

True
False
3
True
True
False
2

Bir tekrarı eklemek hata değildir; Add sadece false döndürür ve küme değişmez. Bu dönüş değeri metodun en kullanışlı yanıdır. "Bunu gördüm mü?" ve "bunu hatırla"yı tek bir çağrıda birleştirir:

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

Çıktı:

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

Contains neden hızlı

List<T>.Contains değeri her elemanla sırayla karşılaştırır, bu yüzden maliyeti listeyle birlikte büyür. Bir HashSet<T> öğenin hash kodunu hesaplar, o kodun kovasına atlar ve yalnızca orada saklanan birkaç öğeyi karşılaştırır. Bir döngü içindeki üyelik testi için bu, O(n) bir adımı O(1) bir adıma, iki liste üzerindeki iç içe bir döngüyü de tek bir geçişe çevirir:

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

Kümeyi oluşturmak liste üzerinde bir geçişe mal olur, bu yüzden yalnızca birkaç kereden fazla arama yaptığınızda kendini amorti eder.

Bir listeden tekrarları silmek

Üç yaygın yol vardır ve sıraya ne olduğu bakımından farklılaşırlar:

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

Çıktı:

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

Geriye bir liste istediğinizde doğru varsayılan Distinct'tir. Yerinde sürüm çalışır, çünkü RemoveAll koşulu her eleman için sırayla bir kez çağırır: seen.Add ikinci ve sonraki kopyalar için false döndürür, bu yüzden tam olarak onlar silinir.

Küme işlemleri: birleşim, kesişim, fark

HashSet<T> küme teorisindeki işlemlere sahiptir. ...With metotları üzerinde çağrıldıkları kümeyi değiştirir ve hiçbir şey döndürmez.

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

Çıktı:

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

Argüman herhangi bir IEnumerable<T> olabilir: bir dizi, bir liste ya da başka bir küme. SetEquals argümandaki sırayı ve tekrarları yok sayar. Show yardımcısı yazdırmadan önce sıralar, çünkü bir kümenin dolaşma sırası güvenilecek bir şey değildir.

LINQ'in yeni bir dizi döndüren ve girdilere dokunmayan eşleşen metotları vardır: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Bir kümeyi değiştirmek istemediğinizde ya da girdiler liste olduğunda bunları kullanın.

Kendi sınıflarınız için özel eşitlik

Bir küme "aynı öğe"ye GetHashCode ve Equals ile karar verir. Bunları override etmeyen bir sınıf için ikisi de nesnenin kimliğine dayanır, bu yüzden alanları eşit olan iki nesne iki farklı öğedir:

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

Çıktı:

2
1
True

Kural: Equals olan nesneler aynı GetHashCode'u döndürmelidir. Yalnızca Equals'ı override ederseniz küme yanlış kovaya bakar ve yine tekrar bildirir. .NET Core 2.1 ve sonrasında HashCode.Combine(X, Y) elle yazılmış aritmetik olmadan iyi bir hash kodu oluşturur.

Sınıfı değiştiremediğinizde ya da tek bir küme için farklı bir "aynı" kavramına ihtiyacınız olduğunda constructor'a bir IEqualityComparer<T> verin. String'ler hazır karşılaştırıcılarla gelir:

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

Çıktı:

True
False
2

C# 9 ve sonrasında bir record değere dayalı Equals ve GetHashCode'u sizin için üretir, bu yüzden record Point(int X, int Y); ek kod olmadan bir kümede çalışır.

Nesne bir kümedeyken GetHashCode'u besleyen bir alanı asla değiştirmeyin. Nesne eski hash'inin kovasında kalır, bu yüzden Contains ve Remove onu bulamaz hale gelir.

Sıra ve SortedSet

Bir HashSet<T>, rastgele kabul etmeniz gereken bir sırayla dolaşılır. Öğelerin sıralı olmasına ihtiyacınız varsa yazdırırken sıralayın (set.OrderBy(x => x)) ya da öğeleri her zaman sıralı tutan ve işlem başına O(log n) ile Min, Max ve aralık sorguları ekleyen SortedSet<T> kullanın:

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

HashSet, List ve Dictionary

İhtiyaç	Kullanın
Benzersiz öğeler, hızlı "orada mı?"	`HashSet<T>`
Benzersiz öğeler, her zaman sıralı	`SortedSet<T>`
Sıra, tekrarlar, indeks erişimi	`List<T>`
Her anahtar altında saklanan bir değer	`Dictionary<TKey, TValue>`

Bir küme, anahtarları olan ve değerleri olmayan bir dictionary'dir. Kendinizi yalnızca üyeliği izlemek için Dictionary<string, bool> yazarken bulursanız, bir HashSet<string> aynı şeyi daha açık söyler.

Yaygın hatalar

Bir sıra beklemek. Kümenin güvenebileceğiniz bir sırası yoktur; sıralayın ya da SortedSet<T> kullanın.
Equals ve GetHashCode'u olmayan özel sınıflar. Eşit görünen nesneler ayrı öğeler olur.
Yalnızca Equals'ı override etmek. Onunla birlikte her zaman GetHashCode'u da override edin.
Bir öğeyi ekledikten sonra değiştirmek. Küme onu artık bulamaz.
Bir kümeyi indekslemek. set[0] derlenmez; indeks yoktur. Konumlara ihtiyacınız varsa ToList() ile dönüştürün.

Sıkça Sorulan Sorular

C#'ta HashSet nedir?

HashSet<T>, tanımlı bir sırası olmayan benzersiz öğelerden oluşan bir koleksiyondur. Zaten var olan bir öğeyi eklemek hiçbir şey yapmaz ve küme ne kadar büyük olursa olsun Contains kabaca sabit zamanda cevap verir, çünkü öğeler bir Dictionary'nin anahtarları gibi hash koduna göre saklanır.

HashSet.Add ne döndürür?

Add, öğe eklendiğinde true, zaten kümedeyse false döndürür. Bu da if (!seen.Add(x))'i tek satırlık bir tekrar kontrolü yapar: yeni öğeleri ekler ve tekrarlananları aynı çağrıda size bildirir.

C#'ta bir List'ten tekrarlar nasıl silinir?

list.Distinct().ToList() tekrarsız yeni bir liste döndürür ve her öğenin ilk geçişini orijinal sırasında tutar. new HashSet<T>(list) de tekrarları siler, ama bir kümenin garanti edilmiş bir sırası yoktur. Yerinde tekrar silmek için var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x)); kullanın.

List yerine ne zaman HashSet kullanmalıyım?

Çoğunlukla "bu öğe koleksiyonda mı?" diye soruyorsanız ya da öğelerin benzersiz olması gerekiyorsa HashSet<T> kullanın. List<T>.Contains her elemanı tarar, bu yüzden liste büyüdükçe yavaşlar; HashSet<T>.Contains yavaşlamaz. Sıra, tekrarlar ya da indeks erişimi önemliyse List<T> kullanın.

HashSet'im neden tekrar eden nesneler içeriyor?

Sınıfınız Equals ve GetHashCode'u override etmiyor, bu yüzden küme referansları karşılaştırıyor ve alan değerleri aynı olan iki nesne farklı sayılıyor. İki metodu da override edin (her zaman birlikte) ya da kümenin constructor'ına bir IEqualityComparer<T> verin.

İlgili kavramlar