हैश मैप # हैश (int) विधि का स्पष्टीकरण

Question

क्या कोई मुझे स्थिर हैश मैप # हैश (int) विधि समझा सकता है?

समान रूप से वितरित हैंश उत्पन्न करने के लिए इसके पीछे क्या औचित्य है?

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

एक उदाहरण पचाने में आसान बना देगा।

स्पष्टीकरण मैं ऑपरेटरों, सत्य तालिकाओं और बिटवाईर संचालन से अवगत हूं। मैं वास्तव में कार्यान्वयन और वास्तव में टिप्पणी वास्तव में डीकोड नहीं कर सकता। या इसके पीछे भी तर्क।

Answer 1

>>> तार्किक सही पारी (साइन-विस्तार) (JLS 15.19 Shift Operators) है, और ^ बिटवाइज़ अनन्य या (JLS 15.22.1 Integer Bitwise Operators) है।

यह क्यों किया जाता है, प्रलेखन एक संकेत प्रदान करता है: HashMap पावर-ऑफ-दो लम्बाई टेबल का उपयोग करता है, और उच्च बिट्स को मास्क करके और अपने हैश कोड के केवल निम्न बिट्स ले कर हैश की चाबियाँ का उपयोग करता है।

// HashMap.java -- edited for conciseness 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

public V put(K key, V value) { 
    int hash = hash(key.hashCode()); 
    int index = indexFor(hash, table.length); 
    // ... 
} 

तो hash() प्रयास उच्च बिट्स, जो अन्यथा दूर नकाबपोश जायेगा की प्रासंगिकता लाने के लिए (indexFor मूल रूप से h के उच्च बिट्स को छोड़ देता है और उसमें केवल छोटे k बिट्स जहां length == (1 << k) लेता है)।

Hashtable (जिसमें बिजली की दो लंबाई वाली तालिका नहीं होनी चाहिए) के साथ इसे एक कुंजी के हैश कोड का उपयोग करता है।

// Hashtable.java -- edited for conciseness 
public synchronized V get(Object key) { 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % table.length; 
    // ... 
} 

अधिक महंगा % आपरेशन (सरल सा मास्किंग के बजाय) ऐसा करने से, Hashtable के प्रदर्शन कम कम बिट्स (खासकर अगर table.length अभाज्य संख्या है) में गरीब वितरण के साथ कोड हैश करने के लिए संवेदनशील है।

Answer 2

मैं नहीं जानता कि कैसे सब स्थानांतरण काम करता है, लेकिन प्रेरणा टिप्पणी में खर्च की गई थी:

रास्ता HashMap कार्यान्वित किया जाता है hashCode समारोह पर्याप्त रूप में अच्छी तरह से लागू किया जा रहा है पर निर्भर करता है। विशेष रूप से, हैश मान के निचले बिट समान रूप से वितरित किए जाने चाहिए। यदि आपके पास निचले बिट्स पर कई टकराव हैं, तो हैश मैप अच्छा प्रदर्शन नहीं करेगा।

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

तो खराब कार्यान्वित हैशकोड विधियों की उपस्थिति में टकराव को कम करने (और इस प्रकार प्रदर्शन में सुधार) करने का प्रयास करना क्या है।