Tập hợp: HashSet<T>

1. Giới thiệu

Hãy tưởng tượng: bạn đang code hệ thống cho shop online, cần lưu danh sách tất cả mã sản phẩm duy nhất từng bán. Hoặc, bạn viết app mạng xã hội, cần kiểm tra nhanh xem username đã tồn tại chưa. Hoặc bạn muốn đếm có bao nhiêu từ khác nhau trong một đoạn văn bản lớn?

Trong tất cả tình huống này, ta cần một tập hợp mà mỗi phần tử chỉ xuất hiện một lần. Và đây là lúc HashSet<T> xuất hiện.

HashSet<T> — là collection lưu trữ tập hợp không có thứ tự các phần tử duy nhất. Từ khóa ở đây là duy nhất. Nếu bạn thử thêm phần tử đã có trong HashSet, nó sẽ lơ đi và không thêm trùng. Kiểu như club "chỉ cho người độc nhất": đã vào rồi thì không được vào lần hai đâu.

Những điểm chính của HashSet<T>:

• Duy nhất: Đảm bảo mỗi phần tử trong collection chỉ xuất hiện một lần.
• Hiệu năng: Kiểm tra tồn tại, thêm, xóa phần tử siêu nhanh. Trung bình các thao tác này là O(1), không phụ thuộc số lượng phần tử! Có được nhờ cơ chế gọi là băm (hashing).
• Không có thứ tự: Khác với List<T>, phần tử trong HashSet<T> không có thứ tự cụ thể. Không thể lấy phần tử theo index (kiểu "phần tử thứ năm").
• Dựa trên hash table: Bên trong HashSet<T> dùng hash table để lưu phần tử, nhờ đó hiệu năng rất cao. Mình sẽ không đi sâu vào hash table (để dành cho bài nâng cao), nhưng cứ tưởng tượng mỗi phần tử được "biến" thành mã số đặc biệt (hash), nhờ đó tìm kiếm cực nhanh.

So sánh với việc dùng List<T> để lưu phần tử duy nhất: bạn sẽ phải duyệt hết list mỗi lần để chắc chắn chưa có phần tử đó trước khi thêm. Với list lớn thì chậm như máy tính Windows XP cũ vậy. HashSet<T> thì làm cái này cực nhanh!

2. HashSet<T> để làm gì cho lập trình viên?

Bí mật của collection duy nhất

Trong lập trình, rất hay gặp bài toán: cần lưu phần tử không trùng lặp. Ví dụ, bạn parse danh sách email user app và muốn chắc chắn không có trùng. Hoặc gom tên file duy nhất đọc từ folder. Cách đơn giản nhất — collection mà không thể thêm lần hai cái đã có.

Tất nhiên, bạn có thể giải quyết bằng List<T>, tự kiểm tra trước khi thêm:

var users = new List<string>();
if (!users.Contains("vasya@example.com"))
    users.Add("vasya@example.com");

Nhưng cách này rất tệ với dữ liệu lớn — Contains của List phải duyệt hết, nếu user hàng ngàn thì app chậm như máy tính cổ chạy Windows XP.

HashSet<T> làm gì?

HashSet<T> thì đảm bảo mỗi phần tử chỉ lưu một lần. Nó dựa trên hash table (giống dictionary), nên thêm, tìm, xóa đều cực nhanh — thường là thời gian cố định, không cần duyệt hết.

3. Cơ bản về HashSet<T>

Khai báo và tạo mới

Không cần import thư viện gì thêm — class đã có sẵn trong namespace System.Collections.Generic.

using System.Collections.Generic;

var emails = new HashSet<string>();

Có thể khởi tạo luôn với giá trị ban đầu, truyền vào constructor:

var fruits = new HashSet<string> { "táo", "chuối", "lê", "chuối" };
// "chuối" xuất hiện hai lần, nhưng chỉ lưu một lần thôi!

Thêm phần tử

Thêm phần tử bằng method Add. Nếu chưa có, trả về true. Nếu đã có — không làm gì, trả về false.

bool added = emails.Add("vasya@example.com"); // true, đã thêm
added = emails.Add("vasya@example.com");      // false, đã có, không thêm

Vui nè: Bạn gọi Add cả trăm lần với cùng giá trị cũng được — HashSet không giận đâu, chỉ lịch sự lơ đi thôi.

Kiểm tra tồn tại: Contains

Để kiểm tra phần tử đã có chưa, dùng method Contains:

if (emails.Contains("vasya@example.com"))
    Console.WriteLine("Email này đã tồn tại!");

Xóa phần tử

Xóa cũng nhanh lắm:

emails.Remove("vasya@example.com");

Nếu không có phần tử — không sao, method chỉ trả về false.

4. Ví dụ thực tế

Giờ mình nâng cấp CRM sinh viên mà tụi mình phát triển suốt khóa học nhé.

Yêu cầu

Giả sử, theo quy định hệ thống, mỗi user phải có username (login) duy nhất. Trước khi thêm user mới phải kiểm tra, nếu trùng thì báo lỗi.

Ví dụ code

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Collection lưu login duy nhất
        var userNames = new HashSet<string>();

        while (true)
        {
            Console.Write("Nhập tên user (hoặc leave để thoát): ");
            string name = Console.ReadLine();

            if (name == "leave")
                break;

            if (userNames.Add(name))
            {
                Console.WriteLine("Thêm tên thành công!");
            }
            else
            {
                Console.WriteLine("Lỗi: tên này đã có, thử tên khác đi.");
            }
        }

        Console.WriteLine("Danh sách user:");
        foreach (var user in userNames)
            Console.WriteLine($"- {user}");

        // Lưu ý! Thứ tự in ra có thể ngẫu nhiên.
    }
}

Vậy là đảm bảo duy nhất cực dễ. Không cần tự kiểm tra — HashSet lo hết.

5. Bên trong HashSet<T> hoạt động thế nào? Hash code để làm gì

Ví dụ: ô lưu trữ

Tưởng tượng bạn có chồng thẻ login cực lớn, và cái bàn có ô từ 0 đến 1000. Mỗi login bạn bỏ vào ô, số ô tính bằng hàm (GetHashCode). Nếu thẻ trùng — nó rơi vào cùng ô, bạn biết ngay login đã có.

Hàm GetHashCode

HashSet<T> so sánh phần tử không chỉ bằng giá trị, mà trước tiên tính hash code bằng method GetHashCode(). Với các kiểu có sẵn (int, string, double v.v.) đã tối ưu sẵn rồi.

Fun fact: Nếu bạn tự tạo class và muốn lưu trong HashSet<T>, nhớ override method so sánh bằng nhau và lấy mã duy nhất (Equals và GetHashCode), để đảm bảo duy nhất hoạt động đúng. Nhưng cái này sẽ nói kỹ ở bài sau.

Một số lỗi thường gặp khi dùng HashSet<T>

Khi mới học collection giá trị duy nhất, nhiều bạn nghĩ HashSet<T> lưu phần tử theo thứ tự thêm vào. Không phải đâu! HashSet không đảm bảo thứ tự gì cả, mọi thứ có thể lộn xộn. Nếu cần thứ tự — dùng collection khác, ví dụ SortedSet<T>, nhưng đó là chuyện khác.

Lỗi phổ biến thứ hai — thử dùng index:

string name = userNames[0]; // Lỗi! HashSet<T> không có index.

Khác với array hay list, ở đây không truy cập phần tử theo số thứ tự được. Chỉ duyệt bằng foreach thôi.

Lỗi thứ ba là khi serialize hoặc lưu hash set ra file — vì không có thứ tự, mỗi lần chạy chương trình phần tử có thể đảo lộn.

6. Thao tác với tập hợp: hợp, giao, hiệu

HashSet<T> có nhiều method giúp thao tác như toán học: hợp, giao, hiệu và hiệu đối xứng.

Dưới đây là mấy method chính:

UnionWith(other)

IntersectWith(other)

ExceptWith(other)

SymmetricExceptWith(other)

Ví dụ: giao và hợp

Ví dụ nhé. Có hai nhóm tên:

var groupA = new HashSet<string> { "Anya", "Boris", "Vera" };
var groupB = new HashSet<string> { "Vera", "Gleb", "Dasha" };

// Tìm ai có ở cả hai nhóm
var common = new HashSet<string>(groupA); // copy nội dung, không thì groupA bị đổi!
common.IntersectWith(groupB);

Console.WriteLine("Có ở cả hai nhóm:");
foreach (var name in common)
    Console.WriteLine(name); // In ra "Vera"

// Hợp tất cả sinh viên hai nhóm, không ai bị sót:
var all = new HashSet<string>(groupA);
all.UnionWith(groupB);

Console.WriteLine("Tất cả sinh viên:");
foreach (var name in all)
    Console.WriteLine(name); // "Anya", "Boris", "Vera", "Gleb", "Dasha"

7. Method và thuộc tính thêm

Count — xem có bao nhiêu phần tử trong set:

Console.WriteLine(userNames.Count);

Clear — xóa sạch (kiểu CTRL+A, DELETE ngoài đời):

userNames.Clear();

SetEquals, IsSubsetOf, IsSupersetOf — kiểm tra hai set giống nhau không, set này có nằm trong set kia không, v.v. Hữu ích nếu bạn chơi (hoặc code) kiểu "toán học — ai bá hơn".

if (groupA.IsSubsetOf(groupB))
    Console.WriteLine("Tất cả nhóm A đều có trong nhóm B");

8. Lưu object tự định nghĩa trong HashSet<T>

Như đã nói ở trên, kiểu chuẩn đã biết tính hash và so sánh bằng nhau đúng cách.

Nhưng nếu bạn muốn lưu user là object, cần đảm bảo so sánh theo thuộc tính nào đó (ví dụ login):

class User
{
    public string Login { get; set; }

    public override bool Equals(object obj)
    {
        if (obj is User other)
            return Login == other.Login;
        return false;
    }

    public override int GetHashCode()
    {
        return Login.GetHashCode();
    }
}

// Giờ có thể:
var users = new HashSet<User>();
users.Add(new User { Login = "vasya" });
users.Add(new User { Login = "petya" });
users.Add(new User { Login = "vasya" }); // Không thêm đâu!

Nếu không override Equals và GetHashCode thì HashSet sẽ coi mọi instance là khác nhau (dù login giống), vì mặc định nó so sánh địa chỉ bộ nhớ.

1

Khảo sát/đố vui

, cấp độ , bài học

Không có sẵn

Tổng quan về các collection cơ bản

Các loại collection và generics

Mở