विभिन्न प्रारंभिक क्षमता और लोड फैक्टर

Question

के साथ हैश मैप का प्रदर्शन यहां मेरी स्थिति है। मैं दो java.util.HashMap का उपयोग कर रहा हूं ताकि टॉमकैट पर चल रहे जावा वेब ऐप में कुछ बार इस्तेमाल किए गए डेटा को स्टोर किया जा सके। मुझे प्रत्येक हैशमैप में प्रविष्टियों की सटीक संख्या पता है। चाबियां तार क्रमशः, और स्याही होगी।

मेरा सवाल है, आरंभिक क्षमता और लोडफैक्टर सेट करने का सबसे अच्छा तरीका क्या है?

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

मान लीजिए (और यह एक खिंचाव है) हैश फ़ंक्शन पूर्णांक कुंजी का एक साधारण मोड 5 है, इसका मतलब यह नहीं होगा कि कुंजी 5, 10, 15 एक ही बाल्टी को दबाएगी और फिर एक भरने की तलाश करेगी उनके बगल में बाल्टी? क्या एक बड़ी प्रारंभिक क्षमता प्रदर्शन में वृद्धि होगी?

इसके अलावा, यदि इसके लिए हैशपैप की तुलना में बेहतर डेटास्ट्रक्चर है, तो मैं इसके साथ पूरी तरह से खुला हूं।

Answer 1

अपने डेटा के लिए एक आदर्श हैशिंग समारोह के अभाव में, और यह सोचते हैं कि यह वास्तव में कुछ की एक सूक्ष्म अनुकूलन कि वास्तव में कोई फर्क नहीं पड़ता नहीं है, मैं कोशिश करेंगे निम्नलिखित:

डिफ़ॉल्ट लोड मान लें हैश मैप द्वारा उपयोग की जाने वाली क्षमता (.75) ज्यादातर स्थितियों में एक अच्छा मूल्य है। यह मामला है, आप इसका उपयोग कर सकते हैं, और अपने हैशैप की प्रारंभिक क्षमता को अपने स्वयं के ज्ञान के आधार पर सेट कर सकते हैं कि यह कितनी चीजें रखेगा - इसे सेट करें ताकि आरंभिक क्षमता x .75 = आइटमों की संख्या (राउंड अप) हो।

यदि यह एक बड़ा मानचित्र था, तो ऐसी स्थिति में जहां हाई स्पीड लुकअप वास्तव में महत्वपूर्ण था, मैं हैश मैप के बजाय trie के किसी प्रकार का उपयोग करने का सुझाव दूंगा। लंबे तारों के लिए, बड़े मानचित्रों में, आप एक और स्ट्रिंग-उन्मुख डेटा संरचना, जैसे कि त्रिभुज का उपयोग कर अंतरिक्ष, और कुछ समय बचा सकते हैं।

Answer 2

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

यदि आपके पास अधिक बाल्टी हैं, तो आपके पास कम टक्कर होगी। हालांकि, अधिक बाल्टी का मतलब स्मृति में फैल रहा है और इसलिए धीमा है। आम तौर पर 0.7-0.8 की सीमा में एक लोड कारक लगभग इष्टतम है, इसलिए शायद यह बदलने योग्य नहीं है।

हमेशा की तरह, यह संभवतः इन चीजों को microtuning पर लटका पाने से पहले प्रोफाइलिंग लायक है।

Answer 3

मान लिया जाये कि (और यह एक खंड है) हैश फंक्शन पूर्णांक कुंजी

यह नहीं है की एक सरल आधुनिक 5 है। HashMap.java से:

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

मैं भी नाटक करने के लिए मुझे लगता है कि समझ में नहीं जा रहा हूँ, लेकिन उस तरह सिर्फ इतना है कि स्थिति से निपटने के लिए बनाया गया है यह लग रहा है।

ध्यान दें कि बाल्टी की संख्या हमेशा 2 की शक्ति होती है, इससे कोई फर्क नहीं पड़ता कि आप किस आकार के लिए पूछते हैं।

Answer 4

मुझे सबसे अच्छा लगता है कि डिफ़ॉल्ट सेटिंग्स के साथ चारों ओर झुकाव न करें जब तक कि मुझे वास्तव में वास्तव में आवश्यकता न हो।

हॉटस्पॉट आपके लिए अनुकूलन करने का एक अच्छा काम करता है।

किसी भी मामले में; मैं पहले समस्या को मापने के लिए एक प्रोफाइलर (नेटबीन्स प्रोफाइलर कहें) का उपयोग करूंगा।

हम नियमित रूप से 10000 तत्वों के साथ नक्शे स्टोर करते हैं और यदि आपके पास एक अच्छा बराबर और हैशकोड कार्यान्वयन (और तार और इंटीग्रर्स करते हैं!) यह आपके द्वारा किए जा सकने वाले किसी भी लोड परिवर्तन से बेहतर होगा।

Answer 5

मान लीजिए कि आपका हैश फ़ंक्शन "अच्छा" है, सबसे अच्छी बात यह है कि प्रारंभिक आकार को तत्वों की अपेक्षित संख्या में सेट करना है, यह मानते हुए कि आप सस्ते अनुमान लगा सकते हैं। ऐसा करना एक अच्छा विचार है क्योंकि जब हैश मैप का आकार बदलता है तो उसे तालिका में प्रत्येक कुंजी के लिए हैश मानों को फिर से गणना करना होता है।

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

यदि आप हैश टेबल व्यवहार के गणित में खोदना चाहते हैं: डोनाल्ड Knuth (1 99 8)। कंप्यूटर प्रोग्रामिंग की कला'। 3: छंटनी और खोज (द्वितीय संस्करण)। एडिसन-वेस्ले। पीपी 513-558। आईएसबीएन 0-201-89685-0।