【数据结构】Java对象的比较

文章目录一、Java对象比较的痛点1.1 基本类型直接比较简单直接1.2 引用类型二、Java对象的三种比较方式2.1 方式一覆写Object的equals方法2.2 方式二实现Comparable接口2.3 方式三实现Comparator接口三种比较方式对比三、PriorityQueue中的对象比较Comparable与Comparator3.1 底层实现原理3.2 用Comparable实现PriorityQueue3.3 用Comparator实现PriorityQueue一、Java对象比较的痛点在Java中数据类型分为基本类型int、char、boolean等和引用类型自定义类、String等1.1 基本类型直接比较简单直接基本类型的比较无需额外操作可直接使用、、、!等运算符因为JVM已为其定义了明确的数值大小规则。publicstaticvoidmain(String[]args){inta10,b20;System.out.println(ab);// true数值直接比较charc1A,c2B;System.out.println(c1c2);// falseASCII码值比较booleanb1true,b2false;System.out.println(b1b2);// false布尔值直接比较}1.2 引用类型对于自定义引用类型直接使用、会编译报错而的行为也并非比较对象内容而是比较引用地址。publicstaticvoidmain(String[]args){Students1newStudent(daisy,18);Students2newStudent(rare,20);Students3s1;// s3指向s1的地址// System.out.println(s1 s2); // 编译报错引用类型不能用比较System.out.println(c1c2);// falses1和s2指向不同对象地址不同System.out.println(c1c3);// trues1和s3指向同一对象地址相同}所有自定义类默认继承自Object类而Object的equals方法底层就是用实现的本质是比较引用地址// Object类的equals方法源码publicbooleanequals(Objectobj){return(thisobj);// 直接比较引用地址}但实际开发中我们往往需要比较“对象内容”此时就需要手动实现比较逻辑。二、Java对象的三种比较方式2.1 方式一覆写Object的equals方法equals方法的作用是判断两个对象“内容是否相等”覆写套路先判断自比较若this o直接返回true同一对象内容必然相同若o null或o不是当前类的实例返回false强转类型将o强转为当前类再比较关键属性Card的rank和suit引用类型属性需用equals比较例如String不能用。示例代码classCard{publicintrank;publicStringsuit;publicCard(intrank,Stringsuit){this.rankrank;this.suitsuit;}Overridepublicbooleanequals(Objecto){// 1. 自比较if(thiso)returntrue;// 2. 排除null和类型不匹配if(onull||!(oinstanceofCard))returnfalse;// 3. 强转并比较关键属性Cardcard(Card)o;// 4. 基本类型用引用类型用equalsreturnrankcard.ranksuit.equals(card.suit);}}局限性仅能判断“相等与否”无法比较“大小关系”如判断一张牌是否比另一张大因此不适用于需要排序的场景如PriorityQueue。2.2 方式二实现Comparable接口Comparable是Java.lang包下的泛型接口定义了对象的自然排序规则。通过实现该接口并覆写compareTo方法可让类本身具备“大小比较能力”属于内部比较。compareTo返回值返回值 0当前对象this小于目标对象o返回值 0当前对象等于目标对象返回值 0当前对象大于目标对象。示例代码Card按数值比较// 实现Comparable接口指定比较的类型为CardclassCardimplementsComparableCard{publicintrank;publicStringsuit;publicCard(intrank,Stringsuit){this.rankrank;this.suitsuit;}// 覆写compareTo按rank从小到大排序OverridepublicintcompareTo(Cardo){if(onull)return1;// 约定null为最小returnthis.rank-o.rank;// 数值差即比较结果}}优缺点优点一旦实现类的所有实例都自带排序能力无需额外代码适合固定排序规则的场景缺点侵入性强类定义时必须实现接口若需修改排序规则需修改类源码灵活性低。2.3 方式三实现Comparator接口Comparator是Java.util包下的泛型接口属于外部比较器——无需修改目标类的源码只需单独实现一个比较器类定义比较规则。compare返回值与Comparable一致返回值 0o1小于o2返回值 0o1等于o2返回值 0o1大于o2。示例代码Card按数值比较的外部比较器// 1. 定义比较器类实现ComparatorCardclassCardComparatorimplementsComparatorCard{Overridepublicintcompare(Cardo1,Cardo2){if(o1o2)return0;if(o1null)return-1;// 约定null为最小if(o2null)return1;returno1.rank-o2.rank;// 按数值从小到大排序}}// 2. 目标类Card无需修改classCard{publicintrank;publicStringsuit;publicCard(intrank,Stringsuit){this.rankrank;this.suitsuit;}}优缺点优点无侵入性不修改目标类可定义多个比较器如“按数值排序”“按花色排序”灵活性极高适合“动态排序规则”的场景缺点每次比较需创建比较器对象若比较逻辑复杂会增加少量代码量。三种比较方式对比比较方式覆写/实现的方法特点适用场景覆写Object.equalsequals(Object o)仅比较相等性无侵入性只需判断对象内容是否相同的场景实现Comparable接口compareTo(E o)内部比较侵入性强固定排序规则类的排序规则固定实现Comparator接口compare(T o1, T o2)外部比较无侵入性灵活切换排序规则需动态修改排序规则三、PriorityQueue中的对象比较Comparable与ComparatorPriorityQueue优先级队列是Java集合框架中典型的需要对象比较的场景。底层基于堆结构插入元素时必须通过比较调整堆以保证小根堆或大根堆的性质。PriorityQueue支持两种比较方式优先级Comparator外部 Comparable内部。3.1 底层实现原理PriorityQueue的源码中通过comparator成员变量存储外部比较器插入元素时通过offer方法触发堆的向上调整并根据是否有外部比较器选择不同的比较逻辑publicclassPriorityQueueEextendsAbstractQueueE{privatefinalComparator?superEcomparator;// 外部比较器privateObject[]queue;// 存储堆元素的数组// 构造方法1无外部比较器使用Comparable内部比较publicPriorityQueue(){this(11,null);// 默认容量11comparator为null}// 构造方法2传入外部比较器使用Comparator外部比较publicPriorityQueue(intinitialCapacity,Comparator?superEcomparator){this.queuenewObject[initialCapacity];this.comparatorcomparator;}// 插入元素触发向上调整publicbooleanoffer(Ee){// ... 省略空判断 ...siftUp(size,e);// 向上调整堆returntrue;}// 向上调整根据是否有外部比较器选择逻辑privatevoidsiftUp(intk,Ex){if(comparator!null){siftUpUsingComparator(k,x);// 用外部比较器}else{siftUpComparable(k,x);// 用内部Comparable}}// 内部比较ComparableprivatevoidsiftUpComparable(intk,Ex){Comparable?superEkey(Comparable?superE)x;while(k0){intparent(k-1)1;// 父节点索引Objectequeue[parent];if(key.compareTo((E)e)0)break;// 用compareTo比较queue[k]e;kparent;}queue[k]key;}// 外部比较ComparatorprivatevoidsiftUpUsingComparator(intk,Ex){while(k0){intparent(k-1)1;Objectequeue[parent];if(comparator.compare(x,(E)e)0)break;// 用comparator比较queue[k]e;kparent;}queue[k]x;}}3.2 用Comparable实现PriorityQueue如果自定义类实现了Comparable接口PriorityQueue会自动使用其compareTo方法作为排序规则默认小根堆// Card实现Comparable按数值从小到大classCardimplementsComparableCard{publicintrank;publicStringsuit;publicCard(intrank,Stringsuit){this.rankrank;this.suitsuit;}OverridepublicStringtoString(){returnranksuit;// 便于打印}OverridepublicintcompareTo(Cardo){returnthis.rank-o.rank;// 小根堆数值小的优先}}// 测试PriorityQueuepublicclassTestPriorityQueue{publicstaticvoidmain(String[]args){PriorityQueueCardpqnewPriorityQueue();pq.offer(newCard(3,♠));pq.offer(newCard(1,♥));pq.offer(newCard(2,♦));// 输出1♥ 3♠ 2♦堆的物理存储逻辑上是小根堆弹出时按从小到大System.out.println(pq);// 弹出元素小根堆每次弹出最小元素while(!pq.isEmpty()){System.out.print(pq.poll() );// 输出1♥ 2♦ 3♠}}}3.3 用Comparator实现PriorityQueue若需修改排序规则大根堆无需修改Card类只需传入自定义的Comparatorimportjava.util.Comparator;importjava.util.PriorityQueue;// 自定义大根堆比较器按数值从大到小classCardMaxComparatorimplementsComparatorCard{Overridepublicintcompare(Cardo1,Cardo2){returno2.rank-o1.rank;// 大根堆o2.rank大则返回正o1排在后面}}classCard{publicintrank;publicStringsuit;publicCard(intrank,Stringsuit){this.rankrank;this.suitsuit;}OverridepublicStringtoString(){returnranksuit;}}// 测试大根堆publicclassTestPriorityQueueMax{publicstaticvoidmain(String[]args){// 传入外部比较器创建大根堆PriorityQueueCardmaxHeapnewPriorityQueue(newCardMaxComparator());maxHeap.offer(newCard(3,♠));maxHeap.offer(newCard(1,♥));maxHeap.offer(newCard(2,♦));// 弹出元素大根堆每次弹出最大元素while(!maxHeap.isEmpty()){System.out.print(maxHeap.poll() );// 输出3♠ 2♦ 1♥}}}