जावा के हैशकोड अलग-अलग तारों के लिए समान मूल्य उत्पन्न कर सकते हैं?

Question

क्या जावा के हैशकोड फ़ंक्शन का उपयोग करके अलग-अलग तारों के लिए एक ही हैशकोड होना संभव है? या यदि यह संभव है तो इसकी संभावना का% क्या है?

Answer 1

जावा हैश कोड 32 बिट है। संभव है कि यह संभव तारों की संख्या अनंत है।

तो हाँ, टकराव होंगे। प्रतिशत व्यर्थ है - वस्तुओं की एक अनंत संख्या (तार) और संभावित हैश की एक सीमित संख्या है।

Answer 2

यह सीधे आपके प्रश्न का उत्तर नहीं देगा, लेकिन मुझे आशा है कि इससे मदद मिलेगी।

नीचे java.lang.String के स्रोत कोड से है।

/** 
* Returns a hash code for this string. The hash code for a 
* <code>String</code> object is computed as 
* <blockquote><pre> 
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
* </pre></blockquote> 
* using <code>int</code> arithmetic, where <code>s[i]</code> is the 
* <i>i</i>th character of the string, <code>n</code> is the length of 
* the string, and <code>^</code> indicates exponentiation. 
* (The hash value of the empty string is zero.) 
* 
* @return a hash code value for this object. 
*/ 
public int hashCode() { 
    int h = hash; 
    int len = count; 
    if (h == 0 && len > 0) { 
    int off = offset; 
    char val[] = value; 

     for (int i = 0; i < len; i++) { 
      h = 31*h + val[off++]; 
     } 
     hash = h; 
    } 
    return h; 
} 

Answer 3

हाँ, कबूतर छेद अवधारणा की परिभाषा के द्वारा, दो अलग अलग तार एक ही hashCode उत्पादन कर सकते हैं और कोड हमेशा इस तरह की स्थितियों के लिए पूरा करने के लिए लिखा जाना चाहिए (आमतौर पर, तोड़ नहीं है।)

Answer 4

हाँ । बहुत। जोड़ी

• "अमेरिकन प्लान" और "ईए"

एक ही हैश कोड लौट सकते हैं, भले ही यह में पात्रों ही नहीं हैं निम्नलिखित पर

देखो।

असल में यह एक पूर्णांक द्वारा गुणा स्ट्रिंग में वर्णों का योग है।

Answer 5

हाँ, यह संभव है दो स्ट्रिंग्स ही hashCode के लिए के लिए - आप Wikipedia article पर एक नज़र डालें, तो आप उस "FB" और "Ea" दोनों एक ही hashCode है देखेंगे। विधि अनुबंध में कुछ भी नहीं है कि hashCode() समानता की तुलना करने के लिए उपयोग किया जाना चाहिए, इसके लिए आप equals() का उपयोग करना चाहते हैं।

जावा 1.2 के बाद से, स्ट्रिंग hashCode()using a product sum algorithm over the entire text of the string लागू करता है।

Answer 6

यदि यह संभव है तो इसकी संभावना का% क्या है?

यह एक विशेष रूप से सार्थक सवाल नहीं है।

हालांकि, hashcode फ़ंक्शन में कुछ व्यवस्थित पूर्वाग्रह होने तक, संभावना है कि किसी भी दो अलग-अलग (गैर-बराबर) स्ट्रिंग्स में एक ही हैश कोड 2^32 में 1 होगा।

यह मानता है कि स्ट्रिंग्स को सभी संभव स्ट्रिंग मानों के सेट से यादृच्छिक रूप से चुना जाता है। यदि आप सेट को विभिन्न तरीकों से प्रतिबंधित करते हैं, तो संभावना उपर्युक्त संख्या से भिन्न होगी। (उदाहरण के लिए, "अमेरिकन प्लान"/"ईए" टक्कर के अस्तित्व का मतलब है सभी 2 पत्र तार के सेट में एक टक्कर की संभावना के आदर्श से अधिक है।)

---

नोट करने के लिए एक और बात है कि यादृच्छिक रूप से चुने गए 2^32 अलग-अलग तारों का मौका (स्ट्रिंग्स के बहुत बड़े निष्पक्ष सेट से) कोई हैश टकराव नहीं है गायब होकर छोटा।समझने के लिए, Birthday Paradox पर विकिपीडिया पृष्ठ पढ़ें। हकीकत में, यदि आप स्ट्रिंग का चयन या उत्पन्न करते हैं तो 2^32 अलग-अलग तारों के सेट में कोई हैश टक्कर नहीं मिलने वाला एकमात्र तरीका है। (और यहां तक ​​कि यादृच्छिक रूप से जेनरेट किए गए तारों का चयन करके सेट भी बनाकर कम्प्यूटेशनल रूप से महंगा होगा।)

Answer 7

यादृच्छिक तारों के लिए टकराव का प्रतिशत न्यूनतम होना चाहिए। हालांकि, अगर आप बाहरी स्रोतों से हैश स्ट्रिंग करते हैं, तो हमलावर आसानी से सैकड़ों हजारों तारों को एक ही हैशकोड बना सकता है। जावा हैश मैप में ये सभी एक ही बाल्टी पर नक्शा करेंगे और प्रभावी ढंग से मानचित्र को एक लिंक सूची में बदल देंगे। मानचित्र के लिए एक्सेस समय तब स्थिरता के बजाय मानचित्र आकार के आनुपातिक होंगे, जिससे सेवा हमले से इनकार किया जा सकता है।

प्रस्तुति के लिए और जानकारी लिंक के लिए इस पृष्ठ को Effective DoS attacks against Web Application Plattforms पर देखें।

Answer 8

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

आकार ~ 9000 का एक सेट के साथ
• , आप सेट
आकार ~ 30,000 का एक सेट के साथ
• में एक हैश के साथ टकराने दो तार के एक 1% मौका होगा, सेट
• आकार में एक हैश के साथ टकराव के दो तारों का 10% मौका होगा, आकार ~ 77,000 के सेट के साथ, आपके पास सेट

में हैश के साथ टकराने वाले दो तारों का 50% मौका होगा

धारणाएं बनाई गई हैं:

• hashCode समारोह कोई पूर्वाग्रह है
• ऊपर उल्लिखित सेट में प्रत्येक स्ट्रिंग अद्वितीय है

इस साइट में यह स्पष्ट रूप से बताते हैं: http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/ ("दूसरी बात आपको पता होना चाहिए" को देखो)