जावा हैशैप टकराव का पता लगाता है

Question

जावा हैश-मानचित्र में टकराव का पता लगाने का कोई तरीका है? क्या कोई भी ऐसी स्थिति को इंगित कर सकता है जहां टक्कर हो सकती है। बेशक यदि आप किसी ऑब्जेक्ट के लिए हैशकोड ओवरराइड करते हैं और बस एक स्थिर मूल्य टक्कर वापस आते हैं तो सुनिश्चित हो जाता है। मैं इसके बारे में बात नहीं कर रहा हूं। मैं जानना चाहता हूं कि पहले की उल्लिखित सभी स्थितियों में क्या है जो बड़ी संख्या में टकराव होते हैं डिफ़ॉल्ट हैशकोड कार्यान्वयन को संशोधित किए बिना।

Answer 1

मैंने इस तरह की चीजों को बेंचमार्क करने के लिए एक प्रोजेक्ट बनाया है: http://code.google.com/p/hashingbench/ (चेनिंग, ओपन-एड्रेसिंग और ब्लूम फ़िल्टर के साथ हैशटेबल्स के लिए)। hashCode() कुंजी से

अलावा, आप (, के रूप में मैं यह है कि परियोजना में कॉल या "पांव मार") hashtable के समारोह "को धब्बे" जानना चाहते हैं। this list से, HashMap के धब्बे समारोह के बराबर है: scramble(k1.hashCode()) == scramble(k2.hashCode()): तो एक टक्कर एक HashMap में होने के लिए

public int scramble(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

, आवश्यक और पर्याप्त हालत निम्नलिखित है। यह हमेशा सच, अगरk1.hashCode() == k2.hashCode() (अन्यथा, smearing/समारोह पांव मार एक समारोह नहीं हैं) है, ताकि एक पर्याप्त है, लेकिन एक टक्कर होने के लिए नहीं आवश्यक हालत।

संपादित करें: वास्तव में, इसके बाद के संस्करण आवश्यक और पर्याप्त शर्त compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) किया जाना चाहिए था - compress समारोह एक पूर्णांक लेता है और {0, ..., N-1}, जहां N बकेट की संख्या है करने के लिए इसे नक्शे, तो यह मूल रूप से एक बाल्टी चयन करता है। आम तौर पर, इसे बस hash % N के रूप में कार्यान्वित किया जाता है, या जब हैशटेबल आकार दो की शक्ति है (और वास्तव में यह है कि hash & N (तेज) के रूप में पावर ऑफ द हैंशटेबल आकारों के लिए एक प्रेरणा है। ("संपीड़न" नाम गुड्रिच और तामासिया है जो Data Structures and Algorithms in Java में इस चरण का वर्णन करने के लिए उपयोग किया जाता है)। धन्यवाद मेरी sloppiness स्पॉट के लिए आईएलएमटीटन जाओ।

अन्य हैशटेबल कार्यान्वयन (ConcurrentHashMap, IdentityHashMap, आदि) की अन्य ज़रूरतें हैं और एक और धुंधला/स्कैम्बलिंग फ़ंक्शन का उपयोग करें, इसलिए आपको यह जानना होगा कि आप किस बारे में बात कर रहे हैं।

(उदाहरण के लिए, हैश मैप के स्मियरिंग फ़ंक्शन को जगह में रखा गया था क्योंकि लोग हैश मैप का उपयोग सबसे खराब प्रकार के हैशकोड() के साथ पुराने, बिजली के दो-टेबल कार्यान्वयन के बिना हैश मैप के बिना, बिना किसी चीज के - थोड़ा, या बिल्कुल नहीं, उनके कम ऑर्डर बिट्स में जो बाल्टी का चयन करने के लिए उपयोग किए जाते थे - उदाहरण के लिए new Integer(1 * 1024), new Integer(2 * 1024) *, आदि। जैसा कि आप देख सकते हैं, हैश मैप के स्मीयरिंग फ़ंक्शन के सभी सर्वोत्तम बिट्स को प्रभावित करते हैं कम ऑर्डर बिट्स)।

हालांकि, उनमें से सभी सामान्य मामलों में अच्छी तरह से काम करने के लिए हैं - एक विशेष मामला ऐसी ऑब्जेक्ट्स है जो सिस्टम के हैशकोड() को प्राप्त करता है।

पीएस: दरअसल, पूरी तरह से बदसूरत मामला जो कार्यान्वयनकर्ताओं को स्मीयरिंग फ़ंक्शन डालने के लिए प्रेरित करता है, फ्लोट/डबल्स के हैशकोड() और मूल्यों की कुंजी के रूप में उपयोग है: 1.0, 2.0, 3.0, 4.0 ..., उनमें से सभी एक ही (शून्य) कम ऑर्डर बिट्स रखते हैं। यह संबंधित वर्ष बग रिपोर्ट है: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

Answer 2

सरल उदाहरण: Long हैशिंग। जाहिर है 64 बिट इनपुट और आउटपुट के केवल 32 बिट्स हैं। Long के हैश होने के लिए दर्ज है:

(int)(this.longValue()^(this.longValue()>>>32)) 

अर्थात कल्पना यह दो int मूल्यों एक दूसरे के बगल अटक है, और उन्हें XOR।

तो इन सब 0 से hashCode होगा:

0 
1L | (1L << 32) 
2L | (2L << 32) 
3L | (3L << 32) 

आदि

मैं कि क्या है कि एक "टकराव की भारी संख्या" के रूप में गिना जाता है पता नहीं है, लेकिन यह एक उदाहरण है, जहां टकराव हैं निर्माण करने में आसान है।

जाहिर किसी भी हैश जहां अधिक से अधिक 2 संभावित मान देखते हैं टकराव होगा, लेकिन कई मामलों में वे निर्माण करने के लिए कठिन हो। उदाहरण के लिए, जबकि मैंने निश्चित रूप से ASCII मानों का उपयोग करके String पर हैश टकराव देखा है, तो वे ऊपर की तुलना में उत्पादन करने के लिए थोड़ा कठिन हैं।

Answer 3

अन्य दो जवाब मैं IMO एक अच्छा देखते हैं लेकिन मैं सिर्फ साझा करने के लिए परीक्षण करने के लिए है कि सबसे अच्छा तरीका है कितनी अच्छी तरह एक HashMap में अपने hashCode() बर्ताव करता है वास्तव में का एक बड़ा संख्या उत्पन्न करने के लिए चाहता था अपनी कक्षा से ऑब्जेक्ट्स, उन्हें विशेष HashMap कार्यान्वयन कुंजी और परीक्षण CPU और मेमोरी लोड के रूप में डाल दें। मापने के लिए 1 या 2 मिलियन प्रविष्टियां एक अच्छी संख्या हैं लेकिन यदि आप अपने अनुमानित मानचित्र आकारों का परीक्षण करते हैं तो आपको सर्वोत्तम परिणाम मिलते हैं।

मैंने अभी एक कक्षा को देखा जिस पर मैंने अपने हैशिंग फ़ंक्शन पर संदेह किया था। तो मैंने उस प्रकार की यादृच्छिक वस्तुओं और टकराव की परीक्षण संख्या के साथ हैश मैप भरने का फैसला किया। मैंने जांच के तहत कक्षा के दो हैशकोड() कार्यान्वयन का परीक्षण किया। इसलिए मैंने हैश मैप में टकराव की संख्या की गणना करने के लिए हैश मैप के ओपनजेडके कार्यान्वयन को विस्तारित करने वाले वर्ग को ग्रोवी में लिखा है (countCollidingEntries() देखें)। ध्यान दें कि ये पूरे हैश के असली टकराव नहीं हैं लेकिन प्रविष्टियों वाले सरणी में टकराव हैं। ऐरे इंडेक्स की गणना hash & (length-1) के रूप में की जाती है जिसका अर्थ है कि इस सरणी के आकार जितना छोटा है, उतना अधिक टक्कर आपको मिलती है। और इस सरणी का आकार initialCapacity और loadFactorHashMap पर निर्भर करता है (यह put() अधिक डेटा में बढ़ सकता है)।

अंत में मुझे लगता है कि इन संख्याओं को देखते हुए थोड़ा सा अर्थ नहीं है। तथ्य यह है कि हैश मैप खराब hashCode() विधि के साथ धीमा है इसका मतलब है कि मानचित्र से डेटा के सम्मिलन और पुनर्प्राप्ति को बेंचमार्क करके आप प्रभावी ढंग से जानते हैं कि hashCode() कार्यान्वयन बेहतर है।

public class TestHashMap extends HashMap { 

    public TestHashMap(int size) { 
     super(size); 
    } 

    public TestHashMap() { 
     super(); 
    } 

    public int countCollidingEntries() { 
     def fs = this.getClass().getSuperclass().getDeclaredFields(); 
     def table; 
     def count =0 ; 
     for (java.lang.reflect.Field field: fs) { 
     if (field.getName() == "table") { 
      field.setAccessible(true); 
      table = field.get(super); 
      break; 
     } 
     } 
     for(Object e: table) { 
     if (e != null) { 
      while (e.next != null) { 
       count++ 
       e = e.next; 
      } 
     } 
     } 
     return count; 
    } 
}