जावा: हैशसेट बनाम हैश मैप

Question

मेरे पास एक विशाल डेटा सेट पर काम करने वाला एक प्रोग्राम है। ऑब्जेक्ट को कंटेनर में ऑब्जेक्ट्स की तलाश रखने के बाद से हैश लागू कंटेनर पर ऑब्जेक्ट्स सबसे अच्छी तरह से संग्रहीत हैं।

पहला विचार हैश मैप का उपयोग करना था क्योंकि इस कंटेनर के तरीके प्राप्त करने और निकालने के लिए मुझे आवश्यक उपयोगों के लिए अधिक उपयुक्त है।

लेकिन, मुझे देखने के लिए HashMap के उपयोग सुंदर स्मृति उपभोज्य जो एक बड़ी समस्या है है आया था, इसलिए मैंने सोचा HashSet का उपयोग करने जा बेहतर होगा क्योंकि यह केवल <E> का उपयोग करता है, और तत्व प्रति नहीं <K,V>, लेकिन जब मैं को देखा कार्यान्वयन मैंने सीखा है कि यह अंतर्निहित हैश मैप का उपयोग करता है! इसका मतलब है कि यह किसी भी स्मृति को बचा नहीं होगा!

तो यह मेरे सवालों का है:

• मेरे सभी मान्यताओं सच हैं?
• हैश मैप मेमोरी बर्बाद है? अधिक विशेष रूप से, प्रत्येक प्रविष्टि के लिए इसका ओवरहेड क्या है?
• हैशसेट बस हैश मैप के रूप में अपमानजनक है?

• क्या कोई अन्य हैश आधारित कंटेनर है जो काफी कम उपभोग्य सामग्रियों का होगा?

  अद्यतन

टिप्पणी में अनुरोध के रूप में मैं अपने कार्यक्रम के बारे में थोड़ा विस्तार होगा, HashMap अन्य वस्तुओं की एक जोड़ी है, और कुछ संख्यात्मक मान का मतलब है - एक float- गणना से उन्हें। जिस तरह से यह उनमें से कुछ निकालता है और नए जोड़े में प्रवेश करता है। एक जोड़ी को देखते हुए इसे यह सुनिश्चित करने की ज़रूरत है कि यह इस जोड़ी को पकड़ न सके या इसे हटा दें। मानचित्रण को फ्लोट मान या जोड़ी ऑब्जेक्ट के hashCode का उपयोग करके किया जा सकता है।

इसके अतिरिक्त जब मैं कहते हैं कि "विशाल डेटा सेट" मैं के बारे में ~ 4 * 10^9 वस्तुओं

Answer 1

बात कर रहा हूँ मेरे सभी मान्यताओं सच हैं?

आप सही है कि HashSetHashMap का उपयोग कर कार्यान्वित किया जाता है, इसलिए आप के बजाय HashSet उपयोग करके किसी भी स्मृति नहीं बचत होगी।

आप तत्वों की एक बड़ी संख्या के साथ नक्शे बना रहे हैं, तो आप अपने HashMap रों आपकी जानकारी के, के लिए एक initialCapacity साथ क्रम दोहराया rehashing (इस प्रकार स्मृति ताड़ना) को रोकने के लिए निर्माण करना चाहिए।

हैश मैप मेमोरी बर्बाद है? अधिक विशेष रूप से, प्रत्येक प्रविष्टि के लिए इसके ओवरहेड क्या है?

नहीं, यह अपर्याप्त नहीं है। ओवरहेड एक अंतर्निहित सरणी है (आकार loadFactor द्वारा संशोधित), और प्रत्येक कुंजी-मूल्य जोड़ी के लिए Entry ऑब्जेक्ट है। एक कुंजी और मूल्य को संग्रहीत करने के अलावा, एंट्री ऑब्जेक्ट एक स्लॉट में अगली प्रविष्टि में एक पॉइंटर भी संग्रहीत करता है (यदि दो या दो से अधिक प्रविष्टियां अंतर्निहित सरणी में एक ही स्लॉट पर कब्जा कर रही हैं)। 0.75 का डिफ़ॉल्ट लोड फ़ैक्टर अंतर्निहित सरणी आकार प्रविष्टियों की संख्या के 133% पर रखता है।

बहुत विशेष रूप से, प्रत्येक प्रविष्टि के लिए स्मृति भूमि के ऊपर है:

• कुंजी के लिए प्रवेश वस्तु के संदर्भ,
• मूल्य के लिए प्रवेश वस्तु के संदर्भ,
• अगले के लिए प्रवेश वस्तु के संदर्भ प्रविष्टि,
• और प्रविष्टि के अंतर्निहित सरणी का संदर्भ (लोड कारक द्वारा विभाजित)।

हैश-आधारित संग्रह के लिए उससे अधिक ट्रिम करना बहुत मुश्किल है।

हैशसेट बस हैश मैप के रूप में अपमानजनक है?

HashMap के बजाय आपको HashSet का उपयोग करके कोई मेमोरी दक्षता नहीं मिलेगी।

क्या कोई अन्य हैश आधारित कंटेनर है जो कम मेमोरी उपभोग्य सामग्रियों में महत्वपूर्ण होगा?

अपनी चाबी पुरातन (जैसे int रों) कर रहे हैं, देखते हैं कस्टम Map और वहाँ बाहर Set कार्यान्वयन (third party libraries में) जो अधिक स्मृति कुशल डाटा संरचनाओं का उपयोग करें।

Answer 2

जावा में संग्रह प्रदर्शन के बारे में this site पर बहुत उपयोगी युक्तियां हैं।

HashSet एक HashMap< T, Object >, जहां मूल्य एक सिंगलटन 'वर्तमान' वस्तु है के शीर्ष पर बनाया गया है। इसका मतलब है कि the memory consumption of aHashSet is identical to HashMap: SIZE मानों को स्टोर करने के लिए, आपको 32 * SIZE + 4 * क्षमता बाइट्स (आपके मूल्यों का प्लस आकार) की आवश्यकता है। यह निश्चित रूप से स्मृति-अनुकूल संग्रह नहीं है।

THashSetHashSet के लिए सबसे आसान प्रतिस्थापन संग्रह हो सकता है - यह सेट और इटेबल लागू करता है, जिसका अर्थ है कि आपको बस अपने सेट के प्रारंभ में एक ही अक्षर अपडेट करना चाहिए।

THashSet अपने मानों के लिए एक ऑब्जेक्ट सरणी का उपयोग करता है, इसलिए यह भंडारण के लिए 4 * क्षमता बाइट्स का उपयोग करता है। जैसा कि आप देख सकते हैं, जेडीके हैशसेट की तुलना में, आप 32 * SIZE बाइट्स समान लोड फैक्टर के मामले में बाइट्स, जो एक बड़ा सुधार है, बचाएंगे।

इसके अलावा नीचे दी गई छवि जो मैं here से ले लिया सही संग्रह

Answer 3

यह सच है कि HashSet HashMap के रूप में बस के रूप में अधिक स्मृति का उपयोग करता है चुनने के लिए हमें मन में कुछ रखने कर सकते हैं। हैससेट सेट अप दोनों के बीच का अंतर, यानी, यह किसी कुंजी से जुड़े किसी भी मूल्य, केवल उपस्थिति या किसी विशेष मूल्य की कमी के बारे में परवाह नहीं करता है। हैश मैप प्रति कुंजी मानों को संग्रहित/पुनर्प्राप्त (रख/प्राप्त) से संबंधित है।

जबकि हैश मैप/हैशसेट डेटा को उस सरणी में संग्रहीत करता है जो आम तौर पर तत्वों की संख्या से थोड़ा बड़ा होता है, यह एक समस्या का बहुत अधिक नहीं होता क्योंकि लोड कारक है .75। इसका मतलब यह है कि तत्वों की संख्या अंतर्निहित सरणी के आकार के 75% तक पहुंचने पर हैश मैप बढ़ेगा।

बहुत बड़ा मानचित्र से एक बड़ा चिंता का विषय है, खाली नक्शे के बहुत सारे होगा के बाद से एक HashMap का डिफ़ॉल्ट आकार 16. यह 0.

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

इसके अतिरिक्त, ट्रीमैप प्रोग्रामिंग कारणों के लिए उपयोग किया जा सकता है जब आप या तो equals और hashCode अपने कुंजी प्रकार के तरीकों का कस्टम कार्यान्वयन नहीं करना चाहते हैं। आप इसके बजाय कुंजी प्रकार के लिए तुलनित्र बना सकते हैं। उदा।, केस-असंवेदनशील स्ट्रिंग के आधार पर एक नक्शा/सेट बनाने के लिए, String.CASE_INSENSITIVE_ORDER का उपयोग ट्रीसेट