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

Như chúng ta đã biết, LinkedHashSet là một phiên bản mở rộng của HashSet. HashSet không đảm bảo thứ tự sắp xếp của các phần tử. Trong khi đó, LinkedHashSet duy trì thứ tự chèn phần tử. HashSet sử dụng đối tượng HashMap bên trong để lưu trữ các phần tử của nó, còn LinkedHashSet sử dụng đối tượng LinkedHashMap bên trong để lưu trữ và xử lý các phần tử của nó.

Trong bài này, chúng ta sẽ thấy LinkedHashSet hoạt động như thế nào, cách duy trì thứ tự chèn các phần tử và cách đảm bảo các phần tử là duy nhất trong tập hợp.

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

Chúng ta hãy bắt đầu với việc xem xét các hàm xây dựng (contructors) của lớp LinkedHashSet. Có 4 hàm xây dựng bên trong lớp LinkedHashSet. Tất cả các hàm này chỉ đơn giản là gọi đến hàm xây dựng của lớp cha (super class), tức là lớp HashSet. Dưới đây là cách các hàm xây dựng được định nghĩa trong lớp LinkedHashSet:

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

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

Trong đoạn mã ở trên, bạn có thể nhận thấy rằng tất cả 4 hàm xây dựng đang gọi cùng một hàm xây dựng của lớp cha (super class). Hàm xây dựng này là hàm private, chỉ được sử dụng bởi lớp LinkedHashSet.

Hàm xây dựng này lấy sức chứa ban đầu (capacity), hệ số tải (load factor ) và một giá trị giả (dummy) làm đối số. Giá trị dummy này chỉ được sử dụng để phân biệt các hàm xây dựng của lớp HashSet. Dưới đây là cách constructor này được định nghĩa trong lớp HashSet:

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

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
	
}

Như bạn thấy, hàm xây dựng bên trong HashSet tạo ra một đối tượng mới LinkedHashMap. Đối tượng LinkedHashMap này được sử dụng bởi LinkedHashSet để lưu trữ các phần tử của nó.

LinkedHashSet không có phương thức của chính nó. Tất cả các phương thức trong LinkedHashSet được thừa kế từ lớp cha của nó là HashSet. Vì thế, tất cả các hoạt động trên LinkedHashSet hoạt động theo cách tương tự như của HashSet. Thứ thay đổi duy nhất của LinkedHashSet là đối tượng bên trong được sử dụng để lưu trữ các phần tử. Trong hashSet, các phần tử bạn thêm vào được lưu trữ như các khóa của đối tượng HashMap. Trường hợp như trong LinkedHashSet, các phần tử bạn thêm vào được lưu trữ như là khóa của đối tượng LinkedHashMap. Các giá trị của các khóa này là giống nhau một hằng số PRESENT. Chúng ta đã tìm hiểu phần này trong bài viết HashSet trong Java hoạt động như thế nào.

Cách LinkedHashSet đảm bảo thứ tự chèn các phần tử

LinkedHashSet sử dụng đối tượng LinkedHashMap để lưu trữ các phần tử của nó. Các phần tử bạn chèn vào LinkedHashSet được lưu trữ như các khóa của đối tượng LinkedHashMap này.

Mỗi cặp khóa, giá trị (key, value) trong LinkedHashMap là thể hiện (instance) của lớp tĩnh bên trong (static inner class) được gọi là Entry<K, V>. Lớp Entry<K, V> này mở rộng từ lớp HashMap.Entry.

Trình tự chèn các phần tử vào LinkedHashMap được duy trì bằng cách thêm hai trường mới vào lớp này, đó là before và after. Hai trường này giữ các tham chiếu đến các phần tử trước và tiếp theo. Hai trường này làm cho LinkedHashMap hoạt động như một danh sách liên kết gấp đôi (doubly linked list).

public class LinkedHashMap<K,V>
		extends HashMap<K,V>
		implements Map<K,V> {
	
	static class Entry<K,V> extends HashMap.Entry<K,V> {
		// These fields comprise the doubly linked list used for iteration.
		Entry<K,V> before, after;

		Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
			super(hash, key, value, next);
		}
	}

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;
}

Hai trường đầu tiên của lớp LinkedHashMap.Entry: before và after có trách nhiệm duy trì trật tự chèn của LinkedHashSet. Trường head của LinkedHashMap lưu trữ phần đứng đầu danh sách liên kết đôi này. Trường tail của LinkedHashMap lưu trữ phần đứng cuối danh sách liên kết đôi này.

Trong LinkedHashMap, cùng một tập hợp các đối tượng Entry (thay vì tham chiếu đến các đối tượng Entry) được sắp xếp theo hai cách khác nhau. Một là HashMap và một cái khác là Danh sách liên kết đôi (doubly linked list). Đối tượng Entry được đặt trên bộ nhớ heap, và là một phần của hai cấu trúc dữ liệu khác nhau.

Hãy xem một ví dụ về LinkedHashSet để biết cách hoạt động của nó:

public class LinkedHashSetExample {
    public static void main(String[] args) {
        //Creating LinkedHashSet
        LinkedHashSet<String> set = new LinkedHashSet<String>();

        //Adding elements to LinkedHashSet
        set.add("BLUE");
        set.add("RED");
        set.add("GREEN");
        set.add("BLACK");
    }
}

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

Như bạn thấy:

• Khi gọi hàm khởi tạo LinkedHashSet thì nó cũng gọi hàm khởi tạo ở lớp cha HashSet. Tiếp đó, lớp HashSet cũng gọi hàm khởi tạo của LinkedHashMap.
• Khi bạn gọi hàm add để thêm phần tử vào set, thì nó cũng gọi hàm add của lớp HashSet. Tiếp đó, lớp HashSet sẽ gọi hàm put của LinkedHashMap để thêm phần tử. Lớp LinkedHashMap lưu thông tin vào đối tượng Entry. Đối tượng Entry lưu thông tin cặp khóa-giá trị (key-value), Entry trước (before) và sau (after) nó.

Cách LinkedHashSet đảm bảo các phần tử là duy nhất

Bạn hãy xem lại hàm add của lớp HashSet 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 HashSet(int initialCapacity , float loadFactor , boolean dummy) {
         map = new LinkedHashMap<>(initialCapacity , loadFactor); 
    }    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

Bất cứ khi nào bạn tạo ra một đối tượng của LinkedHashSet, nó sẽ gián tiếp tạo ra một đối tượng của LinkedHashMap. Trong LinkedHashMap mỗi khóa là duy nhất. Vì vậy, những gì đã làm trong HashSet là tạo ra phương thức add (Elemenent e) và e như một khóa (key) trong LinkedHashMap. Bây giờ cần phải liên kết một khóa (key) với một giá trị (value), do đó các nhà phát triển Java đã tạo ra thêm một đối tượng PRESENT làm giá trị giả (dummy) để kết hợp vói khóa.

Vì vậy, khi thêm một phần tử vào LinkedHashSet như linkedhashset.add(e) thì những gì bên trong Java thực hiện là nó sẽ đưa phần tử e ở đây 5 như là một khóa (key) trong LinkedHashMap (tạo ra trong quá trình khởi tạo đối tượng LinkedHashSet) và một giá trị (value) dummy PRESENT được truyền như một giá trị cho khoá.

Tài liệu tham khảo:

• http://javaconceptoftheday.com/how-linkedhashset-works-internally-in-java/

Chuyên mục: Collection Được gắn thẻ: Collection, How to

Bình luận

bình luận