வரிசைப்படுத்தப்பட்ட வரைபடம்

வரிசைப்படுத்தப்பட்ட வரைபடம்

இந்தப் பாடத்தில், வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகத்தைப் படிப்போம் . இந்த இடைமுகத்தில் தோன்றும் புதிய முறைகள் மற்றும் வரிசைப்படுத்தப்பட்ட வரைபடம் - ட்ரீமேப் - மற்றும் செயல்படுத்தல்களுக்கு இடையே உள்ள வேறுபாடுகள் மற்றும் ஹாஷ்மேப்புடன் ஒப்பிடும் போது அவற்றின் நன்மைகள் ஆகியவற்றை நாங்கள் ஆராய்வோம் .

வரைபடங்களின் படிநிலை எப்படி இருக்கும் என்று பார்ப்போம். வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகம் மற்றும் அதன் ட்ரீமேப் செயல்படுத்தல் ஆகியவற்றில் சிறப்பு கவனம் செலுத்துங்கள் - அவை இன்று எங்கள் கவனம்:

வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகம் வரைபட இடைமுகத்தை நீட்டிக்கிறது . பல வழிகளில், இது SortedSet ஐப் போன்றது (இது Set ஐ நீட்டிக்கிறது ), ஏனெனில் அவை இரண்டும் வரிசைப்படுத்தப்பட்ட மதிப்புகளைச் சேமிப்பதற்கும் பயன்படுத்துவதற்கும் ஒரே மாதிரியான செயல்பாட்டை விவரிக்கின்றன.

SortedSet <TValue>செயல்படுகிறது மற்றும் சேமிக்கிறது, ஆனால் SortedMap<TKey, TValue>ஜோடிகளை சேமிக்கிறது. இது அதன் அனைத்து கூறுகளையும் அவற்றின் விசைகளின் ஏறுவரிசையில் சேமிக்கும் வரைபடம்.

வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகம் வரைபடத்தை நீட்டிக்கிறது . இது பின்வரும் முறைகளைச் சேர்க்கிறது:

ட்ரீமேப் வகுப்பு

ட்ரீமேப் வகுப்பு என்பது வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகத்தின் செயலாக்கமாகும் . அதாவது, SortedMap ஆல் சேர்க்கப்பட்ட அனைத்து முறைகளையும் , வரைபட இடைமுகத்திலிருந்து நிலையானவற்றையும் TreeMap செயல்படுத்துகிறது .

இது போன்ற கன்ஸ்ட்ரக்டர்களைப் பயன்படுத்தி ட்ரீமேப் பொருளை உருவாக்கலாம் :

• TreeMap() : ஒரு மரமாக செயல்படுத்தப்பட்ட ஒரு வெற்று வரைபடத்தை உருவாக்குகிறது;

• TreeMap(வரைபடம் <? TKey நீட்டிக்கிறது, ? TValue> வரைபடத்தை நீட்டிக்கிறது) : ஒரு மரத்தை உருவாக்குகிறது மற்றும் உள்ளீட்டு வரைபடத்திலிருந்து அனைத்து கூறுகளையும் சேர்க்கிறது;

• TreeMap(வரிசைப்படுத்தப்பட்ட வரைபடம்<TKey, ? நீட்டிக்கிறது TValue> smap) : ஒரு மரத்தை உருவாக்குகிறது மற்றும் உள்ளீடு வரிசைப்படுத்தப்பட்ட வரைபடத்தில் இருந்து அனைத்து கூறுகளையும் சேர்க்கிறது;

• TreeMap(Comparator<? super TKey> comparator) : ஒரு வெற்று மரத்தை உருவாக்குகிறது - அனைத்து கூறுகளையும் பின்னர் சேர்க்கும்போது அவற்றை வரிசைப்படுத்த ஒப்பீட்டாளர் பயன்படுத்தப்படும்.

இங்கே TKey என்பது சேமிக்கப்பட்ட ஜோடிகளில் உள்ள விசைகளின் வகையாகும், மேலும் TValue என்பது 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);
   

   முடிவு: 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);
   

   முடிவு: துணை வரைபடம்: {Oliver=5, Roxy=5}

HashMap மற்றும் வரிசைப்படுத்தப்பட்ட வரைபடம்/TreeMap ஆகியவற்றின் ஒப்பீடு

கூறுகள் எவ்வாறு ஆர்டர் செய்யப்பட்டு சேமிக்கப்படுகின்றன என்பதைப் பற்றி பேசலாம்:

• மீண்டும் செய்யும் போது ஆர்டர் பற்றிய எந்த உத்தரவாதத்தையும் HashMap வழங்காததால் , புதிய கூறுகள் சேர்க்கப்படும் போது ஆர்டர் முற்றிலும் மாறலாம்.

• TreeMap இல் , ஆர்டர் விசைகளின் "இயற்கை வரிசைப்படுத்தல்" அடிப்படையில் அவற்றின் compareTo() முறையின்படி (அல்லது நாங்கள் வழங்கும் ஒப்பீட்டாளர் ) மேலும், TreeMap வரிசைப்படுத்தப்பட்ட வரைபட இடைமுகத்தை செயல்படுத்துகிறது என்பதை மறந்துவிடாதீர்கள் , இதில் இந்த வரிசை வரிசையைச் சார்ந்திருக்கும் முறைகள் உள்ளன.

இப்போது நாம் செயல்திறன் மற்றும் வேகத்தை கருத்தில் கொள்கிறோம்:

• HashMap என்பது ஹாஷிங் விசைகளை அடிப்படையாகக் கொண்ட ஒரு வரைபடம். இது O(1)உறுப்புகளைச் செருகலாம் மற்றும் பெறலாம். இதை ஆதரிக்க, விசைகள்hashCode()மற்றும்equals().

• TreeMap என்பது மரம் சார்ந்த வரைபடம். அதன் செருகல் மற்றும் பெறுதல் செயல்பாடுகள் மடக்கை நேரம் எடுக்கும், அதாவதுO(log n), இது வரைபடத்தில் உள்ள உறுப்புகளின் எண்ணிக்கையைப் பொறுத்தது. உறுப்புகள் நமது விசை அல்லது வெளிப்புற ஒப்பீட்டாளரால் வழங்கப்படும் ஒருவித ஒப்பீட்டு பொறிமுறையைக் கொண்டிருப்பதற்கு இது அவசியம். இந்த பொறிமுறையானது மறு செய்கை வரிசையை தீர்மானிக்கிறது.

இந்த காரணிகள் எந்த சேகரிப்புகளை எப்போது பயன்படுத்த வேண்டும் என்பதை தீர்மானிக்க உதவுகின்றன.

ஒரு குறிப்பிட்ட வரிசையில் மதிப்புகளைச் சேமிக்க வேண்டும் என்றால், தேர்வு தெளிவாக இருக்கும் - நமக்கு வரிசைப்படுத்தப்பட்ட வரைபடம் தேவை . இது HashMap ஐ விட சற்று மெதுவாக இருந்தாலும் , அது நமக்கு முக்கியமான பணிகளை செய்கிறது.

முன்பே குறிப்பிட்டது போல், SortedMap நமது வரைபடத்தில் முதல் (அல்லது கடைசி) விசை, அல்லது மதிப்பு அல்லது முக்கிய மதிப்பு ஜோடியை, அந்த மதிப்பு எப்போது சேர்க்கப்பட்டது என்பதைப் பொருட்படுத்தாமல் கொடுக்க முடியும். 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);

ஹாஷ்மேப்பைப் பயன்படுத்துவது பணியை மிகவும் சிக்கலாக்குகிறது என்பதை எடுத்துக்காட்டு காட்டுகிறது , ஏனெனில் ஹாஷ்மேப் சேமிப்பகத்தின் வரிசை அல்லது வரைபடத்திலிருந்து கூறுகளைப் பெறுவதற்கான வரிசைக்கு உத்தரவாதம் அளிக்காது.