Comapring Objects of TreeSet and HashSet

Question

List<String> list = Arrays.asList("Snehal", "Masne", "Anything", "Else");

HashSet<String> hashSet = new HashSet<String>(list);
TreeSet<String> treeSet = new TreeSet<String>(list);

System.out.println("Equality  = " + hashSet.equals(treeSet));  // returns True

How the equals() is evaluating the result by comparing diff structures? How come its true? Is just Hashcode being compared? If so, how come its same?

"Is just Hashcode being compared" No. Hash codes are not and should not, by definition, be used to test equality. Hash codes are within a finite space (32 bits) and [hash collisions are possible](https://learncryptography.com/hash-functions/hash-collision-attack). — Michael, Dec 05 '17 at 10:38
@Michael nitpick: in this case since `HashSet` is based on a `HashMap`, hashCode will be called. — Eugene, Dec 05 '17 at 11:18
@Eugene Of course you're right, it is called. But that alone is not enough to guarantee equality and any matching hash of the elements will be followed by a call to `equals`. Sorry if that wasn't clear. — Michael, Dec 05 '17 at 11:28

score 4 · Answer 1 · answered Dec 05 '17 at 10:33

The Javadoc of Set has the answer:

boolean java.util.Set.equals(Object o)

Compares the specified object with this set for equality. 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.

As long as the two Sets have the exact same elements, it doesn't matter if they have different implementations of the Set interface.

score 2 · Answer 2 · edited Dec 05 '17 at 11:38

Underneath AbstractSet#equals calls containsAll. For every single element this method checks it's presence in the other Set:

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

This will call HashSet#contains that looks like this:

public boolean contains(Object o) {
    return map.containsKey(o);
}

Notice that since HashSet is nothing more then a HashMap with a dummy value - hashCode does gets called, but only to find the bucket of where it might be - the comparison is still using equals

Comapring Objects of TreeSet and HashSet

2 Answers2