Why do two different HashSets with the same data have the same HashCode?

user_19355037 0
Viewed 114

I recently ran across a problem on leetcode which I solved with a nested hashset. This is the problem, if you're interested: https://leetcode.com/problems/group-anagrams/.

My intuition was to add all of the letters of each word into a hashset, then put that hashset into another hashset. At each iteration, I would check if the hashset already existed, and if it did, add to the existing hashset.

Oddly enough, that seems to work. Why do 2 hashsets share the same hashcode if they are different objects? Would something like if(set1.hashCode() == set2.hashCode()) doStuff() be valid code?

hashcode hashset java
2 Answers

This is expected. HashSet extends AbstractSet. The hashCode() method in AbstractSet says:

Returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of Object.hashCode.

This implementation iterates over the set, calling the hashCode method on each element in the set, and adding up the results.

Here's the code from AbstractSet:

public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

Why do 2 hashsets share the same hashcode if they are different objects?

With HashSet, the hashCode is calculated using the contents of the set. Since it's just numeric addition, the order of addition doesn't matter – just add them all up. So it makes sense that you have two sets, each containing objects which are equivalent (and thus should have matching hashCode() values), and then the sum of hashCodes within each set is the same.

Would something like if(set1.hashCode() == set2.hashCode()) doStuff() be valid code?

Sure.

EDIT: The best way of comparing two sets for equality is to use equals(). In the case of AbstractSet, calling set1.equals(set2) would result in individual calls to equals() at the level of the objects within the set (as well as some other checks).

user_113749570

Why do two different HashSets with the same data have the same HashCode?

Actually this is needed to fulfill another need that is specified in Java.

The equals method of Set is overridden to take in consideration that equals returns true (example a.equals(b)) if:

  • a is of type Set and b is of type Set.
  • both a and b have exactly the same size.
  • a contains all elements of b.
  • b contains all elements of a.

Since the default equals (which compares only the memory reference to be the same) is overridden for Set, according to java guidelines the hashCode method has to be overridden as well. So, this custom implementation of hashCode is provided in order to match with the custom implementation of equals.

In order to see why it is necessary to override hashCode method when the equals method is overridden, you can take a look at this previous answer of mine.

Why do 2 hashsets share the same hashcode if they are different objects

Because as explained above this is needed so that Set can have the custom functionality for equals that it currently has.

If you want to just check if a and b are different instances of set you can still check this with operators == and !=.

a == b -> true means a and b point to the same instance of Set in memory

a != b -> true means a and b point to different instances of Set in memory

user_72378840
Related