Java: to use contains in a ArrayList full of custom object should I override equals or implement Comparable/Comparator?

Question

I have an ArrayList full of these:

class TransitionState {

    Position positionA;
    Position positionB;

    int counter;

    public boolean equals (Object o){

        if (o instanceof TransitionState){

          TransitionState transitionState= (TransitionState)o;

          if ((this.positionA.equals(transitionState.positionA))
                  &&(this.positionB.equals(transitionState.positionB)))
          {
              return true;
          }
        }
     return false;

    }

    @Override
    public String toString() {

        String output = "Position A " + positionA.i+ " "+ positionA.j + " "+ positionA.orientation + " "+
                "Position B " + positionB.i + " "+ positionB.j + " "+ positionB.orientation;

        return output;
    }

}

class Position {

    int i;
    int j;
    char orientation;

    Position() {

    }


    void setIJ(int i, int j){
        this.i=i;
        this.j=j;
    }

    void setOrientation(char c){

        orientation = c;
    }

   public boolean equals(Object o){

        if(o instanceof Position){

          Position p = (Position)o;
          if((p.i==this.i)&&(p.j==this.j)&&(p.orientation==this.orientation))
          {
              return true;
          }
              else return false;

        }

            return false;
   }

} //end class Position

I query it with this:

 if(!transitionStatesArray.contains(newTransitionState)){  //if the transition state is new add and enqueue new robot positions

                 transitionStatesArray.add(newTransitionState); //marks as visited

I'm finding duplicate elements inside my transitionStatesArray, why is this?

I'm using these i,j and orientation values to fill unique values in a matrix, yet here I have a duplicate:

 S  .  N 
 *  *  * 
 .  D  D 


 E  .  O 
 *  *  * 
 .  D  D 


 N  .  S 
 *  *  * 
 .  D  D 


 S  .  N 
 *  *  * 
 .  D  D 

Solution 1

The List.contains(...) method is defined to use equals(Object) to decide if the argument object is "contained" by the list. So you need to override equals ... assuming that the default implementation is not what you need.

However, you need to be aware that List.contains(...) potentially tests the argument against every element in the list. For a long list, that's expensive. Depending on the details of your application, it may be better to use a different collection type (e.g. a HashSet, TreeSet or LinkedHashSet) instead of a List. If you use one of those, your class will need to override hashCode or implement Comparable, or you will need to create a separate Comparator ... depending on what you choose.

---

(A bit more advice on the alternatives ... since the OP is interested)

The performance of contains on a List type like ArrayList or LinkedList is O(N). The worst-case cost of a contains call is directly proportional to the list length.

For a TreeSet the worst-case performance of contains is proportional to log2(N).

For a HashSet or LinkedHashSet, the average performance of contains is a constant, independent of the size of the collection, but the worst-case performance is O(N). (The worst case performance occurs if you 1) implement a poor hashcode() function that hashes everything to a small number of values, or 2) tweak the "load factor" parameter so that the hash table doesn't automatically resize as it grows.)

The downside of using Set classes are:

• they are sets; i.e. you cannot put two or more "equal" objects into the collection, and
• they can't be indexed; e.g. there's no get(pos) method, and
• some of the Set classes don't even preserve the insertion order.

These issues need to be considered when deciding what collection class to use.

Solution 2

You probably need to implement hashCode(). In general you should always do this when overriding equals anyway.

From the collections docs:

This specification should not be construed to imply that invoking Collection.contains with a non-null argument o will cause o.equals(e) to be invoked for any element e. Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two elements. (The Object.hashCode() specification guarantees that two objects with unequal hash codes cannot be equal.) More generally, implementations of the various Collections Framework interfaces are free to take advantage of the specified behavior of underlying Object methods wherever the implementor deems it appropriate.

Comments

[Stephen C]

This assumes that the OP changes to use a different collection type. It is not relevant if he continues using ArrayList.

[verdesmarald]

Where does the specification of ArrayList.contains() guarantee a call to equals()? It is specified by List.contains() and Collection.contains(), both of which only guarantee the result is true iff the collection contains an element e such that ( o == null ? e == null : o.equals(e) ) is true. The implementation is free to use the same hashCode shortcutting as any other collection.

[Stephen C]

@veredesmarald - here - download.oracle.com/javase/1.5.0/docs/api/java/util/…

[verdesmarald]

As far as I can see that interface has the same contains contract as List and Collection... can you quote the specific part you are referring to? Note that requiring o == null ? e == null : o.equals(e) to be true is not the same as saying it will call equals. As noted in the summary on Collection, Collections Framework interfaces are free to take advantage of the specified behavior of underlying Object methods [...] In particular, we can use hashCode to short-circuit the comparison since Object guarantees o.Equals(e) must be false if o.hashCode != e.hashCode().

[Stephen C]

@veredesmarald - The javadoc for AbstractCollection.contains says "This implementation iterates over the elements in the collection, checking each element in turn for equality with the specified element." And that's the behaviour that the ArrayList code implements as well ...

[verdesmarald]

Checking for equality can still be implemented as if (o.hashCode() == e.hashCode() && o.equals(e)). Maybe that's not the way it is implemented right now, but relying on the current implementation is not a great idea. I'd rather just take the 10 seconds it takes to generate a hashCode method, and save all the headaches later on.

[Stephen C]

A general List<E> implementation that did that would be a mistake. For many element classes, hashCode will (on average) be more expensive than equals.