TreeSet và sử dụng Comparable, Comparator trong java - GP Coder (Lập trình Java)

Tóm Tắt

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.

Hierarchy của lớp TreeSet

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

Bạn đang đọc: TreeSet và sử dụng Comparable, Comparator trong java – GP Coder (Lập trình Java)

public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable {
    private transient NavigableMap m;

    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap m) {
        this.m = m;
    }
	
    public TreeSet() {
        this(new TreeMap());
    }
}

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

.

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

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

Ví dụ minh họa

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

package com.gpcoder.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 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

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

Student. java

package com.gpcoder.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.gpcoder.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 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.gpcoder.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.gpcoder.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 và override phương thức compare(T obj1, T obj2).
Implement Comparable và override phương thức compareTo(T obj).

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

Student. java

package com.gpcoder.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.gpcoder.collection.treeset;

import java.util.Comparator;

public class StudentComparator implements Comparator {

	@Override
	public int compare(Student o1, Student o2) {
		// sort student's name by ASC
		return o1.getName().compareTo(o2.getName());
	}

}

TreeSetExample. java


package com.gpcoder.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 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]

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

Xem thêm: Các Cấu trúc Dữ liệu Array, Linked list, Stack năm 2022

Student. java

package com.gpcoder.collection.treeset;

public class Student implements Comparable {
	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.gpcoder.collection.treeset;

public class TreeSetExample {
	public static final int NUM_OF_ELEMENT = 5;

	public static void main(String[] args) {
		// Create list
		Set 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]

So sánh Comparable vs Comparator

Comparable	Comparator
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).

Ví dụ tạo chỉ hoàn toàn có thể tạo một Comparable

Một class Student chỉ hoàn toàn có thể setup một phương pháp compareTo của Comparator interface

public class Student2 implements Comparable {
	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;
	}
}

Ví dụ hoàn toàn 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 pháp 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 {

	@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 {

	@Override
	public int compare(Student o1, Student o2) {
		// sort student's id by DESC
		return o2.getName().compareTo(o1.getName());
	}

}

Ví dụ sử dụng Comparator để sắp xếp list ( List )

SortListExample. java

package com.gpcoder.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 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 students2 = new ArrayList<>(students);
		Collections.sort(students2, new StudentNameComparator());
		printData(students2);
		System.out.println("--- ");

		System.out.println("List sorted using StudentIdComparator: ");
		List students3 = new ArrayList<>(students);
		Collections.sort(students3, new StudentIdComparator());
		printData(students3);
		System.out.println("--- ");

	}

	public static void printData(List 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]
---

Sử dụng Anonymous Class : Comparable, Comparator

Student. java

package com.gpcoder.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.gpcoder.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 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 students2 = new ArrayList<>(students);
		Collections.sort(students2, new Comparator() {
			@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 students3 = new ArrayList<>(students);
		Collections.sort(students3, new Comparator() {
			@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 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]
---

4.9

Xem thêm: Câu hỏi phỏng vấn Java Spring: Spring Framework, Boot & MVC

Nếu bạn thấy hay thì hãy chia sẻ bài viết cho mọi người nhé!