Java: для использования содержит в ArrayList полный пользовательский объект, если я переопределяю equals или реализую Comparable/Comparator?
У меня есть полный массив ArrayList:
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
Я запрошу его с помощью этого:
if(!transitionStatesArray.contains(newTransitionState)){ //if the transition state is new add and enqueue new robot positions
transitionStatesArray.add(newTransitionState); //marks as visited
Я нахожу повторяющиеся элементы внутри своего transitionStatesArray, почему это?
Я использую эти значения i, j и ориентации для заполнения уникальных значений в матрице, но здесь у меня есть дубликат:
S . N
* * *
. D D
E . O
* * *
. D D
N . S
* * *
. D D
S . N
* * *
. D D
Ответы
Ответ 1
Метод List.contains(...) определяется как использовать equals(Object), чтобы решить, содержит ли объект аргумента список. Поэтому вам нужно переопределить equals... при условии, что реализация по умолчанию - это не то, что вам нужно.
Однако вам нужно знать, что List.contains(...) потенциально проверяет аргумент против каждого элемента в списке. Для длинного списка это дорого. В зависимости от деталей вашего приложения может быть лучше использовать другой тип коллекции (например, HashSet, TreeSet или LinkedHashSet) вместо List. Если вы используете один из них, ваш класс должен будет переопределить hashCode или реализовать Comparable, или вам нужно будет создать отдельный Comparator... в зависимости от того, что вы выберете.
(Немного больше советов по альтернативам... поскольку OP заинтересован)
Производительность contains для типа List типа ArrayList или LinkedList равна O(N). Наихудшая стоимость вызова contains прямо пропорциональна длине списка.
При a TreeSet наихудшая производительность contains пропорциональна log2(N).
Для HashSet или LinkedHashSet средняя производительность contains является константой, независимой от размера коллекции, но наихудшая производительность - O(N). (Наихудшая производительность возникает, если вы 1) реализуете плохую функцию hashcode(), которая хэширует все до небольшого числа значений или 2) настраивает параметр "коэффициент загрузки", чтобы хеш-таблица не изменялась автоматически по мере ее роста.)
Недостатком использования классов Set является:
- они являются множествами; т.е. вы не можете поместить в коллекцию два или более "равных" объектов, а
- они не могут быть проиндексированы; например нет метода
get(pos) и
- некоторые из классов
Set даже не сохраняют порядок вставки.
Эти проблемы необходимо учитывать при определении того, какой класс коллекции использовать.
Ответ 2
Вероятно, вам нужно реализовать hashCode(). В общем, вы всегда должны делать это, когда переопределение равно.
Из коллекций docs:
Эта спецификация не должна быть подразумевается, что вызов Collection.contains с ненулевым аргумент o приведет к тому, что o.equals(e) для любого элемента e. Реализации могут быть бесплатными для реализации оптимизация, при которой равны вызова можно избежать, например, путем сначала сравнение хэш-кодов два элемента. (Object.hashCode() спецификация гарантирует, что два объекты с неравными хэш-кодами не могут быть равным.) В более общем плане, реализации различных Интерфейсы коллекции Framework бесплатно воспользоваться заданное поведение Объектные методы везде, где разработчик считает это целесообразным.
