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 đúng bằ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<E> giống một HashMap chỉ có key, không có value. add trả về false nếu phần tử đã có, nên vừa kiểm tra 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 HashMap từ tên sang số lượng:

// Main.java
void main() {
    List<String> sold = List.of(
        "Bút bi", "Vở", "Bút bi",
        "Thước", "Bút bi", "Vở");

    Map<String, Integer> counts = new HashMap<>();
    for (String name : sold) {
        if (counts.containsKey(name)) {
            counts.put(name, counts.get(name) + 1);
        } else {
            counts.put(name, 1);
        }
    }

    for (var item : counts.entrySet()) {
        System.out.println("%s: %d".formatted(
            item.getKey(), item.getValue()));
    }
}

• Duyệt list đúng một lần, mỗi lần tra và cập nhật map là O(1). Tổng cộng O(n).
• Chương trình in Bút bi: 3, Vở: 2, Thước: 1. Thứ tự này do ô của từng key quyết định: HashMap không hứa giữ thứ tự thêm vào.

Tìm hai món đúng bằng 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.

// Main.java
void main() {
    List<Long> prices = List.of(
        5000L, 12000L, 350000L, 7000L);
    long budget = 19000;

    Set<Long> seen = new HashSet<>();
    for (long price : prices) {
        long need = budget - price;
        if (seen.contains(need)) {
            System.out.println("%d + %d".formatted(
                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²).

void main() {
    List<Long> prices = List.of(5000L, 12000L, 350000L, 7000L);
    long budget = 19000;
    Set<Long> seen = new HashSet<>();
    for (long price : prices) {
        long need = budget - price;
        if (seen.contains(need)) {
            System.out.println("%d + %d".formatted(need, price));
        }
        seen.add(price);
    }
}

Thử ngay

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

// Main.java
void main() {
    Set<String> customers = new HashSet<>();
    System.out.println(customers.add("An"));
    System.out.println(customers.add("Bình"));
    System.out.println(customers.add("An"));
    System.out.println(customers.size());
}

Đ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ó get(i).

// SAI — lỗi compile: HashSet không có get(i)
Set<String> customers = new HashSet<>();
customers.add("An");
System.out.println(customers.get(0));

// ĐÚNG — cần hỏi "có hay không" thì dùng contains
Set<String> customers = new HashSet<>();
customers.add("An");
System.out.println(customers.contains("An"));

Tóm tắt

• HashSet<E> giữ phần tử không trùng, add trả false nếu đã có.
• Đếm số lần xuất hiện bằng HashMap 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).