Java：要使用包含完全自定義對象的ArrayList，我應該重寫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調用的最壞情況成本與列表長度成正比。

對於TreeSetcontains的最壞情況表現與log2(N)成比例。

對於HashSet或LinkedHashSet，的contains的平均性能是一個常數，不依賴於集合的大小，但是在最壞情況下的性能是O(N)。 （如果你是1，則會出現最糟糕的情況）執行一個窮舉的hashcode()函數，該函數會將所有內容散列爲少量值，或者2）調整「加載因子」參數，以便散列表不會隨着其增長而自動調整大小。

使用Set類的缺點是：

• 它們套;即不能將兩個或更多「相等」對象放入集合中，並且它們不能被索引;例如沒有get(pos)方法，並且
• 某些Set類甚至不保留廣告訂單。

當決定使用哪個集合類時，需要考慮這些問題。

Answer 2

你可能需要實現的hashCode（）。一般來說，無論如何你應該總是這樣做。

從collections docs：

本說明書不應當被 解釋爲暗示調用 Collection.contains具有非空 參數ö將導致o.equals（e）至 被調用用於任何元素e。 實現可以自由執行 優化，從而避免等於 調用，例如，首先比較 兩個元素的哈希代碼。 （該是Object.hashCode（） 規範保證具有不相等的哈希碼2個 對象不能 相等。）更一般地，各種 集合框架接口的 實現是 自由採取底層 的 指定的行爲的優點對象方法在實現者認爲合適的任何地方。