HashSet trong Java: giá trị duy nhất và phép toán tập hợp

Set lưu các giá trị duy nhất

HashSet (trong java.util) là một collection chứa mỗi giá trị tối đa một lần. Không có cặp khóa và giá trị như trong HashMap, chỉ có một túi các phần tử khác nhau. Toàn bộ nhiệm vụ của nó là trả lời thật nhanh một câu hỏi: "thứ này có ở trong đây không?"

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // duplicate - ignored

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

Chỉ có một tham số kiểu, <ElementType>. Cũng như với ArrayList và HashMap, bạn thường khai báo biến theo interface Set và tạo đối tượng HashSet.

add cho biết giá trị có mới hay không

add không chỉ lưu giá trị: nó trả về một boolean cho biết set có thực sự thay đổi hay không. Thêm một giá trị đã có sẵn sẽ trả về false và set giữ nguyên.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true  - 7 was new
        System.out.println(seen.add(7));  // false - already there
        System.out.println(seen);
    }
}

Giá trị trả về đó thực sự hữu ích: if (!seen.add(x)) { /* x is a repeat */ } giúp bạn phát hiện phần tử trùng chỉ trong một dòng khi đang duyệt.

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

Vì set từ chối giá trị lặp lại, cách nhanh nhất để loại bỏ trùng lặp trong một collection là đổ nó vào một set. Constructor của HashSet nhận bất kỳ collection nào khác:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // each name once
        System.out.println(unique.size());   // 3

        // need a List back?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

Đây là lý do phổ biến nhất khiến người mới học dùng set. Chỉ cần nhớ rằng bạn mất thứ tự ban đầu sau khi chuyển qua lại: hãy dùng LinkedHashSet nếu thứ tự quan trọng (xem bên dưới).

contains, remove và size

Các thao tác thường ngày giống như ở các collection khác:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

Lợi thế lớn so với ArrayList nằm ở contains. List phải duyệt qua từng phần tử để trả lời (O(n)); HashSet gần như nhảy thẳng tới câu trả lời (khoảng O(1)). Khi thấy mình gọi list.contains(...) bên trong một vòng lặp, đó thường là dấu hiệu nên chuyển sang set.

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

Set phát huy sức mạnh khi bạn kết hợp chúng. Tên các phương thức dễ hiểu ngay khi bạn biết cái nào làm gì:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // everything in either set
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // only what's in both
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // in a but not b
        System.out.println(difference);   // 1 2
    }
}

Điểm cần lưu ý: addAll, retainAll và removeAll thay đổi chính set được gọi. Đó là lý do mỗi ví dụ đều sao chép a sang một HashSet mới trước: nếu không, bạn sẽ phá hỏng set ban đầu. Hãy tạo một set mới cho mỗi kết quả.

HashSet không giữ thứ tự

Giống HashMap, HashSet không cam kết gì về thứ tự duyệt, và thứ tự có thể khác nhau giữa các lần chạy. Nếu bạn cần thứ tự dự đoán được:

• LinkedHashSet giữ thứ tự thêm vào, tức thứ tự bạn thêm các phần tử.
• TreeSet giữ các phần tử được sắp xếp theo thứ tự tự nhiên (hoặc theo Comparator bạn cung cấp).

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

Cả ba đều cài đặt interface Set, nên muốn đổi qua lại chỉ cần sửa một dòng ở constructor.

Phần tử phải băm được

Bên dưới, HashSet được xây dựng trên một HashMap, nên cùng một quy tắc được áp dụng: nó định vị phần tử bằng cách băm, nghĩa là hashCode() và equals() của phần tử phải nhất quán. Các kiểu có sẵn như String và Integer đã làm đúng điều này, đó là lý do các chuỗi "java" trùng nhau ở trên được gộp lại chính xác. Nếu bạn lưu instance của lớp do mình viết, hãy override cả equals lẫn hashCode: nếu không, hai đối tượng "bằng nhau" về ý nghĩa sẽ bị coi là khác nhau, và contains cũng như việc loại bỏ trùng lặp sẽ lặng lẽ thất bại.

Tiếp theo: duyệt collection

Giờ bạn đã làm quen với ba collection chủ lực: ArrayList, HashMap và HashSet. Mỗi loại được duyệt theo cách hơi khác nhau, và có những cái bẫy tinh vi (như thay đổi collection trong lúc đang lặp qua nó). Tiếp theo, chúng ta sẽ tổng hợp lại và học cách duyệt collection gọn gàng bằng vòng lặp for-each, iterator và forEach.