PriorityQueue 中的 CompareTo 和 equals

Question

我对所有“如果 c 对 S 施加的排序与 equals 不一致，则排序集（或排序映射）将表现得很奇怪”感到有点困惑。 Javadoc 中的警告。 我什至不再确定 PriorityQueue 是我需要的......

我的情况是这样的： 我有一个带有整数时间戳和其他一些字段的类事件。 我正在寻找一种数据结构，我可以在其中插入这些事件并按时间戳对事件进行排序。 不同的事件可以具有相同的时间戳，因此 - 如果我理解正确 - CompareTo 和 equals 将不一致。

我的第一个方法是让 Event 实现 Comparable 并提供compareTo，如下所示： 公共 int 比较（事件 e）{ 返回 this.timestamp - e.getTimestamp(); 我不明白

我应该如何解决这个问题。我考虑过创建一个自定义比较器，但是在比较器的 javadoc 中也弹出了关于奇怪行为的相同警告。 我不想插入事件的多个相等实例，我只想将它们按时间戳排序。

预先感谢您的帮助:)

编辑：
我只希望事件按时间戳排序。两个不同的事件很可能具有相同的时间戳。因此，compareTo 将返回 0，因为它们具有相同的时间戳并且对于排序而言是相等的。但 equals() 不会返回 true，因为它们是不同的事件。
我不确定，使用 PriorityQueue 是否正确。我查看了 SortedSet，但它对 CompareTo 和 equals 的一致性有相同的警告。
也许我从错误的角度来解决这个问题，我不知道......

Answer 1

不同的事件可以具有相同的时间戳

并按时间戳对事件进行排序

后一个要求有些不清楚。 Collection 的迭代器是否应该按排序顺序返回实例？或者，如果您在循环中 poll() ，集合是否应该按排序顺序返回其以前的内容？

iterator() 按顺序返回元素

PriorityQueue 的情况并非如此。您可以使用 SortedSet，但它们要求排序顺序与 equals 一致，正如您所注意到的，您无法实现这一点。据我所知，JDK 中没有 Collection 可以将其元素保持在排序顺序中，以实现认为某些元素相等的排序顺序。但是，您可以使用数组或 ArrayList，并在更改后使用 Arrays.sort 或 Collection.sort 对其进行手动排序。如果集合很少变化，这就是我选择的方法。如果它经常更改，您将不得不超越 JDK 或自己实现数据结构。

poll() 按排序顺序返回元素

这就是优先级队列的优点。 PriorityQueue 不要求 Comparator（或 Comparable 的实现）与 equals 一致；它的JavaDoc明确写道：

此队列的头是相对于指定顺序的最少元素。如果多个元素都具有最小价值，则头部就是这些元素之一 - 关系会被任意打破。

而且，JDK 6中PriorityQueue的实现仅使用equals来实现indexOf(E)、contains(Object) 和 remove(Object)，两者都不以任何方式使用比较器。因此，对于这个Collection来说，equals 的一致性实际上并不重要。

Comparable 与 Comparator

请注意，就 equals 的一致性而言，实现 Comparable 还是 Comparator 并不重要。对于 SortedSet，其中一个必须与 equals 一致，对于 PriorityQueue、Collection.sort 或 Arrays.sort ，两者都不必是。

TreeSet 以及与 equals 的一致性

摘自注释：

TreeSet 是一个 SortedSet，并明确声明仅依赖于compareTo/compare。它明确表示：“即使集合的顺序与 equals 不一致，集合的行为也是明确定义的；它只是未能遵守 Set 接口的一般契约。”

如果您报价，请报价所有相关部分。完整段落如下：

请注意，如果要正确实现 Set 接口，集合维护的顺序（无论是否提供显式比较器）必须与 equals 一致。 [...] 之所以如此，是因为 Set 接口是根据 equals 操作定义的，但 TreeSet 实例执行所有元素比较使用其 compareTo （或 compare）方法，因此从集合的角度来看，此方法认为相等的两个元素是相等的。即使集合的顺序与 equals 不一致，集合的行为也是明确定义的；它只是未能遵守 Set 接口的一般契约。

所以是的，它是明确定义的，但它并没有满足问题的要求：如果您传递 TreeSet.add 一个 Event ，其时间戳与另一个 >Event 在集合中，新的 Event 将被视为重复且不会添加，即使 Event 不相等 >。该问题询问如何对Collection进行排序；这不应该消除重复排序键的事件，不是吗？

Answer 2

如果 c 对 S 施加的排序与 equals 不一致，则排序集（或排序映射）将会表现得很奇怪。

这仅仅意味着当且仅当 e1.equals(e2) 则 e1.compareTo(e2) == 0。

当且仅当 !e1.equals(e2) 则 e1.compareTo(e2) != 0。

这就是您必须做的才能使两种方法保持一致。

因此，通过实现compareTo的方式，您还应该重写equals()为：

@Override
public boolean equals(Event e) {
    return this.timestamp.equals(e.timestamp);
}

注意：我不知道时间戳的数据类型，但如果它是原始类型，请使用==而不是equals() 用于重写方法。

Answer 3

当您实现Comparable时，您还应该重写equals(Object)，因为compareTo只应返回零当且仅当equals< /code> 返回 true。

当且仅当 equals(Object) 返回 true 时，compareTo(T) 才应返回零。

这还不是全部。由于另一个合同，当您覆盖 equals 时，您应该/必须覆盖 hashCode()。

相同的对象必须具有相同的哈希码。

public class Event implements Comparable<Event> {

    private long timestamp;

    public long getTimestamp() {
        return this.timestamp;
    }

    @Override
    public int compareTo(Event o) {
        return (this.timestamp < o.timestamp ? -1
                : (this.timestamp == o.timestamp ? 0 : 1));
    }

    @Override
    public int hashCode() {
        return (int) (this.timestamp ^ (this.timestamp >>> 32));
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Event) {
            return this.timestamp == ((Event) obj).timestamp;
        }

        return false;
    }

}

compareTo、equals 和 hashCode 实现取自您在 java.lang.Long 中看到的实现。您还可以通过 Eclipse 等 IDE 生成这些方法。

如果您希望在 equals 必须返回 false 时计算结果为 0（如另一条注释中所述），那么您必须实现 Comparator 而不是实现 Comparable。

public class EventComparator implements Comparator<Event>, Serializable {

    private static final long serialVersionUID = 1L;

    @Override
    public int compare(Event o1, Event o2) {
        return (o1.getTimestamp() < o2.getTimestamp() ? -1
                : (o1.getTimestamp() == o2.getTimestamp() ? 0 : 1));
    }

}