बिट पैटर्न की कौन सी संपत्ति टकराव का कारण बनती है?

Question

मैं हैश कुंजी को यादृच्छिक बनाने के लिए जावा के दृष्टिकोण के बारे में पढ़ रहा था here
जाहिर है यह विचार यह सुनिश्चित करना है कि निचले बिट्स वितरण में मदद करने के लिए "यादृच्छिक" हैं लेकिन मैं इसे और समझने की कोशिश कर रहा हूं।
तो यदि हमारे पास आकार 10 की एक तालिका है तो संख्या 0,10,20,30,40 आदि सभी बाल्टी 0 में आती हैं, संख्या 1,11,21,31 आदि बाल्टी 1 आदि में गिरती हैं (मॉड्यूलो 10 का उपयोग करके) ।
तो बिट पैटर्न को बदलने से आप इन्हें बाल्टी 0 पर जाने के बजाए अलग-अलग बाल्टी में जा सकते हैं।
लेकिन मुझे इस बारे में स्पष्ट नहीं है कि यह कितना संपत्ति है जिससे कम ऑर्डर बिट प्रभावित होते हैं और हमें यादृच्छिक बनाना होगा उन्हें। तो हमने:

0000 0000 (0) 
0000 1010 (10) 
0001 0100 (20) 
0001 1110 (30) 
0010 1000 (40) 

कम आदेश बिट है कि उन्हें बनाता में नियमितता ही स्लॉट के लिए रखा क्या है?
शायद मैं निम्नलिखित पर उलझन में हूं? मेरी समझ यह है कि यह कम ऑर्डर बिट्स में कुछ नियमितता है जो टकराव का कारण बनती है और हम

Answer 1

को क्षतिपूर्ति करने के लिए बिट को यादृच्छिक करने का प्रयास करते हैं। कुछ हैश फ़ंक्शंस कम ऑर्डर बिट्स को यादृच्छिक करने का वास्तव में खराब काम करते हैं।

एक क्लासिक केस हार्डवेयर पते का उपयोग ऑब्जेक्ट संदर्भों के लिए हैश के रूप में है (सी में "पॉइंटर्स"), जो अन्यथा ऑब्जेक्ट-आईडी के लिए एक अद्वितीय संख्या प्राप्त करने का उचित तरीका होगा। यदि हैश टेबल की बाल्टी गिनती एक प्रमुख संख्या थी, तो यह ठीक काम करेगा, लेकिन हैश कार्यान्वयन के लिए जहां बाल्टी की संख्या हमेशा 2 की शक्ति होती है, तथ्य यह है कि सभी हैंश 8 से विभाजित होते हैं, इसका मतलब यह होगा कि अधिकतर बाल्टी खाली थीं।

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

Answer 2

जावा का हैश मैप एक हैश टेबल आकार का उपयोग करता है जो दो की शक्तियां हैं। यदि आप सामान्य रूप से संपीड़न फ़ंक्शन के रूप में शेष/मॉड्यूलो ऑपरेशन का उपयोग करते हैं, तो आप बाल्टी इंडेक्स के रूप में हैश कोड के निम्नतम बिट्स लेते हैं। यदि हैश कोड दो शक्तियों के गुणक होते हैं, तो निम्नतम बिट्स में से कुछ हमेशा शून्य होंगे, और आप उपलब्ध बाल्टी के एक अंश का उपयोग करके समाप्त हो जाते हैं।

कंक्रीट उदाहरण: मान लें कि आपके पास 32 बाल्टी हैं और हैश कोड 8 के गुणक हैं। तालिका कोड के केवल 5 कम महत्वपूर्ण बिट्स का उपयोग करती है, और उनमें से 3 हमेशा 0 होती हैं। इसलिए केवल 2 बिट बाल्टी निर्धारित करते हैं, और आप केवल 4 32 बाल्टियों की का उपयोग करें: यह बिट्स scrambles इतना है कि यह काफी नहीं है के रूप में:

XXXXXX00000 -> bucket 0 
XXXXXX01000 -> bucket 8 
XXXXXX10000 -> bucket 16 
XXXXXX11000 -> bucket 24 

सौभाग्य से बातें इस बुरा जावा में क्योंकि HashMap सिर्फ हैश कोड के निम्नतम बिट्स का प्रयोग नहीं करता नहीं कर रहे हैं गलती से खराब परिदृश्यों का उत्पादन करना आसान है।

/** 
* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
}