LinkedHashMap का कार्यान्वयन हैश मैप से अलग कैसे है?

Question

यदि LinkedHashMap की समय जटिलता हैश मैप की जटिलता के समान है तो हमें हैश मैप की आवश्यकता क्यों है? जावा में हैश मैप की तुलना में सभी अतिरिक्त ओवरहेड लिंक किए गए हैशैप क्या हैं?

Answer 1

LinkedHashMap अधिक मेमोरी लेगा। सामान्य HashMap में प्रत्येक प्रविष्टि में केवल कुंजी और मान होता है। प्रत्येक LinkedHashMap प्रविष्टि में उन संदर्भों को और अगली और पिछली प्रविष्टियों के संदर्भ हैं। ऐसा करने के लिए थोड़ा और अधिक हाउसकीपिंग भी है, हालांकि यह आमतौर पर अप्रासंगिक है।

Answer 2

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

Answer 3

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

Answer 4

यदि लिंकड हैशैप की समय जटिलता हैश मैप की जटिलता के समान है तो हमें हैश मैप की आवश्यकता क्यों है?

आपको प्रदर्शन के साथ जटिलता को भ्रमित नहीं करना चाहिए। दो एल्गोरिदम में एक ही जटिलता हो सकती है, फिर भी कोई लगातार दूसरे से बेहतर प्रदर्शन कर सकता है।

याद रखें f(N) is O(N) इसका मतलब है कि:

C1*N <= limit(f(N), N -> infinity) <= C2*N 

जहां C1 और C2 सख्ती से सकारात्मक स्थिरांक हैं। जटिलता कुछ भी नहीं कहती है कि C मान कितने छोटे या बड़े हैं। दो अलग-अलग एल्गोरिदम के लिए, स्थिरांक अलग-अलग होंगे।

(और याद रखें बड़ा-ओ जटिलता व्यवहार/प्रदर्शन के बारे में है कि के रूप में N बहुत बड़े हो जाता है। यह आप छोटे N मूल्यों के लिए व्यवहार/प्रदर्शन के बारे में कुछ भी नहीं बताता है।)

---

कहा है, कि समकक्ष उपयोग-मामलों में HashMap और LinkedHashMap संचालन के बीच प्रदर्शन में अंतर अपेक्षाकृत छोटा है। अक्सर, अतिरिक्त मेमोरी ओवरहेड जो अधिक प्रासंगिक होते हैं।

Answer 5

हैश मैप और लिंक्ड हैशैप के बीच एक और बड़ा अंतर है: लिंक्ड हैशैप के मामले में इटरेशन अधिक कुशल है।

LinkedHashMap में तत्वों एक दूसरे के साथ जुड़े हुए हैं वैसे ही यात्रा समय नक्शे के आकार के अनुपात में, अपनी क्षमता की परवाह किए बिना की आवश्यकता है। लेकिन के मामले में हैश मैप; क्योंकि कोई निश्चित आदेश नहीं है, इसलिए इसके प्रति पुनरावृत्ति के लिए इसकी क्षमता के अनुपात के लिए समय की आवश्यकता होती है।

मैंने अपने blog पर अधिक जानकारी दी है।

Answer 6

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

Answer 7

लिंक्ड हैशैप हैश मैप को विरासत में मिला, जिसका अर्थ यह है कि यह नोड (प्रविष्टि ऑब्जेक्ट) में कुंजी और मानों को स्टोर करने के लिए हैश मैप के मौजूदा कार्यान्वयन का उपयोग करता है। इसके अलावा यह सम्मिलन आदेश को बनाए रखने के लिए एक अलग दोगुनी लिंक्ड सूची कार्यान्वयन को संग्रहीत करता है जिसमें कुंजी दर्ज की गई है।

हैडर नोड < ---> नोड 1 < ---> नोड 2 < ---> नोड 3 < ----> नोड 4 < ---> हैडर:

यह इस तरह दिखता है नोड।

तो अतिरिक्त ओवरलोड इस दोगुनी लिंक्ड सूची में सम्मिलन और हटाना बनाए रखता है। लाभ है: इटरेशन ऑर्डर सम्मिलन आदेश होने की गारंटी है, जो हैश मैप में नहीं है।

Answer 8

HashMap सम्मिलन आदेश को बनाए रखता नहीं है, इसलिए किसी भी दोगुनी लिंक वाली सूची को बनाए रखता नहीं है।

LinkedHashMap की सबसे प्रमुख विशेषता यह है कि यह कुंजी-मूल्य जोड़े के सम्मिलन आदेश को बनाए रखती है। LinkedHashMap ऐसा करने के लिए दोगुनी लिंक्ड सूची का उपयोग करता है।

LinkedHashMap का प्रवेश इस तरह दिखता है:

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K,V> next; 
    Entry<K,V> before, after;  //For maintaining insertion order  
    public Entry(K key, V value, Entry<K,V> next){ 
     this.key = key; 
     this.value = value; 
     this.next = next; 
    } 
    } 

से पहले का उपयोग करके और बाद - हम LinkedHashMap में नए जोड़े गए प्रविष्टि है, जो हमें प्रविष्टि व्यवस्था बनाए रखने में मदद करता है पर नज़र रखें।

पिछली प्रविष्टि और को संदर्भित करने से पहले LinkedHashMap में अगली प्रविष्टि को संदर्भित करने के बाद।

चित्र और कदम विवरण द्वारा कदम देखें http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html