সাজানো মানচিত্র

সাজানো মানচিত্র

এই পাঠে, আমরা SortedMap ইন্টারফেস অধ্যয়ন করব। আমরা এই ইন্টারফেসে প্রদর্শিত নতুন পদ্ধতিগুলি, সেইসাথে SortedMap — TreeMap — এর একটি বাস্তবায়নের বৈশিষ্ট্য এবং বাস্তবায়নের মধ্যে পার্থক্য, সেইসাথে হ্যাশম্যাপের তুলনায় তাদের সুবিধাগুলি অন্বেষণ করব ।

আসুন দেখি মানচিত্রের অনুক্রমটি কেমন দেখায়। SortedMap ইন্টারফেস এবং এর TreeMap বাস্তবায়নের প্রতি বিশেষ মনোযোগ দিন — তারা আজ আমাদের ফোকাস:

SortedMap ইন্টারফেস ম্যাপ ইন্টারফেসকে প্রসারিত করে। অনেক উপায়ে, এটি SortedSet এর অনুরূপ (যা ঘুরে Set প্রসারিত করে ), যেহেতু তারা উভয়ই সাজানো মান সংরক্ষণ এবং ব্যবহার করার জন্য একই কার্যকারিতা বর্ণনা করে।

SortedSet <TValue>সাথে কাজ করে এবং সঞ্চয় করে, কিন্তু SortedMap<TKey, TValue>জোড়া সঞ্চয় করে। এটি এমন একটি মানচিত্র যা এর সমস্ত উপাদানগুলিকে তাদের কীগুলির ক্রমবর্ধমান ক্রমে সংরক্ষণ করে৷

SortedMap ইন্টারফেস মানচিত্র প্রসারিত করে । এটি নিম্নলিখিত পদ্ধতি যোগ করে:

ট্রিম্যাপ ক্লাস

TreeMap ক্লাস হল SortedMap ইন্টারফেসের একটি বাস্তবায়ন । অর্থাৎ, ট্রিম্যাপ সর্টডম্যাপ দ্বারা যোগ করা সমস্ত পদ্ধতির পাশাপাশি মানচিত্র ইন্টারফেস থেকে স্ট্যান্ডার্ডগুলি প্রয়োগ করে।

আপনি এই মত কনস্ট্রাক্টর ব্যবহার করে একটি TreeMap অবজেক্ট তৈরি করতে পারেন:

• TreeMap() : একটি খালি মানচিত্র একটি গাছ হিসাবে বাস্তবায়িত তৈরি করে;

• ট্রিম্যাপ(ম্যাপ<? বিস্তার করে TKey, ? প্রসারিত করে TValue> মানচিত্র) : একটি ট্রি তৈরি করে এবং ইনপুট মানচিত্র থেকে সমস্ত উপাদান যোগ করে;

• TreeMap(SortedMap<TKey, ? প্রসারিত TValue> smap) : একটি ট্রি তৈরি করে এবং ইনপুট সাজানো মানচিত্র থেকে সমস্ত উপাদান যোগ করে;

• TreeMap(Comparator<? super TKey> comparator) : একটি খালি ট্রি তৈরি করে — কম্প্যারেটরটি পরবর্তীতে যোগ করা হলে সমস্ত উপাদান সাজানোর জন্য ব্যবহার করা হবে।

এখানে TKey হল সংরক্ষিত জোড়ার কীগুলির ধরন, এবং TValue হল TreeMap- এ সংরক্ষিত জোড়ার মানগুলির ধরন ।

SortedMap / TreeMap- এর জন্য তুলনাকারী বেশ গুরুত্বপূর্ণ। এটি আমাদের মানচিত্র বাছাই - বা অর্ডার করার নিয়ম প্রতিষ্ঠা করে৷ যদি আমরা একটি তুলনাকারী প্রদান না করি, তাহলে যখন আমরা একটি SortedMap তৈরি করি তখন আমাদের কীগুলির স্বাভাবিক ক্রম ব্যবহার করা হবে ।

একটি TreeMap উপাদান যোগ করা

put() পদ্ধতি ব্যবহার করে উপাদানগুলি জোড়া হিসাবে একটি মানচিত্রে যোগ করা হয় । কীটি প্রথম আর্গুমেন্ট হিসাবে পাস করা হয় এবং মানটি দ্বিতীয় হিসাবে পাস করা হয়। উদাহরণস্বরূপ, ধরুন আমরা শিক্ষার্থীদের এবং তাদের গ্রেডের একটি তালিকা তৈরি করতে চাই।

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. " Sara " কী দিয়ে অবজেক্টের পরে আসা সমস্ত বস্তু পান :

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

   ফলাফল: tailMap: {সারা=5, জেফ=4}

4. " Nick " কী দিয়ে অবজেক্টের আগে আসা সমস্ত বস্তু পান :

   
   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 SortedMap ইন্টারফেস প্রয়োগ করে , যা এই সাজানোর অর্ডারের উপর নির্ভর করে এমন পদ্ধতি ধারণ করে।

এখন আমরা কর্মক্ষমতা এবং গতির বিবেচনায় ফিরে যাই:

• হ্যাশম্যাপ হ্যাশিং কীগুলির উপর ভিত্তি করে একটি মানচিত্র। এটি O(1), ধ্রুবক সময়েউপাদানগুলি সন্নিবেশ ও পেতে পারেএটি সমর্থন করার জন্য, কীগুলিকে অবশ্যইহ্যাশকোড()এবংসমান()।

• TreeMap একটি গাছ-ভিত্তিক মানচিত্র। এর সন্নিবেশ এবং আনয়ন অপারেশন লগারিদমিক সময় নেয়, যেমনO(log n), যা মানচিত্রে উপাদানের সংখ্যার উপর নির্ভর করে। এটি প্রয়োজনীয় যাতে উপাদানগুলির মধ্যে আমাদের কী বা একটি বহিরাগত তুলনাকারী দ্বারা সরবরাহিত কিছু ধরণের তুলনা প্রক্রিয়া থাকে। এই প্রক্রিয়াটি পুনরাবৃত্তির ক্রম নির্ধারণ করে।

এবং এই বিষয়গুলি আমাদের সিদ্ধান্ত নিতে সাহায্য করে যে কোন সংগ্রহগুলি কখন ব্যবহার করা হবে।

যদি আমাদের একটি নির্দিষ্ট ক্রমে মান সঞ্চয় করতে হয়, পছন্দটি সুস্পষ্ট — আমাদের একটি SortedMap প্রয়োজন । যদিও এটি হ্যাশম্যাপের চেয়ে একটু ধীর , এটি আমাদের জন্য গুরুত্বপূর্ণ কাজ করে।

যেমন আগে উল্লেখ করা হয়েছে, 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);

উদাহরণটি দেখায় যে হ্যাশম্যাপ ব্যবহার করা কাজটিকে আরও জটিল করে তোলে, যেহেতু হ্যাশম্যাপ স্টোরেজের ক্রম বা মানচিত্র থেকে উপাদানগুলি প্রাপ্তির আদেশের গ্যারান্টি দেয় না।