HashSet trong Java hoạt động như thế nào?

Trong bài HashSet trong Java chúng ta đã tìm hiểu về đặc điểm của HashSet, các constructor, các phương thức và ví dụ minh họa trong việc sử dụng HashSet trong Java. Trong bài này, chúng ta sẽ cùng tìm về cấu trúc dữ liệu lưu trữ các phần tử, cách HashSet trong Java hoạt động như thế nào?

Set interface vs HashSet trong Java

Set interface

Set là một interface kế thừa Collection interface trong java. Set trong java là một Collection không thể chứa các phần tử trùng lặp.

HashSet trong Java

Lớp HashSet trong java là một lớp kế thừa lớp AbstractSet và triển khai của Set Interface trong Collections Framework nên nó sẽ có một vài đặc điểm và phương thức tương đồng với Set. HashSet được sử dụng để tạo một bộ sưu tập sử dụng bảng băm để lưu trữ. Nó kế thừa lớp AbstractSet và triển khai Set interface.

Constructor của lớp HashSet trong Java

Cấu trúc dữ liệu bên trong HashSet

HashSet sử dụng HashMap nội bộ để lưu trữ các phần tử. Bất cứ khi nào bạn tạo một đối tượng HashSet, một đối tượng HashMap liên kết với nó cũng được tạo ra. Đối tượng HashMap này được sử dụng để lưu trữ các phần tử bạn thêm vào HashSet. Các phần tử bạn thêm vào HashSet được lưu trữ như các khóa (key) của đối tượng HashMap này. Giá trị (value) kết hợp với các khóa (key) đó sẽ là một hằng số (constant).

Mỗi hàm tao doi tuong (constructor) bên trong lớp HashSet tạo ra một đối tượng HashMap. Bạn có thể kiểm tra điều này trong mã nguồn của lớp HashSet trong thư mục cài đặt JDK. Dưới đây là cách các hàm xây dựng được định nghĩa trong lớp HashSet:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
 
    private transient HashMap<E,Object> map;
 
    // tao dummy value de lien ket voi doi tuong map
    private static final Object PRESENT = new Object();
     
    public HashSet() {
        map = new HashMap<>();
    }
     
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
     
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
     
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
     
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}

Bạn có thể nhận thấy rằng mỗi constructor bên trong HashSet tạo ra một đối tượng HashMap mới.

Cách HashSet hoạt động trong Java

Bất cứ khi nào bạn thêm một phần tử vào HashSet bằng cách sử dụng phương thức add(), nó thực sự tạo ra một đối tượng Entry bên trong đối tượng HashMap, với phần tử đã chỉ định làm khóa và giá trị không đổi gọi là PRESENT. Giá trị PRESENT được định nghĩa trong lớp HashSet như dưới đây:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private transient HashMap<E,Object> map;

    // tao dummy value de lien ket voi doi tuong map
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
}

Bạn có thể nhận thấy rằng, phương thức add() của lớp HashSet gọi phương thức put() của đối tượng HashMap bằng cách truyền các phần tử bạn đã chỉ định như là một khoá và giá trị không đổi PRESENT.

Phương thức remove() cũng hoạt động theo cách tương tự.

Hãy xem một ví dụ về HashSet và xem cách nó hoạt động với HashMap:

public class HashSetExample {
    public static void main(String[] args) {
        // tao mot doi tuong HashSet
        HashSet<String> set = new HashSet<String>();
  
        //Adding elements to HashSet
        set.add("RED");
        set.add("GREEN");
        set.add("BLUE");
        set.add("PINK");
  
        // xoa doi tuong co key = "RED" khoi HashSet
        set.remove("RED");
    }
}

Xem hình dưới đây để hiểu chương trình hoạt động như thế nào:

Bạn có thể quan sát rằng bên trong đối tượng HashMap chứa các phần tử của HashSet như các khóa và PRESENT làm giá trị của chúng.

Theo cùng một cách, tất cả các phương thức của lớp HashSet hoạt động tương tự như HashMap, do nó sử dụng đối tượng HashMap bên trong để có được kết quả mong muốn. Nếu bạn biết cách HashMap hoạt động, bạn sẽ dễ dàng hiểu cách HashSet hoạt động. Bạn hãy xem qua mã nguồn của lớp HashSet để có một bức tranh rõ ràng về cách HashSet hoạt động trong Java hoặc xem thêm bài viết HashMap trong Java hoạt động như thế nào? để hiểu rõ hơn.

Tham khảo:

https://javaconceptoftheday.com/how-hashset-works-internally-in-java

https://www.javatpoint.com/working-of-hashset-in-java