27

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?

Gilles 'SO- stop being evil'
  • 104,111
  • 38
  • 209
  • 254
Faiyet
  • 5,341
  • 14
  • 51
  • 66

5 Answers5

45

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();
  }

}
Jonas Eicher
  • 1,413
  • 12
  • 18
  • 7
    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`. – Martin Nov 14 '13 at 21:25
  • 1
    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. – Jonas Eicher Dec 02 '13 at 12:55
11

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.

SharkAlley
  • 11,399
  • 5
  • 51
  • 42
  • 3
    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`). – Moinonime Jul 16 '13 at 20:01
  • 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. – SharkAlley Jul 20 '13 at 07:17
6

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.

Jeff Foster
  • 43,770
  • 11
  • 86
  • 103
3

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.

Paul Wintz
  • 2,542
  • 1
  • 19
  • 33
-3

There are PredicatedList or PredicatedSet in Apache Commons Collection

Grooveek
  • 10,046
  • 1
  • 27
  • 37