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> מחשב את ה-hash code של הפריט, קופץ לדלי של הקוד הזה, ומשווה רק את הפריטים המעטים ששמורים שם. בבדיקת שייכות בתוך לולאה, זה הופך צעד של 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) בונה hash code טוב בלי חישוב שנכתב ביד.

כשאי אפשר לשנות את המחלקה, או כשצריך הגדרה אחרת של "אותו דבר" עבור קבוצה אחת, העבירו 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 בזמן שהאובייקט נמצא בקבוצה. האובייקט נשאר בדלי של ה-hash הישן שלו, ו-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() אם צריך מיקומים.