《Java初阶数据结构》----8.<java对象的比较总结>
目录
2.2 PriorityQueue采用的Comparble和Comparator两种方式。
三、使用PriorityQueue创建大小堆,解决TOPK问题
前言
大家好,我目前在学习java。之前也学了一段时间,但是没有发布博客。时间过的真的很快。我会利用好这个暑假,来复习之前学过的内容,并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论!!!
喜欢我文章的兄弟姐妹们可以点赞,收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦,我会持续更新滴,
望支持!!!!! 一起加油呀!!!!
语言只是工具,不能决定你好不好找工作,决定你好不好找工作的是你的能力!!!
学历本科及以上就够用了!!!
本篇博客主要讲解Java基础语法中的、
1.java中对象的比较
基本类型的比较、对象比较的问题(==与equals)、对象的比较 (三种常用方式)
2.集合框架中PriorityQueue的比较方式采用的Comparble和Comparator两种方式。
3.使用PriorityQueue创建大小堆,解决TOPK问题
一、Java对象的比较
1.1基本类型的比较
我们知道基本类型的数据可以直接比较大小
比较整型
int a = 10;
int b = 20;
System.out.println(a > b);
System.out.println(a < b);
System.out.println(a == b);
运行结果
false
true
false
比较字符型
char c1 = 'A';
char c2 = 'B';
System.out.println(c1 > c2);
System.out.println(c1 < c2);
System.out.println(c1 == c2);
运行结果
false
true
false
比较布尔型
boolean b1 = true;
boolean b2 = false;
System.out.println(b1 == b2);
System.out.println(b1 != b2);
运行结果
false
true
1.2 对象比较的问题(==与equals)
我们定义一张卡牌,第一张是红桃1的牌。第二张是红桃2牌。
第三张与第一张一样是红桃1。
class Card{
public int rank;//数值
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
public class Main {
public static void main(String[] args) {
Card card1 = new Card(1,"♥");
Card card2 = new Card(2,"♥");
Card card3 =card1;
System.out.println(card1 == card2);
System.out.println(card1 == card3);
}
}
//运行结果
false
true
card1和card2指向不同的对象。因此打印false。(哈希值不同)
card1和card3是指向同一个对象因此打印true(哈希值相同)
注意:我们不能使用大于号、小于号去比较。
因为Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。会编译报错。
可以使用==去比较,是因为用户实现自定义类型默认继承自Object类,而Object类中提供了equal方法,而==默认情况下调用的就是equals方法。
但是该方法的比较规则是:没有比较引用变量引用对象的内容,而是直接比较引用变量的地址(也就是哈希值)
Object中equals的实现源码。
//可以看到:直接比较的是两个引用变量的地址
public boolean equals(Object obj) {
return (this == obj);
}
1.3对象的比较 (三种常用方式)
1.重写equals方法
有些情况下,需要比较的是对象中的内容,比如:向优先级队列中插入某个对象时,需要对按照对象中内容来调整堆,那该如何处理呢?
我们需要重写父类的equals方法。
如下代码中,我们在Card类中重写父类Object的equals方法。
this的含义。this是本类Card的类型。而谁调用了这个方法,this就是谁的引用。
我们通过
return this.rank == c.rank && this.suit.equals(c.suit);
这个来比较对象里面的内容。
注意基本类型可以直接比较,但引用类型最好调用其equal方法。如比较字符串suit我们最好使用equals。而不是==。
因为 == 用于检查两个字符串变量是否引用同一个对象。String类的equals方法用来比较字符串的内容。。
class Card{
public int rank;//数值
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public boolean equals(Object obj) {
if (this == obj){
return true;
}
//如果obj为null或者obj不是Card的子类。返回false
if ((obj == null || !(obj instanceof Card))){
return false;
}
Card c = (Card) obj;
//this的含义。this本类Card的类型。而谁调用了这个方法,this就是谁的引用。
return this.rank == c.rank && this.suit.equals(c.suit);
//我们通过return这个来比较对象里面的内容。
}
}
public class Main {
public static void main(String[] args) {
Card card1 = new Card(1,"♥");
Card card2 = new Card(1,"♥");
Card card3 = new Card(2,"♥");
Card card4 =card1;
System.out.println(card1 == card2);
System.out.println(card1.equals(card2));
System.out.println(card1.equals(card3));
System.out.println(card1.equals(card4));
}
}
//运行结果
false
true
false
运行结果:
1.card1和card2。使用==比较。对象里面的内容虽然相同但是,引用地址不同。因此第一个是false。
2.card1和card2。使用我们重写的equals比较。对象里面的内容相同,因此返回true。
3.card1和card3。使用我们重写的equals比较。对象内容不同因此返回false
注:
一般重写 equals 就是上面演示的
1. 如果指向同一个对象,返回 true
2. 如果传入的为 null,返回 false
3. 如果传入的对象类型不是 Card,返回 false
4. 按照类的实现目标完成比较,例如这里只要花色和数值一样,就认为是相同的牌
重写基类equal的方式虽然可以比较,但缺陷是:equals只能按照相等进行比较,不能按照大于、小于的方式进行比较。
2.基于Comparble接口类的比较
Comparble是JDK提供的泛型的比较接口类,源码实现具体如下:
public interface Comparable<T> { public int compareTo(T o); }
返回值:
< 0: 表示 this 指向的对象小于 o 指向的对象
== 0: 表示 this 指向的对象等于 o 指向的对象
> 0: 表示 this 指向的对象大于 o 指向的对象
对用用户自定义类型,如我们的Card类。如果要想按照大小与方式进行比较时:在定义类时,实现Comparble接口即可,然后在类中重写compareTo方法。代码如下:
class Card implements Comparable<Card>{
public int rank;//数值
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
//这里我们根据数值比较。不管花色。
@Override
public int compareTo(Card o) {
if (o == null){
return 1;//>0.表示 this 指向的对象大于 o 指向的对象
}
return this.rank - o.rank;
//>0.表示 this 指向的对象大于 o 指向的对象
//=0.表示 this 指向的对象等于 o 指向的对象
//<0.表示 this 指向的对象小于 o 指向的对象
}
}
public class Main {
public static void main(String[] args) {
Card card1 = new Card(2,"♥");
Card card2 = new Card(1,"♥");
Card card3 = new Card(3,"♥");
Card card4 = new Card(3,"♥");
System.out.println(card1.compareTo(card2));
System.out.println(card1.compareTo(card3));
System.out.println(card3.compareTo(card4));
}
}
//运行结果:
1 //表示card1更大
-1 //表示card2更大
0 //表示card3和card4一样大
注意:
1.如下代码,是泛型比较,别忘了<Card>。
class Card implements Comparable<Card>
Compareble是java.lang中的接口类,可以直接使用。不需要导入包。
3.基于比较器比较(Comparator接口)
按照比较器方式进行比较,具体步骤如下:
1.用户自定义比较器类,实现Comparator接口。Comparator接口比较的源码如下:
public interface Comparator<T> { // 返回值: // < 0: 表示 o1 指向的对象小于 o2 指向的对象 // == 0: 表示 o1 指向的对象等于 o2 指向的对象 // > 0: 表示 o1 指向的对象大于 o2 指向的对象 int compare(T o1, T o2); }
2.与Comparble接口的比较方法的返回值类似。
3.重写Comparator中的compare方法
@Override public int compare(Card o1, Card o2) { if(o1 == o2){ return 0; } if (o1 == null){ return -1; } if(o2 == null){ return 1; } return o1.rank-o2.rank; }
注意:Comparator是java.util 包中的泛型接口类,使用时必须导入对应的包。
完整代码如下:
class Card{
public int rank;//数值
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
//定义一个比较器类,专门实现Card的比较
class CardComparator implements Comparator<Card> {
@Override
public int compare(Card o1, Card o2) {
if(o1 == o2){
return 0;
}
if (o1 == null){
return -1;
}
if(o2 == null){
return 1;
}
return o1.rank-o2.rank;
}
}
public class Main {
public static void main(String[] args) {
Card card1 = new Card(2,"♥");
Card card2 = new Card(1,"♥");
Card card3 = new Card(3,"♥");
Card card4 = new Card(3,"♥");
//定义比较器对象
CardComparator comparator = new CardComparator();
System.out.println(comparator.compare(card1,card2));
System.out.println(comparator.compare(card1,card3));
System.out.println(comparator.compare(card3,card4));
}
}
//运行结果
1//表示card1 > card2
-1//表示card1 < card3
0//表示card3 = card4
三种方式对比
二、集合框架中PriorityQueue的比较方式
2.1 PriorityQueue中插入对象
上一篇文章我们讲了优先级队列,优先级队列在插入元素时有个要求:插入的元素不能是null或者元素之间必须要能够进行比较,为了简单起见,我们只是插入了Integer类型,那优先级队列中能否插入自定义类型对象呢?
优先级队列底层使用堆,而向堆中插入元素时,为了满足堆的性质,必须要进行元素的比较。而如果Card没有实现比较的方法,则会抛出异常。
2.2 PriorityQueue采用的Comparble和Comparator两种方式。
集合框架中的PriorityQueue底层使用堆结构,因此其内部的元素必须要能够比大小
PriorityQueue采用了: Comparble和Comparator两种方式。
1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法
2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现 Comparator接口并覆写compare方法。
JDK中PriorityQueue的实现:
// JDK中PriorityQueue的实现:
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
// ...
// 默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 内部定义的比较器对象,用来接收用户实例化PriorityQueue对象时提供的比较器对象
private final Comparator<? super E> comparator;
// 用户如果没有提供比较器对象,使用默认的内部比较,将comparator置为null
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 如果用户提供了比较器,采用用户提供的比较器进行比较
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// ...
// 向上调整:
// 如果用户没有提供比较器对象,采用Comparable进行比较
// 否则使用用户提供的比较器对象进行比较
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// 使用Comparable
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
// 使用用户提供的比较器对象进行比较
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
}
三、使用PriorityQueue创建大小堆,解决TOPK问题
使用比较器创建小根堆
//使用比较器创建小根堆
class LessIntComp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
使用比较器创建大根堆
//使用比较器创建大根堆
class GreaterIntComp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
解决TOPK问题
public class TestDemo<E> {
//求最小的K个数,通过比较器创建大根堆
public static int[] smallestK(int[] array, int k) {
if(k <= 0) {
return new int[k];
}
GreaterIntComp greaterCmp = new GreaterIntComp();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp);
//先将前K个元素,创建大根堆
for(int i = 0; i < k; i++) {
maxHeap.offer(array[i]);
}
//从第K+1个元素开始,每次和堆顶元素比较
for (int i = k; i < array.length; i++) {
int top = maxHeap.peek();
if(array[i] < top) {
maxHeap.poll();
maxHeap.offer(array[i]);
}
}
//取出前K个
int[] ret = new int[k];
for (int i = 0; i < k; i++) {
int val = maxHeap.poll();
ret[i] = val;
}
return ret;
}
public static void main(String[] args) {
int[] array = {4,1,9,2,8,0,7,3,6,5};
int[] ret = smallestK(array,3);
System.out.println(Arrays.toString(ret));
}
}
原文地址:https://blog.csdn.net/m0_73456341/article/details/140722719
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!