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

मैं आपका स्वागत करता हूं, हेब्रिटाचेटेली!

मैं जावा में डेटा संरचनाओं की कल्पना करने का प्रयास जारी रखता हूं। पिछले एपिसोड में, हम पहले से ही ArrayList और LinkedList के साथ खुद को परिचित कर चुके हैं, आज हम जशपस्ट को देखेंगे।



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

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

Map<String, String> hashmap = new HashMap<String, String>(); 

Footprint{Objects=2, References=20, Primitives=[int x 3, float]}
Object size: 120 bytes

नव-निर्मित हैशमैप ऑब्जेक्ट में कई गुण होते हैं:

• तालिका - प्रकार प्रविष्टि की एक सरणी [] , जो मूल्यों की सूचियों (जंजीरों) के लिंक का भंडार है;
• loadFactor - भार कारक। 0.75 का डिफ़ॉल्ट मान एक्सेस समय और संग्रहीत डेटा की मात्रा के बीच एक अच्छा समझौता है;
• दहलीज - जिन तत्वों की अधिकतम संख्या हैश तालिका दोगुनी है। यह सूत्र (क्षमता * loadFactor) द्वारा गणना की जाती है;
• आकार - हाशप तत्वों की संख्या;

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

 //     // capacity -     16 table = new Entry[capacity]; 

आप HashMap (क्षमता) और HashMap (क्षमता, loadFactor) कंस्ट्रक्टर का उपयोग करके अपनी क्षमता और लोड कारक निर्दिष्ट कर सकते हैं। आपके द्वारा निर्धारित अधिकतम क्षमता इंट (1073741824) का अधिकतम मूल्य आधा है।

आइटम जोड़ना

 hashmap.put("0", "zero"); 

Footprint{Objects=7, References=25, Primitives=[int x 10, char x 5, float]}
Object size: 232 bytes

किसी आइटम को जोड़ते समय, चरणों का क्रम इस प्रकार है:

1. सबसे पहले, कुंजी नल के लिए जाँच की है। यदि यह जांच सही हो जाती है, तो putForNullKey (मान) विधि को बुलाया जाएगा ( हम थोड़ी देर बाद शून्य कुंजी जोड़ने के विकल्प पर विचार करेंगे)।
   
   
2. इसके बाद, एक कुंजी-आधारित हैश उत्पन्न होता है। पीढ़ी के लिए, हैश (हैशकोड) पद्धति का उपयोग किया जाता है, जिसमें key.hashCode () पास होता है ।
   
   

    static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

   
   स्रोतों से एक टिप्पणी बताती है कि क्या परिणाम की उम्मीद की जानी चाहिए - हैश (कुंजी) विधि यह सुनिश्चित करती है कि प्राप्त हैश कोड में केवल सीमित संख्या में टकराव होंगे (लगभग 8, लोड कारक के डिफ़ॉल्ट मूल्य के साथ)।
   
   मेरे मामले में, '`0' के मान के साथ एक कुंजी के लिए , हैशकोड () विधि 48 लौटा, परिणामस्वरूप:
   
   

    h ^ (h >>> 20) ^ (h >>> 12) = 48 h ^ (h >>> 7) ^ (h >>> 4) = 51 

   
   
   
3. इंडेक्सफोर (हैश, टेबल लैंथ) विधि का उपयोग करके , एरे में वह स्थान जहां तत्व रखा जाएगा, निर्धारित किया जाता है।
   
   

    static int indexFor(int h, int length) { return h & (length - 1); } 

   
   51 के हैश मान और 16 के एक टेबल आकार के साथ, हम सरणी में सूचकांक प्राप्त करते हैं:
   
   

    h & (length - 1) = 3 

   
   
   
4. अब, सरणी में सूचकांक को जानने के बाद, हमें इस सेल से जुड़े तत्वों की एक सूची (श्रृंखला) मिलती है। नए तत्व के हैश और कुंजी की तुलना सूची से तत्वों की हैश और कुंजी के साथ एक-एक करके की जाती है और, यदि ये पैरामीटर मेल खाते हैं, तो तत्व का मान ओवरराइट हो जाता है।
   
   

    if (e.hash == hash && (e.key == key || key.equals(e.key))) { V oldValue = e.value; e.value = value; return oldValue; } 

   
   
   
5. यदि पिछले चरण में कोई मिलान नहीं मिला, तो एक नया तत्व जोड़ने के लिए addEntry (हैश, की, वैल्यू, इंडेक्स) विधि को बुलाया जाएगा।
   
   

    void addEntry(int hash, K key, V value, int index) { Entry<K, V> e = table[index]; table[index] = new Entry<K, V>(hash, key, value, e); ... } 

   
   
   
   

यह दिखाने के लिए कि हाशप कैसे भरता है, हम कुछ और तत्व जोड़ते हैं।

---

 hashmap.put("key", "one"); 

Footprint{Objects=12, References=30, Primitives=[int x 17, char x 11, float]}
Object size: 352 bytes

1. छोड़ दिया, कुंजी शून्य नहीं है
   
   
2. '' की ''। हैशकोड () = 106079
   
   

    h ^ (h >>> 20) ^ (h >>> 12) = 106054 h ^ (h >>> 7) ^ (h >>> 4) = 99486 

   
   
3. एक सरणी में स्थिति की परिभाषा
   
   

    h & (length - 1) = 14 

   
   
4. कोई समान आइटम नहीं मिला
   
   
5. आइटम जोड़ें
   
   
   
   

---

 hashmap.put(null, null); 

Footprint{Objects=13, References=33, Primitives=[int x 18, char x 11, float]}
Object size: 376 bytes

जैसा कि ऊपर उल्लेख किया गया है, यदि किसी आइटम को जोड़ते समय नल को कुंजी के रूप में पारित किया गया था, तो क्रियाएं अलग होंगी। PutForNullKey (मान) विधि को कहा जाएगा, जिसके अंदर हैश () और इंडेक्सफ़ोर () विधियों के लिए कोई कॉल नहीं है (क्योंकि अशक्त कुंजियों वाले सभी तत्वों को हमेशा तालिका [0] में रखा जाता है), लेकिन ऐसी क्रियाएं हैं:

1. तालिका [0] से बंधी श्रृंखला के सभी तत्वों को नल कुंजी के साथ एक तत्व की तलाश में वैकल्पिक रूप से खोजा जाता है। यदि श्रृंखला में ऐसा कोई तत्व मौजूद है, तो इसका मान अधिलेखित है।
   
   
2. यदि नल कुंजी के साथ तत्व नहीं मिला, तो परिचित addEntry () विधि कहा जाएगा।
   
   

    addEntry(0, null, value, 0); 

   
   
   
   

---

 hashmap.put("idx", "two"); 

Footprint{Objects=18, References=38, Primitives=[int x 25, char x 17, float]}
Object size: 496 bytes

अब मामले पर विचार करें जब कोई तत्व जोड़ा जाता है तो टकराव होता है।

1. छोड़ दिया, कुंजी शून्य नहीं है
   
   
2. '' आईडीएक्स ''। हैशकोड () = 104125
   
   

    h ^ (h >>> 20) ^ (h >>> 12) = 104100 h ^ (h >>> 7) ^ (h >>> 4) = 101603 

   
   
3. एक सरणी में स्थिति की परिभाषा
   
   

    h & (length - 1) = 3 

   
   
4. कोई समान आइटम नहीं मिला
   
   
5. आइटम जोड़ें
   
   

    //  table[3]       ["0", "zero"] Entry<K, V> e = table[index]; //       table[index] = new Entry<K, V>(hash, key, value, e); 

   
   
   
   

आकार बदलें और स्थानांतरित करें

जब तालिका [] सरणी को सीमा मान से भर दिया जाता है, तो इसका आकार दोगुना हो जाता है और तत्वों का पुनर्वितरण हो जाता है। जैसा कि आप अपने लिए देख सकते हैं, आकार (क्षमता) और स्थानांतरण (newTable) विधियों में कुछ भी जटिल नहीं है।

 void resize(int newCapacity) { if (table.length == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } 

वर्तमान संग्रहण के सभी तत्वों पर स्थानांतरण () विधि पुन: प्रसारित होती है, अपने अनुक्रमणिका (नए आकार को ध्यान में रखते हुए) को पुन: संयोजित करती है और नए सरणी में तत्वों का पुनर्वितरण करती है।

यदि हम कहते हैं, एक और 15 तत्वों को मूल हैशमैप में जोड़ते हैं, तो परिणामस्वरूप आकार में वृद्धि होगी और तत्वों का वितरण बदल जाएगा।

आइटम हटाएं

HashMap के पास ArrayList के समान "समस्या" है - तत्वों को हटाने पर, तालिका [] सरणी का आकार कम नहीं होता है। और अगर ArrayList में trimToSize () विधि प्रदान की जाती है, तो HashMap में ऐसी कोई विधियाँ नहीं हैं (हालाँकि, मेरे एक सहयोगी ने कहा, " शायद यह आवश्यक नहीं है? ")।

ऊपर जो लिखा गया है उसे प्रदर्शित करने के लिए एक छोटा परीक्षण। स्रोत वस्तु 496 बाइट्स है। उदाहरण के लिए, 150 तत्व जोड़ें।

Footprint{Objects=768, References=1028, Primitives=[int x 1075, char x 2201, float]}
Object size: 21064 bytes

अब समान 150 तत्वों को हटाएं, और फिर से मापें।

Footprint{Objects=18, References=278, Primitives=[int x 25, char x 17, float]}
Object size: 1456 bytes

जैसा कि आप देख सकते हैं, आकार अपने मूल आकार के करीब भी नहीं था। यदि स्थिति को ठीक करने की इच्छा / आवश्यकता है, तो आप उदाहरण के लिए, HashMap (मैप) कंस्ट्रक्टर का उपयोग कर सकते हैं।

 hashmap = new HashMap<String, String>(hashmap); 

Footprint{Objects=18, References=38, Primitives=[int x 25, char x 17, float]}
Object size: 496 bytes

iterators

हैशपॉप में अंतर्निहित पुनरावृत्तियां हैं , जैसे कि आप सभी कुंजी कीसेट () , सभी मान () या सभी कुंजी / मान जोड़े में प्रवेश कर सकते हैं । नीचे तत्वों पर पुनरावृत्ति के लिए कुछ विकल्प दिए गए हैं:

 // 1. for (Map.Entry<String, String> entry: hashmap.entrySet()) System.out.println(entry.getKey() + " = " + entry.getValue()); // 2. for (String key: hashmap.keySet()) System.out.println(hashmap.get(key)); // 3. Iterator<Map.Entry<String, String>> itr = hashmap.entrySet().iterator(); while (itr.hasNext()) System.out.println(itr.next()); 

यह याद रखने योग्य है कि अगर इटरेटर के संचालन के दौरान हाशप को बदल दिया गया था (अपने स्वयं के इटरेटर विधियों का उपयोग किए बिना), तो तत्वों को मानने का परिणाम अप्रत्याशित होगा।

परिणाम

- एक तत्व जोड़ना ओ (1) समय के दौरान किया जाता है, क्योंकि नए तत्वों को श्रृंखला की शुरुआत में डाला जाता है;
- किसी तत्व को प्राप्त करने और हटाने का कार्य O (1) समय के दौरान किया जा सकता है यदि हैश फ़ंक्शन समान रूप से तत्वों को वितरित करता है और कोई टकराव नहीं होता है। औसत ऑपरेटिंग समय Θ (1 + α) होगा, जहां α लोड फैक्टर है। सबसे खराब स्थिति में, रनटाइम worst (n) हो सकता है (एक ही श्रृंखला के सभी तत्व);
- कुंजी और मान किसी भी प्रकार के हो सकते हैं, जिसमें अशक्त भी शामिल है। आदिम प्रकारों को संग्रहीत करने के लिए, संबंधित आवरण वर्ग का उपयोग किया जाता है;
- सिंक्रनाइज़ नहीं।

संदर्भ

HashMap स्रोत
JDK7 से HashMap स्रोत
JDK के स्रोत OpenJDK और व्यापार 6 स्रोत रिलीज़ - बिल्ड b23

माप उपकरण - स्मृति-मापक और अमरूद (Google कोर पुस्तकालय)।