Search code examples
javaequalspriority-queuehashcode

.equals() on a PriorityQueue returns unexpected results

I'm sorry if this is a dumb question (especially for someone who has developed in java for over 4 years) or if it has been answered (I've searched stack overflow and despite the simplicity of the problem, I couldn't find a duplicate) but I created two priority queues and wanted to check if they contain exactly the same elements in exactly the same order. However, I was returned false when I called .equals() on two seemingly equal priority queues. I would expect this much from a direct comparison (==) but not from the .equals() method. I've looked on java docs and they don't provide an explanation for this behavior.

To test out this behavior I ran the following code segments:

PriorityQueue<Character> window = new PriorityQueue<>();
PriorityQueue<Character> base = new PriorityQueue<>();
System.out.println(window.equals(base));
System.out.println(base.equals(base));
window.offer('a');
window.offer('b');
base.offer('a');
base.offer('b');
System.out.println(window.equals(base));

And the output was:

false
true
false

However, I expected:

true
true
true

I have overridden equals methods before, so if this is something I must do, I can handle that, but I was just very taken aback by the results. I know I could convert my PriorityQueue to a string or an array, and then compare them, but that defeats the entire point of using a PriorityQueue (not to mention all the excess space it will take up).

Solution

  • The Javadoc for PriorityQueue shows that neither PriorityQueue nor any of its superclasses provide an implementation of equals(), and thus it inherits the one from Object.

    Thus you get only reference equality, not contents equality.

    As to implementing your own equals(), this looks complex for several reasons:

    • Queue implements iterable() but the iterator is not guaranteed to return items in any particular order. So equals() must deal with order differences in otherwise identical queues.
    • You could add the items to a Set, but if you have items that are duplicates (according to their equals()) then you need to handle that.

    This is why the Javadoc contains the statement:

    The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).