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 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 thức hoạt động bên trong của HashSet.

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

HashSet sử dụng HashMap nội bộ để lưu trữ các đối tượng đó. 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 xây dựng (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 LinkedHashSet:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
 
    private transient HashMap<E,Object> map;
 
    // Dummy value to associate with an Object in the backing 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.

2. 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;
 
    // Dummy value to associate with an Object in the backing 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) {
        //Creating One HashSet object 
        HashSet<String> set = new HashSet<String>();
  
        //Adding elements to HashSet 
        set.add("RED"); 
        set.add("GREEN"); 
        set.add("BLUE"); 
        set.add("PINK");
  
        //Removing "RED" from 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 Cách thức HashMap hoạt động trong Java để hiểu rõ hơn.