क्रमवारी लावलेला नकाशा

क्रमवारी लावलेला नकाशा

या धड्यात, आम्ही सॉर्टेड मॅप इंटरफेसचा अभ्यास करू. आम्ही या इंटरफेसमध्ये दिसणार्‍या नवीन पद्धती, तसेच सॉर्टेडमॅप — ट्रीमॅप —च्या एका अंमलबजावणीची वैशिष्ट्ये आणि अंमलबजावणीमधील फरक तसेच हॅशमॅपच्या तुलनेत त्यांचे फायदे एक्सप्लोर करू .

नकाशांचे पदानुक्रम कसे दिसते ते पाहू या. सॉर्टेडमॅप इंटरफेस आणि त्याच्या ट्रीमॅप अंमलबजावणीवर विशेष लक्ष द्या — ते आज आमचे लक्ष आहेत:

सॉर्टेडमॅप इंटरफेस मॅप इंटरफेसचा विस्तार करतो . बर्‍याच प्रकारे, हे सॉर्टेडसेट सारखेच आहे (जे यामधून Set चा विस्तार करते ), कारण ते दोन्ही क्रमवारी केलेली मूल्ये संग्रहित करण्यासाठी आणि वापरण्यासाठी समान कार्यक्षमतेचे वर्णन करतात.

सॉर्टेडसेट <TValue>कार्य करतो आणि संग्रहित करतो, परंतु सॉर्टेडमॅप<TKey, TValue>जोड्या संग्रहित करतो. हा एक नकाशा आहे जो त्यातील सर्व घटक त्यांच्या कळांच्या चढत्या क्रमाने संग्रहित करतो.

सॉर्टेडमॅप इंटरफेस नकाशाचा विस्तार करतो . हे खालील पद्धती जोडते:

ट्रीमॅप वर्ग

ट्रीमॅप क्लास सॉर्टेड मॅप इंटरफेसची अंमलबजावणी आहे . म्हणजेच, सॉर्टेडमॅपद्वारे जोडलेल्या सर्व पद्धती तसेच नकाशा इंटरफेसमधील मानक पद्धती TreeMap लागू करते .

तुम्ही यासारखे कन्स्ट्रक्टर वापरून TreeMap ऑब्जेक्ट तयार करू शकता:

• TreeMap() : झाड म्हणून लागू केलेला रिक्त नकाशा तयार करतो;

• ट्रीमॅप(नकाशा<? विस्तारित करते TKey, ? विस्तारित करते TValue> नकाशा) : एक झाड तयार करतो आणि इनपुट नकाशावरील सर्व घटक जोडतो;

• TreeMap(SortedMap<TKey, ? expends TValue> smap) : एक झाड तयार करते आणि इनपुट क्रमवारी केलेल्या नकाशामधून सर्व घटक जोडते;

• TreeMap(Comparator<? super TKey> comparator) : रिक्त ट्री तयार करते — सर्व घटकांची क्रमवारी लावण्यासाठी comparator चा वापर केला जाईल कारण ते नंतर जोडले जातात.

येथे TKey हा संग्रहित जोड्यांमधील कीचा प्रकार आहे आणि TValue हा TreeMap मध्ये संग्रहित जोड्यांमधील मूल्यांचा प्रकार आहे .

SortedMap / TreeMap साठी तुलनाकर्ता खूप महत्वाचे आहे. हे आमच्या नकाशाची क्रमवारी लावण्यासाठी — किंवा क्रमाने — नियम स्थापित करते. आम्ही तुलना करणारा प्रदान न केल्यास, आम्ही सॉर्टेडमॅप तयार करतो तेव्हा आमच्या कीजचा नैसर्गिक क्रम वापरला जाईल .

TreeMap मध्ये घटक जोडणे

पुट() पद्धतीचा वापर करून घटक जोड्या म्हणून नकाशावर जोडले जातात . की प्रथम वितर्क म्हणून पास केली जाते आणि मूल्य दुसरे म्हणून पास केले जाते. उदाहरणार्थ, समजा आम्हाला विद्यार्थ्यांची आणि त्यांच्या ग्रेडची यादी तयार करायची आहे.

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);

येथे परिणामी क्रम आहे:

हे वर्तन ट्रीमॅपला क्रमवारी लावलेल्या अॅरे किंवा सूचीसारखे बनवते ज्याचे निर्देशांक संख्यांऐवजी शब्द ( स्ट्रिंग ) आहेत.

TreeMap वर्गात क्रमवारी लावलेल्या मॅप पद्धती

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 मध्ये , ऑर्डर त्यांच्या compareTo() पद्धतीनुसार (किंवा आम्ही प्रदान केलेल्या तुलनाकर्ता ) की च्या "नैसर्गिक ऑर्डरिंग" वर आधारित आहे. तसेच, हे विसरू नका की TreeMap सॉर्टेडमॅप इंटरफेस लागू करते , ज्यामध्ये या क्रमवारीवर अवलंबून असलेल्या पद्धती आहेत.

आता आम्ही कार्यप्रदर्शन आणि गतीचा विचार करू:

• हॅशमॅप हा हॅशिंग की वर आधारित नकाशा आहे. तो O(1)मध्ये घटक घालू शकतो आणि मिळवू शकतो, स्थिर वेळ. याचे समर्थन करण्यासाठी, कीनेहॅशकोड()आणिequals().

• TreeMap हा वृक्ष-आधारित नकाशा आहे. त्याच्या इन्सर्ट आणि फेच ऑपरेशनला लॉगरिदमिक वेळ लागतो, म्हणजेO(log n), जे नकाशामधील घटकांच्या संख्येवर अवलंबून असते. हे आवश्यक आहे जेणेकरुन घटकांकडे आमच्या की किंवा बाह्य तुलनाकर्त्याद्वारे प्रदान केलेली तुलनात्मक यंत्रणा असेल. ही यंत्रणा पुनरावृत्ती क्रम निर्धारित करते.

आणि हे घटक आम्हाला कोणते संग्रह आणि कधी वापरायचे हे ठरविण्यात मदत करतात.

आम्हाला एका विशिष्ट क्रमाने मूल्ये साठवायची असल्यास, निवड स्पष्ट आहे — आम्हाला सॉर्टेडमॅपची आवश्यकता आहे . जरी हे हॅशमॅप पेक्षा थोडे हळू असले तरी ते आमच्यासाठी महत्त्वपूर्ण कार्ये करते.

आधी सांगितल्याप्रमाणे, सॉर्टेडमॅप आम्हाला आमच्या नकाशातील पहिली (किंवा शेवटची) की, किंवा मूल्य किंवा की-व्हॅल्यू जोडी देऊ शकते, ते मूल्य कधी जोडले गेले याची पर्वा न करता. हॅशमॅप अंमलबजावणी हे करू शकत नाही .

उदाहरणार्थ, की (विद्यार्थ्यांची नावे) आणि मूल्ये (त्यांचे ग्रेड) असलेल्या नकाशाचा विचार करा. समजा आम्हाला उलट वर्णमाला क्रमाने सूचीसह कार्य करायचे आहे.

१.

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);

उदाहरण दाखवते की हॅशमॅप वापरल्याने कार्य अधिक क्लिष्ट होते, कारण हॅशमॅप स्टोरेजच्या ऑर्डरची किंवा नकाशावरून घटक मिळविण्याच्या ऑर्डरची हमी देत ​​नाही.