上节课我们讲了优先级队列,优先级队列在插入元素时有个要求:插入的元素不能是null或者元素之间必须要能够进行比较,为了简单起见,我们只是插入了Integer类型,那优先级队列中能否插入自定义类型对象呢?
先来看一段代码:
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(1, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(); //先向这个优先级队列中插入一个元素 qu.offer(card1); //打印的结果为[Card{rank=1, suit='♦'}] System.out.println(qu); } }
可以看到此时打印的结果是好的,接下来继续看:当我们向这个堆中加入第二个自定义对象的时候,我们来看会发生什么把:
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(1, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(); //先向这个优先级队列中插入一个元素 qu.offer(card1); qu.offer(card2); System.out.println(qu); } }
此时我们会发现出现了类型转换异常
(ClassCastException):这是为什么呢?
此时我们点开我们报错的代码:
然后找到了对应的报错语句:
此处我们发现其强行将x转换成了Comparable类型,换到我们上面的代码中去相当于x就是我们的Card,而Card这个类型要是想实现类型转换至少应该继承我们的Comparable接口,并且还有一个问题,之前我们在讲优先级队列的时候提到过,我们每个元素再插入的时候都会调整成小根堆,调整成为小根堆的过程其实就是比较大小的过程,之前我们所有的代码插入的是对象是整数,整数非常容易比较大小,但是这次我们插入的是自定义对象,就拿我们card举例,当我们插入第二个自定义对象的时候,我们是比较花色还是比较牌的数字的大小,这个并没有告诉我们怎么比,所以最终当我们的优先级队列查看到第二个插入的元素的时候,需要构建小根堆,但是并没有告诉我们比较插入进来的对象的方式,最终导致了类型转换一吃昂,所以此时我们应该让Card类去实现我们的Comparable接口,并告诉我们比较的方式是什么.
并且大家要注意了:为什么我们之前插入一个整数的时候人家就自动每插入一个元素就可以自动比较大小并且建大/小堆呢?我们来看:
我们摁住Ctrl进入到Integer的源码中:
此时我们会发现人家Integer早已经实现了Comparable接口
此处我们提供两种方法来告诉我们比较的方式是什么:
1:Comparable接口
2:Comparator接口
下面我们来给出在优先级队列中插入一个自定义对象时为了防止类型转换异常的正确比较方式:
先来看我们的代码:
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 String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } @Override public int compareTo(Card o) { //此处是告诉我们按照牌的数值来比较,此时默认为小根堆 return this.rank - o.rank; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(2, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(); qu.offer(card2); qu.offer(card1); qu.offer(card3); //输出结果为[Card{rank=1, suit='♦'}, Card{rank=2, suit='♦'}, Card{rank=3, suit='♦'}] System.out.println(qu); }
注意事项:
1:首先因为我们向我们优先级队列中插入的是我们自定义的对象card,其有两个属性,一个是牌的值card,一个是牌的花色,上面的代码我们是先按照牌的值来进行比较的
2:当我们的card类实现了comparable接口后,就要重写我们的compareTo方法,当return this.rank - o.rank的时候,就代表我们每次向堆中插入card对象后,我们的堆是按照小根堆的形式进行调整的,所以比较方式也是按照小根堆的形式,比较的值就是我们card对象中rank的值
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 String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } @Override public int compareTo(Card o) { //此处是告诉我们按照牌的数值来比较,此时默认为大根堆 return o.rank - this.rank; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(2, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(); qu.offer(card2); qu.offer(card1); qu.offer(card3); //输出结果为[Card{rank=3, suit='♦'}, Card{rank=1, suit='♦'}, Card{rank=2, suit='♦'}] System.out.println(qu); } }
注意事项:
注意我们此处指定我们向优先级队列中插入的这个自定义对象是按照rank的值来进行比较的,同时我们还规定了这个堆每次在插入的时候是按照大根堆的形式调整的.
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(2, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(new Comparator<Card>() { @Override public int compare(Card o1, Card o2) { //根据rank值来比较 默认为小根堆 return o1.rank - o2.rank; } }); qu.offer(card2); qu.offer(card1); qu.offer(card3); //输出结果为[Card{rank=1, suit='♦'}, Card{rank=2, suit='♦'}, Card{rank=3, suit='♦'}] System.out.println(qu); } }
注意事项
此处我们是使用Comparator接口来实现的,注意与之前的不同。然后o1.rank - o2.rank代表默认建堆形式为小根堆
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(2, "♦"); Card card3 = new Card(3, "♦"); //创建一个优先级队列 Queue<Card> qu = new PriorityQueue<>(new Comparator<Card>() { @Override public int compare(Card o1, Card o2) { //根据rank值来比较 默认为小根堆 return o2.rank - o1.rank; } }); qu.offer(card2); qu.offer(card1); qu.offer(card3); //输出结果为[Card{rank=3, suit='♦'}, Card{rank=1, suit='♦'}, Card{rank=2, suit='♦'}] System.out.println(qu); } }
注意事项
此处我们是使用Comparator接口来实现的,注意与之前的不同。然后o2.rank - o1.rank代表默认建堆形式为大根堆
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 String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + '\'' + '}'; } @Override public int compareTo(Card o) { return o.rank - this.rank; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(2, "♦"); Card card3 = new Card(3, "♦"); //直接编译报错 System.out.println(card1 > card2); //false,因为在内存中的地址不相同 System.out.println(card1 == card2); //编译出错 System.out.println(card1 < card2); //结果为1 System.out.println(card1.compareTo(card2)); //结果为false //因为我们的Card类中并没有重写我们Object类中的equals方法,所以此处的equals方法调用的是Object类中的equals方法 System.out.println(card1.equals(card2)); } }
注意事项
1:从编译结果可以看出,Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。 那为什么==可以比较?
因为:对于用户实现自定义类型,都默认继承自Object类,而Object类中提供了equals方法,而==默认情况下调用的就是equals方法,但是该方法的比较规则是:没有比较引用变量引用对象的内容,而是直接比较引用变量的地址,但有些情况下该种比较就不符合题意
。
什么情况下就不符合题意呢?来看:
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(1, "♦"); Card card3 = new Card(3, "♦"); //结果为false System.out.println(card1.equals(card2)); } }
此时我们card1这个引用和card2这个引用所指向的对象我们会发现实际上是一张牌,但是因为这两个引用虽然逻辑上是一样的,但是在堆中却开辟了两个内存来存储这两个引用所指向的对象,而且此处的equals方法调用的是我们Object类中的equals方法,其比较方式为引用的比较,对应到上述的代码就是card1 == card2,故为false,但是我们明明是一张牌,为什么要返回false,我们想让它为true,就像字符串的equals方法一样比较其内容,不比较地址,那我们就需要在Card这个类中重写我们Object类中的equals方法,(字符串中之所以可以使用equals方法比较内容,是因为其在String类中重写了equals方法
)下面来看代码
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } //注意equals与hashcode方法是成对出现的,并且直接生成无需我们自己修改 @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Card card = (Card) o; return rank == card.rank && Objects.equals(suit, card.suit); } @Override public int hashCode() { return Objects.hash(rank, suit); } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(1, "♦"); Card card3 = new Card(3, "♦"); //结果为true System.out.println(card1.equals(card2)); } }
重写过后此时我们card1这个引用再去调用equals方法的时候就会直接比较内容是否相等.
并且注意当我们重写equals方法的时候我们会发现此处的equals方法与我们的hashcode方法一块出现了,这两个其实是经常搭配在一起出现的,并且这块的equals方法我们会发现人家帮我们已经写好了,我们根本无需再去自己编写逻辑了
2:对象的比较还可以使用compareTo方法,要注意使用compareTo方法的前提是我们的类要继承Comparable接口并且重写compareTo方法.
同时我们也可以使用Comparator接口来完成比较:来看代码:
public 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; } }
class Card { public int rank; // 数值 public String suit; // 花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } } public class TestDemo { public static void main(String[] args) { Card card1 = new Card(1, "♦"); Card card2 = new Card(1, "♦"); Card card3 = new Card(2, "♦"); CardComparator cardComparator = new CardComparator(); //结果为0 System.out.println(cardComparator.compare(card1, card2)); //结果为-1 System.out.println(cardComparator.compare(card2, card3)); //结果为1 System.out.println(cardComparator.compare(card3, card2)); } }
对于对象的比较其实一共有三种方式,第一种是覆写基类的equals方法,第二种是基于Comparble接口类的比较,第三种是基于比较器比较,也就是我们的Comparator接口,关于Comparator接口的比较既可以在类外声明一个类去定义比较方式,也可以像本文一样在类内定义比较方式,我们之前也写过关于Comparable接口与Comparator接口的博客,大家可以点击如下链接再去复习下:
点我进入博客