क्या यह हैश फ़ंक्शन असामान्य रूप से अक्सर टकराएगा?

Question

मेरे पास ऑब्जेक्ट का हैश उत्पन्न करने के लिए निम्न कोड था:

public int GetHashCode(MyType obj) 
{ 
    return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode(); 
} 

I.e. मैं सभी गुणों के हैश कोड जोड़ता हूं और फिर इसका हैश लेता हूं।

समीक्षा में, एक सहकर्मी ने सुझाव दिया कि यह बहुत बार टकराएगा। मुझे यकीन नहीं है कि यह सच है क्योंकि:

1. यह देखते हुए कि हैश कोड सकारात्मक और नकारात्मक संख्याओं के बीच समान आवृत्ति के साथ चुने गए हैं और वे चारों ओर लपेटते हैं, मुझे नहीं लगता कि हमें संभावना के बारे में कोई अतिरिक्त जानकारी मिलती है संख्याओं के विपरीत इन संख्याओं के योग के रूप में
2. इस सीमा तक कि उनकी राशि गैर-यादृच्छिक है, हैश कोड उन संख्याओं को बनाने के लिए डिज़ाइन किए गए हैं जो "एक साथ बंद" हो जाते हैं, "बहुत अलग" हो जाते हैं, इसलिए गैर-समान रूप से भोजन करना समारोह में वितरित मूल्य एक मुद्दा नहीं होना चाहिए

कौन सही है?

यह सी # में है, अगर उत्तर भाषा-विशिष्ट है।

Answer 1

हां।

बस मान लें कि Prop1, Prop2 आदि int प्रकार के हैं। आमतौर पर केवल पूर्णांक की निचली रेंज का उपयोग किया जाता है। आपका योग दृष्टिकोण आवश्यक से अधिक बार टकरा जाएगा।

7 का हैसकोड 7 है, जो int हैशिंग द्वारा स्वयं को सही समझ में आता है। लेकिन आपके कोड के साथ tuples <7, 3>, <3, 7> और <8, 2> सभी के पास एक ही हैश होगा। अतिरिक्त के बजाय सरल एक्सओआर के साथ ही।

public int GetHashCode(MyType obj) 
{ 
    int hash = 0; 
    unchecked 
    {   
    hash += 19 * obj.Prop1.GetHashCode(); 
    hash += 31 * obj.Prop2.GetHashCode(); 
    hash += 37 * obj.Prop3.GetHashCode(); 
    } 
    return hash; 
} 

संख्या 19, 31, 37 भी महत्वपूर्ण नहीं हैं:

आम दृष्टिकोण कुछ (प्रधानमंत्री) संख्या और स्थानांतरण जोड़ना है। और यदि आप चाहें तो आप + के बजाय OR या XOR का उपयोग कर सकते हैं।

Answer 2

XORing बेहतर होगा:

public int GetHashCode(MyType obj) 
{ 
    return obj.Prop1.GetHashCode()^
      obj.Prop2.GetHashCode()^
      obj.Prop3.GetHashCode(); 
} 

Answer 3

आपने एक संशोधित FNV हैशकोड जनरेटर का उपयोग करें, एक बहुत ही इसी तरह के सवाल (मेरे द्वारा) here