क्रमबद्ध मानचित्र

क्रमबद्ध मानचित्र

इस पाठ में, हम SortedMap इंटरफ़ेस का अध्ययन करेंगे। हम इस इंटरफ़ेस में दिखाई देने वाली नई विधियों का पता लगाएंगे, साथ ही सॉर्टेड मैप - ट्रीमैप - के एक कार्यान्वयन की विशेषताओं और कार्यान्वयन के बीच के अंतरों के साथ-साथ हैश मैप की तुलना में उनके फायदे भी तलाशेंगे ।

आइए देखें कि मानचित्रों का पदानुक्रम कैसा दिखता है। SortedMap इंटरफ़ेस और इसके TreeMap कार्यान्वयन पर विशेष ध्यान दें - वे आज हमारा ध्यान हैं:

SortedMap इंटरफ़ेस मानचित्र इंटरफ़ेस का विस्तार करता है। कई मायनों में, यह सॉर्टेडसेट (जो बदले में सेट का विस्तार करता है) के समान है , क्योंकि वे दोनों सॉर्ट किए गए मानों को संग्रहीत करने और उपयोग करने के लिए समान कार्यक्षमता का वर्णन करते हैं।

SortedSet <TValue>के साथ काम करता है और स्टोर करता है, लेकिन SortedMap<TKey, TValue>पेयर्स को स्टोर करता है। यह एक नक्शा है जो अपने सभी तत्वों को उनकी चाबियों के आरोही क्रम में संग्रहीत करता है।

SortedMap इंटरफ़ेस मानचित्र का विस्तार करता है । यह निम्नलिखित विधियों को जोड़ता है:

ट्रीमैप वर्ग

ट्रीमैप वर्ग सॉर्टेडमैप इंटरफ़ेस का कार्यान्वयन है । यही है, TreeMap SortedMap द्वारा जोड़े गए सभी तरीकों के साथ-साथ मानचित्र इंटरफ़ेस से मानक को लागू करता है।

आप इस तरह के कंस्ट्रक्टर का उपयोग करके ट्रीमैप ऑब्जेक्ट बना सकते हैं :

• TreeMap () : एक पेड़ के रूप में कार्यान्वित एक खाली नक्शा बनाता है;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : एक ट्री बनाता है और इनपुट मैप से सभी तत्वों को जोड़ता है;

• TreeMap(SortedMap<TKey, ? TValue> smap बढ़ाता है) : एक ट्री बनाता है और इनपुट सॉर्ट किए गए मानचित्र से सभी तत्व जोड़ता है;

• TreeMap(तुलनित्र<? सुपर टीके> तुलनित्र) : एक खाली पेड़ बनाता है - तुलनित्र का उपयोग सभी तत्वों को सॉर्ट करने के लिए किया जाएगा क्योंकि वे बाद में जोड़े जाते हैं।

यहां TKey संग्रहीत जोड़े में कुंजियों का प्रकार है, और TValue TreeMap में संग्रहीत जोड़े में मानों का प्रकार है ।

SortedMap / TreeMap के लिए तुलनित्र बहुत महत्वपूर्ण है। यह हमारे मानचित्र को छाँटने - या क्रमबद्ध करने के लिए नियम स्थापित करता है। यदि हम एक तुलनित्र प्रदान नहीं करते हैं, तो जब हम एक SortedMap बनाते हैं तो हमारी चाबियों के प्राकृतिक क्रम का उपयोग किया जाएगा ।

ट्री-मैप में तत्व जोड़ना

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

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

परिणाम:

जब हम कुंजी-मूल्य जोड़ी जोड़ते हैं, यदि संग्रह में कुंजी पहले से मौजूद है, तो पुराने मान को नए मान से बदल दिया जाता है। यह व्यवहार हमारे उदाहरण में दो जोड़ियों के साथ चित्रित किया गया है जिनकी एक ही कुंजी है - ("ओलिवर", 3) और ("ओलिवर", 5) ।

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

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

यहाँ परिणामी क्रम है:

यह व्यवहार एक ट्रीमैप को एक क्रमबद्ध सरणी या सूची की तरह बनाता है जिसका सूचकांक संख्या के बजाय शब्द ( स्ट्रिंग ) हैं।

ट्रीमैप क्लास में सॉर्टेडमैप तरीके

1. यदि आपको पहले छात्र की कुंजी प्राप्त करने की आवश्यकता है, तो आप firstKey() विधि का उपयोग कर सकते हैं:

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   परिणाम: पहली कुंजी → एंथोनी

2. यदि आपको अंतिम छात्र की कुंजी प्राप्त करने की आवश्यकता है, तो आप lastKey() विधि का उपयोग कर सकते हैं:

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   परिणाम: अंतिम कुंजी → जेफ

3. ऑब्जेक्ट के बाद आने वाली सभी वस्तुओं को कुंजी " सारा " के साथ प्राप्त करें:

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   परिणाम: टेलमैप: {सारा = 5, जेफ = 4}

4. ऑब्जेक्ट से पहले आने वाली सभी वस्तुओं को कुंजी " निक " के साथ प्राप्त करें:

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   परिणाम: हेडमैप: {एंथनी = 5}

5. ऑब्जेक्ट के बाद आने वाली सभी वस्तुओं को " ओलिवर " कुंजी के साथ प्राप्त करें और कुंजी " सारा " के साथ ऑब्जेक्ट से पहले आएं :

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   परिणाम: सबमैप: {ओलिवर = 5, रॉक्सी = 5}

हैशमैप और सॉर्टेडमैप/ट्रीमैप की तुलना

आइए बात करते हैं कि तत्वों को कैसे व्यवस्थित और संग्रहीत किया जाता है:

• चूंकि हैश मैप हमें पुनरावृति के दौरान ऑर्डर के बारे में कोई गारंटी नहीं देता है, नए तत्व जोड़े जाने पर ऑर्डर पूरी तरह से बदल सकता है।

• ट्रीमैप में , ऑर्डर उनकी तुलना () विधि (या एक तुलनित्र जो हम प्रदान करते हैं) के अनुसार कुंजियों के "प्राकृतिक क्रम" पर आधारित है। साथ ही, यह न भूलें कि TreeMap SortedMap इंटरफ़ेस लागू करता है , जिसमें ऐसे तरीके शामिल हैं जो इस क्रम क्रम पर निर्भर करते हैं।

अब हम प्रदर्शन और गति पर विचार करते हैं:

• हैश मैप हैशिंग कुंजियों पर आधारित मानचित्र है। यहO(1)निरंतर समय में तत्वों को सम्मिलित और प्राप्त कर सकता है। इसका समर्थन करने के लिए, कुंजियों कोहैशकोड ()औरबराबर () को।

• ट्री मैप एक ट्री-बेस्ड मैप है। इसके डालने और लाने के संचालन में लघुगणकीय समय लगता है, अर्थातO(log n), जो मानचित्र में तत्वों की संख्या पर निर्भर करता है। यह आवश्यक है ताकि तत्वों में हमारी कुंजी या बाहरी तुलनित्र द्वारा प्रदान की गई किसी प्रकार की तुलना तंत्र हो। यह तंत्र पुनरावृत्ति क्रम को निर्धारित करता है।

और ये कारक हमें यह तय करने में मदद करते हैं कि कौन से संग्रह का उपयोग करना है और कब।

यदि हमें मूल्यों को एक निश्चित क्रम में संग्रहीत करने की आवश्यकता है, तो विकल्प स्पष्ट है - हमें SortedMap की आवश्यकता है । हालांकि यह हैश मैप से थोड़ा धीमा है , यह हमारे लिए महत्वपूर्ण कार्य करता है।

जैसा कि पहले उल्लेख किया गया है, सॉर्टेडमैप हमें हमारे मानचित्र में पहली (या अंतिम) कुंजी, या मान, या कुंजी-मूल्य जोड़ी दे सकता है, भले ही वह मान जोड़ा गया हो। हैश मैप कार्यान्वयन ऐसा नहीं कर सकता है।

उदाहरण के लिए, चाबियों (छात्रों के नाम) और मूल्यों (उनके ग्रेड) के साथ एक मानचित्र पर विचार करें। मान लीजिए कि हम उल्टे वर्णमाला क्रम में एक सूची के साथ काम करना चाहते हैं।

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

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