HashSet trong Java (Java HashSet)

1. HashSet là gì?

HashSet trong Java là một cấu trúc dữ liệu thuộc thư viện Java Collections Framework được sử dụng để lưu trữ các phần tử duy nhất, không trùng lặp và không duy trì thứ tự. HashSet được triển khai dựa trên HashMap sử dụng bảng băm (hash table) để lưu trữ các phần tử, cho nên các phần tử trong HashSet không được sắp xếp theo thứ tự nhất định.

2. Đặc điểm của HashSet

• Không cho phép các phần tử trùng lặp: HashSet chỉ lưu trữ các phần tử duy nhất. Nếu một phần tử đã tồn tại trong tập hợp, HashSet sẽ không cho phép thêm phần tử đó lần nữa.
• Không duy trì thứ tự: HashSet không đảm bảo thứ tự của các phần tử (thứ tự chèn hoặc sắp xếp).
• Cho phép phần tử null: HashSet cho phép thêm một phần tử null.
• Hiệu suất cao cho các thao tác cơ bản: HashSet có hiệu suất trung bình là O(1) cho các thao tác thêm, xóa, và kiểm tra sự tồn tại của phần tử nhờ vào cấu trúc bảng băm.

2. Cách hoạt động của HashSet

HashSet sử dụng hàm băm của phần tử (thông qua phương thức hashCode()) để tính toán vị trí của phần tử trong bảng băm. Để thêm một phần tử vào HashSet, Java tính toán giá trị băm (hashCode) của phần tử và đặt nó tại vị trí tương ứng trong bảng băm. Khi kiểm tra phần tử trùng lặp, HashSet sử dụng cả hashCode() và equals() để xác định xem phần tử đã tồn tại hay chưa.

3. Các phương thức quan trọng của HashSet

HashSet cung cấp các phương thức sau để thao tác với tập hợp:

• add(E e): Thêm một phần tử vào HashSet. Nếu phần tử đã tồn tại, phương thức này trả về false.
• remove(Object o): Xóa một phần tử khỏi HashSet.
• contains(Object o): Kiểm tra xem phần tử có tồn tại trong HashSet hay không.
• size(): Trả về số lượng phần tử trong HashSet.
• isEmpty(): Kiểm tra xem HashSet có trống hay không.
• clear(): Xóa tất cả các phần tử khỏi HashSet.

– Ví dụ:

import java.util.HashSet;

public class App {

    public static void main(String[] args) {
        // Khởi tạo HashSet
        HashSet hashSet = new HashSet<>();

        // Thêm phần tử vào HashSet
        hashSet.add("Cam");
        hashSet.add("Quýt");
        hashSet.add("Mít");
        hashSet.add("Dừa");

        // Thử thêm phần tử trùng lặp
        hashSet.add("Cam");

        // In ra các phần tử của HashSet
        System.out.println("HashSet: " + hashSet); // [Mít, Quýt, Cam, Dừa]

        // Kiểm tra sự tồn tại của một phần tử
        System.out.println("HashSet có chứa 'Quýt' không? " + hashSet.contains("Quýt")); // true

        // Xóa phần tử
        hashSet.remove("Mít");
        System.out.println("HashSet sau khi xóa 'Mít': " + hashSet); // [Quýt, Cam, Dừa]

        // Duyệt qua các phần tử trong HashSet
        System.out.println("Các phần tử trong HashSet:");
        for (String language : hashSet) {
            System.out.println(language);
        }
    }
}

– Kết quả:

HashSet: [Mít, Quýt, Cam, Dừa]
HashSet có chứa 'Quýt' không? true
HashSet sau khi xóa 'Mít': [Quýt, Cam, Dừa]
Các phần tử trong HashSet:
Quýt
Cam
Dừa

4. Khi nào nên dùng HashSet?

HashSet hữu ích khi:

• Bạn cần lưu trữ các phần tử duy nhất và không quan tâm đến thứ tự của chúng.
• Muốn tìm kiếm, thêm, xóa phần tử với hiệu suất cao.

6. Ưu và nhược điểm của HashSet

• Ưu điểm:
  • Hiệu suất cao cho các thao tác thêm, xóa, và tìm kiếm phần tử.
  • Không cho phép phần tử trùng lặp.
• Nhược điểm:
  • Không duy trì thứ tự của các phần tử.
  • Không thích hợp khi cần thao tác với các phần tử theo thứ tự (chèn hoặc sắp xếp).

7. Câu hỏi phỏng vấn HashSet

1. Câu hỏi lý thuyết

• HashSet trong Java là gì? Giải thích về cấu trúc HashSet và tại sao nó chỉ lưu trữ các phần tử duy nhất.
• HashSet khác gì với List và Set? So sánh sự khác biệt giữa HashSet, ArrayList và LinkedHashSet.
• Làm sao để HashSet đảm bảo không có phần tử trùng lặp? Giải thích cách HashSet sử dụng hashCode() và equals() để kiểm tra trùng lặp.
• HashSet có duy trì thứ tự không? So sánh thứ tự của các phần tử trong HashSet, LinkedHashSet và TreeSet.
• Tại sao HashSet không cho phép các phần tử trùng lặp? Điều gì sẽ xảy ra khi cố thêm phần tử trùng lặp vào HashSet?
• HashSet có cho phép phần tử null không? Có thể thêm bao nhiêu phần tử null vào HashSet?
• HashSet có phải là thread-safe không? Nếu không, làm thế nào để biến HashSet thành thread-safe?

2. Câu hỏi về thao tác với HashSet

• Làm sao để kiểm tra xem HashSet có chứa một phần tử cụ thể không? Viết ví dụ code cho phương thức contains.
• Làm cách nào để xóa một phần tử khỏi HashSet? Điều gì xảy ra nếu phần tử không tồn tại trong tập hợp?
• Làm thế nào để duyệt qua các phần tử trong HashSet? Cho ví dụ code để duyệt qua HashSet.
• Cách chuyển đổi HashSet sang ArrayList hoặc LinkedList: Làm thế nào để chuyển đổi HashSet sang các loại List khác?
• Làm thế nào để hợp nhất hai HashSet? Viết code để hợp nhất hai HashSet thành một tập hợp duy nhất.

3. Câu hỏi thực hành và thuật toán

• Loại bỏ phần tử trùng lặp từ ArrayList bằng HashSet: Viết code để loại bỏ các phần tử trùng lặp từ một ArrayList bằng cách sử dụng HashSet.
• So sánh hiệu suất của HashSet và TreeSet: Khi nào thì nên sử dụng HashSet thay vì TreeSet?
• Tìm phần tử chung giữa hai HashSet: Viết code để tìm các phần tử chung (giao nhau) giữa hai HashSet.
• Kiểm tra tập con: Viết code để kiểm tra xem một HashSet có là tập con của HashSet khác hay không.
• Chuyển đổi HashSet thành một mảng: Viết code để chuyển đổi tất cả các phần tử của HashSet thành một mảng.

4. Câu hỏi nâng cao

• HashSet hoạt động như thế nào ở cấp độ nội bộ? Giải thích cách các phần tử được lưu trữ trong HashSet và cách nó xử lý xung đột (hash collisions).
• Cách HashSet xử lý xung đột hàm băm (hash collision): Giải thích điều gì sẽ xảy ra nếu hai phần tử có cùng hashCode nhưng không bằng nhau về equals().
• Thiết kế cấu trúc dữ liệu tương tự HashSet: Nếu không có HashSet, bạn sẽ triển khai một tập hợp không trùng lặp bằng cách sử dụng bảng băm như thế nào?
• Ứng dụng của HashSet trong các bài toán xử lý chuỗi: Bạn sẽ dùng HashSet như thế nào để tìm các ký tự duy nhất trong một chuỗi?
• Làm thế nào để tối ưu hóa bộ nhớ của HashSet với số lượng phần tử rất lớn? Khi HashSet chứa hàng triệu phần tử, bạn sẽ làm gì để tối ưu bộ nhớ?