Java: 在使用一个装满自定义对象的ArrayList时，我应该重写equals方法还是实现Comparable/Comparator接口来使用contains方法？

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 

- andandandand

Answer 1

List.contains(...) 方法定义使用equals(Object)来确定参数对象是否被列表所“包含”。因此，您需要重写equals方法...假设默认实现不适合您的需求。

然而，您需要知道List.contains(...)可能会将参数与列表中的每个元素进行比较。对于长列表，这是昂贵的。根据应用程序的细节，使用不同的集合类型（例如HashSet、TreeSet或LinkedHashSet）而不是List也许更好。如果您使用其中之一，您的类将需要重写hashCode或实现Comparable，或者您需要创建单独的Comparator...取决于您的选择。

---

（有关替代方案的更多建议...因为OP感兴趣）

List类型（例如ArrayList或LinkedList）的contains性能为O(N)。调用contains的最坏情况成本直接与列表长度成正比。

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

HashSet或LinkedHashSet的平均性能为一个常数，与集合的大小无关，但最坏情况下的性能为O(N)。（如果您1）实现了一个糟糕的hashcode()函数，将所有内容散列到少量值中，或2）调整“负载因子”参数，使哈希表在增长时不会自动调整大小，则会出现最坏情况性能。）

使用Set类的缺点是：

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

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

- Stephen C

Answer 2

你可能需要实现hashCode()方法。通常情况下，当你重写equals()方法时，你应该总是这样做。

来自集合文档：

不应将此规范解释为调用Collection.contains方法时，使用非空参数o将导致o.equals(e)对任何元素e进行调用。实现可以自由地实现优化，从而避免equals方法的调用，例如通过首先比较两个元素的哈希码。（Object.hashCode()规范保证具有不相等哈希码的两个对象不能相等。）更一般地说，各种集合框架接口的实现可以在实现者认为适当的任何地方利用底层Object方法的指定行为。

- verdesmarald

---

这假设 OP 更改为使用不同的集合类型。如果他继续使用 ArrayList，则无关紧要。 - Stephen C

ArrayList.contains()的规范在哪里保证了调用equals()？它由List.contains()和Collection.contains()指定，两者都只保证结果为true当且仅当集合包含一个元素e，使得（o == null ? e == null : o.equals(e)）为true。实现可以自由地使用与任何其他集合相同的hashCode快捷方式。 - verdesmarald

@veredesmarald - 在这里 - http://download.oracle.com/javase/1.5.0/docs/api/java/util/AbstractCollection.html#contains(java.lang.Object) - Stephen C

就我所见，这个接口具有与 List 和 Collection 相同的包含契约...您能引用您所指的具体部分吗？请注意，要求 o == null ? e == null : o.equals(e) 为 true 并不意味着它将调用 equals。正如在 Collection 概述中所指出的那样，集合框架接口可以利用底层对象方法的指定行为[...] 特别是，我们可以使用 hashCode 来短路比较，因为 Object 保证如果 o.hashCode != e.hashCode() 则 o.Equals(e) 必须为 false。 - verdesmarald

一个普通的 List<E> 实现这样做是错误的。对于许多元素类，hashCode 的计算成本（平均而言）比 equals 更高。 - Stephen C