HashSet và bài toán đếm

Nhiều bài toán hằng ngày chỉ là đếm và kiểm tra trùng: mỗi sản phẩm bán được bao nhiêu cái, có bao nhiêu khách khác nhau, có hai món nào vừa đúng ngân sách không. Làm bằng hai vòng lặp lồng nhau là O(n²). Dùng hash table thì chỉ còn O(n).

Khái niệm

🫧 HashSet: tập hợp các phần tử không trùng nhau, bên trong là hash table nên Add, Contains, Remove trung bình là O(1).

HashSet<T> giống một Dictionary chỉ có key, không có value. Add trả về false nếu phần tử đã có, nên vừa kiểm trùng vừa thêm chỉ bằng một lời gọi.

Ví dụ

Đếm số lần mỗi sản phẩm được bán, dùng Dictionary từ tên sang số lượng:

List<string> sold = new List<string>
{
    "Bút bi", "Vở", "Bút bi", "Thước", "Bút bi", "Vở"
};

var counts = new Dictionary<string, int>();
foreach (string name in sold)
{
    if (counts.ContainsKey(name))
    {
        counts[name] = counts[name] + 1;
    }
    else
    {
        counts[name] = 1;
    }
}

foreach (var item in counts)
{
    Console.WriteLine($"{item.Key}: {item.Value}");
}

• Duyệt list đúng một lần, mỗi lần tra và cập nhật dictionary là O(1). Tổng cộng O(n).
• Nếu đã học khoá SQL: câu GROUP BY kèm COUNT(*) làm đúng việc này.

Tìm hai món vừa đủ ngân sách

Khách có 19.000đ, muốn mua đúng hai món cho hết số tiền đó. Với mỗi giá price, món còn lại phải có giá budget - price. Hỏi HashSet xem đã gặp giá đó chưa, thay vì so với mọi giá khác.

List<decimal> prices = new List<decimal>
{
    5000m, 12000m, 350000m, 7000m
};
decimal budget = 19000m;

var seen = new HashSet<decimal>();
foreach (decimal price in prices)
{
    decimal need = budget - price;
    if (seen.Contains(need))
    {
        Console.WriteLine($"{need} + {price}");
    }
    seen.Add(price);
}

• Gặp 7000, cần thêm 12000, mà 12000 đã có trong seen. In ra 12000 + 7000.
• Một vòng lặp, mỗi bước O(1), nên tổng là O(n). Hai vòng lồng nhau so từng cặp thì là O(n²).

Thử ngay

Đếm số khách khác nhau đã đặt hàng hôm nay:

var customers = new HashSet<string>();
Console.WriteLine(customers.Add("An"));
Console.WriteLine(customers.Add("Bình"));
Console.WriteLine(customers.Add("An"));
Console.WriteLine(customers.Count);

Đoán trước khi chạy: bốn dòng in ra là gì?

True
True
False
2

Lỗi hay gặp

Lấy phần tử của HashSet theo vị trí. HashSet chỉ trả lời "có hay không", không đánh số vị trí cho phần tử, nên không có [i].

// SAI — lỗi compile: HashSet không có [i]
var customers = new HashSet<string>();
customers.Add("An");
Console.WriteLine(customers[0]);

// ĐÚNG — cần hỏi "có hay không" thì dùng Contains
var customers = new HashSet<string>();
customers.Add("An");
Console.WriteLine(customers.Contains("An"));

Tóm tắt

• HashSet<T> giữ phần tử không trùng, Add trả false nếu đã có.
• Đếm số lần xuất hiện bằng Dictionary từ phần tử sang số đếm.
• Tìm cặp có tổng cho trước: với mỗi phần tử, hỏi HashSet phần còn thiếu.
• Các bài này từ O(n²) xuống O(n) nhờ tra hash table là O(1).