Different events can have the same timestamp.
and sorts events by label
The last requirement is somewhat fuzzy. Should the iterator collector return instances in sorted order? Or should the collection, if you poll() in a loop, return the old contents in sorted order?
iterator() returns items in order
This does not apply to a PriorityQueue . You can use a SortedSet , but this requires that the sort order is consistent with equals, which, as you correctly noted, you cannot achieve. As far as I know, there is no Collection in the JDK that saves its elements in sorted order for a sort order that considers some elements to be equal. However, you can use an array or ArrayList and sort it manually after the changes using Arrays.sort or Collection.sort . If the collection rarely changes, this is the approach I would choose. If it changes frequently, you will have to search outside the JDK or implement the data structure yourself.
poll() returns items in sorted order
What suits a priority queue. A PriorityQueue does not require a Comparator (or Comparable implementation) to conform to equalities; its JavaDoc clearly writes:
The head of this queue is the smallest element relative to the specified order. If several elements are attached to the smallest value, the head is one of these elements - the bonds break arbitrarily.
In addition, the PriorityQueue implementation in JDK 6 uses equals only to implement indexOf(E) , contains(Object) and remove(Object) , none of which use the comparator in any way. Therefore, for this Collection there can be no consistency with equals.
Comparison with Comparator
Note that it doesn't matter if you use Comparable or Comparator, as far as consistency with equals. For a SortedSet must either be consistent with equals, for a PriorityQueue , Collection.sort or Arrays.sort , none of them should be.
TreeSet and consistency with equals
From the comments:
TreeSet is a SortedSet and explicitly indicates that it relies only on compareTo / compare. It clearly states: "The behavior of a set is well defined, even if its order is not consistent with equals, it simply does not obey the general contract of the Set interface."
If you indicate, quote all relevant parts. The full paragraph reads:
Note that the order supported by the set (whether it be an explicit comparator) must be consistent with equals if it implements the Set interface correctly. [...] This is due to the fact that the Set interface is defined in terms of the equals operation, but the TreeSet instance performs all element comparisons using the compareTo (or compare ) method, so the two elements that are considered equal by this method are equal, from the point view of the multitude. The behavior of the set is well defined, even if its ordering does not match the equal; it simply does not obey the general contract of the Set interface.
So yes, itβs well defined, but it doesnβt fulfill what the question requires: if you pass TreeSet.add a Event with the same timestamp as another Event in the set, the new Event will be considered as a duplicate and will not be added. although Event not equal . The question asks about sorting Collection ; which should not exclude Events , which duplicates the sort key, should it not?