openplanning

Hướng dẫn và ví dụ Java TreeSet

  1. TreeSet
  2. TreeSet lưu trữ dữ liệu như thế nào?
  3. Examples
  4. TreeSet với phần tử null

1. TreeSet

Trong bài viết này chúng ta sẽ khám phá về lớp TreeSet, nó là một triển khai (implementation) của interaface NavigableSet và nằm trong nền tảng tập hợp của Java (Java Collection Framework).
public class TreeSet<E> extends AbstractSet<E>
                    implements NavigableSet<E>, Cloneable, java.io.Serializable
Về cơ bản, trong bài viết này chúng ta sẽ tìm hiểu các đặc điểm của TreeSet và cách nó lưu trữ các phần tử. Bạn nên tìm hiểu các khái niệm cơ bản về Set trước khi tiếp tục với bài viết này.
Các đặc điểm của TreeSet:
Set<E>
SortedSet<E>
NavigableSet<E>
TreeSet<E>
Không cho phép phần tử trùng lặp. Nếu bạn cố tình thêm 1 phần tử trùng lặp, hành động này sẽ bị bỏ qua.
Cho phép nhiều nhất một phần tử null.
Cho phép nhiều nhất một phần tử null và chỉ cho phép phần tử null nếu được cung cấp một Comparator phù hợp.
Thứ tự của các phần tử không được đảm bảo.
Sắp xếp các phần tử tăng dần theo thứ tự tự nhiên của chúng hoặc theo một Comparator được cung cấp.
Thừa hưởng các đặc điểm của interface SortedSet. Tất cả các phần tử của TreeSetphải là kiểu Comparable (có thể so sánh) hoặc bạn phải cung cấp một Comparator (bộ so sánh) cho TreeSet để nó so sánh các phần tử với nhau. Ngược lại, ClassCastException sẽ bị ném ra. Comparator được cung cấp tại thời điểm tạo đối tượng TreeSet thông qua một trong các constructor của nó.
Các constructor của TreeSet:
TreeSet​(Comparator<? super E> comparator)   

// Using the same ordering as the specified sortedSet.
TreeSet​(SortedSet<E> sortedSet)    

TreeSet()     

TreeSet​(Collection<? extends E> c)

2. TreeSet lưu trữ dữ liệu như thế nào?

TreeSet<E> quản lý một đối tượng TreeMap<E,Object> nội bộ - internalMap. Tất cả các hoạt động trên TreeSet đều được thực hiện trên internalMap. Trong đó, như đã biết TreeMap lưu trữ dữ liệu của nó trong một cấu trúc cây, và đó là lý do giải thích cho cái tên của TreeSet.
Để dễ hiểu, hãy nhìn vào mã nguồn của lớp java.util.TreeSet, bạn sẽ thấy rằng nó hoạt động giống như một người uỷ nhiệm của đối tượng TreeMap mà nó quản lý.
java.util.TreeSet class
public class TreeSet<E> extends AbstractSet<E>
                   implements NavigableSet<E>, Cloneable, java.io.Serializable {

    private static final Object PRESENT = new Object();
    
    private transient TreeMap<E,Object> internalMap;
    
    public boolean add(E e) {
        return this.internalMap.put(e, PRESENT)==null;
    }
    
    public boolean remove(Object o) {
        return this.internalMap.remove(o)==PRESENT;
    }
    
    public void clear() {
        this.internalMap.clear();
    }
    
     public E first() {
        return this.internalMap.firstKey();
    }
     
    public E last() {
        return this.internalMap.lastKey();
    }
    // Other methods..
}
TreeMap lưu trữ dữ liệu của nó theo một cấu trúc cây, điều đó được giải thích trong bài viết dưới đây của tôi, xem nó nếu bạn quan tâm.

3. Examples

Như chúng ta đã biết, lớp Integer thi hành interface Comparable, nên các đối tượng Integer có khả năng so sánh được với nhau. TreeSet với các phần tử kiểu Integer không cần thiết phải cung cấp một Comparator.
TreeSetEx1.java
package org.o7planning.treeset.ex;

import java.util.TreeSet;

public class TreeSetEx1 {

    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[1, 3, 5, 7, 9, 11]
Ví dụ: Sử dụng Comparator tuỳ biến để đảo ngược thứ tự các phần tử.
TreeSet_reverseOrder_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSet_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeSet<Integer> set = new TreeSet<>(reverseOrderComparator);
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[11, 9, 7, 5, 3, 1]
Xem thêm các ví dụ khác về việc sử dụng Comparator tuỳ biến trong TreeSet và cách điều hướng, tìm kiếm các phần tử.

4. TreeSet với phần tử null

TreeSet chỉ cho phép phần tử null nếu nó được cung cấp một Comparator hỗ trợ việc so sánh phần tử null với các phần tử khác.
TreeSet_nullElement_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}
Output:
[null, A, B, D, E, F]
Ví dụ: Viết một Comparator tuỳ biến hỗ trợ việc so sánh phần tử null với các phần tử khác:
TreeSet_nullElement_ex2.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex2 {

    public static void main(String[] args) {
        Comparator<String> comparator = new StringNullComparator();

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}

// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if (o1 == o2) {
            return 0; // o1 = o2
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
[null, A, B, D, E, F]

Các hướng dẫn Java Collections Framework

Show More