हैशकोड विशिष्टता

Question

क्या ऑब्जेक्ट के दो उदाहरणों के लिए एक ही हैशकोड संभव है?

सिद्धांत रूप में एक वस्तु की hashCode अपनी स्मृति पते से ली गई है, इसलिए सभी hashcodes अद्वितीय होना चाहिए, लेकिन वस्तुओं जीसी दौरान चारों ओर ले जाया जाता है क्या है?

Answer 1

वस्तुओं के उचित संग्रह को देखते हुए, एक ही हैश कोड के साथ दो होने की संभावना काफी है। सबसे अच्छे मामले में यह जन्मदिन की समस्या बन जाती है, जिसमें हजारों वस्तुओं के साथ संघर्ष होता है। प्रैक्टिस ऑब्जेक्ट्स में संभावित हैश कोड के अपेक्षाकृत छोटे पूल के साथ बनाया गया है, और केवल हजारों ऑब्जेक्ट्स के साथ संघर्ष आसानी से हो सकता है।

स्मृति पता का उपयोग करना थोड़ा यादृच्छिक संख्या प्राप्त करने का एक तरीका है। सूर्य जेडीके स्रोत में एक सुरक्षित रैंडम नंबर जेनरेटर या स्थिर के उपयोग को सक्षम करने के लिए एक स्विच है। मेरा मानना ​​है कि आईबीएम (इस्तेमाल किया जाता है?) एक तेज़ यादृच्छिक संख्या जनरेटर का उपयोग करता है, लेकिन यह बिल्कुल सुरक्षित नहीं था। स्मृति पते के दस्तावेज़ों में उल्लेख ऐतिहासिक प्रकृति का प्रतीत होता है (लगभग एक दशक पहले निश्चित स्थानों के साथ ऑब्जेक्ट हैंडल करना असामान्य नहीं था)। इस बात आती है, क्योंकि ऊपर जिस तरह से बहुत जल्दी-जल्दी,

class HashClash { 
    public static void main(String[] args) { 
     final Object obj = new Object(); 
     final int target = obj.hashCode(); 
     Object clash; 
     long ct = 0; 
     do { 
      clash = new Object(); 
      ++ct; 
     } while (clash.hashCode() != target && ct<10L*1000*1000*1000L); 
     if (clash.hashCode() == target) { 
      System.out.println(ct+": "+obj+" - "+clash); 
     } else { 
      System.out.println("No clashes found"); 
     } 
    } 
} 

RFE डॉक्स स्पष्ट करने के लिए:

यहाँ कुछ कोड मैं कुछ साल पहले लिखा था संघर्ष प्रदर्शित करने के लिए है CR 6321873

Answer 2

मुझे लगता है कि docs for object's hashCode method राज्य जवाब।

"जितना यथोचित व्यावहारिक है, hashCode विधि वर्ग वस्तु द्वारा परिभाषित अलग वस्तुओं के लिए अलग पूर्णांकों वापसी करता है। (यह आम तौर पर वस्तु की आंतरिक पता परिवर्तित एक में द्वारा कार्यान्वित है JavaTM भाषा प्रोग्रामिंग के लिए आवश्यक नहीं पूर्णांक है, लेकिन इस कार्यान्वयन तकनीक है।) "

Answer 3

क्या यह संभव है?

हां।

क्या यह किसी भी उचित आवृत्ति के साथ होता है?

सं।

Answer 4

इसके बारे में सोचें। संभावित वस्तुओं की एक अनंत संख्या है, और केवल 4 अरब हैश कोड हैं। जाहिर है, संभावित वस्तुओं की अनंतता प्रत्येक हैश कोड साझा करती है।

सूर्य JVM या तो वस्तु के लिए एक स्थिर हैंडल पर ठिकानों Object हैश कोड या प्रारंभिक हैश कोड संचित करता है। जीसी के दौरान कॉम्पैक्शन hashCode() में बदलाव नहीं करेगा। अगर ऐसा होता तो सबकुछ टूट जाएगा।

Answer 5

अगर कोई स्मृति के रूप में थे के रूप में कई hashcodes पते, तो हैश को स्टोर करने के लिए संपूर्ण मेमोरी ले ली जाएगी। :-)

तो, हाँ, हैश कोड कभी-कभी मेल होना चाहिए।

Answer 6

आप वास्तविक वर्ग Object या सामान्य रूप में वस्तुओं के बारे में बात कर रहे हैं? आप दोनों प्रश्नों का उपयोग करते हैं।(और असली दुनिया के ऐप्स आम तौर पर Object के बहुत से उदाहरण नहीं बनाते हैं)

सामान्य रूप से वस्तुओं के लिए, एक कक्षा लिखना आम है जिसके लिए आप equals() ओवरराइड करना चाहते हैं; और यदि आप ऐसा करते हैं, तो आपको hashCode() को ओवरराइड करना होगा ताकि "वर्ग" वाले उस वर्ग के दो अलग-अलग उदाहरणों में भी एक ही हैश कोड होना चाहिए। आपको उसी मामले के उदाहरणों के दौरान उस मामले में "डुप्लिकेट" हैश कोड प्राप्त होने की संभावना है।

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

किसी वास्तविक दुनिया ऐप में, एक ही हैश कोड के साथ विभिन्न ऑब्जेक्ट्स को ढूंढना असामान्य नहीं है।

Answer 7

मुझे लगता है कि मूल प्रश्न डिफ़ॉल्ट Object कार्यान्वयन द्वारा उत्पन्न हैश कोड के बारे में है। तथ्य यह है कि हैश कोडों को समानता परीक्षण के लिए भरोसा नहीं किया जाना चाहिए और केवल कुछ विशिष्ट हैश मैपिंग परिचालनों में उपयोग किया जाता है (जैसे कि बहुत उपयोगी HashMap कार्यान्वयन द्वारा लागू)।

इस तरह उन्हें वास्तव में अद्वितीय होने की आवश्यकता नहीं है - उन्हें केवल बहुत सारे संघर्ष उत्पन्न करने के लिए पर्याप्त अद्वितीय होना चाहिए (जो HashMap कार्यान्वयन अक्षम कर देगा)।

यह भी उम्मीद की जाती है कि जब डेवलपर हैश मैप्स में संग्रहीत कक्षाओं को लागू करता है तो वे एक हैश कोड एल्गोरिदम लागू करेंगे जिसमें एक ही कक्षा की वस्तुओं के लिए झड़पों का कम मौका होता है (माना जाता है कि आप केवल वही वस्तुओं को संग्रहित करते हैं आवेदन हैश मैप्स में कक्षा), और डेटा के बारे में जानना मजबूत हैशिंग को लागू करना अधिक आसान बनाता है।

समान हैश कोडों की आवश्यकता के समानता के बारे में केन के उत्तर को भी देखें।