जावा 6, HashSet<E> के स्रोत को देखते हुए वास्तव में सेट की प्रत्येक प्रविष्टि पर डमी ऑब्जेक्ट उदाहरण का उपयोग करके HashMap<E,Object> का उपयोग करके कार्यान्वित किया जाता है।सन जावा में हैशसेट कार्यान्वयन हैश मैप का समर्थन बैकिंग के रूप में क्यों करता है?
मुझे लगता है कि प्रविष्टि के आकार के लिए 4 बाइट (32-बिट मशीनों पर) को बर्बाद कर देता है।
लेकिन, इसका अभी भी उपयोग क्यों किया जाता है? कोड को बनाए रखना आसान बनाने के अलावा इसका उपयोग करने का कोई कारण है?
वास्तव में, यह केवल HashSet नहीं है। सभी जावा 6 में Set इंटरफेस के कार्यान्वयन अंतर्निहित Map पर आधारित हैं। यह एक आवश्यकता नहीं है; यह कार्यान्वयन का तरीका है। आप Set के विभिन्न कार्यान्वयन के लिए प्रलेखन की जांच करके स्वयं के लिए देख सकते हैं।
आपका मुख्य सवाल कर रहे हैं
लेकिन, क्यों यह अभी भी प्रयोग किया जाता है? क्या इसे कोड बनाए रखने के लिए आसान बनाने के अलावा इसका उपयोग करने का कोई कारण है?
मुझे लगता है कि कोड रखरखाव एक बड़ा प्रेरक कारक है। तो नकल और ब्लोट को रोक रहा है।
Set और Map समान इंटरफ़ेस हैं, उस डुप्लिकेट तत्वों की अनुमति नहीं है। (मुझे लगता है कि केवल Setनहीं एक Map द्वारा समर्थित CopyOnWriteArraySet है, जो एक असामान्य संग्रह है, क्योंकि यह अपरिवर्तनीय है।)
:
एक संग्रह है कि इसमें डुप्लिकेट तत्व नहीं हैं। अधिक औपचारिक रूप से, सेट में तत्वों की कोई जोड़ी नहीं है e1 और e2 जैसे कि e1.equals (e2), और अधिकतर शून्य तत्व। जैसा कि द्वारा इसका नाम है, यह इंटरफ़ेस गणितीय सेट अबास्ट्रक्शन मॉडल करता है।
सेट इंटरफ़ेस अतिरिक्त शर्तों देता है, संग्रह इंटरफ़ेस से विरासत में मिला किए जाने के बावजूद, सभी निर्माताओं की ठेके पर और जोड़ने के ठेके पर, के बराबर होती है और hashCode तरीकों। अन्य विरासत विधियों के लिए घोषणा भी सुविधा के लिए यहां शामिल हैं। कंस्ट्रक्टर्स, है आश्चर्यजनक रूप से नहीं, कि सभी निर्माताओं के एक बनाना होगा पर ( विनिर्देशों इन घोषणाओं के साथ सेट इंटरफेस के अनुरूप किया गया है, लेकिन वे किसी भी अतिरिक्त शर्तों शामिल नहीं है।)
अतिरिक्त शर्त सेट जिसमें कोई डुप्लिकेट तत्व नहीं है (जैसा कि ऊपर परिभाषित किया गया है)।
और Map से:
एक वस्तु है कि मूल्यों के लिए कुंजी मैप करता है। एक मानचित्र में डुप्लिकेट कुंजी नहीं हो सकती हैं; प्रत्येक कुंजी अधिकतम एक मूल्य पर मैप कर सकती है।
आप (, गति उदाहरण के लिए) मौजूदा कोड, कोई लाभ का उपयोग कर मौजूदा कोड के साथ-साथ अपने Set को जमा कर लेता से आप महसूस कर सकते हैं अपने Set रों को लागू कर सकते हैं।
यदि आप को Map बैकिंग के बिना लागू करना चुनते हैं, तो आपको डुप्लिकेट तत्वों को रोकने के लिए डिज़ाइन किए गए कोड को डुप्लिकेट करना होगा। आह, स्वादिष्ट विडंबना।
यह कहा गया है कि, आपको Set एस को अलग-अलग लागू करने से रोकने में कुछ भी नहीं है।
"जावा 6 में 'सेट' इंटरफेस के सभी कार्यान्वयन अंतर्निहित 'संग्रह' पर आधारित हैं।" (मुझे लगता है कि आप 'संग्रह' के बजाय 'मानचित्र' का मतलब है।) कम से कम एक काउंटर उदाहरण मौजूद है (सबसेट्स और इसी तरह के अलावा)। 'EnumSet' 'मानचित्र' पर आधारित नहीं है। –
एक और संभावना है: इसे नक्शा
मुझे लगता है कि यह वास्तविक अनुप्रयोगों या महत्वपूर्ण मानकों के लिए एक महत्वपूर्ण समस्या के रूप में कभी नहीं बन गया है। वास्तविक लाभ के लिए कोड जटिल क्यों करें?
यह भी ध्यान दें कि ऑब्जेक्ट आकार कई JVM कार्यान्वयन में गोलाकार हैं, इसलिए वास्तव में आकार में वृद्धि नहीं हो सकती है (मुझे इस उदाहरण के बारे में पता नहीं है)। HashMap के लिए कोड भी संकलित और कैश में होने की संभावना है। अन्य चीजें बराबर होती हैं, अधिक कोड => अधिक कैश मिस => कम प्रदर्शन।
हाँ आप सही हैं, वहां थोड़ी मात्रा में बर्बादी निश्चित है। छोटा क्योंकि, प्रत्येक प्रविष्टि के लिए यह एक ही ऑब्जेक्ट PRESENT (जिसे अंतिम घोषित किया जाता है) का उपयोग करता है। इसलिए हैश मैप में प्रत्येक प्रविष्टि के मूल्य के लिए एकमात्र बर्बादी है।
अधिकतर मुझे लगता है कि उन्होंने रखरखाव और पुन: प्रयोज्यता के लिए यह दृष्टिकोण लिया है। (जेसीएफ डेवलपर्स ने सोचा होगा कि हमने हैश मैप का परीक्षण किया है, फिर भी इसका पुन: उपयोग न करें।)
लेकिन यदि आपके पास विशाल संग्रह हैं, और आप एक मेमोरी सनकी हैं, तो आप Trove जैसे बेहतर विकल्पों के लिए ऑप्ट आउट कर सकते हैं या Google Collections।
अतिरिक्त अपशिष्ट को कुंजी के संदर्भ को संग्रहीत करना है, जो कि आपके पास सेट में लाखों प्रविष्टियां होने पर बड़ी हो सकती है।8bytes * 1M ऑब्जेक्ट्स = 8 एमबी कचरा –
मैंने आपके प्रश्न को देखा और आपने जो कहा, उसके बारे में सोचने में मुझे कुछ समय लगा। तो HashSet कार्यान्वयन के संबंध में मेरी राय यहां दी गई है।
डमी उदाहरण यह जानना आवश्यक है कि मूल्य निर्धारित है या सेट में मौजूद नहीं है।
ऐड विधि पर एक नजर डालें
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
अब्द अब के पुट वापसी मान
पर एक नज़र डालते हैं पिछले मान कुंजी के साथ जुड़े, या नल अगर वहाँ था @returns नहीं कुंजी के लिए मैपिंग। (ए अशक्त वापसी भी इंगित कर सकते है कि नक्शे पहले से कुंजी से संबद्ध अशक्त।)
तो PRESENT वस्तु सिर्फ प्रतिनिधित्व करने के लिए है कि सेट ई मान प्रयोग किया जाता है। मुझे लगता है कि आपने पूछा कि PRESENT के बजाय null का उपयोग क्यों न करें। लेकिन, अगर आप प्रविष्टि पहले मानचित्र पर थे तो आप अंतर नहीं कर पाएंगे क्योंकि map.put(key,value) हमेशा null लौटाएगा और आपको यह जानने का कोई तरीका नहीं होगा कि कुंजी मौजूद है या नहीं।
कहा जा रहा है कि आप बहस कर सकते हैं कि वे, इस
public boolean add(E e) {
if(map.containsKey(e)) {
return false;
}
map.put(e, null);
return true;
}
मुझे लगता है कि वे 4 बाइट बर्बाद hashCode कंप्यूटिंग से बचने के लिए, के रूप में यह महंगा हो सकता है की तरह एक कार्यान्वयन के लिए इस्तेमाल किया जा सकता था कुंजी दो बार (यदि कुंजी को जोड़ा जा रहा है)।
आप केवल 4 की एक ऐसी ही प्रवेश का उपयोग कर कुछ अन्य डेटा संरचना के बजाय क्यों वे एक HashMap इस्तेमाल किया करने के लिए भेजा सवाल तो यह है कि 8 बाइट (Map.Entry की वजह से) बर्बाद होगा, तो हाँ, मैं कहूंगा कि उन्होंने किया आपके द्वारा उल्लिखित कारणों के लिए।
मेरा अनुमान है कि हैशसेट को मूल रूप से हैश मैप के संदर्भ में लागू किया गया ताकि इसे जल्दी और आसानी से किया जा सके। कोड की रेखाओं के संदर्भ में, हैशसेट हैश मैप का एक अंश है।
मुझे लगता है कि अभी भी इसे अनुकूलित नहीं किया गया कारण परिवर्तन का डर है।
हालांकि, अपशिष्ट आपके विचार से भी बदतर है। 32-बिट और 64-बिट दोनों पर, हैशसेट आवश्यक से 4x बड़ा है, और हैश मैप आवश्यक से 2x बड़ा है। हैश मैप को सरणी और मूल्यों के साथ एक सरणी के साथ कार्यान्वित किया जा सकता है (टकराव के लिए चेन)। इसका अर्थ है प्रति प्रवेश दो पॉइंटर्स, या 64-बिट वीएम पर 16 बाइट्स। वास्तव में, हैश मैप में एक एंट्री ऑब्जेक्ट प्रति प्रविष्टि है, जो प्रविष्टि के लिए पॉइंटर के लिए 8 बाइट जोड़ती है और एंट्री ऑब्जेक्ट हेडर के लिए 8 बाइट जोड़ती है। हैशसेट भी प्रति तत्व 32 बाइट्स का उपयोग करता है, लेकिन अपशिष्ट 2x के बजाय 4x है क्योंकि इसे केवल प्रति तत्व 8 बाइट की आवश्यकता होती है।
आपका प्रश्न: मुझे लगता है कि प्रविष्टि के आकार के लिए 4 बाइट (32-बिट मशीनों पर) को बर्बाद कर देता है।
हैशसेट के पूरे डेटास्ट्रक्चर के लिए केवल एक ऑब्जेक्ट वैरिएबल बनाया गया है और ऐसा करने से आप पूरे हैश मैप प्रकार को फिर से लिखने से बचाएंगे।
private static final Object PRESENT = new Object();
सभी चाबियाँ एक मूल्य यानी वर्तमान वस्तु हो रही है।
सोच क्यों हल्का अक्षम मानक कार्यान्वयन इस तरह पृष्ठों के माध्यम से खोज के बाद, पाया com.carrotsearch.hppc.IntOpenHashSet
@yuku: डिफ़ॉल्ट जावा संग्रह में कचरे के स्तर डरावना है। जब आप प्राइमेटिव्स में हेरफेर करते हैं तो सबसे खराब अपराधी होते हैं। आपको लगता है कि हैशसेट
@yuku: मेरी टिप्पणी जारी रखने के लिए ... मेरा मतलब है: या तो perfs और मेमोरी पदार्थ और फिर आपको एक विकल्प खोजना होगा क्योंकि डिफ़ॉल्ट जावा संग्रह में अपशिष्ट का स्तर बहुत अधिक है या आपको इसकी आवश्यकता नहीं है perfs और memory कोई फर्क नहीं पड़ता, क्योंकि आप तत्वों की छोटी संख्या का उपयोग करेंगे और फिर डिफ़ॉल्ट जावा संग्रह ठीक हैं (मुश्किल है Google संग्रह आदि जैसे बेहतर विकल्प हैं) – SyntaxT3rr0r
@WizardOfOdds: यह बहुत सारे बोल्ड स्टेटमेंट्स हैं उन्हें वापस करने के लिए थोड़ा सबूत के साथ। – skaffman