जावा में आंतरिक हैशपॉप

[अनुवाद के लेखक से ध्यान दें] अनुवाद किसी की अपनी जरूरतों के लिए किया गया था, लेकिन अगर यह किसी के लिए उपयोगी हो, तो दुनिया कम से कम, लेकिन बेहतर हो गई है! मूल लेख - जावा में HashMap का आंतरिक कार्य

इस लेख में, हम देखेंगे कि कैसे और कैसे HashMap संग्रह में तरीके डाल आंतरिक रूप से काम करते हैं। कौन से ऑपरेशन किए जाते हैं। हैशिंग कैसे होता है मान को कुंजी द्वारा कैसे प्राप्त किया जाता है। कुंजी-मूल्य जोड़े कैसे संग्रहीत किए जाते हैं?

पिछले लेख के अनुसार , हैशपॉप में नोड की एक सरणी है और नोड निम्नलिखित वस्तुओं से युक्त वर्ग का प्रतिनिधित्व कर सकता है:

1. int - हैश
2. K कुंजी है
3. V मान है
4. नोड - अगला आइटम

अब हम देखेंगे कि यह सब कैसे काम करता है। सबसे पहले, हम हैशिंग प्रक्रिया को देखेंगे।

हैशिंग

हैशिंग एक पूर्णांक रूप में किसी वस्तु को परिवर्तित करने की प्रक्रिया है, जो हैशकोड () पद्धति का उपयोग करके किया जाता है। हैशपॉप क्लास के सर्वश्रेष्ठ प्रदर्शन को सुनिश्चित करने के लिए हैशकोड () पद्धति को सही ढंग से लागू करना बहुत महत्वपूर्ण है।

यहां मैं अपने स्वयं के कुंजी वर्ग का उपयोग करता हूं और इस तरह मैं विभिन्न लिपियों को प्रदर्शित करने के लिए हैशकोड () पद्धति को ओवरराइड कर सकता हूं। मेरी कुंजी वर्ग:

//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } } 

यहाँ, ओवरराइड किया गया हैशकोड () विधि स्ट्रिंग के पहले वर्ण का ASCII कोड लौटाती है। इस प्रकार, यदि स्ट्रिंग के पहले अक्षर समान हैं, तो हैश कोड समान होंगे। अपने कार्यक्रमों में इसी तरह के तर्क का उपयोग न करें।

यह कोड केवल प्रदर्शन उद्देश्यों के लिए है। क्योंकि हैशकोड एक अशक्त कुंजी को स्वीकार करता है, अशक्त हैश कोड हमेशा 0 होगा।

हैशकोड () विधि

हैशकोड () विधि का उपयोग ऑब्जेक्ट के हैश कोड को प्राप्त करने के लिए किया जाता है। ऑब्जेक्ट क्लास का हैशकोड () विधि एक पूर्णांक मेमोरी संदर्भ (पहचान हैश कोड ) देता है। public native hashCode() पद्धति के हस्ताक्षर। इससे पता चलता है कि विधि को मूल के रूप में लागू किया गया है, क्योंकि जावा में वस्तु का संदर्भ प्राप्त करने की कोई विधि नहीं है। इसे हैशकोड () पद्धति के अपने स्वयं के कार्यान्वयन को परिभाषित करने की अनुमति है। हैशपॉप कक्षा में, हैशकोड () पद्धति का उपयोग बाल्टी की गणना करने और इसलिए सूचकांक की गणना करने के लिए किया जाता है।

बराबर () विधि

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

टोकरी (बाल्टी)

बाल्टी HashMap सरणी का एकमात्र तत्व है। इसका उपयोग नोड्स (नोड्स) को स्टोर करने के लिए किया जाता है। दो या अधिक नोड्स में एक ही बाल्टी हो सकती है। इस स्थिति में, नोड्स को लिंक करने के लिए लिंक की गई डेटा संरचना का उपयोग किया जाता है। बाल्टी की क्षमता (क्षमता संपत्ति) में भिन्नता है। बाल्टी और क्षमता के बीच संबंध इस प्रकार है:

 capacity = number of buckets * load factor 

एक बाल्टी में एक से अधिक नोड हो सकते हैं, यह हैशकोड () पद्धति के कार्यान्वयन पर निर्भर करता है। आपके हैशकोड () पद्धति को जितना बेहतर तरीके से लागू किया जाएगा, आपकी बाल्टी उतनी ही बेहतर होगी।

हैशपैप इंडेक्स गणना

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

 index = hashCode(key) & (n-1). 

जहाँ n बाल्टी की संख्या या सरणी की लंबाई के मूल्य के बराबर है। हमारे उदाहरण में, मैं n को 16 का डिफ़ॉल्ट मान मानता हूं।

• प्रारंभ में हैश मैप खाली है: यहाँ हैशमैप का आकार 16 है:

 HashMap map = new HashMap(); 

HashMap:

• जोड़े जोड़े कुंजी - मूल्य: HashMap के अंत में एक जोड़ी कुंजी - मूल्य जोड़ें

 map.put(new Key("vishal"), 20); 

कदम:

1. मुख्य मान {"vishal"} की गणना करें। इसे 118 के रूप में जनरेट किया जाएगा।

   
   

2. index विधि का उपयोग करके सूचकांक की गणना करें, जो 6 होगा।

   
   

3. नोड ऑब्जेक्ट बनाएँ।

   
   

    { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null } 

   
   

4. ऑब्जेक्ट को इंडेक्स 6 के साथ स्थिति में रखें, यदि स्थान खाली है।

   
   

हशपॉप अब कुछ इस तरह दिखता है:

• एक और कुंजी-मूल्य जोड़ी जोड़ना : अब एक और जोड़ी जोड़ें

 map.put(new Key("sachin"), 30); 

कदम:

1. कुंजी मान {"sachin"} की गणना करें। इसे 115 के रूप में जनरेट किया जाएगा।

   
   

2. index विधि का उपयोग करके सूचकांक की गणना करें, जो 3 होगा।

   
   

3. नोड ऑब्जेक्ट बनाएँ।

   
   

    { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null } 

   
   

4. ऑब्जेक्ट को इंडेक्स 3 के साथ स्थिति में रखें, यदि स्थान खाली है।

   
   

हशपॉप अब कुछ इस तरह दिखता है:

• टक्कर के मामले में: अब एक और जोड़ी जोड़ें

 map.put(new Key("vaibhav"), 40); 

कदम:

1. कुंजी मूल्य की गणना {"वैभव"}। इसे 118 के रूप में जनरेट किया जाएगा।

   
   

2. index विधि का उपयोग करके सूचकांक की गणना करें, जो 6 होगा।

   
   

3. नोड ऑब्जेक्ट बनाएँ।

   
   

    { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null } 

   
   

4. ऑब्जेक्ट को इंडेक्स 6 के साथ स्थिति में रखें, यदि स्थान खाली है।

   
   

5. इस मामले में, सूचकांक 6 के साथ स्थिति में एक और वस्तु पहले से मौजूद है, इस मामले को टकराव कहा जाता है।

   
   

6. इस स्थिति में, हैशकोड () और बराबर () विधियों के साथ जांच की जाती है कि दोनों कुंजी समान हैं।

   
   

7. यदि कुंजियाँ समान हैं, तो वर्तमान मान को एक नए के साथ बदलें।

   
   

8. अन्यथा, नई और पुरानी वस्तुओं को "लिंक की गई सूची" डेटा संरचना का उपयोग करके लिंक को मौजूदा एक में अगले ऑब्जेक्ट के लिए लिंक करके निर्दिष्ट करें और दोनों को इंडेक्स 6 के तहत सहेजें।

   
   

हशपॉप अब कुछ इस तरह दिखता है:

[अनुवाद के लेखक से ध्यान दें] चित्र मूल लेख से लिया गया है और शुरू में इसमें एक त्रुटि है। सूचकांक 6 के साथ वीथल ऑब्जेक्ट में अगली ऑब्जेक्ट का संदर्भ शून्य नहीं है, इसमें वैभव ऑब्जेक्ट का सूचक होता है।

• हमें साचिन कुंजी द्वारा मान मिलता है:

 map.get(new Key("sachin")); 

कदम:

1. {{Sachin »} ऑब्जेक्ट के हैश कोड की गणना करें। इसे 115 के रूप में जनरेट किया गया था।

   
   

2. index विधि का उपयोग करके सूचकांक की गणना करें, जो 3 होगा।

   
   

3. सूचकांक 3 पर जाएं और पहले तत्व की कुंजी की मौजूदा मूल्य के साथ तुलना करें। यदि वे समान हैं, तो मूल्य को चालू करें, अन्यथा, अगले तत्व की जांच करें, यदि यह मौजूद है।

   
   

4. हमारे मामले में, तत्व पाया जाता है और वापसी मूल्य 30 है।

   
   

• हमें कुंजी वैभव द्वारा मूल्य मिलता है:

 map.get(new Key("vaibhav")); 

कदम:

1. ऑब्जेक्ट {"वैभव"} के हैश कोड की गणना करें। इसे 118 के रूप में जनरेट किया गया था।

   
   

2. index विधि का उपयोग करके सूचकांक की गणना करें, जो 6 होगा।

   
   

3. सूचकांक 6 पर जाएं और पहले तत्व की कुंजी की मौजूदा मूल्य के साथ तुलना करें। यदि वे समान हैं, तो मूल्य को चालू करें, अन्यथा, अगले तत्व की जांच करें, यदि यह मौजूद है।

   
   

4. इस मामले में, यह नहीं मिला था और अगले नोड ऑब्जेक्ट शून्य नहीं है।

   
   

5. यदि अगला नोड ऑब्जेक्ट अशक्त है, तो अशक्त लौटें।

   
   

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

   
   

 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } } 

निष्कर्ष:

 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40 

जावा 8 में परिवर्तन

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

जावा 8 में इस समस्या को ठीक करने के लिए, एक निश्चित सीमा तक पहुंचने के बाद, लिंक किए गए सूचियों के बजाय संतुलित पेड़ों का उपयोग किया जाता है। इसका मतलब यह है कि शुरुआत में हैशपॉप एक लिंक की गई सूची में वस्तुओं को बचाता है, लेकिन हैश में तत्वों की संख्या एक निश्चित सीमा तक पहुंचने के बाद, संतुलित पेड़ों में संक्रमण होता है। जो ओ (एन) से ओ (लॉग एन) तक के सबसे खराब मामले में प्रदर्शन में सुधार करता है।

महत्वपूर्ण बिंदु

1. जब तक फिर से हैशिंग नहीं किया जाता है तब तक गेट () और पुट () परिचालन की जटिलता लगभग स्थिर है।
2. टकराव के मामले में, यदि दो या अधिक नोड ऑब्जेक्ट्स के सूचकांक समान हैं, तो नोड ऑब्जेक्ट्स को एक लिंक की गई सूची का उपयोग करके जोड़ा जाता है, अर्थात। दूसरी नोड ऑब्जेक्ट के लिंक को पहले, तीसरे में दूसरे, आदि में संग्रहीत किया जाता है।
3. यदि दी गई कुंजी पहले से ही HashMap में मौजूद है, तो मान अधिलेखित हो जाता है।
4. अशक्त हैश कोड 0 है।
5. जब कोई ऑब्जेक्ट कुंजी द्वारा प्राप्त किया जाता है, तो लिंक की गई सूची के माध्यम से संक्रमण तब तक होता है जब तक कि वस्तु नहीं मिलती है या अगली वस्तु के लिए लिंक शून्य है।