క్రమబద్ధీకరించబడిన మ్యాప్

క్రమబద్ధీకరించబడిన మ్యాప్

ఈ పాఠంలో, మేము క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్‌ను అధ్యయనం చేస్తాము. మేము ఈ ఇంటర్‌ఫేస్‌లో కనిపించే కొత్త పద్ధతులను, అలాగే SortedMap — TreeMap — యొక్క ఒక అమలు యొక్క లక్షణాలను మరియు అమలుల మధ్య తేడాలను అలాగే HashMap తో పోలిస్తే వాటి ప్రయోజనాలను అన్వేషిస్తాము .

మ్యాప్‌ల సోపానక్రమం ఎలా ఉంటుందో చూద్దాం. క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్ మరియు దాని ట్రీమ్యాప్ అమలుపై ప్రత్యేక శ్రద్ధ వహించండి — అవి ఈ రోజు మా దృష్టిలో ఉన్నాయి:

క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్ మ్యాప్ ఇంటర్‌ఫేస్‌ను విస్తరించింది . అనేక విధాలుగా, ఇది క్రమబద్ధీకరించబడిన సెట్‌ని పోలి ఉంటుంది (ఇది సెట్‌ని పొడిగిస్తుంది ), ఎందుకంటే అవి రెండూ క్రమబద్ధీకరించబడిన విలువలను నిల్వ చేయడానికి మరియు ఉపయోగించడం కోసం ఒకే విధమైన కార్యాచరణను వివరిస్తాయి.

SortedSet <TValue>పని చేస్తుంది మరియు నిల్వ చేస్తుంది, కానీ SortedMap<TKey, TValue>జతలను నిల్వ చేస్తుంది. ఇది అన్ని మూలకాలను వాటి కీల ఆరోహణ క్రమంలో నిల్వ చేసే మ్యాప్.

క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్ మ్యాప్‌ను విస్తరించింది . ఇది క్రింది పద్ధతులను జోడిస్తుంది:

ట్రీమ్యాప్ తరగతి

ట్రీమ్యాప్ క్లాస్ అనేది క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్ యొక్క అమలు . అంటే, ట్రీమ్యాప్ క్రమబద్ధీకరించబడిన మ్యాప్ ద్వారా జోడించబడిన అన్ని పద్ధతులను అలాగే మ్యాప్ ఇంటర్‌ఫేస్ నుండి ప్రామాణికమైన వాటిని అమలు చేస్తుంది.

మీరు ఇలాంటి కన్స్ట్రక్టర్‌లను ఉపయోగించి ట్రీమ్యాప్ ఆబ్జెక్ట్‌ను సృష్టించవచ్చు :

• ట్రీమ్యాప్() : ట్రీగా అమలు చేయబడిన ఖాళీ మ్యాప్‌ను సృష్టిస్తుంది;

• TreeMap(మ్యాప్ <? TKeyని పొడిగిస్తుంది, ? TValue> మ్యాప్‌ను పొడిగిస్తుంది) : ఒక చెట్టును సృష్టిస్తుంది మరియు ఇన్‌పుట్ మ్యాప్ నుండి అన్ని మూలకాలను జోడిస్తుంది;

• TreeMap(క్రమబద్ధీకరించబడిన మ్యాప్<TKey, ? TValue> smapని పొడిగిస్తుంది) : ఒక చెట్టును సృష్టిస్తుంది మరియు ఇన్‌పుట్ క్రమబద్ధీకరించబడిన మ్యాప్ నుండి అన్ని మూలకాలను జోడిస్తుంది;

• TreeMap(Comparator<? super TKey> comparator) : ఖాళీ ట్రీని సృష్టిస్తుంది — కంపారిటర్ అన్ని ఎలిమెంట్‌లను క్రమబద్ధీకరించడానికి ఉపయోగించబడుతుంది.

ఇక్కడ TKey అనేది నిల్వ చేయబడిన జతలలోని కీల రకం మరియు TValue అనేది 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);
   

   ఫలితం: tailMap: {Sara=5, Jeff=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}

హాష్‌మ్యాప్ మరియు క్రమబద్ధీకరించబడిన మ్యాప్/ట్రీమ్యాప్ పోలిక

మూలకాలు ఎలా ఆర్డర్ చేయబడతాయి మరియు నిల్వ చేయబడతాయి అనే దాని గురించి మాట్లాడుదాం:

• పునరావృతం చేసేటప్పుడు ఆర్డర్ గురించి HashMap మాకు ఎటువంటి హామీలను ఇవ్వదు కాబట్టి , కొత్త మూలకాలు జోడించబడినప్పుడు ఆర్డర్ పూర్తిగా మారవచ్చు.

• ట్రీమ్యాప్‌లో , ఆర్డర్ వారి compareTo() పద్ధతి (లేదా మేము అందించే కంపారేటర్ ) ప్రకారం కీల యొక్క " సహజ క్రమం"పై ఆధారపడి ఉంటుంది. అలాగే, ట్రీమ్యాప్ క్రమబద్ధీకరించబడిన మ్యాప్ ఇంటర్‌ఫేస్‌ను అమలు చేస్తుందని మర్చిపోవద్దు , ఈ క్రమబద్ధీకరణపై ఆధారపడిన పద్ధతులను కలిగి ఉంటుంది.

ఇప్పుడు మేము పనితీరు మరియు వేగాన్ని పరిగణనలోకి తీసుకుంటాము:

• HashMap అనేది హ్యాషింగ్ కీల ఆధారంగా రూపొందించబడిన మ్యాప్. ఇది O(1), స్థిరమైన సమయంలోమూలకాలను చొప్పించగలదు మరియు పొందవచ్చుదీనికి మద్దతు ఇవ్వడానికి, కీలు తప్పనిసరిగాhashCode()మరియుequals().

• ట్రీమ్యాప్ అనేది చెట్టు ఆధారిత మ్యాప్. దీని ఇన్సర్ట్ మరియు ఫెచ్ ఆపరేషన్‌లకు లాగరిథమిక్ సమయం పడుతుంది, అనగాO(log n), ఇది మ్యాప్‌లోని మూలకాల సంఖ్యపై ఆధారపడి ఉంటుంది. మూలకాలు మా కీ లేదా బాహ్య కంపారేటర్ ద్వారా అందించబడిన ఒక విధమైన పోలిక యంత్రాంగాన్ని కలిగి ఉండేలా ఇది అవసరం. ఈ మెకానిజం పునరావృత క్రమాన్ని నిర్ణయిస్తుంది.

మరియు ఈ కారకాలు ఏ సేకరణలను ఎప్పుడు ఉపయోగించాలో నిర్ణయించడంలో మాకు సహాయపడతాయి.

మనం ఒక నిర్దిష్ట క్రమంలో విలువలను నిల్వ చేయవలసి వస్తే, ఎంపిక స్పష్టంగా ఉంటుంది - మనకు క్రమబద్ధీకరించబడిన మ్యాప్ అవసరం . ఇది HashMap కంటే కొంచెం నెమ్మదిగా ఉన్నప్పటికీ , ఇది మనకు ముఖ్యమైన పనులను చేస్తుంది.

ఇంతకు ముందు చెప్పినట్లుగా, క్రమబద్ధీకరించబడిన మ్యాప్ మా మ్యాప్‌లోని మొదటి (లేదా చివరి) కీ, లేదా విలువ లేదా కీ-విలువ జతని, ఆ విలువ ఎప్పుడు జోడించబడిందనే దానితో సంబంధం లేకుండా ఇస్తుంది. HashMap అమలు దీన్ని చేయదు .

ఉదాహరణకు, కీలు (విద్యార్థుల పేర్లు) మరియు విలువలు (వారి గ్రేడ్‌లు) ఉన్న మ్యాప్‌ను పరిగణించండి. మేము రివర్స్ ఆల్ఫాబెటికల్ క్రమంలో జాబితాతో పని చేయాలనుకుంటున్నాము.

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

హ్యాష్‌మ్యాప్‌ని ఉపయోగించడం పనిని మరింత క్లిష్టతరం చేస్తుందని ఉదాహరణ చూపిస్తుంది , ఎందుకంటే హ్యాష్‌మ్యాప్ మ్యాప్ నుండి నిల్వ క్రమానికి లేదా ఎలిమెంట్‌లను పొందే క్రమానికి హామీ ఇవ్వదు.