LinkedHashSet .equals() vs LinkedList .equals() with same elements but different order

Question

Consider the following SSCCE:

public static void main(String[] args) {
    LinkedHashSet<String> set1 = new LinkedHashSet<>();
    set1.add("Bob");
    set1.add("Tom");
    set1.add("Sam");
    LinkedHashSet<String> set2 = new LinkedHashSet<>();
    set2.add("Sam");
    set2.add("Bob");
    set2.add("Tom");

    System.out.println(set1);
    System.out.println(set2);
    System.out.println(set1.equals(set2));
}

This prints:

[Bob, Tom, Sam]
[Sam, Bob, Tom]
true

Yet if you change LinkedHashSet to LinkedList:

public static void main(String[] args) {
    LinkedList<String> set1 = new LinkedList<>();
    set1.add("Bob");
    set1.add("Tom");
    set1.add("Sam");
    LinkedList<String> set2 = new LinkedList<>();
    set2.add("Sam");
    set2.add("Bob");
    set2.add("Tom");

    System.out.println(set1);
    System.out.println(set2);
    System.out.println(set1.equals(set2));
}

it produces:

[Bob, Tom, Sam]
[Sam, Bob, Tom]
false

My question is one of clarification. Can someone help make sense of this? Why would a LinkedHashSet be considered equals whereas the same LinkedList would not? I'm assuming the definition of List and Set plays a role, but I'm not sure.

Basically, I'm saying if you consider the Sets to be the same, wouldn't you consider the Lists to be the same too? And vice-versa (assuming no duplicate elements)?

score 13 · Accepted Answer · answered Apr 25 '14 at 20:09

13

The guarantee that LinkedHashSet makes is about iteration order. However, it's still a Set and a set doesn't care about order in itself. A List on the other hand, does. A List with an element in 3rd position is not the same as another List with the same element in the 1st position.

Set javadoc for the equals(Object) method

Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set). This definition ensures that the equals method works properly across different implementations of the set interface.

The LinkedHashSet javadoc states

Hash table and linked list implementation of the Set interface, with predictable iteration order.

A LinkedHashSet is a Set. It has the same rules, ie. those that apply to the set ADT.

answered Apr 25 '14 at 20:09

Sotirios Delimanolis

274,122
60
696
724

1

But a `LinkedHashSet` does care about order, so shouldn't it have it's own `.equals()` method to determine order equality? – ryvantage Apr 25 '14 at 20:11
@ryvantage The order is only for iterating, not for what the `Set` represents. And, no, it doesn't have its own `equals` method. It inherits it from `AbstractSet`. – Sotirios Delimanolis Apr 25 '14 at 20:12
I guess my question was more of a _why_ question. "This definition ensures that the equals method works properly across different implementations of the set interface." That part really helps. Every implementation of `Set` must have the same standard. I'm still not sure why, though, but it's clear that LHS is just following the standards set in the `Set` definition of equals. It still seems logical to me that two `LinkedHashSet`s with different ordering would not be equal. Am I the only one? – ryvantage Apr 25 '14 at 20:25
2

@ryvantage These classes are meant to be implementations of [ADTs](http://en.wikipedia.org/wiki/Abstract_data_type). A set is one such data structure. It's defined as `an abstract data structure that can store certain values, without any particular order, and no repeated values.` In other words, the order is not important to the set. The order in `LinkedHashSet` is only important to the programmer, but doesn't take away from the definition of the set data structure. – Sotirios Delimanolis Apr 25 '14 at 20:27
@ryvantage Look at it from the other side. If you're depending on a library that has an API that returns `Set` and you apply some patch of that library to your application that is supposed to be internal bug fixes, and your application crashes and burns because the developer changed the implementation under the hood for internal reasons... would that seem logical to you? :) – Affe Apr 25 '14 at 20:37
@affe well my hope wasn't to change the implementation _now_ but just that at the outset, it seemed to me that with a `Linked` data struct the order mattered, thus two `LinkedHashSet`s with different orders should not be equal. But in hindsight after asking this question I can see the virtue of using `AbstractSet` to define equals and that the `Linked` portion of a data struct is strictly related to iteration order only. – ryvantage Nov 27 '17 at 23:47

Bojan Petkovic · Answer 2 · 2017-07-18T19:21:55.313

As mentioned above: LinkedHashSet extends HashSet which extends AbstractSet which implements equals method: https://docs.oracle.com/javase/8/docs/api/java/util/AbstractSet.html#equals-java.lang.Object-

Compares the specified object with this set for equality. Returns true if the given object is also a set, the two sets have the same size, and every member of the given set is contained in this set. This ensures that the equals method works properly across different implementations of the Set interface.

The easiest way to compare LinkedHashSet if order if important to you is to serialize it and compare them then:

    LinkedHashSet<Integer> reverseOrder = new LinkedHashSet<>();
    reverseOrder.add(2);
    reverseOrder.add(1);
    LinkedHashSet<Integer> ordered = new LinkedHashSet<>();
    ordered.add(1);
    ordered.add(2);
    System.out.println("Equals via set: " + ordered.equals(reverseOrder));
    System.out.println("Equals With Arrays: " + ordered.ordered.toString().equals(reverseOrder.ordered.toString()));

Result:

Equals via Set: true
Equals With Arrays: false

The `toArray` method returns a new array anyhow, and for arrays, the `equal` method checks for *reference equality* - so the code snippet does not really make sense (i.e. even if the order in both sets was the *same*, then the second output would still be `false` ...) — Marco13, Jul 18 '17 at 15:59
Marco13 good point, changing to serialize both lists then compare. — Bojan Petkovic, Jul 18 '17 at 19:37

LinkedHashSet .equals() vs LinkedList .equals() with same elements but different order

2 Answers2

Linked

Related