HashSet في C#: العناصر الفريدة وContains وعمليات المجموعات

HashSet<T> مجموعة يظهر فيها كل عنصر مرة واحدة على الأكثر. لا فهرس لها ولا ترتيب مضمون، وفي المقابل تفحص العضوية في زمن ثابت تقريبًا: العثور على وسم واحد بين مليون يستغرق نحو ما يستغرقه العثور عليه بين عشرة.

إضافة العناصر: Add تعيد 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);
    }
}

المخرجات:

True
False
3
True
True
False
2

إضافة عنصر مكرّر ليست خطأ؛ تعيد Add ببساطة false وتبقى المجموعة دون تغيير. هذه القيمة المعادة أنفع ما في الدالة. تجمع بين "هل رأيت هذا؟" و"تذكّره" في استدعاء واحد:

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

المخرجات:

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

لماذا Contains سريعة

تقارن List<T>.Contains القيمة بكل عنصر بدوره، فتنمو كلفتها مع القائمة. أما HashSet<T> فتحسب رمز تجزئة العنصر، وتقفز إلى الدلو الخاص بذلك الرمز، ولا تقارن إلا العناصر القليلة المخزّنة هناك. لفحص عضوية داخل حلقة يحوّل ذلك خطوة O(n) إلى خطوة O(1)، وحلقة متداخلة على قائمتين إلى مرور واحد:

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

بناء المجموعة يكلّف مرورًا واحدًا على القائمة، فلا يجدي إلا حين تبحث أكثر من بضع مرات.

إزالة التكرارات من قائمة

هناك ثلاث طرق شائعة، وتختلف فيما يحدث للترتيب:

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

المخرجات:

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

Distinct هي الافتراضي الصحيح حين تريد قائمة في النتيجة. وتعمل النسخة التي تعمل في المكان لأن RemoveAll تستدعي الشرط مرة لكل عنصر بالترتيب: تعيد seen.Add القيمة false للنسخة الثانية وما بعدها، فتُحذف تلك بالضبط.

عمليات المجموعات: الاتحاد والتقاطع والفرق

في HashSet<T> عمليات نظرية المجموعات. دوال ...With تغيّر المجموعة التي تُستدعى عليها ولا تعيد شيئًا.

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

المخرجات:

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

يمكن أن يكون الوسيط أي IEnumerable<T>: مصفوفة أو قائمة أو مجموعة أخرى. تتجاهل SetEquals الترتيب والتكرارات في الوسيط. وترتّب الدالة المساعدة Show قبل الطباعة لأن ترتيب تعداد المجموعة ليس شيئًا يُعتمد عليه.

في LINQ دوال مقابلة تعيد تسلسلًا جديدًا وتترك المدخلات كما هي: monday.Union(tuesday) وmonday.Intersect(tuesday) وmonday.Except(tuesday). استخدمها حين لا تريد تغيير مجموعة، أو حين تكون المدخلات قوائم.

المساواة المخصصة لأصنافك

تقرّر المجموعة "العنصر نفسه" بـ GetHashCode وEquals. في الصنف الذي لا يتجاوزهما تقوم الدالتان على هوية الكائن، فيكون كائنان بحقول متساوية عنصرين مختلفين:

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

المخرجات:

2
1
True

القاعدة: الكائنات المتساوية بـ Equals يجب أن تعيد GetHashCode نفسه. تجاوز Equals وحدها فتبحث المجموعة في الدلو الخطأ وتظل تبلّغ عن التكرارات. في .NET Core 2.1 وما بعده تبني HashCode.Combine(X, Y) رمز تجزئة جيدًا دون الحساب المكتوب يدويًا.

حين لا تستطيع تغيير الصنف، أو تحتاج إلى مفهوم مختلف لـ "الشيء نفسه" في مجموعة واحدة، مرّر IEqualityComparer<T> إلى المُنشئ. وللنصوص أدوات مقارنة جاهزة:

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

المخرجات:

True
False
2

في C# 9 وما بعده يولّد record الدالتين Equals وGetHashCode بالقيمة عنك، فيعمل record Point(int X, int Y); في مجموعة دون شيفرة إضافية.

لا تغيّر أبدًا حقلًا يدخل في GetHashCode بينما الكائن في مجموعة. يبقى الكائن في دلو تجزئته القديمة، فتتوقف Contains وRemove عن إيجاده.

الترتيب وSortedSet

يُعدَّد HashSet<T> بترتيب يجب أن تعامله على أنه اعتباطي. إن احتجت إلى العناصر مرتّبة فرتّب عند الطباعة (set.OrderBy(x => x)) أو استخدم SortedSet<T>، الذي يبقي العناصر مرتّبة دائمًا ويضيف Min وMax واستعلامات النطاق بكلفة O(log n) لكل عملية:

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

HashSet مقابل List مقابل Dictionary

المجموعة قاموس بمفاتيح بلا قيم. إن وجدت نفسك تكتب Dictionary<string, bool> فقط لتتبّع العضوية، فإن HashSet<string> تقول الشيء نفسه بوضوح أكبر.

أخطاء شائعة

• توقّع ترتيب. لا ترتيب يُعتمد عليه في المجموعة؛ رتّب، أو استخدم SortedSet<T>.
• أصناف مخصصة بلا Equals وGetHashCode. تصبح الكائنات المتشابهة عناصر منفصلة.
• تجاوز Equals وحدها. تجاوز GetHashCode معها دائمًا.
• تغيير عنصر بعد إضافته. لا تعود المجموعة قادرة على إيجاده.
• فهرسة مجموعة. لا تُترجم set[0]؛ لا فهرس. حوّل بـ ToList() إن احتجت إلى مواضع.