HashSet C#: phần tử duy nhất, Contains và phép toán tập hợp

HashSet<T> là một collection trong đó mỗi phần tử xuất hiện nhiều nhất một lần. Nó không có chỉ số và không đảm bảo thứ tự, đổi lại nó kiểm tra phần tử có mặt hay không trong thời gian gần như hằng số: tìm một tag trong một triệu tag mất khoảng chừng ấy thời gian như tìm trong mười tag.

Thêm phần tử: Add trả về 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);
    }
}

Đầu ra:

True
False
3
True
True
False
2

Thêm một phần tử trùng không phải là lỗi; Add chỉ trả về false và set giữ nguyên. Giá trị trả về đó là điểm hữu ích nhất của phương thức này. Nó gộp "mình đã thấy cái này chưa?" và "ghi nhớ nó" vào một lần gọi:

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

Đầu ra:

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

Vì sao Contains nhanh

List<T>.Contains so sánh giá trị với từng phần tử lần lượt, nên chi phí tăng theo độ dài list. HashSet<T> tính mã băm của phần tử, nhảy thẳng tới bucket ứng với mã đó, và chỉ so sánh vài phần tử được lưu ở đó. Với phép kiểm tra có mặt bên trong vòng lặp, điều này biến một bước O(n) thành một bước O(1), và một vòng lặp lồng nhau trên hai list thành một lần duyệt duy nhất:

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

Tạo set tốn một lần duyệt qua list, nên chỉ đáng khi bạn tra cứu nhiều hơn vài lần.

Xóa phần tử trùng trong list

Có ba cách phổ biến, và chúng khác nhau ở chỗ thứ tự sẽ ra sao:

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

Đầu ra:

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

Distinct là lựa chọn mặc định hợp lý khi bạn muốn nhận lại một list. Cách làm tại chỗ hoạt động được vì RemoveAll gọi predicate một lần cho mỗi phần tử theo thứ tự: seen.Add trả về false cho bản sao thứ hai trở đi, nên đúng những bản sao đó bị xóa.

Phép toán tập hợp: hợp, giao, hiệu

HashSet<T> có các phép toán của lý thuyết tập hợp. Các phương thức ...With thay đổi chính set gọi chúng và không trả về gì.

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

Đầu ra:

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

Đối số có thể là bất kỳ IEnumerable<T> nào: một mảng, một list hay một set khác. SetEquals bỏ qua thứ tự và phần tử trùng trong đối số. Hàm phụ Show sắp xếp trước khi in vì thứ tự duyệt của set không phải thứ để dựa vào.

LINQ có các phương thức tương ứng trả về một chuỗi phần tử mới và giữ nguyên đầu vào: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Hãy dùng chúng khi bạn không muốn thay đổi set, hoặc khi đầu vào là list.

So sánh bằng tùy chỉnh cho lớp của bạn

Set quyết định "cùng một phần tử" bằng GetHashCode và Equals. Với một lớp không ghi đè hai phương thức này, cả hai đều dựa trên định danh của đối tượng, nên hai đối tượng có các trường bằng nhau vẫn là hai phần tử khác nhau:

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

Đầu ra:

2
1
True

Quy tắc: các đối tượng Equals nhau phải trả về cùng một GetHashCode. Nếu chỉ ghi đè Equals, set sẽ tìm sai bucket và vẫn báo có phần tử trùng. Trên .NET Core 2.1 trở lên, HashCode.Combine(X, Y) tạo ra một mã băm tốt mà không cần tự viết phép tính.

Khi bạn không sửa được lớp, hoặc cần một định nghĩa "giống nhau" khác cho một set cụ thể, hãy truyền một IEqualityComparer<T> vào hàm khởi tạo. Chuỗi có sẵn các comparer dùng ngay được:

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

Đầu ra:

True
False
2

Từ C# 9 trở đi, một record tự sinh Equals và GetHashCode theo giá trị cho bạn, nên record Point(int X, int Y); dùng được trong set mà không cần thêm code.

Đừng bao giờ thay đổi một trường dùng để tính GetHashCode khi đối tượng đang nằm trong set. Đối tượng vẫn nằm trong bucket ứng với mã băm cũ, nên Contains và Remove không còn tìm thấy nó.

Thứ tự và SortedSet

HashSet<T> duyệt theo một thứ tự mà bạn nên coi là tùy ý. Nếu cần các phần tử được sắp xếp, hãy sắp xếp khi in (set.OrderBy(x => x)) hoặc dùng SortedSet<T>, loại set luôn giữ phần tử theo thứ tự và có thêm Min, Max cùng truy vấn theo khoảng với chi phí O(log n) mỗi thao tác:

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

HashSet, List hay Dictionary

Set là một dictionary chỉ có khóa mà không có giá trị. Nếu bạn thấy mình viết Dictionary<string, bool> chỉ để theo dõi phần tử có mặt hay không, một HashSet<string> diễn đạt cùng ý đó rõ ràng hơn.

Lỗi thường gặp

• Trông chờ một thứ tự. Set không có thứ tự nào để dựa vào; hãy sắp xếp, hoặc dùng SortedSet<T>.
• Lớp tự định nghĩa không có Equals và GetHashCode. Các đối tượng trông giống nhau trở thành những phần tử riêng biệt.
• Chỉ ghi đè Equals. Luôn ghi đè GetHashCode đi kèm.
• Thay đổi một phần tử sau khi đã thêm vào. Set không còn tìm thấy nó.
• Truy cập set theo chỉ số. set[0] không biên dịch được; set không có chỉ số. Hãy chuyển bằng ToList() nếu bạn cần vị trí.