Java 笔记 —— Set 集合的排序原理（源码分析）
public V put(K key, V value) {
//生成一个根
Entry<K,V> t = root;
//在还没有元素插入的时候，树的根是 null，然后生成一个根
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
//由于是无参构造，comparator 的值是 null
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
//key 就是想要添加到集合中的元素值
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//这里进行了强制类型转换，向下转型
//Comparable 是自然比较
//这里要求了传入的对象的类必须实现了 Comparable<T>接口
Comparable<? super K> k = (Comparable<? super K>) key;
/*
这里是把要传入集合中的元素 key，进行类型强制转换后，变成 k
第一个传入的元素会被作为第一个根节点
之后传入的元素 k 与树的每一个根节点进行比较，所以这里是 do while 循环，所有根节点都要比较
这里是借助 compareTo 方法来做比较，格式为: 要插入的元素.compareTo(集合原来的元素)
如果 k 的值小于根节点，则作为左孩子，加入树的左侧
如果 k 的值大于根节点，则作为右孩子，加入树的右侧
如果 k 的值与根节点相同，则说明元素重复，不会加入集合中
*/
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
}
这里具体的过程可以拿第一个例子，传入的对象是 Integer 类型的例子来说明
自定义类继承 Comparable 接口
现在回过头来，为什么 Integer 可以实现自然排序，因为 Integer 类已经实现 Comparable 接口
那么如果想让自定义类的对象也可以实现自然排序，就需要让自定义类也实现 Comparable 接口
package review.SetDemo;
public class Student2 implements Comparable<Student2>{
private String name;
private int age;
public Student2() {
}
public Student2(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Student2 o) {
int i = this.age - o.age;
//先比较年龄是否相同，如果不同则返回年龄的比较结果
//如果年龄相同则比较姓名是否相同
//姓名相同则返回 0，说明两个元素相同
//姓名不同则按照 this.name.compareTo(o.name)返回的结果排序
int i2 = i==0 ? this.name.compareTo(o.name) : i;
return i2;
}
}
package review.SetDemo;
import java.util.TreeSet;
public class demo4 {
public static void main(String[] args) {
TreeSet<Student2> tree = new TreeSet<>();
Student2 s1 = new Student2("zhang",12);
Student2 s2 = new Student2("zhou",15);
Student2 s3 = new Student2("cao",16);
Student2 s4 = new Student2("zhang",23);
Student2 s5 = new Student2("zhang",12);
Student2 s6 = new Student2("jing",15);
tree.add(s1);
tree.add(s2);
tree.add(s3);
tree.add(s4);
tree.add(s5);
tree.add(s6);
for(Student2 s : tree){
System.out.println(s.getName()+"---"+s.getAge());
}
}
}
结果为
去重成功，对象 s5 没有加入到集合中
而姓名相同的对象 s1 和对象 s4，则是按照年龄大小进行排序
而年龄相同的对象对象 s2 和对象 s6，则是按照姓名进行排序
当然这里也可以加入更多的条件
重写的 compareTo 方法中，不止要有排序的判断，还要有元素是否相同的判断
比如这里，排序的判断是优先判断名字的长度
后面的 i2 和 i3 都有两个功能：
功能一、判断元素是否相同，如果相同则返回 0
功能二、如果元素不相同，则按照对应的属性值进行排序
比如这里 i2 比较的姓名，如果不同则直接按这个比较结果排序，不会看年龄
如果 i2 返回的结果为 0，说明姓名相同，这时会用 i3 中的年龄的比较结果进行排序
如果 i3 返回的结果也是 0，说明所有属性值都相同，此时应该认为元素相同，不加入到集合中
@Override
public int compareTo(Student2 o) {
//先比较姓名的长
度
int i = this.name.length() - o.name.length();
//姓名的长度相同不代表内容也相同
int i2 = i == 0 ? this.name.compareTo(o.name) : i;
//姓名的长度和内容都一样，但是年龄可能不一样
//只有当姓名和年龄都一样的时候才判断为同一个人，才算重复
int i3 = i2 == 0 ? this.age - o.age : i2;
return i3;
}
比较器排序
**注意：
自然排序的类里面实现的是 Comparable<>接口，里面重写的方法是 compareTo(Object obj)
比较器排序的类实现的是 Comparator 接口，里面重写的方法是 compare(Object o1, Object o2)**
实现比较器排序，需要在创建集合的时候，调用带参数的构造方法，这个参数是实现了 Comparator 接口的子类对象
用匿名内部类的形式实现 Comparator 接口
注意看注释部分
package review.SetDemo;
import java.util.Comparator;
import java.util.TreeSet;
public class demo5 {
public static void main(String[] args) {
TreeSet<Student3> tree = new TreeSet<>(new Comparator<Student3>() {
@Override
public int compare(Student3 o1, Student3 o2) {
//！！易错点 o1 和 o2
// o1 相当于 this 是要插入集合的元素
// o2 是集合中原来的元素
//按名字的长度来进行排序
int i = o1.getName().length() - o2.getName().length();
//名字长度相同不代表元素相同，进行元素是否相同的判断
int i2 = i==0 ? o1.getName().compareTo(o2.getName()) : i;
//名字长度和名字都相同，还要判断年龄是否相同
int i3 = i2==0 ? o1.getAge() - o2.getAge() : i2;
return i3;
}
});
Student3 s1 = new Student3("zhang",12);
Student3 s2 = new Student3("zhou",15);
Student3 s3 = new Student3("cao",16);
Student3 s4 = new Student3("zhang",23);
Student3 s5 = new Student3("zhang",12);
tree.add(s1);
tree.add(s2);
tree.add(s3);
tree.add(s4);
tree.add(s5);
for(Student3 s : tree){
System.out.println(s.getName()+"---"+s.getAge());
}
}
}
另外创建一个实现了 Comparator 接口的类
package review.SetDemo;
import java.util.Comparator;
public class MyComparator implements Comparator<Student3> {
@Override
public int compare(Student3 o1,Student3 o2){
int i = o2.getName().length() - o1.getName().length();
int i2 = i == 0 ? o1.getName().compareTo(o2.getName()) : i;
int i3 = i2 == 0 ? o1.getAge() - o2.getAge() : i2;
return i3;
}
}
顺带一提，这里将
int i = o1.getName().length() - o2.getName().length();
改成了
int i = o2.getName().length() - o1.getName().length();
结果将按照倒序来排序
package review.SetDemo;
import java.util.TreeSet;
public class demo6 {
public static void main(String[] args) {
TreeSet<Student3> tree = new TreeSet<Student3>(new MyComparator());
Student3 s1 = new Student3("zhang",12);
Student3 s2 = new Student3("zhou",15);
Student3 s3 = new Student3("cao",16);
Student3 s4 = new Student3("zhang",23);
Student3 s5 = new Student3("zhang",12);
tree.add(s1);
tree.add(s2);
评论