बराबर में समानता का परीक्षण करने के लिए GetHashCode का उपयोग

Question

क्या गेटहाशकोड को बराबर ओवरराइड के अंदर से समानता का परीक्षण करने के लिए एक विधि के रूप में कॉल करना ठीक है?

उदाहरण के लिए, क्या यह कोड स्वीकार्य है?

public class Class1 
{ 
    public string A 
    { 
    get; 
    set; 
    } 

    public string B 
    { 
    get; 
    set; 
    } 

    public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    return other != null && other.GetHashCode() == this.GetHashCode(); 
    } 

    public override int GetHashCode() 
    { 
    int result = 0; 
    result = (result^397)^(A == null ? 0 : A.GetHashCode()); 
    result = (result^397)^(B == null ? 0 : B.GetHashCode()); 
    return result; 
    } 
} 

Answer 1

अन्य सही हैं; आपका समानता संचालन टूट गया है। इसे समझने के लिए:

public static void Main() 
{ 
    var c1 = new Class1() { A = "apahaa", B = null }; 
    var c2 = new Class1() { A = "abacaz", B = null }; 
    Console.WriteLine(c1.Equals(c2)); 
} 

मैं कल्पना आपको लगता है कि कार्यक्रम के उत्पादन में "गलत" होना चाहते हैं लेकिन समानता की अपनी परिभाषा के साथ यह CLR के कुछ कार्यान्वयन पर "सही" है।

याद रखें, वहाँ केवल के बारे में चार अरब संभव हैश कोड हैं। चार बिलियन से अधिक संभावित छः अक्षरों के तार हैं, और इसलिए उनमें से कम से कम दो में एक ही हैश कोड है। मैंने आपको दो दिखाया है; अनगिनत कई और हैं।

सामान्य तौर पर आप उम्मीद कर सकते हैं कि यदि n संभव हैश कोड तो कर रहे हैं एक टक्कर वृद्धि नाटकीय रूप से एक बार आप खेल में n तत्वों का वर्गमूल के बारे में है प्राप्त करने की बाधाओं। यह तथाकथित "जन्मदिन विरोधाभास" है। आप समानता के लिए हैश कोड पर क्यों निर्भर नहीं होना चाहिए पर मेरे लेख के लिए देखें:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Answer 2

नहीं, यह नहीं ठीक है, है क्योंकि यह नहीं

equality <=> hashcode equality है।

यह सिर्फ

equality => hashcode equality है।

या दूसरी दिशा में:

hashcode inequality => inequality।

http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx का हवाला देते हुए:

दो वस्तुओं के रूप में बराबर की तुलना करें, प्रत्येक वस्तु के लिए GetHashCode विधि समान मान चाहिए। हालांकि, यदि दो ऑब्जेक्ट्स बराबर की तुलना नहीं करते हैं, तो दो ऑब्जेक्ट्स के लिए GetHashCode विधियों को अलग-अलग मान वापस नहीं करना पड़ता है।

Answer 3

नहीं, यह समानता के परीक्षण के लिए स्वीकार्य तरीका नहीं है। 2 गैर-बराबर मानों के लिए एक ही हैश कोड होना बहुत संभव है। यह Equals अपने क्रियान्वयन की true वापस जाने के लिए जब यह false

Answer 4

लौट जाना मैं कहूंगा कि, जब तक आप Equals के लिए चाहते हैं मूल रूप से मतलब करने के लिए कारण होगा अपने प्रकार के लिए, तो कोई, क्योंकि दो "के रूप में ही हैश कोड है" तार अलग हो सकते हैं लेकिन एक ही हैश कोड साझा करें। संभावना छोटी हो सकती है, लेकिन यह शून्य नहीं है।

Answer 5

आप निर्धारित करने के लिए करता है, तो आइटम बराबर नहीं हैं GetHashCode कॉल कर सकते हैं, लेकिन अगर दो वस्तुओं एक ही हैश कोड लौटने के लिए, इसका मतलब यह नहीं है कि वे हैं बराबर। दो वस्तुओं में एक ही हैश कोड हो सकता है लेकिन बराबर नहीं हो सकता है।

यदि दो आइटमों की तुलना करना महंगा है, तो आप हैश कोड की तुलना कर सकते हैं। अगर वे असमान हैं, तो आप जमानत दे सकते हैं। अन्यथा (हैश कोड बराबर हैं), आपको पूर्ण तुलना करना है।

उदाहरण के लिए:

public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    if (other == null || other.GetHashCode() != this.GetHashCode()) 
     return false; 
    // the hash codes are the same so you have to do a full object compare. 
    } 

Answer 6

आप नहीं कर सकते हैं का कहना है कि सिर्फ इसलिए कि हैश कोड बराबर हैं तो वस्तुओं बराबर होना चाहिए।

Equals के अंदर GetHashCode पर कॉल करने का एकमात्र समय यह था कि समानता की जांच करने के लिए किसी ऑब्जेक्ट के लिए हैश मान (कहें, क्योंकि आप इसे कैश करते हैं) की गणना करना बहुत सस्ता था। उस स्थिति में आप if (this.GetHashCode() != other.GetHashCode()) return false; कह सकते हैं ताकि आप जल्दी से सत्यापित कर सकें कि ऑब्जेक्ट बराबर नहीं थे।

तो आप कभी ऐसा कब करेंगे?मैंने कुछ कोड लिखा है जो आवधिक अंतराल पर स्क्रीनशॉट लेता है और यह पता लगाने की कोशिश करता है कि स्क्रीन बदलने के बाद से कितनी देर हो चुकी है। चूंकि मेरे स्क्रीनशॉट 8 एमबी हैं और स्क्रीनशॉट अंतराल के भीतर अपेक्षाकृत कुछ पिक्सल बदलते हैं, यह पता लगाने के लिए कि वे कौन सा हैं, उनकी सूची खोजने के लिए काफी महंगा है। एक हैश मान छोटा है और प्रति स्क्रीनशॉट में केवल एक बार गणना की जानी चाहिए, जिससे ज्ञात गैर-बराबर वाले को खत्म करना आसान हो जाता है। वास्तव में, अपने आवेदन में मैंने तय कर लिया है कि समान हैश होने बराबर होने के काफ़ी करीब है कि मैं भी Equals अधिभार लागू करने के लिए परेशान नहीं किया था, मुझे चेतावनी देने के लिए है कि मैं Equals अधिक भार के बिना GetHashCode अधिक भार था सी # संकलक के कारण।

Answer 7

एक मामले में जहां hashcodes का उपयोग कर के रूप में समानता तुलना पर एक छोटी-कट समझ में आता है नहीं है।

मामले ऐसे हैं जिनमें एक hashtable या HashSet निर्माण कर रहे हैं पर विचार करें। वास्तव में, आइए बस हैशसेट्स पर विचार करें (हैशटेबल्स का विस्तार भी एक मूल्य धारण करके, लेकिन यह प्रासंगिक नहीं है)।

कई अलग-अलग दृष्टिकोण हैं जो कोई भी ले सकते हैं, लेकिन उनमें से सभी में आपके पास ढेर मूल्यों की एक छोटी संख्या है, और हम या तो खुले या बंद दृष्टिकोण (जो सिर्फ मस्ती के लिए, कुछ लोग दूसरों के लिए विपरीत शब्दकोष का उपयोग करें); अगर हम दो अलग-अलग वस्तुओं के लिए एक ही स्लॉट पर टकराते हैं तो हम उन्हें एक ही स्लॉट में स्टोर कर सकते हैं (लेकिन एक लिंक की गई सूची या ऐसी वस्तुओं के लिए जहां वस्तुओं को वास्तव में संग्रहीत किया जाता है) या एक अलग स्लॉट लेने के लिए फिर से जांच करके (विभिन्न हैं इसके लिए रणनीतियों)।

अब, या तो दृष्टिकोण के साथ, हम दूर हे (1) जटिलता हम एक hashtable साथ चाहते से जा रहे हैं, और एक हे (एन) जटिलता की ओर। इसका जोखिम उपलब्ध स्लॉट की संख्या के विपरीत आनुपातिक है, इसलिए एक निश्चित आकार के बाद हम हैशटेबल का आकार बदलते हैं (भले ही सबकुछ आदर्श था, हमें अंततः यह करना होगा यदि संग्रहित वस्तुओं की संख्या से अधिक थी स्लॉट्स)।

फिर से डालने एक आकार बदलने पर आइटम हैश कोड पर निर्भर स्पष्ट रूप से होगा। इस वजह से, यह किसी ऑब्जेक्ट में GetHashCode() को याद करने के लिए शायद ही कभी समझ में आता है (इसे अक्सर अधिकांश ऑब्जेक्ट्स पर पर्याप्त नहीं कहा जाता है), यह निश्चित रूप से हैश टेबल के भीतर इसे याद करने के लिए समझ में आता है (या शायद, उत्पादित को याद करने के लिए नतीजतन, जैसे कि यदि आप खराब GetHashCode() कार्यान्वयन के कारण होने वाले नुकसान को कम करने के लिए एक वैंग/जेनकिन्स हैश के साथ फिर से धोया गया है)। वस्तु के लिए हैश कोड प्राप्त करें

1. :

   अब, जब हम अपने तर्क डालने के लिए आते हैं की तरह कुछ होने जा रहा है।

2. ऑब्जेक्ट के लिए स्लॉट प्राप्त करें।
3. यदि स्लॉट खाली है, तो उसमें ऑब्जेक्ट रखें और वापस आएं।
4. यदि स्लॉट में समान वस्तु है, तो हम हैशसेट के लिए किए गए हैं और हैशटेबल के लिए मान को प्रतिस्थापित करने की स्थिति है। ऐसा करो, और वापस आओ।
5. टक्कर रणनीति के अनुसार अगले स्लॉट का प्रयास करें, और आइटम 3 पर वापस आएं (शायद यह आकार बदलना अगर हम इसे अक्सर लूप करते हैं)।

तो, इस मामले में हमें समानता की तुलना करने से पहले हैश कोड प्राप्त करना होगा। हमारे पास आकार बदलने की अनुमति देने के लिए पहले से गणना की गई मौजूदा वस्तुओं के लिए हैश कोड भी है। इन दोनों तथ्यों के संयोजन मतलब है कि यह समझ में आता है के रूप में आइटम 4 के लिए हमारे तुलना लागू करने के लिए:

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash) 
{ 
    return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types) 
    || 
    (
     newHash == oldHash // fast, false positives, no fast negatives 
     && 
     _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result. 
    ); 
} 

जाहिर है, इस का लाभ _cmp.Equals की जटिलता पर निर्भर करता है। यदि हमारा मुख्य प्रकार int था तो यह कुल अपशिष्ट होगा। यदि हमारे मुख्य प्रकार जहां स्ट्रिंग और हम केस-असंवेदनशील यूनिकोड-सामान्यीकृत समानता तुलना का उपयोग कर रहे थे (इसलिए यह लंबाई पर भी शॉर्टकट नहीं कर सकता) तो बचत अच्छी तरह से लायक हो सकती है।

आम तौर पर याद रखने वाले हैश कोड को समझ में नहीं आता है क्योंकि उन्हें अक्सर प्रदर्शन जीतने के लिए पर्याप्त उपयोग नहीं किया जाता है, लेकिन हैशसेट या हैशटेबल में उन्हें संग्रहीत करना स्वयं समझ सकता है।

Answer 8

1. यह गलत कार्यान्वयन है, जैसा कि अन्य ने कहा है।

2. आप चाहिए शॉर्ट सर्किट समानता की जांच की तरह GetHashCode का उपयोग कर:

   if (other.GetHashCode() != this.GetHashCode() 
       return false; 
   

   Equals विधि में

   केवल यदि आप सुनिश्चित हों आगामी बराबरी कार्यान्वयन ज्यादा GetHashCode से ज्यादा महंगा है जो विशाल बहुमत नहीं है मामलों में से

3. इस एक कार्यान्वयन में आपने दिखाया है (जो 99% मामलों में है) यह न केवल टूटा हुआ है, यह भी धीमा है। और कारण? आपकी संपत्तियों के हैश की गणना करना लगभग की तुलना में धीमा हो जाएगा, इसलिए आप प्रदर्शन शर्तों में भी लाभ नहीं उठा रहे हैं। एक उचित GetHashCode लागू करने का लाभ तब होता है जब आपकी कक्षा हैश टेबल के लिए मुख्य प्रकार हो सकती है जहां हैश की गणना केवल एक बार की जाती है (और उस मान को तुलना के लिए उपयोग किया जाता है)। आपके मामले में GetHashCode को संग्रह में होने पर कई बार बुलाया जाएगा। भले ही GetHashCode स्वयं तेज़ होना चाहिए, यह समकक्षEquals से अधिक तेज़ नहीं है।

   बेंचमार्क के लिए, अपने Equals (एक उचित कार्यान्वयन, वर्तमान हैश आधारित कार्यान्वयन बाहर ले) चलाने

   और GetHashCode यहाँ

   var watch = Stopwatch.StartNew(); 
   for (int i = 0; i < 100000; i++) 
   { 
       action(); //Equals and GetHashCode called here to test for performance. 
   } 
   watch.Stop(); 
   Console.WriteLine(watch.Elapsed.TotalMilliseconds);