Java: ¿para usar contiene en una ArrayList llena de objetos personalizados si debo anular iguales o implementar Comparable/Comparator?

Question

tengo un ArrayList completa de estos:

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 

que consultarlo con esto:

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

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

estoy encontrando elementos duplicados dentro de mi transitionStatesArray, ¿por qué es esto?

estoy usando estos valores i, j y orientación para llenar valores únicos en una matriz, sin embargo, aquí tengo un duplicado:

S . N 
* * * 
. D D 


E . O 
* * * 
. D D 


N . S 
* * * 
. D D 


S . N 
* * * 
. D D 

Answer 1

List.contains(...) El método se define a utilizar equals(Object) para decidir si el objeto argumento está "contenido" de la lista. Por lo tanto, debe sobrescribir equals ... suponiendo que la implementación predeterminada no es la que necesita.

Sin embargo, debe tener en cuenta que List.contains(...) potencialmente prueba el argumento contra cada elemento en la lista. Para una larga lista, es caro. Según los detalles de su aplicación, puede ser mejor usar un tipo de colección diferente (por ejemplo, HashSet, TreeSet o LinkedHashSet) en lugar de List. Si usa uno de ellos, su clase deberá anular hashCode o implementar Comparable, o tendrá que crear un Comparator por separado ... dependiendo de lo que elija.

---

(Un poco más consejos sobre las alternativas ... ya que el PO está interesado)

El rendimiento de contains en un tipo List como ArrayList o LinkedList es O(N). El costo en el peor de los casos de una llamada contains es directamente proporcional a la longitud de la lista.

Para un TreeSet el peor de los casos de contains es proporcional a log2(N).

Para una HashSet o LinkedHashSet, el rendimiento promedio de contains es una constante, independiente del tamaño de la colección, pero el rendimiento del peor caso es O(N). (El peor de los casos ocurre si 1) implementa una función hashcode() deficiente que hace que todo se reduzca a un pequeño número de valores, o 2) modifique el parámetro "factor de carga" para que la tabla hash no cambie de tamaño automáticamente a medida que crece).

La desventaja de usar Set clases son:

• son conjuntos; es decir, no puede poner dos o más objetos "iguales" en la colección, y
• no se pueden indexar; p.ej. no hay un método get(pos) y
• algunas de las clases Set ni siquiera conservan el orden de inserción.

Estos problemas deben tenerse en cuenta al decidir qué clase de colección usar.

Answer 2

es probable que necesite para implementar hashCode(). En general, siempre debes hacer esto cuando la anulación es igual a igual.

Desde el collections docs:

Esta especificación no debe ser interpretado dar a entender que la invocación de Collection.contains con un no nulo argumento o causará o.equals (E) para ser invocada para cualquier elemento e. Las implementaciones son libres de implementar optimizaciones mediante las cuales se evita la invocación de , por ejemplo, por primero comparando los códigos de hash de los dos elementos. (El Object.hashCode() especificación garantiza que dos objetos con códigos hash desiguales no pueden ser iguales.) Más generalmente, implementaciones de las diferentes interfaces de marco colecciones son libre para tomar ventaja de la comportamiento especificado de subyacente Métodos de objetos dondequiera que el implementador lo considere apropiado.