TreeSet và sử dụng Comparable, Comparator trong java

1. Giới thiệu

Lớp TreeSet trong Java cài đặt (implement) Set Interface, nó sử dụng một cây (tree) cho lưu giữ các phần tử. TreeSet kế thừa lớp (extends) AbstractSet và cài đặt (implement) NavigableSet Interface. Các đối tượng của lớp TreeSet được lưu trữ theo thứ tự tăng dần.

Các điểm quan trọng về lớp TreeSet trong java là:

  • Chỉ chứa các phần tử duy nhất giống như HashSet.
  • Duy trì thứ tự tăng dần.
  • TreeSet không cho phép chứa phần tử null.
  • Bạn cần phải cung cấp bộ Comparator trong khi tạo một TreeSet. Nếu bạn không cung cấp bộ so sánh (Comparator) cho TreeSet, các phần tử sẽ được đặt theo thứ tự tăng dần.
  • TreeSet không được đồng bộ. Để có được một TreeSet đồng bộ, hãy sử dụng phương thức Collections.synchronizedSortedSet ().
  • Độ phức tạp của TreeSet là log(n) cho thao tác thêm (insertion), loại bỏ (removal) và truy xuất (retrieval).
  • TreeSet sử dụng TreeMap để lưu trữ các phần tử, giống như HashSet và LinkedHashSet sử dụng HashMap và LinkedHashMap tương ứng để lưu trữ các phần tử của chúng.

2. Hierarchy của lớp TreeSet

Lớp java.util.TreeSet được định nghĩa như sau:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
 
    private static final Object PRESENT = new Object();
 
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
     
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
}

3. Các phương thức khởi tạo (constructor) của lớp TreeSet

  • TreeSet(): khởi tạo một tập hợp rỗng.
  • TreeSet(Collection c): khởi tạo một tập hợp với các phần tử của collection c
  • TreeSet(Comparator comparator): khởi tạo một tập hợp rỗng mà các phần tử được xếp thứ tự theo bộ so sánh được xác định bởi comparator.

4. Các phương thức (method) của lớp TreeSet

Xem thêm các phương thức của Set ở bài viết Set Interface trong java.

5. Ví dụ minh họa

5.1. Ví dụ sử dụng TreeSet với kiểu dữ liệu cơ bản (Wrapper)

package com.maixuanviet.collection.treeset;
 
import java.util.Set;
import java.util.TreeSet;
 
public class TreeSetExample2 {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create set
        Set<String> set = new TreeSet<>();
        set.add("Item01");
        set.add("Item02");
        set.add("Item03");
        set.add("Item04");
        set.add("Item05");
        set.add("Item02");
        set.add("Item03");
 
        // Show set through for-each
        for (String item : set) {
            System.out.print(item + " ");
        }
    }
}

Kết quả thực thi chương trình trên:

Item01 Item02 Item03 Item04 Item05 

5.2. Ví dụ sử dụng TreeSet với kiểu do người dùng tự định nghĩa (Object)

Student.java

package com.maixuanviet.collection.treeset;
 
public class Student {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    public String getName() {
        return name;
    }
}

TreeSetExample.java

package com.maixuanviet.collection.treeset;
 
import java.util.Set;
import java.util.TreeSet;
 
public class TreeSetExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list with no comparator
        Set<Student> students = new TreeSet<>();
        Student student1 = new Student(1, "myname1");
        Student student2 = new Student(2, "myname2");
        Student student3 = new Student(3, "myname3");
        Student student4 = new Student(4, "myname4");
        Student student5 = new Student(5, "myname5");
        students.add(student1);
        students.add(student3);
        students.add(student2);
        students.add(student5);
        students.add(student4);
        students.add(student2);
        students.add(student3);
 
        // Show set student
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

Kết quả thực thi chương trình trên:

Exception in thread "main" java.lang.ClassCastException: com.maixuanviet.collection.treeset.Student cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)
    at com.maixuanviet.collection.treeset.TreeSetExample.main(TreeSetExample.java:17)

Đối với kiểu Object nếu bạn không cung cấp bộ so sánh (Comaparator) cho TreeSet thì bạn sẽ gặp lỗi như trên. Có 2 cách để cung cấp bộ Comparator:

  • Implement Comparator<T> và override phương thức compare(T obj1, T obj2).
  • Implement Comparable<T> và override phương thức compareTo(T obj).

5.2.1. Implement Comparator<T> và override phương thức compare(T obj1, T obj2)

Student.java

package com.maixuanviet.collection.treeset;
 
public class Student {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    public String getName() {
        return name;
    }
}

StudentComparator.java

package com.maixuanviet.collection.treeset;
 
import java.util.Comparator;
 
public class StudentComparator implements Comparator<Student> {
 
    @Override
    public int compare(Student o1, Student o2) {
        // sort student's name by ASC
        return o1.getName().compareTo(o2.getName());
    }
 
}

TreeSetExample.java

package com.maixuanviet.collection.treeset;
 
import java.util.Set;
import java.util.TreeSet;
 
public class TreeSetExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list with StudentComparator
        Set<Student> students = new TreeSet<>(new StudentComparator());
        Student student1 = new Student(1, "myname1");
        Student student2 = new Student(2, "myname2");
        Student student3 = new Student(3, "myname3");
        Student student4 = new Student(4, "myname4");
        Student student5 = new Student(5, "myname5");
        students.add(student1);
        students.add(student3);
        students.add(student2);
        students.add(student5);
        students.add(student4);
        students.add(student2);
        students.add(student3);
 
        // Show set student
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

Kết quả thực thi chương trình trên:

Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]

5.2.2. Implement Comparable<T> và override phương thức compareTo(T obj)

Student.java

package com.maixuanviet.collection.treeset;
 
public class Student implements Comparable<Student> {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    @Override
    public int compareTo(Student student) {
        // sort student's name by ASC
        return this.getName().compareTo(student.getName());
    }
 
    public String getName() {
        return name;
    }
}

TreeSetExample.java

package com.maixuanviet.collection.treeset;
 
public class TreeSetExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list
        Set<Student> students = new TreeSet<>();
        Student student1 = new Student(1, "myname1");
        Student student2 = new Student(2, "myname2");
        Student student3 = new Student(3, "myname3");
        Student student4 = new Student(4, "myname4");
        Student student5 = new Student(5, "myname5");
        students.add(student1);
        students.add(student3);
        students.add(student2);
        students.add(student5);
        students.add(student4);
        students.add(student2);
        students.add(student3);
 
        // Show set student
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

Kết quả thực thi chương trình trên:

Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]

6. So sánh Comparable vs Comparator

ComparableComparator
Comparable chỉ cung cấp một cách so sánh duy nhất. Tức là chúng ta chỉ có thể so sánh theo id hoặc name, hoặc age, …Comparable cung cấp nhiều cách so sánh. Tức là chúng ta có thể sắp xếp dựa trên nhiều yếu tố như id, name, age, …
Comparable làm thay đổi lớp gốc (original class), tức là lớp của đối tượng so sánh phải chỉnh sửa và implement Comparable Interface để cài đặt bộ so sánh.Comparator không làm thay đổi lớp gốc (original class). Chúng ta có thể tạo một class mới, implement Comparator Interface để cài đặt bộ so sánh.
Comparable cung cấp phương thức compareTo() để so sánh 2 phần tử.Comparable cung cấp phương thức compare() để so sánh 2 phần tử.
Comparable nằm trong package java.lang.Comparator nằm trong package java.util.
Có thể sắp xếp một danh sách bất kỳ bằng phương thức Collections.sort(List).Có thể sắp xếp một danh sách bất kỳ bằng phương thức Collections.sort(List, Comparator).

6.1. Ví dụ tạo chỉ có thể tạo một Comparable

Một class Student chỉ có thể cài đặt một phương thức compareTo của Comparator interface

public class Student2 implements Comparable<Student> {
    private int id;
    private String name;
 
    public Student2(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    @Override
    public int compareTo(Student2 student) {
        // sort student's name by ASC
        return this.getName().compareTo(student.getName());
    }
 
    public String getName() {
        return name;
    }
}

6.2. Ví dụ có thể tạo nhiều Comparator

Có thể tạo nhiều comparator cho class Student bằng cách tạo nhiều class Comparator và override phương thức compare của Comparator Interface.

Student.java

public class Student {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    public int getId() {
        return id;
    }
 
    public String getName() {
        return name;
    }
 
}

StudentComparator.java

import java.util.Comparator;
 
public class StudentComparator implements Comparator<Student> {
 
    @Override
    public int compare(Student o1, Student o2) {
        // sort student's name by ASC
        return o1.getName().compareTo(o2.getName());
    }
 
}

StudentIdComparator.java

import java.util.Comparator;
 
public class StudentIdComparator implements Comparator<Student> {
 
    @Override
    public int compare(Student o1, Student o2) {
        // sort student's id by DESC
        return o2.getName().compareTo(o1.getName());
    }
 
}

6.3. Ví dụ sử dụng Comparator để sắp xếp danh sách (List)

SortListExample.java

package com.maixuanviet.collection.treeset;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class SortListExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list
        List<Student> students = new ArrayList<>();
        Student student1 = new Student(1, "myname1");
        Student student2 = new Student(2, "myname2");
        Student student3 = new Student(3, "myname3");
        Student student4 = new Student(4, "myname4");
        Student student5 = new Student(5, "myname5");
        students.add(student1);
        students.add(student3);
        students.add(student2);
        students.add(student5);
        students.add(student4);
        students.add(student2);
 
        // Show list student
        System.out.println("List without sorted: ");
        printData(students);
        System.out.println("--- ");
 
        System.out.println("List sorted using StudentNameComparator: ");
        List<Student> students2 = new ArrayList<>(students);
        Collections.sort(students2, new StudentNameComparator());
        printData(students2);
        System.out.println("--- ");
 
        System.out.println("List sorted using StudentIdComparator: ");
        List<Student> students3 = new ArrayList<>(students);
        Collections.sort(students3, new StudentIdComparator());
        printData(students3);
        System.out.println("--- ");
 
    }
 
    public static void printData(List<Student> students) {
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

Kết quả thực thi chương trình trên:

List without sorted: 
Student [id=1, name=myname1]
Student [id=3, name=myname3]
Student [id=2, name=myname2]
Student [id=5, name=myname5]
Student [id=4, name=myname4]
Student [id=2, name=myname2]
--- 
List sorted using StudentNameComparator: 
Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]
--- 
List sorted using StudentIdComparator: 
Student [id=5, name=myname5]
Student [id=4, name=myname4]
Student [id=3, name=myname3]
Student [id=2, name=myname2]
Student [id=2, name=myname2]
Student [id=1, name=myname1]
--- 

6.4. Sử dụng Anonymous Class: Comparable, Comparator

Student.java

package com.maixuanviet.collection.treeset;
 
public class Student {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
 
    public int getId() {
        return id;
    }
 
    public String getName() {
        return name;
    }
 
}

SortListExample.java

package com.maixuanviet.collection.treeset;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class SortListExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list
        List<Student> students = new ArrayList<>();
        Student student1 = new Student(1, "myname1");
        Student student2 = new Student(2, "myname2");
        Student student3 = new Student(3, "myname3");
        Student student4 = new Student(4, "myname4");
        Student student5 = new Student(5, "myname5");
        students.add(student1);
        students.add(student3);
        students.add(student2);
        students.add(student5);
        students.add(student4);
        students.add(student2);
 
        // Show list student
        System.out.println("List without sorted: ");
        printData(students);
        System.out.println("--- ");
 
        System.out.println("List sorted using Comparable: ");
        List<Student> students2 = new ArrayList<>(students);
        Collections.sort(students2, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                // sort student's name by ASC
                return o1.getName().compareTo(o2.getName());
            }
        });
        printData(students2);
        System.out.println("--- ");
 
        System.out.println("List sorted using Comparable: ");
        List<Student> students3 = new ArrayList<>(students);
        Collections.sort(students3, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                // sort student's id by DESC
                return o2.getName().compareTo(o1.getName());
            }
        });
        printData(students3);
        System.out.println("--- ");
    }
 
    public static void printData(List<Student> students) {
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

Kết quả thực thi chương trình trên:

List without sorted: 
Student [id=1, name=myname1]
Student [id=3, name=myname3]
Student [id=2, name=myname2]
Student [id=5, name=myname5]
Student [id=4, name=myname4]
Student [id=2, name=myname2]
--- 
List sorted using Comparable: 
Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]
--- 
List sorted using Comparable: 
Student [id=5, name=myname5]
Student [id=4, name=myname4]
Student [id=3, name=myname3]
Student [id=2, name=myname2]
Student [id=2, name=myname2]
Student [id=1, name=myname1]
--- 

2 Trackbacks / Pingbacks

  1. So sánh HashSet, LinkedHashSet và TreeSet trong Java – Blog của VietMX
  2. Sắp xếp trong Java 8 - Blog của VietMX

Comments are closed.