क्या कोई बता सकता है कि कैसे जावा डिजाइन हैश मैप हैश() फ़ंक्शन? जेडीके के स्रोत कोड को पढ़ने के बाद

Question

, मुझे लगता है कि हैश मैप का hash() फ़ंक्शन मजेदार लगता है। इस तरह इसका soucre कोड:

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); 
} 

पैरामीटर hObjects से hashCode जो HashMap का माध्यम बनाया गया है। यह विधि कैसे काम करती है और क्यों? यह विधि खराब हैशकोड फ़ंक्शंस के विरुद्ध क्यों बचाव कर सकती है?

Answer 1

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

हैश मैप 'दो की शक्ति' का उपयोग करता है, जिसका अर्थ है कि आकार दो की शक्ति है। इसका कारण यह है कि इसे प्राइम नंबर गणना से तेज होना चाहिए। हालांकि, चूंकि दो की शक्ति एक प्रमुख संख्या नहीं है, इसलिए अधिक टक्कर होगी, विशेष रूप से हैश मानों के साथ समान कम बिट्स।

क्यों? आकार (बाल्टी/स्लॉट) इंडेक्स प्राप्त करने के आकार के खिलाफ किए गए मॉड्यूलस की गणना केवल हैश & (आकार -1) (जो इंडेक्स प्राप्त करने के लिए हैश मैप में उपयोग की जाती है!)। यह मूल रूप से 'शक्ति-दो-दो' दृष्टिकोण के साथ समस्या है: यदि लंबाई सीमित है, उदा। 16, हैश मैप का डिफ़ॉल्ट मान, केवल अंतिम बिट्स का उपयोग किया जाता है और इसलिए, उसी निचले बिट्स के साथ हैश मान उसी परिणाम (बाल्टी) इंडेक्स में होंगे। 16 के मामले में, सूचकांक की गणना करने के लिए केवल अंतिम 4 बिट्स का उपयोग किया जाता है।

यही कारण है कि एक अतिरिक्त हैश की गणना की जाती है और मूल रूप से यह उच्च बिट मानों को स्थानांतरित कर रहा है, और कम बिट मानों के साथ उन पर काम करता है। संख्या 20, 12, 7 और 4 के कारण, मुझे वास्तव में पता नहीं है। वे अलग होते थे (जावा 1.5 या तो में, हैश फ़ंक्शन थोड़ा अलग था)। मुझे लगता है कि अधिक उन्नत साहित्य उपलब्ध है। आपको अधिक जानकारी मिल सकती है कि वे उन सभी संख्याओं का उपयोग क्यों करते हैं जिनका उपयोग वे सभी प्रकार के एल्गोरिदम से संबंधित साहित्य में करते हैं, उदाहरण के लिए

http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

http://mitpress.mit.edu/books/introduction-algorithms

http://burtleburtle.net/bob/hash/evahash.html#lookup लंबाई (जो कुछ समझ में आता है) के आधार पर अलग एल्गोरिदम का उपयोग करता।

http://www.javaspecialists.eu/archive/Issue054.html शायद दिलचस्प भी है। लेख के निचले भाग के पास जोशुआ ब्लोच की प्रतिक्रिया की जांच करें: "प्रतिस्थापन माध्यमिक हैश फ़ंक्शन (जिसे मैंने कंप्यूटर की सहायता से विकसित किया है) में मजबूत सांख्यिकीय गुण हैं जो बहुत अच्छी बाल्टी वितरण की गारंटी देते हैं।") तो, अगर आप मुझसे पूछें , संख्या जोश द्वारा किए गए किसी प्रकार के विश्लेषण से आती है, संभवतः कौन जानता है कि कौन जानता है।

तो: दो की शक्ति तेज गणना देता है, लेकिन स्लॉट/बाल्टी पर अच्छा फैलाने के लिए अतिरिक्त हैश गणना के लिए आवश्यकता होती है।