博客数据结构-7.Java. 对象的比较

数据结构-7.Java. 对象的比较

数栈君发表于 2025-01-20 14:26 133 0

1. PriorityQueue中插入对象

上篇文章我们介绍了优先级队列，优先级队列在插入元素时有个要求：插入的元素不能是 null 或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了 Integer 类型，那优先级队列中能否插入自定义类型对象呢？

class Card {
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
}
public class TestPriorityQueue {
    public static void TestPriorityQueue()
    {
        PriorityQueue<Card> p = new PriorityQueue<>();
        p.offer(new Card(1, "♠"));
        p.offer(new Card(2, "♠"));
    }
    public static void main(String[] args) {
        TestPriorityQueue();
    }
}

优先级队列底层使用堆，而向堆中插入元素时，为了满足堆的性质，必须要进行元素的比较，而此时 Card 是没有办法直接进行比较的，因此抛出异常。

2.元素的比较

2.1 基本类型的比较

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.2 对象比较的问题

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);
    }
}

3. 对象的比较

有些情况下，需要比较的是对象中的内容，比如：向优先级队列中插入某个对象时，需要按照对象中内容来调整堆，那该如何处理呢？

3.1 重写父类(Object)的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 o) {
        //自己和自己比较
        if(this == o) {
            return true;
        }
        //o如果是null对象, 或者o不是Card的子类
        if(o == null || !(o instanceof Card)) {
            return false;
        }
        // 注意基本类型可以直接比较，但引用类型最好调用其equal方法
        Card c = (Card)o;
        return rank == c.rank
                && suit.equals(c.suit);
    }
}

注意：一般重写 equals 的套路就是上面演示的, (多写几遍, 记住就行!!!)
1. 如果指向同一个对象，返回 true
2. 如果传入的为 null ，返回 false
3. 如果传入的对象类型不是 Card ，返回 false
4. 按照类的实现目标完成比较，例如这里只要花色和数值一样，就认为是相同的牌
5. 注意下调用其他引用类型的比较也需要 equals ，例如这里的 suit 的比较
重写父类 equal() 的方式虽然可以比较，但缺陷是： equal 只能按照相等进行比较，不能按照大于、小于的方式进行比较。

3.2 基于Comparble接口类的比较

Comparble 是 JDK 提供的泛型的比较接口类，源码实现具体如下:

public interface Comparable<E> {
// 返回的值表示的意思:
// < 0: 表示 this 指向的对象小于 o 指向的对象
// == 0: 表示 this 指向的对象等于 o 指向的对象
// > 0: 表示 this 指向的对象大于 o 指向的对象
int compareTo(E o);
}

对用用户自定义类型，如果要想按照大小与方式进行比较时：在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

public class Card implements Comparable<Card>{
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    // 先根据数值比较，不管花色
    // 这里我们认为 null 是最小的
    @Override
    public int compareTo(Card o) {
        if (o == null) {
            return 1;
        }
        return this.rank - o.rank;
    }

    public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");

        System.out.println(p.compareTo(o)); // == 0，表示牌相等
        System.out.println(p.compareTo(q)); // < 0，表示 p 比较小
        System.out.println(q.compareTo(p)); // > 0，表示 q 比较大

    }

}

Compareble 是 java.lang 中的接口类，可以直接使用。

3.3 基于比较器比较

按照比较器方式进行比较，具体步骤如下：

用户自定义比较器类，实现 Comparator 接口

public interface Comparator<T> {
// 返回值表示不同意思:
// < 0: 表示 o1 指向的对象小于 o2 指向的对象
// == 0: 表示 o1 指向的对象等于 o2 指向的对象
// > 0: 表示 o1 指向的对象等于 o2 指向的对象
int compare(T o1, T o2);
}

注意：区分 Comparable 和 Comparator 。

复写 Comparator 中的 compare 方法

public class Card {
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
}
public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");
        // 定义比较器对象
        CardComparator cmptor = new CardComparator();
        // 使用比较器对象进行比较
        System.out.println(cmptor.compare(p, o)); // == 0，表示牌相等
        System.out.println(cmptor.compare(p, q)); // < 0，表示 p 比较小
        System.out.println(cmptor.compare(q, p)); // > 0，表示 q 比较大

    }
}

class CardComparator implements Comparator<Card> {
    // 根据数值比较，不管花色
// 这里我们认为 null 是最小的
    @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 包中的泛型接口类，使用时必须导入对应的包, 再重写compare()方法即可.

3.4 三种方式对比

4. 集合框架中PriorityQueue的比较方式

集合框架中的 PriorityQueue 底层使用堆结构，因此其内部的元素必须要能够比大小， PriorityQueue 采用了：
Comparble和Comparator 两种方式。
1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现 Comparator接口并覆写compare方法。
// PriorityQueue 源码自行在 IDEA 读就行. 重点还是理解掌握上面的两种方式.

// 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;
}
}

5. 使用PriorityQueue创建大小堆，解决TOPK问题

top-k 问题：最大或者最小的前 k 个数据。比如：世界前 500 强公司
链接:
面试题 17.14. 最小K个数 - 力扣（LeetCode）
容易想到的常规做法:

上图两种做法虽然很方便但是效率不高.
换种做法:
题目要求的是前 k 个最小的数组
我们不妨先把原数组前 k 个元素建大堆, 然后将大堆的堆顶元素top 与原数组剩余的元素 [ i ] 进行比较, 若是 top较大则 top出堆 [ i ] 入堆. 否则就只让 i++即可. 这样一来比较完之后堆中的 k 个元素必然是前 k 个最小的元素.
同理, 若是题目要求前 k 个最大的数组, 则建小堆, top较小则出堆......
总结成下图:

下面给出OJ面试的答案, 一定要先自己写, 写不出来了再看答案.

//由于PriorityQueue默认是小根堆, 所以需要实现比较器, 重写compare方法,来创建大根堆.
class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) return ret;

        //创建大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int j = k; j < arr.length; j++) {
            int top = priorityQueue.peek();
            if(top > arr[j]) {
                //top大, 出堆, 小的元素入堆
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }
        for(int i = 0;i < k;i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

时间复杂度分析:

本文系转载，版权归原作者所有，如若侵权请联系我们进行删除！

《数据资产管理白皮书》下载地址：https://www.dtstack.com/resources/1073/?src=bbs

《行业指标体系白皮书》下载地址：https://www.dtstack.com/resources/1057/?src=bbs

《数据治理行业实践白皮书》下载地址：https://www.dtstack.com/resources/1001/?src=bbs

《数栈V6.0产品白皮书》下载地址：https://www.dtstack.com/resources/1004/?src=bbs

想了解或咨询更多有关袋鼠云大数据产品、行业解决方案、客户案例的朋友，浏览袋鼠云官网：https://www.dtstack.com/?src=bbs

同时，欢迎对大数据开源项目有兴趣的同学加入「袋鼠云开源框架钉钉技术群」，交流最新开源技术信息，群号码：30537511，项目地址：https://github.com/DTStack

java与大数据结合开发 java 大数据开发大数据基础平台大数据平台大数据大数据开源大数据采集 Java对象的比较 java 数据结构

0条评论

上一篇：高并发访问处理

下一篇：数据库连接池最佳实践

我要提问

分享经验

社区公告

大数据领域最专业的产品&技术交流社区，专注于探讨与分享大数据领域有趣又火热的信息，专业又专注的数据人园地

最新活动更多