GP Coder

Trang chia sẻ kiến thức lập trình Java

Trang chủ Java Core Collection TreeSet và sử dụng Comparable, Comparator trong java

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

Đăng vào Được đăng bởi 613 Lượt xem

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:

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>());
    }
}

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 các phương thức 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<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

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

Implement Comparator<T> 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<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.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<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]

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

Student.java

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

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ỉ 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;
	}
}

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());
	}

}

Ví dụ sử dụng Comparator để sắp xếp danh sách (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<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]
---

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<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]
---
5 (100%) 2 votes

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

Có thể bạn muốn xem:

Bình luận

bình luận

Liên kết website

Giới thiệu

GP Coder là trang web cá nhân, được thành lập với mục đích lưu trữ, chia sẽ kiến thức đã học và làm việc của tôi. Các bài viết trên trang này chủ yếu về ngôn ngữ Java và các công nghệ có liên quan đến Java như: Spring, JSF, Web Services, Unit Test, Hibernate, SQL, ...
Hi vọng góp được chút ít công sức cho sự phát triển cộng đồng Coder Việt.

Liên hệ

Các bạn có thể liên hệ với tôi thông qua: