Java：要在充满定制对象的ArrayList中使用包含，我应该重写等于还是实现可比较/比较器？

我有一个包含以下内容的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 

---

解决方案

List.contains(...)方法被定义为使用equals(Object)来确定参数对象是否包含在列表中。因此，您需要覆盖equals...假定默认实现不是您需要的。

但是，您需要注意List.contains(...)可能会针对列表中的每个元素测试参数。对于一份长长的清单来说，这是昂贵的。根据应用程序的详细信息，使用不同的集合类型(例如，HashSet、TreeSet或LinkedHashSet)可能比使用List更好。如果您使用其中之一，您的类将需要重写hashCode或实现Comparable，否则您将需要创建一个单独的Comparator...取决于您选择的内容。

---

(关于替代方案的更多建议...因为操作员感兴趣)

contains在List类ArrayList或LinkedList上的性能是O(N)。contains调用的最差开销与列表长度成正比。

对于TreeSet，contains的最差性能与log2(N)成正比。

对于HashSet或LinkedHashSet，contains的平均性能是一个常量，与集合的大小无关，但最差的性能是O(N)。(最糟糕的性能发生在以下情况：1)实现一个较差的hashcode()函数，该函数将所有内容散列为少量的值，或者2)调整"加载因子"参数，以便哈希表不会随着其增长而自动调整大小。)

使用Set类的缺点是：

• 它们是集合；即不能将两个或更多"相等"对象放入集合中，并且
• 无法索引；例如，没有get(pos)方法，
• 某些Set类甚至不保留插入顺序。

在决定使用哪个集合类时，需要考虑这些问题。