मैप <K,V> का कौन सा कार्यान्वयन मुझे उपयोग करना चाहिए यदि मेरे मानचित्र को तेज़ से छोटा होना चाहिए?

Question

मैं अपने कार्यक्रमों में HashMap का उपयोग करता हूं, क्योंकि मुझे पता है कि यह आमतौर पर सबसे कुशल (यदि सही ढंग से उपयोग किया जाता है) और आसानी से बड़े मानचित्रों का सामना कर सकता है। मुझे EnumMap पता है जो गणना कुंजी के लिए बहुत उपयोगी है, लेकिन अक्सर मैं एक छोटा नक्शा उत्पन्न कर रहा हूं जो कभी भी बहुत बड़ा नहीं होगा, जल्द ही इसे छोड़ दिया जा सकता है, और इसमें कोई सहमति नहीं है।

HashMap<K,V> इन छोटे, स्थानीय और अस्थायी उपयोगों के लिए बहुत जटिल है? क्या कोई और सरल, कार्यान्वयन है जिसका मैं इन मामलों में उपयोग कर सकता हूं?

मुझे लगता है कि मैं Map कार्यान्वयन की तलाश में हूं जो ArrayListList के लिए समान है। क्या यह अस्तित्व में है?

---

बाद में प्रतिक्रियाओं के बाद जोड़ा गया:

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

संसाधन उपयोग केवल गति से अधिक है - मुझे ऐसा कुछ चाहिए जो ढेर को बहुत कम नहीं करता है और उदाहरण के लिए जीसी को लंबा समय लगता है।

यह हो सकता है कि HashMap सही उत्तर है, लेकिन यह समयपूर्व अनुकूलन (या कम से कम यह नहीं हो सकता है) का मामला नहीं है।

---

जोड़ा बहुत बाद में कुछ विचार के बाद:

मैं करने के लिए हाथ से कोड अपने ही SmallMap फैसला किया। AbstractMap के साथ एक बनाना आसान है। मैंने कुछ रचनाकार भी जोड़े हैं ताकि SmallMap मौजूदा Map से बनाया जा सके।

जिस तरह से मुझे यह तय करना था कि Entry एस का प्रतिनिधित्व कैसे करें और entrySet विधि के लिए SmallSet लागू करने के लिए।

मैंने कोडिंग (और यूनिट-टेस्टिंग) द्वारा बहुत कुछ सीखा और इसे साझा करना चाहते हैं, अगर कोई और चाहता है। यह github here पर है।

Answer 1

जावा में Map का कोई मानक छोटा कार्यान्वयन नहीं है। HashMap आसपास के सबसे अच्छे और सबसे लचीले Map कार्यान्वयन में से एक है, और इसे हरा करना मुश्किल है। हालांकि, बहुत छोटी आवश्यकता क्षेत्र में - जहां ढेर उपयोग और निर्माण की गति सर्वोपरि है - बेहतर करना संभव है।

मैंने गिटहब पर SmallCollections लागू किया है ताकि यह प्रदर्शित किया जा सके कि यह कैसे किया जा सकता है। मैं प्यार पर कुछ टिप्पणियां करता हूं कि मैं सफल हुआ हूं या नहीं। यह निश्चित रूप से निश्चित नहीं है कि मेरे पास है।

हालांकि यहां दिए गए उत्तरों कभी-कभी सहायक होते थे, लेकिन सामान्य रूप से, बिंदु को गलत समझने के लिए वे सामान्य रूप से देखते थे। किसी भी मामले में, मेरे अपने प्रश्न का उत्तर अंत में, एक दिया जाने से मुझे अधिक उपयोगी था।

यहां प्रश्न ने अपना उद्देश्य पूरा किया है, और यही कारण है कि मैंने 'इसे स्वयं उत्तर दिया' है।

Answer 2

मुझे लगता है कि यह समयपूर्व अनुकूलन है। क्या आपको स्मृति समस्याएं हैं? बहुत सारे मानचित्र बनाने से प्रदर्शन समस्याएं? अगर नहीं, मुझे लगता है कि हैश मैप ठीक है।

इसके अलावा, एपीआई को देखते हुए, मुझे HashMap से कुछ भी आसान नहीं दिख रहा है।

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

Answer 3

ए हैश मैप संभवतः सबसे हल्का वजन और सरल संग्रह है।

कभी-कभी पीओजेओ का उपयोग करने के लिए अधिक कुशल समाधान होता है। जैसे यदि आपकी कुंजी फ़ील्ड नाम हैं और/या आपके मान प्राइमेटिव हैं।

Answer 4

मैं @hvgotcodes से सहमत हूं कि यह समयपूर्व अनुकूलन है लेकिन टूलबॉक्स में सभी टूल्स को जानना अभी भी अच्छा है।

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

तो निश्चित रूप से मामले होते हैं जब एक HashMap बिल्कुल कोई मतलब नहीं है, यदि आप तीन मूल्यों जो तुम हमेशा कुंजी 0, 1 और 2 के साथ सूचकांक लेकिन मुझे लगता है होगा की तरह आप समझते हैं कि :-)

Answer 5

हैश मैप एक अच्छी पसंद है क्योंकि यह औसत केस O(1) रखता है और प्राप्त करता है। यह सॉर्टेड मैप कार्यान्वयन की तरह ऑर्डरिंग की गारंटी नहीं देता है (यानी TreeMap O(log n) डालता है और प्राप्त करता है) लेकिन यदि आपके पास आदेश देने के लिए कोई आवश्यकता नहीं है तो हैश मैप बेहतर है।

Answer 6

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

ढेर विखंडन और जीसी चक्र बर्बाद करने और क्या नहीं, उतना ही नहीं है कि नक्शा कार्यान्वयन उनके बारे में कर सकता है; यह सब वापस आ जाता है कि आप इसे कैसे सेट करते हैं। समझें कि यह जावा के कार्यान्वयन के बारे में नहीं है, लेकिन तथ्य यह है कि जेनेरिक (उदाहरण के लिए, EnumMap जैसे प्रमुख मानों के बारे में कुछ भी नहीं मान सकता है) हैशटेबल्स (HashTable एस) मानचित्र संरचना का सर्वोत्तम संभव कार्यान्वयन नहीं है।

Answer 7

एयरकोनक्रेंटमैप नामक एक विकल्प है जो कि किसी अन्य मानचित्र की तुलना में 1K प्रविष्टियों से अधिक मेमोरी कुशल है, और कुंजी-आधारित संचालन के लिए ConcurrentSkipListMap से तेज़ है और पुनरावृत्तियों के लिए किसी भी मानचित्र से तेज़ है, और इसमें आंतरिक थ्रेड पूल है समानांतर स्कैन के लिए। यह एक आदेश दिया गया है यानी NavigableMap और एक ConcurrentMap। यह गैर-वाणिज्यिक नो-सोर्स उपयोग के लिए स्वतंत्र है, और व्यावसायिक रूप से बिना स्रोत के लाइसेंस प्राप्त है। ग्राफ के लिए boilerbay.com देखें। पूर्ण प्रकटीकरण: मैं लेखक हूं।

एयरकॉनक्यूरेंटमैप मानकों के अनुरूप है, इसलिए यह नियमित मानचित्र के लिए भी हर जगह प्लग-संगत है।

आईटरेटर पहले से ही बहुत तेजी से 1K प्रविष्टियों से अधिक तेज़ हैं। उच्च स्पीड स्कैन एक 'विज़िटर' मॉडल का उपयोग एक एकल विज़िट (के, वी) कॉलबैक के साथ करते हैं जो जावा 8 समांतर धाराओं की गति तक पहुंचता है। AirConcurrentMap समानांतर स्कैन लगभग 8x तक जावा 8 समांतर धाराओं से अधिक है। पिरोया आगंतुक जोड़ता() विभाजित है और विलय() एकल धागा आगंतुक है कि नक्शे में से एक को याद दिलाने के तरीकों/कम करने:

static class ThreadedSummingVisitor<K> extends ThreadedMapVisitor<K, Long> { 
    private long sum; 
    // This is idiomatic 
    long getSum(VisitableMap<K, Long> map) { 
     sum = 0; 
     map.getVisitable().visit(this); 
     return sum; 
    } 

    @Override 
    public void visit(Object k, Long v) { 
     sum += ((Long)v).longValue(); 
    } 

    @Override 
    public ThreadedMapVisitor<K, Long> split() { 
     return new ThreadedSummingVisitor<K>(); 
    } 

    @Override 
    public void merge(ThreadedMapVisitor<K, Long> visitor) { 
     sum += ((ThreadedSummingVisitor<K>)visitor).sum; 
    } 
} 
... 
// The threaded summer can be re-used in one line now. 
long sum = new ThreadedSummingVisitor().getSum((VisitableMap)map); 

Answer 8

एंड्रॉयड स्मृति को कम करने के इरादे के साथ एक ArrayMap है। कोर में होने के अलावा, यह v4 समर्थन लाइब्रेरी में है, जो सैद्धांतिक रूप से, ओरेकल या ओपनजेडीके जेआरई के लिए भी संकलित करने में सक्षम होना चाहिए। यहां the source of ArrayMap in a fork of the v4 support library on github का एक लिंक है।