Java Set collection - override equals method

Question

Is there any way to override the the equals method used by a Set datatype? I wrote a custom equals method for a class called Fee. Now I have a LnkedList of Fee and I want to ensure that there are no duplicated entries. Thus I am considering using a Set insted of a LinkedList, but the criteria for deciding if two fees are equal resides in the overriden equals method in the Fee class.

If using a LinkedList, I will have to iterate over every list item and call the overriden equals method in the Fee class with the remaining entries as a parameter. Just reading this alone sounds like too much processing and will add to computational complexity.

Can I use Set with an overridden equals method? Should I?

Solution 1

As Jeff Foster said:

The Set.equals() method is only used to compare two sets for equality.

You can use a Set to get rid of the duplicate entries, but beware: HashSet doesn't use the equals() methods of its containing objects to determine equality.

A HashSet carries an internal HashMap with <Integer(HashCode), Object> entries and uses equals() as well as the equals method of the HashCode to determine equality.

One way to solve the issue is to override hashCode() in the Class that you put in the Set, so that it represents your equals() criteria

For Example:

class Fee {
      String name;

  public boolean equals(Object o) {
      return (o instanceof Fee) && ((Fee)o.getName()).equals(this.getName());
  }

  public int hashCode() {
      return name.hashCode();
  }

}

Solution 2

You can and should use a Set to hold an object type with an overridden equals method, but you may need to override hashCode() too. Equal objects must have equal hash codes.

For example:

public Fee{

    public String fi;

    public String fo;

    public int hashCode(){

        return fi.hashCode() ^ fo.hashCode();
    }

    public boolean equals(Object obj){

        return fi.equals(obj.fi) && fo.equals(obj.fo);
    }
}

(With null checks as necessary, of course.)

Sets often use hashCode() to optimize performance, and will misbehave if your hashCode method is broken. For example, HashSet uses an internal HashMap.

If you check the source code of HashMap, you'll see it depends on both the hashCode() and the equals() methods of the elements to determine equality:

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

If the hash is not generated correctly, your equals method may never get called.

To make your set faster, you should generate distinct hash codes for objects that are not equal, wherever possible.

Solution 3

Set uses the equals method of the object added to the set. The JavaDoc states

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

The Set.equals() method is only used to compare two sets for equality. It's never used as part of adding/remove items from the set.

Solution 4

One solution would be to use a TreeSet with a Comparator.

From the documentation:

TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

This approach would be much faster than using a LinkedList, but a bit slower than a HashSet (ln(n) vs n).

It's worth noting a one side effect of using TreeSet would be that your set is sorted.

View more solutions

Comments

[Moinonime]

I know it's an example, but you shouldn't use concatenation to generate the hashCode. Like you saide, the hashCode method may be called often, and string concatenation is a slow and expensive operation. A better way to do it would be to simply XOR the strings hashCode. For example : return fi.hashCode() ^ fo.hashCode(); Furthermore, your equals()method is a bit over-kill. You dont have to compare fi with fo, and then compare fo with fi. The Object Javadoc makes it clear that equals() method must be symmetric. Therefore, only performin fi.equals(fo) is enough (ignore null).

[SharkAlley]

Thanks Mathieu. I edited my answer to XOR the hash codes rather than concatenating the strings. I don't think your comment regarding the equals method is valid though. fi.equals(fo) would be a different comparison altogether, and not consistent with the hashCode method I defined.

[Martin]

A HashSet follows the Set contract which requires to use the equals() method to determine equality. But it makes use of the fact that an Object is required to have the same hashCode() if it equals() another object. You can have multiple objects with the same hashCode() value in a single HashSet.

[Jonas Eicher]

Good point Martin. I just verified that in a little test-app. If you add an object that neither equals NOR has the same hashCode as the set-objects it is added as a new one. I clarified that in my answer.

[Michael Scheper]

Could you elaborate on how this answers the OP? I'm looking for a way to ignore upper/lowercase for Set<String>.contains("foo")