6

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

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

我的第一种方法是让 Event 实现 Comparable 并像这样提供 compareTo： public int compareTo(Event e) { return this.timestamp - e.getTimestamp(); }

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

在此先感谢您的帮助 ：）

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

4

3 回答 3

5

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

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

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

iterator()按顺序返回元素

对于PriorityQueue. 您可以使用 a SortedSet，但那些要求排序顺序与 equals 一致，正如您正确指出的那样，您无法实现。据我所知，CollectionJDK 中没有将其元素保持排序顺序的排序顺序，即认为某些元素相等。但是，您可以使用数组 or ，并在更改后使用orArrayList手动对其进行排序。如果集合很少更改，这是我会选择的方法。如果它经常更改，您将不得不超越 JDK 或自己实现数据结构。Arrays.sortCollection.sort

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

这就是优先队列的好处。APriorityQueue不要求Comparator（或实现Comparable）与equals一致；它的 JavaDoc 清楚地写道：

此队列的头部是相对于指定排序的最小元素。如果多个元素以最低值绑定，则头部是这些元素之一——绑定被任意打破。

此外，PriorityQueueJDK 6中的实现equals仅用于实现indexOf(E),contains(Object)和remove(Object)，两者都不以任何方式使用比较器。所以真的没有办法与 equals 保持一致对此很重要Collection。

可比与比较器

请注意，就与 equals 的一致性而言，实现 Comparable 或 Comparator 并不重要。对于 a SortedSet，要么必须与 equals 一致，对于 a PriorityQueue，Collection.sort要么Arrays.sort，都不必。

TreeSet并与equals

从评论中删除：

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

如果您引用，请引用所有相关部分。整段内容如下：

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

所以是的，它是明确定义的，但它没有做问题所要求的：如果您传递TreeSet.add的时间戳与集合中的Event另一个时间戳相同Event，那么新的Event将被视为重复而不是添加，即使Events 是不是equal。问题询问关于排序 a Collection; 那不应该消除Events重复的排序键，不是吗？

于 2011-06-25T17:12:37.953 回答
4

如果 c 对 S 施加的排序与 equals 不一致，则排序集（或排序映射）将表现异常。

那只是意味着当且仅当e1.equals(e2)then e1.compareTo(e2) == 0。

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

这就是你必须做的，以使这两种方法保持一致。

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

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

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

于 2011-06-25T14:06:51.290 回答
0

当您实现时Comparable，您还应该覆盖equals(Object)，因为compareTo仅当且仅当equals返回 true 时才应返回零。

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

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

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

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实现。您还可以通过 Eclipse 等 IDE 生成这些方法。hashCodejava.lang.Long

如果您希望在 equals 必须返回 false（如另一条评论中所述）时将 evalTo 评估为 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));
    }

}
于 2011-06-25T14:14:40.070 回答