文章目录
一、元素的比较
1. 基本类型的比较
在Java中，基本类型的对象可以直接比较大小
public class TestCompare {
public static void main(String[] args) {
int a = 10;
int b = 20;
System.out.println(a > b);
System.out.println(a < b);
System.out.println(a == b);
char c1 = 'A';
char c2 = 'B';
System.out.println(c1 > c2);
System.out.println(c1 < c2);
System.out.println(c1 == c2);
boolean b1 = true;
boolean b2 = false;
System.out.println(b1 == b2);
System.out.println(b1 != b2);
}
}
2. 对象的比较
public class Test {
class Student {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
}
public static void main(String[] args) {
Student student1 = new Student("张三",19);
Student student2 = new Student("李四",20);
Student student3 = student1;
//System.out.println(student1 > student2);编译报错
System.out.println(student1 == student2);//不同对象 打印false
//System.out.println(student1 < student3);编译报错
System.out.println(student1 == student3);//相同对象 打印true
}
}
从编译结果可以看出，Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。 那为什么 == 可以比较？
因为：对于用户实现自定义类型，都默认继承自Object类，而Object类中提供了equal方法，而 == 默认情况下调
用的就是equal方法，但是该方法的比较规则是：没有比较引用变量引用对象的内容，而是直接比较引用变量的地址，但有些情况下该种比较就不符合题意。
// Object中equal的实现，可以看到：直接比较的是两个引用变量的地址
public boolean equals(Object obj) {
return (this == obj);
}
二、对象比较
1. 重写基类的equal
假设我们不重写，equal 来直接调用 equal来比较对象
public class Test {
class Student {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public static void main(String[] args) {
Student student1 = new Student("张三",1);
Student student2 = new Student("张三",1);
System.out.println(student1.equals(student2));
}
}
运行结果：
如果我们重写 equals 和 hashCode 方法
class Student {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
@Override
public boolean equals(Object o) {
//谁调用的equals谁就是this
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id == student.id &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, id);
}
}
public class Test {
public static void main(String[] args) {
Student student1 = new Student("张三",1);
Student student2 = new Student("张三",1);
System.out.println(student1.equals(student2));
}
}
运行结果：
如果不重写 equals 就会默认调用 Object 的 equals 方法，它就比较这两个对象是不是同一个对象。
很显然这两个学生类不是同一个对象，但重写 equals 方法后，就会按照我们重写的方式来比较相等
这里的学生类只要两个学生对象的姓名和学号相等就是相等的，放回true
如果自己要设计一个类，一定要实现封装，要有对应的 get和set 方法，并且重写 equals 、toString、hashCode方法。hashCode 方法会在后面的哈希表中讲到。
重写基类equal的方式虽然可以比较，但缺陷是：equal只能按照相等进行比较，不能按照大于、小于的方式进行比较。
2.基于Comparble接口类的比较
用户自定义比较器类，实现Comparator接口
如果以后引用类型要进行比较一定要用 compareTo方法，而且一定要实现 Comparable 接口
代码示例：
import java.util.*;
class Student implements Comparable<Student> {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
@Override
public int compareTo(Student o) {
return this.name.compareTo(o.name);
}
}
public class Test {
public static void main(String[] args) {
Student student1 = new Student("zhangsan",1);
Student student2 = new Student("lisi",5);
Student student3 = new Student("wangwu",4);
Student student4 = new Student("bit",2);
Student[] students = {student1,student2,student3,student4};
System.out.println(Arrays.toString(students));
System.out.println("============按姓名排序后=============");
Arrays.sort(students);
System.out.println(Arrays.toString(students));
}
}
运行结果：
在 sort 方法中会自动调用 compareTo 方法. compareTo 的参数是 Object , 其实传入的就是 Student 类型的对象
然后比较当前对象和参数对象的大小关系(按分数来算).
如果当前对象应排在参数对象之前, 返回小于 0 的数字;
如果当前对象应排在参数对象之后, 返回大于 0 的数字;
如果当前对象和参数对象不分先后, 返回 0
compareTo其实就是一个比较规则，如果以后自定义类型要进行比较一定要重写compareTo这个比较规则。但是如果这个比较规则已经被很多人使用，你突然想换个比较规则，如果修改比较规则必然会造成损失，所以这个方方法对类的侵入性太强了，并不是特别好，不建议使用。
3. Comparator 接口（比较器）
刚刚我们说 Comparable 对类的侵入性太强了，但有另外一个接口它十分灵活。就是Comparator 。
我们写了两个类，分别实现了 Comparator 这个接口，一个是用学号比较，一个是用姓名比较。我们叫做比较器。
import java.util.Comparator;
public class IdComparator implements Comparator<Student> {
//按学号比较
@Override
public int compare(Student o1, Student o2) {
return o1.getId()-o2.getId();
}
}
import java.util.Comparator;
public class NameComparator implements Comparator<Student> {
//按姓名比较
@Override
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
}
再来看原来的代码，我们的Student并没有实现任何接口，也没有重写compareTo 方法。
只是实例化了刚刚上面两个比较器，在用sort比较时，传过去了两个参数，一个是要排序的数组，一个是我们写的比较器对象。
import java.util.*;
class Student {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public class Test {
public static void main(String[] args) {
Student student1 = new Student("zhangsan",1);
Student student2 = new Student("lisi",5);
Student student3 = new Student("wangwu",4);
Student student4 = new Student("bit",2);
Student[] students = {student1,student2,student3,student4};
System.out.println(Arrays.toString(students));
NameComparator nameComparator = new NameComparator();
System.out.println("============按姓名排序后=============");
Arrays.sort(students,nameComparator);//比较器
System.out.println(Arrays.toString(students));
System.out.println("============按学号排序============");
IdComparator idComparator = new IdComparator();
Arrays.sort(students,idComparator);
System.out.println(Arrays.toString(students));
}
}
运行结果：
Comparator 接口，如果要进行比较只需要根据自己的需要单独写一个比较器就好了，并不像第一个接口那样直接写死了。想用直接 new就好了。
4. 三种方式对比
三、集合框架中PriorityQueue的比较方式
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：
Comparble和Comparator两种方式。先来了解一下PriorityQueue的实现。
1.构造方法
(1) 无参构造
无参构造，调用的是带有两个参数的构造方法，且堆的大小是11。比较规则是null也就是采用默认的比较规则，默认为小堆。
(2) 带有一个参数的构造方法
可以给堆指定大小，也可以给它指定比较规则。
(3) 带有两个参数的构造方法
构造堆时可以给它指定大小的同时也指定比较器。
2.入队（offer）
入队的同时会调用比较规则进行比较，如果用户没有提供比较器对象，采用Comparable进行比较。采用向上调整。
3.代码示例
- Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
- 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。
class Student {
private String name;
private int id;//学号
public Student(String name, int id) {
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public static void main(String[] args) {
Student student1 = new Student("zhangsan",1);
Student student2 = new Student("lisi",5);
Student student3 = new Student("wangwu",4);
Student student4 = new Student("bit",2);
Student student5 = new Student("hhh",9);
Student student6 = new Student("hhy",3);
PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
heap.offer(student1);
heap.offer(student2);
heap.offer(student3);
heap.offer(student4);
heap.offer(student5);
heap.offer(student6);
System.out.println(heap);
}
运行结果：
这里是从大到小排序，如果想要变成大根堆还有另外一种写法
这里我们采用一个类似匿名内部类的方式，在构造的同时重写了Comparator方法来构造了一个大根堆。如果要变成小根堆只需要修改 o1和o2的顺序
public static void main(String[] args) {
Student student1 = new Student("zhangsan",1);
Student student2 = new Student("lisi",5);
Student student3 = new Student("wangwu",4);
Student student4 = new Student("bit",2);
Student student5 = new Student("hhh",9);
Student student6 = new Student("hhy",3);
PriorityQueue<Student> maxHeap = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getId()-o1.getId();
}
});
maxHeap.offer(student1);
maxHeap.offer(student2);
maxHeap.offer(student3);
maxHeap.offer(student4);
maxHeap.offer(student5);
maxHeap.offer(student6);
System.out.println(maxHeap);
}
四、TopK 问题
Topk 问题：比如从100个元素中找到前10个最大的，或者找到前10个最小的。
思路：建一个大小为10的堆，找前10个最大建小堆，找前10个最小建大堆。
如果是小堆，那么堆顶元素肯定是最小的，如果堆满了。再来第11个元素比堆顶元素还要大，也就是说这个元素比这10个数据里最小的元素还要大，那么它肯定要放进来，前提是得把堆顶元素出出去。直到遍历完这100个数据。
代码示例：
10个元素找前3个最大
public static void main(String[] args) {
int[] array = {35,12,1,2,9,45,25,38,100,10};
//默认是小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(3);
for (int i = 0; i < array.length; i++) {
if(minHeap.size() < 3) {
minHeap.offer(array[i]);
}else{
int tmp = array[i];
if(tmp > minHeap.peek()) {
minHeap.poll();
minHeap.offer(tmp);
}
}
}
System.out.println(minHeap);
}
运行结果
10个元素找前3个最小
这里重写了比较规则，变成了大堆.
public static void main(String[] args) {
int[] array = {35,12,1,2,9,45,25,38,100,10};
//建大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(3, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < array.length; i++) {
if(maxHeap.size() < 3) {
maxHeap.offer(array[i]);
}else{
int tmp = array[i];
if(tmp < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(tmp);
}
}
}
System.out.println(maxHeap);
}
运行结果
