Java集合之TreeSet

首先上图：

TreeSet是Collection和Set接口的是实现类，特点是元素不重复，且无序（指存入顺序和取出顺序可能不一致）。它内部采用自平衡的排序二叉树来存储元素，以此结构来保证元素不重复且可以对元素进行排序。自平衡的排序二叉树很重要的一个性质是根节点的左子树都小于根节点，根节点的右子树都大于根节点。以此迭代，从而保证有序。另外TreeSet不是线程安全的。下面的代码演示的是TreeSet对元素的排序效果：

package practice;
import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetPractice {
	public static void main(String args[]) {
		TreeSet<String> ts = new TreeSet<>();
		ts.add("Jack");
		ts.add("Helena");
		ts.add("Eve");
		ts.add("Evf");
		Iterator it = ts.iterator();
		while(it.hasNext()) 
			System.out.print(it.next()+" ");
	}
}

运行结果：Eve Evf Helena Jack

由结果可以看出，TreeSet对字符串根据字典序的大小从小到大进行了排序。这些元素是如何保证有序的呢？那是因为TreeSet集合在每次存入元素时，都将待存入元素与树根节点上的元素进行比较，若待存入元素比根节点上的元素要小，则到左子树，反之则到右子树，到达子树后又与根节点进行比较，重复上述操作，直至找到一个合适的位置。元素在比较时都会调用compareTo方法，该方法是Comparable接口中定义的，因此要对集合中的元素进行排序，就必须实现Comparable接口。JDK中大部分的类都实现了Comparable接口，拥有compareTo方法。如Integer，String等。

为了验证compareTo方法对于TreeSet的重要性，我们将自定义的Student1类对象存入集合，并运行程序：

package practice;
import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetPractice {
	public static void main(String args[]) {
		TreeSet<Student1> ts = new TreeSet<>();
		ts.add(new Student1("Jack", 19));
		ts.add(new Student1("Rose", 18));
		ts.add(new Student1("Tom", 19));
		ts.add(new Student1("Rose", 18));
		System.out.println(ts);//输出集合中的内容
	}
}
class Student1{
	String name;
	int age;
	public Student1(String name ,int age){//构造方法
		this.name = name;
		this.age = age;
	}
	public String toString() {//重写toString方法，便于返回描述信息
		return name+":"+age;
	}
}

运行结果：

PS E:\> java TreeSetPractice
Exception in thread "main" java.lang.ClassCastException: Student1 cannot be cast to java.base/java.lang.Comparable
at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
at java.base/java.util.TreeMap.put(TreeMap.java:536)
at java.base/java.util.TreeSet.add(TreeSet.java:255)
at TreeSetPractice.main(TreeSetPractice.java:7)

因为没有实现Compareable接口，所以Student类型的对象无法比较，所以TreeSet集合不知道按照什么排序规则对Student1对象进行排序，最终导致程序报错。接下来对Student1类进行改写，将该类实现Comparable接口，并重写该接口的compareTo方法

package practice;
import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetPractice {
	public static void main(String args[]) {
		TreeSet<Student1> ts = new TreeSet<>();
		ts.add(new Student1("Jack", 19));
		ts.add(new Student1("Rose", 18));
		ts.add(new Student1("Tom", 19));
		ts.add(new Student1("Rose", 18));
		System.out.println(ts);//输出集合中的内容
	}
}
class Student1 implements Comparable{
	String name;
	int age;
	public Student1(String name ,int age){//构造方法
		this.name = name;
		this.age = age;
	}
	public String toString() {//重写toString方法，便于返回描述信息
		return name+":"+age;
	}
	public int compareTo(Object obj) {//重写Comparable的CompareTo方法
		Student1 s = (Student1)obj;//将Object对象强制转换为Student1对象
		if(this.age > s.age)//年龄小的排在前面
			return 1;
		if(this.age == s.age)//如果年龄相同，则名字按字典序排序
			return this.name.compareTo(s.name);//字典序相等返回0
		return -1;
	}
}

运行结果：[Rose:18, Jack:19, Tom:19]

在上述实现的CompareTo方法中，首先针对age值进行比较，年龄小的排在前面，如果年龄相同则再对name进行比较，如果两个name也相等，则返回0，表示元素重复，应该舍弃。

有时候，定义的类没有实现Comparable接口或者原本已有的ComparaTo方法不符合自己的预期要求，例如希望字符串可以按照长度进行排序而不是字典序。这时，可以通过自定义比较器的方式对TreeSet集合中的元素进行排序，即实现Comparator接口，并且在new TreeSet时指定该比较器。下面是一个按照字符串长度排序代码：

package practice;
import java.util.TreeSet;
import java.util.Comparator;
public class TreeSetPractice {
	public static void main(String args[]) {
		TreeSet<String> ts = new TreeSet<>(new MyComparator());//构造时指定比较器
		ts.add("Jack");
		ts.add("Hello world");
		ts.add("January");
		ts.add("Jun");
		System.out.println(ts);
	}
}
class MyComparator implements Comparator{//定义比较器实现Comparator接口
	public int compare(Object obj1 ,Object obj2) {//实现比较方法
		String s1 = (String)obj1;
		String s2 = (String)obj2;
		return s1.length()-s2.length();//根据字符串长度排序
	}
}