Java: для использования содержит в ArrayList полный пользовательский объект я должен переопределить равно или реализовать Comparable / Comparator?

Question

У меня есть 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 

Answer 1

Метод List.contains(...) определен для использования equals(Object) для определения, содержится ли объект аргумента в списке.Поэтому вам нужно переопределить equals ... при условии, что реализация по умолчанию - это не то, что вам нужно.

Однако вы должны знать, что List.contains(...) потенциально проверяет аргумент для каждого элемента в списке.Для длинного списка это дорого.В зависимости от деталей вашего приложения, может быть лучше использовать другой тип коллекции (например, HashSet, TreeSet или LinkedHashSet) вместо List.Если вы используете один из них, ваш класс должен будет переопределить hashCode или реализовать Comparable, или вам нужно будет создать отдельный Comparator ... в зависимости от того, что вы выберете.

---

(Еще несколько советов об альтернативах ... поскольку интересует OP)

Производительность contains для типа List, например ArrayList или LinkedList, равна O(N).Наихудшая стоимость вызова contains прямо пропорциональна длине списка.

Для TreeSet производительность наихудшего случая contains пропорциональна log2(N).

Для HashSet или LinkedHashSet средняя производительность contains является постоянной величиной, не зависящей от размера коллекции, но наихудшая производительность составляет O(N).(Наихудший случай производительности возникает, если вы: 1) внедрили плохую функцию hashcode(), которая хэширует все до небольшого числа значений, или 2) настроили параметр «коэффициент загрузки», чтобы хеш-таблица не изменяла размер автоматически при ее росте..)

Недостатки использования Set классов:

• они комплекты ;т.е. вы не можете поместить два или более «равных» объекта в коллекцию, и
• они не могут быть проиндексированы;например, get(pos) метод отсутствует, а
• некоторые классы Set даже не сохраняют порядок вставки.

Эти проблемы необходимо учитывать при принятии решения о том, какая коллекциякласс для использования.

Answer 2

Возможно, вам нужно реализовать hashCode ().В общем, вы всегда должны делать это, когда переопределение равно равно.

Из документов коллекций :

Эта спецификация не должна быть истолкована как подразумевающая вызов вызывающей коллекции.Содержит с ненулевым аргументом o вызовет o.equals (e) для любого элемента e.Реализации свободны в реализации оптимизаций, благодаря которым избегается вызов равенства, например, сначала сравнивая хэш-коды двух элементов.(Спецификация Object.hashCode () гарантирует, что два объекта с неодинаковыми хеш-кодами не могут быть равными.) В более общем случае реализации различных интерфейсов Framework коллекций могут использовать преимущества указанного поведения базовых методов Object, если разработчик сочтет это целесообразным..