example - Java: para usar contiene en un ArrayList lleno de objetos personalizados, ¿debo anular los iguales o implementar Comparable/Comparator?

implements comparable java

Question

Tengo un ArrayList lleno 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

Lo pregunto 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é sucede esto?

Estoy usando estos valores de i, j y orientación para completar valores únicos en una matriz, pero aquí tengo un duplicado:

 S . N
* * *
. D D
E . O
* * *
. D D
N . S
* * *
. D D
S . N
* * *
. D D 

Answer 1

El List.contains(...) está definido para usar equals(Object) para decidir si el objeto argumento está "contenido" por la lista. Por lo tanto, debe anular los equals ... asumiendo que la implementación predeterminada no es lo que necesita.

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

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

El rendimiento de contains en un tipo de 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 desempeño de los contains es proporcional a log2(N) .

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

Las desventajas de usar clases de Set son:

• son conjuntos es decir, no puede poner dos o más objetos "iguales" en la colección, y
• no pueden ser indexados; por ejemplo, no hay método get(pos) , y
• Algunas de las clases Set no conservan el orden de inserción.

Estas cuestiones deben considerarse al decidir qué clase de colección utilizar.

Answer 2

Probablemente necesites implementar hashCode (). En general, siempre deberías hacer esto cuando anules iguales de todos modos.

De los documentos de colecciones :

No se debe interpretar que esta especificación implica que invocar Collection.contains con un argumento no nulo o causará que se invocen a o.equals (e) para cualquier elemento e. Las implementaciones son libres de implementar optimizaciones mediante las cuales se evite la invocación igual, por ejemplo, comparando primero los códigos hash de los dos elementos. (La especificación Object.hashCode () garantiza que dos objetos con códigos hash desiguales no pueden ser iguales.) Más generalmente, las implementaciones de las diversas interfaces del Marco de Colecciones son libres de aprovechar el comportamiento especificado de los métodos de Objeto subyacentes donde el implementador lo considere apropiado. .