Java:要在一个充满自定义对象的ArrayList中使用contains我应该覆盖equals还是实现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).

对于a HashSet或者LinkedHashSet,平均性能contains是一个常数,与集合的大小无关,但最坏情况下的性能是O(N).(如果你1)实现一个差的hashcode()函数,将所有东西都散列到少量的值,或者2)调整"加载因子"参数,以便哈希表不会随着它的增长自动调整大小,就会出现最坏的情况.)

使用Set类的缺点是:

• 他们是一套 ; 即你不能将两个或更多"相等"的对象放入集合中,并且
• 他们不能被索引; 例如,没有get(pos)方法,和
• 某些Set类甚至不保留插入顺序.

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