चित्रों में डेटा संरचनाएं। LinkedHashMap

हाय हबचेलोवेकी!

एक लंबे विराम के बाद, मैं जावा में डेटा संरचनाओं की कल्पना करना जारी रखने की कोशिश करूंगा। पिछले लेखों में देखा गया था: ArrayList , LinkedList , HashMap । आज, LinkedHashMap के अंदर एक नज़र डालें।



नाम से आप अनुमान लगा सकते हैं कि यह संरचना लिंक की गई सूचियों और हैश मानचित्रों का सहजीवन है। दरअसल, LinkedHashMap, HashMap वर्ग का विस्तार करता है और मैप इंटरफ़ेस को लागू करता है, लेकिन लिंक की गई सूचियों के बारे में यह क्या है? चलो ठीक है।

वस्तु निर्माण

Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>(); 

Footprint{Objects=3, References=26, Primitives=[int x 4, float, boolean]}
size: 160 bytes

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

• हेडर - एक दोहरी लिंक की गई सूची का प्रमुख। आरंभ में, यह खुद को इंगित करता है;
• accessOrder - इंगित करता है कि पुनरावृत्त का उपयोग करते समय तत्वों को कैसे एक्सेस किया जाएगा। यदि सही है , तो अंतिम पहुंच के क्रम में (लेख के अंत में इस पर अधिक)। यदि गलत है, तो एक्सेस उस क्रम में है जिसमें तत्व डाले गए थे।

LinkedHashMap वर्ग के निर्माता काफी उबाऊ हैं, उनके सभी कार्य मूल वर्ग के निर्माता को कॉल करने और एक्सेसऑर्डर संपत्ति के मूल्य को कम करने के लिए कम हैं। लेकिन हेडर प्रॉपर्टी का इनिशियलाइज़ेशन ओवरराइड इनिट () विधि से होता है ( अब यह स्पष्ट हो जाता है कि हाशप क्लास के कंस्ट्रक्टर्स के पास इस फ़ंक्शन के लिए कॉल क्यों नहीं है )।

 void init() { header = new Entry<K,V>(-1, null, null, null); header.before = header.after = header; } 

एक नई वस्तु बनाई गई है, गुण प्रारंभिक हैं, आप तत्वों को जोड़ने के लिए आगे बढ़ सकते हैं।

आइटम जोड़ना

 linkedHashMap.put(1, "obj1"); 

Footprint{Objects=7, References=32, Primitives=[char x 4, int x 9, float, boolean]}
size: 256 bytes

किसी तत्व को जोड़ते समय, createEntry मेथड (हैश, की, वैल्यू, बकेटइंडेक्स) को सबसे पहले (चेन पुट द्वारा ) (> - addEntry () -> createEntry () ) कहा जाता है

 void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; e.addBefore(header); size++; } 

पहली तीन पंक्तियों में एक तत्व जोड़ा जाता है (टकराव के मामले में, श्रृंखला की शुरुआत में जोड़ घटित होगा, हम बाद में देखेंगे)




चौथी पंक्ति रिफ़ाइन डबल लिंक सूची लिंक




AddEntry () पद्धति में आगे जो कुछ भी होता है वह या तो "कार्यात्मक हित" का प्रतिनिधित्व नहीं करता है या मूल वर्ग की कार्यक्षमता को दोहराता है।

कुछ और तत्व जोड़ें।

 linkedHashMap.put(15, "obj15"); 

Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 352 bytes

 linkedHashMap.put(4, "obj4"); 

Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 448 bytes




जब आप अगला तत्व जोड़ते हैं, तो एक टकराव होता है, और चाबियाँ 4 और 38 वाले तत्व एक श्रृंखला बनाते हैं

 linkedHashMap.put(38, "obj38"); 

Footprint{Objects=20, References=51, Primitives=[float, boolean, char x 18, int x 24]}
size: 560 bytes




मैं इस तथ्य पर आपका ध्यान आकर्षित करता हूं कि किसी तत्व के बार-बार सम्मिलन के मामले में (एक ही कुंजी के साथ एक तत्व पहले से मौजूद है), तत्वों तक पहुंच का क्रम नहीं बदलेगा।

accessOrder == सच

अब आइए एक उदाहरण देखें जब एक्सेसऑर्डर संपत्ति सत्य है । इस स्थिति में, LinkedHashMap का व्यवहार बदलता है और जब आप गेट () और पुट () विधियों को कॉल करते हैं , तो तत्वों का क्रम बदल जाएगा - जिस तत्व को हम संदर्भित करते हैं उसे अंत में रखा जाएगा।

 Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>(15, 0.75f, true) {{ put(1, "obj1"); put(15, "obj15"); put(4, "obj4"); put(38, "obj38"); }}; // {1=obj1, 15=obj15, 4=obj4, 38=obj38} linkedHashMap.get(1); // or linkedHashMap.put(1, "Object1"); // {15=obj15, 4=obj4, 38=obj38, 1=obj1} 

iterators

सब कुछ बहुत सुंदर है:

 // 1. Iterator<Entry<Integer, String>> itr1 = linkedHashMap.entrySet().iterator(); while (itr1.hasNext()) { Entry<Integer, String> entry = itr1.next(); System.out.println(entry.getKey() + " = " + entry.getValue()); } // 2. Iterator<Integer> itr2 = linkedHashMap.keySet().iterator(); while(itr2.hasNext()) System.out.println(itr2.next()); // 3. Iterator<String> itr3 = linkedHashMap.values().iterator(); while (itr3.hasNext()) System.out.println(itr3.next()); 

खैर, असफल-उपवास के बारे में मत भूलना। यदि आपने पहले से ही तत्वों की गणना करना शुरू कर दिया है - सामग्री को न बदलें या अग्रिम में सिंक्रनाइज़ेशन का ध्यान न रखें।

योग के बजाय

यह संरचना मूल HashMap के प्रदर्शन में थोड़ी हीन हो सकती है, जबकि ऐड (), निष्पादन (), निष्कासन () संचालन का निष्पादन समय स्थिर रहता है - O (1)। यह तत्वों और उनके कनेक्शन को संग्रहीत करने के लिए मेमोरी में थोड़ी अधिक जगह लेगा, लेकिन अतिरिक्त चिप्स के लिए यह बहुत कम शुल्क है।

सामान्य तौर पर, इस तथ्य के कारण कि मुख्य वर्ग मुख्य कार्य को लेता है, हाशप और लिंक्डहाशप के कार्यान्वयन में कई गंभीर अंतर नहीं हैं । आप कुछ छोटे लोगों का उल्लेख कर सकते हैं:

• तत्वों के बीच द्विदिश संचार की उपस्थिति के कारण स्थानांतरण () और समरूप () तरीके थोड़े सरल हैं;
• LinkedHashMap.Entry classRemoval () और recordAccess () विधियों को लागू करता है ( एक्सेस एडर के साथ अंत में एक तत्व डालता है )। हाशपैप में, ये दोनों तरीके खाली हैं।

संदर्भ

लिंक्डहाशपॉइंट स्रोत
JDK के स्रोत OpenJDK और व्यापार 6 स्रोत रिलीज़ - बिल्ड b23
माप उपकरण - स्मृति-मापक और अमरूद (Google कोर पुस्तकालय)।

---

¹ - RemoveEldestEntry मेथड (Map.Entry सबसे बड़ा) को कॉल करना हमेशा गलत साबित होता है । यह माना जाता है कि इस पद्धति को किसी भी आवश्यकताओं के लिए ओवरराइड किया जा सकता है, उदाहरण के लिए, मानचित्र के आधार पर कैश संरचनाओं को लागू करने के लिए ( एक्सपायरिंग देखें)। RemoveEldestEntry () सही होने के बाद, अधिकतम पार होने पर सबसे पुराना आइटम हटा दिया जाएगा। मदों की संख्या।