जावा: कस्टम ऑब्जेक्ट से भरे एक ऐरेलिस्ट में उपयोग करने के लिए क्या मुझे तुलनात्मक/तुलनात्मक के बराबर या कार्यान्वित करना चाहिए?

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) का उपयोग करने के लिए बेहतर हो सकता है। यदि आप उनमें से किसी एक का उपयोग करते हैं, तो आपकी कक्षा को hashCode ओवरराइड करने की आवश्यकता होगी या Comparable लागू करें, या आपको जो भी चुनते हैं उसके आधार पर आपको एक अलग Comparator बनाना होगा।

---

(विकल्प पर एक थोड़ा और अधिक सलाह ... के बाद से ओपी रुचि रखता है)

एक List प्रकार ArrayList या LinkedList की तरह पर contains के प्रदर्शन 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 (ई) का कारण होगा के लिए लागू किया जा नहीं लगाया जाना चाहिए कोई तत्व ई। क्रियान्वयन अनुकूलन जिससे बराबरी मंगलाचरण से बचा जाता है, उदाहरण के लिए, से पहले दो तत्वों का हैश कोड की तुलना को लागू करने के लिए स्वतंत्र हैं। (Object.hashCode() विनिर्देश गारंटी देता है कि असमान हैश कोड के साथ दो वस्तुओं बराबर नहीं हो सकता है।) आम तौर पर, विभिन्न संग्रह फ्रेमवर्क इंटरफेस की कार्यान्वयन हैं अंतर्निहित की निर्दिष्ट व्यवहार का लाभ उठाने के लिए स्वतंत्र ऑब्जेक्ट विधियों जहां भी कार्यान्वयनकर्ता उचित मानता है।