جاوا میں TreeMap کی خصوصیات

اگر آپ یہ مضمون پڑھ رہے ہیں، تو امکان ہے کہ آپ نقشہ کے انٹرفیس اور اس کے استعمال سے واقف ہوں۔ اگر نہیں، تو آپ یہاں جائیں. آج ہم TreeMap کے نفاذ کی خصوصیات کے بارے میں بات کریں گے، اور خاص طور پر، یہ HashMap سے کیسے مختلف ہے اور اسے صحیح طریقے سے کیسے استعمال کیا جائے۔

TreeMap، HashMap اور LinkedHashMap کا موازنہ

نقشہ انٹرفیس کا سب سے زیادہ استعمال کیا جانے والا عمل ہے HashMap ۔ یہ استعمال کرنا آسان ہے اور ڈیٹا تک تیز رسائی کی ضمانت دیتا ہے، جو اسے زیادہ تر کاموں کے لیے بہترین امیدوار بناتا ہے۔ زیادہ تر، لیکن سب نہیں۔ بعض اوقات ڈیٹا کو اس کے ذریعے نیویگیٹ کرنے کی صلاحیت کے ساتھ ایک منظم شکل میں ذخیرہ کرنا ضروری ہوتا ہے۔ اس صورت میں، نقشہ انٹرفیس کا ایک اور نفاذ بچاؤ کے لیے آتا ہے - TreeMap ۔ TreeMap NavigableMap انٹرفیس کو لاگو کرتا ہے ، جو SortedMap سے وراثت میں ملتا ہے ، جو بدلے میں Map انٹرفیس سے وراثت میں ملتا ہے ۔ NavigableMap اور SortedMap انٹرفیس کو لاگو کرنے سے ، TreeMap اضافی فعالیت حاصل کرتا ہے جو HashMap نہیں کرتا ، لیکن یہ کارکردگی کی قیمت پر آتا ہے۔ ایک LinkedHashMap کلاس بھی ہے ، جو آپ کو ڈیٹا کو ایک خاص ترتیب میں ذخیرہ کرنے کی بھی اجازت دیتی ہے - جس ترتیب سے وہ شامل کیے گئے تھے۔ ان تین کلاسوں کے درمیان فرق کو سمجھنے میں آپ کی مدد کے لیے ، اس جدول کو دیکھیں: جیسا کہ آپ دیکھ سکتے ہیں، ان کلاسوں میں بہت کچھ مشترک ہے، لیکن کچھ اختلافات بھی ہیں۔ اگرچہ کلاس TreeMapسب سے زیادہ ملٹی فنکشنل ہے، اسے ہمیشہ nullکلید کے طور پر محفوظ نہیں کیا جا سکتا۔ اس کے علاوہ، TreeMap عناصر تک رسائی کا وقت سب سے طویل ہوگا۔ لہذا، اگر آپ کو ڈیٹا کو ترتیب شدہ شکل میں ذخیرہ کرنے کی ضرورت نہیں ہے، تو بہتر ہے کہ استعمال کریں HashMapیا LinkedHashMap.

سرخ آبنوس کا درخت

جیسا کہ آپ نے شاید محسوس کیا ہے، ہڈ کے نیچے TreeMapیہ ڈیٹا ڈھانچہ استعمال کرتا ہے جسے سرخ سیاہ درخت کہتے ہیں۔ یہ اس ڈھانچے میں ڈیٹا کا ذخیرہ ہے جو اس ترتیب کو یقینی بناتا ہے جس میں ڈیٹا کو ذخیرہ کیا جاتا ہے۔ یہ درخت کیا ہے؟ آئیے اس کا پتہ لگائیں! تصور کریں کہ آپ کو Number-String جوڑوں کو ذخیرہ کرنے کی ضرورت ہے۔ نمبر 16، 20، 52، 55، 61، 65، 71، 76، 81، 85، 90، 93، 101 کلیدیں ہوں گی۔ اگر آپ روایتی فہرست میں ڈیٹا اسٹور کرتے ہیں اور کلید 101 کے ساتھ ایک عنصر تلاش کرنے کی ضرورت ہے، تو آپ کو اسے تلاش کرنے کے لیے تمام 13 عناصر کے ذریعے اعادہ کرنا ہوگا۔ 13 عناصر کے لیے یہ اہم نہیں ہے؛ ایک ملین کے ساتھ کام کرتے وقت ہمیں بڑی مشکلات کا سامنا کرنا پڑے گا۔ ایسے مسائل کو حل کرنے کے لیے، پروگرامرز قدرے پیچیدہ ڈیٹا ڈھانچے کا استعمال کرتے ہیں۔ لہذا، سرخ سیاہ درخت سے ملو!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

مطلوبہ عنصر کی تلاش درخت کی جڑ سے شروع ہوتی ہے، ہمارے معاملے میں یہ 61 ہے۔ اس کے بعد، مطلوبہ قدر کے ساتھ موازنہ کیا جاتا ہے۔ اگر ہماری قدر کم ہے تو ہم بائیں طرف جاتے ہیں، اگر زیادہ ہے تو دائیں طرف جاتے ہیں۔ یہ اس وقت تک ہوتا ہے جب تک کہ ہمیں مطلوبہ قدر نہ مل جائے یا کسی عنصر کو قدر کے ساتھ مارا جائے null(درخت کا ایک پتا)۔ سرخ اور سیاہ رنگوں کا استعمال درخت کو آسانی سے گشت اور توازن کے لیے کیا جاتا ہے۔ سرخ سیاہ درخت بناتے وقت ایسے اصول ہیں جن پر عمل کرنا ضروری ہے:

• جڑ کا رنگ سیاہ ہونا چاہئے۔
• درخت کے پتے سیاہ ہونے چاہئیں۔
• ایک سرخ نوڈ میں دو سیاہ چائلڈ نوڈس ہونے چاہئیں۔
• بلیک نوڈ میں کوئی بھی چائلڈ نوڈ ہو سکتا ہے۔
• نوڈ سے اس کے پتوں تک کے راستے میں بلیک نوڈس کی اتنی ہی تعداد ہونی چاہیے۔
• پتوں کی جگہ نئے نوڈس شامل کیے جاتے ہیں۔

اگر آپ قواعد 3، 4، اور 5 کو ایک ساتھ دیکھیں تو آپ سمجھ سکتے ہیں کہ رنگین نوڈس درخت کے ذریعے نیویگیشن کو کس طرح تیز کرتے ہیں: بلیک نوڈس کا راستہ ہمیشہ سرخ رنگوں سے چھوٹا ہوتا ہے۔ لہذا، درخت کے کل سائز کا تعین سیاہ نوڈس کی تعداد سے ہوتا ہے، اور اس سائز کو "سیاہ اونچائی" کہا جاتا ہے۔ سرخ سیاہ درخت کو مختلف پروگرامنگ زبانوں میں لاگو کیا جاتا ہے۔ انٹرنیٹ پر جاوا کے لیے بہت سارے نفاذ ہیں، اس لیے ہم اس پر زیادہ دیر تک نہیں رہیں گے، لیکن اس کی فعالیت سے واقفیت حاصل کرتے رہیں گے TreeMap۔

SortedMap اور NavigableMap انٹرفیس سے اخذ کردہ طریقے

جیسے HashMap، TreeMapیہ انٹرفیس کو لاگو کرتا ہے Map، جس کا مطلب ہے کہ اس میں وہ TreeMapتمام طریقے موجود ہیں HashMap۔ لیکن اس کے علاوہ، TreeMapیہ انٹرفیس کو لاگو کرتا ہے SortedMapاور NavigableMap، ان سے اضافی فعالیت حاصل کرتا ہے۔ SortedMap- ایک انٹرفیس جو Mapترتیب شدہ ڈیٹا سیٹ سے متعلقہ طریقوں کو بڑھاتا اور شامل کرتا ہے:

• firstKey(): نقشہ کے پہلے عنصر کی کلید واپس کرتا ہے۔
• lastKey(): آخری عنصر کی کلید واپس کرتا ہے۔
• headMap(K end): ایک نقشہ لوٹاتا ہے جس میں کلید کے ساتھ شروع سے عنصر تک موجودہ کے تمام عناصر شامل ہیں end؛
• tailMap(K start): ایک نقشہ لوٹاتا ہے جس میں موجودہ کے تمام عناصر شامل ہیں، عنصر سے شروع ہوتے ہیں startاور اختتام کے ساتھ ختم ہوتے ہیں۔
• subMap(K start, K end): ایک نقشہ لوٹاتا ہے جس میں موجودہ کے تمام عناصر شامل ہیں، عنصر سے شروع ہوتے ہیں startاور کلید کے ساتھ عنصر کے ساتھ ختم ہوتے ہیں end۔

NavigableMap- ایک انٹرفیس جو SortedMapنقشہ کے عناصر کے درمیان نیویگیٹ کرنے کے طریقوں کو بڑھاتا اور شامل کرتا ہے:

• firstEntry(): پہلا کلیدی قدر جوڑا لوٹاتا ہے۔
• lastEntry(): آخری کلیدی قدر کا جوڑا لوٹاتا ہے۔
• pollFirstEntry(): لوٹتا ہے اور پہلا جوڑا ہٹاتا ہے۔
• pollLastEntry(): واپس کرتا ہے اور آخری جوڑا ہٹاتا ہے۔
• ceilingKey(K obj): سب سے چھوٹی کلید k لوٹاتا ہے جو کلیدی اعتراض سے بڑی یا اس کے برابر ہے۔ اگر ایسی کوئی کلید نہیں ہے تو، null لوٹاتا ہے۔
• floorKey(K obj): سب سے بڑی کلید k لوٹاتا ہے جو کلیدی اعتراض سے کم یا اس کے برابر ہے۔ اگر ایسی کوئی کلید نہیں ہے تو، null لوٹاتا ہے۔
• lowerKey(K obj): سب سے بڑی کلید k لوٹاتا ہے جو کلیدی اعتراض سے چھوٹی ہے۔ اگر ایسی کوئی کلید نہیں ہے تو، null لوٹاتا ہے۔
• higherKey(K obj): سب سے چھوٹی کلید k لوٹاتا ہے جو کلیدی اعتراض سے بڑی ہے۔ اگر ایسی کوئی کلید نہیں ہے تو، null لوٹاتا ہے۔
• ceilingEntry(K obj): ceilingKey(K obj) طریقہ سے ملتا جلتا ہے، لیکن کلیدی قدر کا جوڑا (یا null) لوٹاتا ہے۔
• floorEntry(K obj): floorKey(K obj) طریقہ سے ملتا جلتا ہے، لیکن کلیدی قدر کا جوڑا (یا null) لوٹاتا ہے۔
• lowerEntry(K obj): LowerKey(K obj) طریقہ سے ملتا جلتا، لیکن کلیدی قدر کا جوڑا (یا null) لوٹاتا ہے۔
• higherEntry(K obj): HigherKey(K obj) طریقہ سے ملتا جلتا، لیکن کلیدی قدر کا جوڑا (یا null) لوٹاتا ہے۔
• descendingKeySet(): ایک NavigableSet لوٹاتا ہے جس میں تمام کلیدیں الٹی ترتیب میں ترتیب دی گئی ہیں۔
• descendingMap(): ایک NavigableMap لوٹاتا ہے جس میں تمام جوڑوں کو الٹ ترتیب میں ترتیب دیا گیا ہے۔
• navigableKeySet(): ایک NavigableSet آبجیکٹ لوٹاتا ہے جس میں سٹوریج کی ترتیب میں تمام کلیدیں شامل ہیں۔
• headMap(K upperBound, boolean incl): ایک نقشہ لوٹاتا ہے جس میں شروع سے اوپری باؤنڈ عنصر تک جوڑے ہوتے ہیں۔ incl دلیل یہ بتاتی ہے کہ آیا اوپری باؤنڈ عنصر کو واپس کیے گئے نقشے میں شامل کیا جانا چاہیے؛
• tailMap(K lowerBound, boolean incl): فعالیت پچھلے طریقہ سے ملتی جلتی ہے، صرف لوئر باؤنڈ سے آخر تک جوڑے لوٹائے جاتے ہیں۔
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): پچھلے طریقوں کی طرح، لوئر باؤنڈ سے اپر باؤنڈ تک جوڑے لوٹائے جاتے ہیں، دلائل lowIncl اور highIncl یہ بتاتے ہیں کہ آیا نئے نقشے میں باؤنڈری عناصر کو شامل کرنا ہے۔

خود عمل درآمد میں TreeMap، کنسٹرکٹرز کے علاوہ جن سے ہم واقف ہیں، ایک اور اضافہ کیا جاتا ہے، جو موازنہ کرنے والے کی مثال کو قبول کرتا ہے۔ یہ موازنہ کرنے والا اس ترتیب کے لیے ذمہ دار ہو گا جس میں عناصر کو ذخیرہ کیا جاتا ہے۔

TreeMap استعمال کرنے کی مثالیں۔

اضافی طریقوں کی اس طرح کی کثرت غیر ضروری معلوم ہوسکتی ہے، لیکن اکثر وہ اس سے کہیں زیادہ کارآمد ثابت ہوتی ہیں جتنا کہ شروع میں لگتا تھا۔ آئیے آپ کے ساتھ اس مثال کو دیکھتے ہیں۔ تصور کریں کہ ہم ایک بڑی کمپنی کے مارکیٹنگ ڈیپارٹمنٹ میں کام کرتے ہیں، اور ہمارے پاس ان لوگوں کا ڈیٹا بیس ہے جنہیں ہم اشتہارات دکھانا چاہتے ہیں۔ اس میں دو باریکیاں ہیں:

• ہمیں ہر شخص کے تاثرات کی تعداد کا ٹریک رکھنے کی ضرورت ہے۔
• نابالغوں کو اشتہارات دکھانے کا الگورتھم مختلف ہے۔

آئیے ایک ایسی کلاس بنائیں Personجو کسی شخص کے بارے میں ہمارے پاس دستیاب تمام معلومات کو محفوظ کرے:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

ہم کلاس میں منطق کو نافذ کرتے ہیں Main:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Mainہم جو کلاس بناتے ہیں اس میں ایک مخصوص شخص TreeMapکہاں ہے، اور اس مہینے کے اشتہار کے نقوش کی تعداد ہے۔ کنسٹرکٹر میں ہم ایک موازنہ پاس کرتے ہیں جو لوگوں کو عمر کے لحاظ سے ترتیب دے گا۔ بے ترتیب اقدار سے بھریں ۔ اب ہمیں اپنے منی ڈیٹا اسٹور میں پہلے بالغ کا حوالہ حاصل کرنے کی ضرورت ہے۔ ہم یہ Stream API کا استعمال کرتے ہوئے کرتے ہیں۔ اس کے بعد، ہمیں دو آزاد نقشے ملتے ہیں، جنہیں ہم اشتہارات کو ظاہر کرنے والے طریقوں کو منتقل کرتے ہیں۔ اس مسئلے کو حل کرنے کے بہت سے طریقے ہیں۔ کلاس کے طریقوں کا ہتھیار آپ کو ہر ذائقہ کے مطابق حل ایجاد کرنے کی اجازت دیتا ہے۔ ان سب کو یاد رکھنا ضروری نہیں ہے، کیونکہ آپ ہمیشہ ترقیاتی ماحول سے دستاویزات یا اشارے استعمال کر سکتے ہیں۔ بس! مجھے امید ہے کہ کلاس اب آپ کے لیے واضح ہے، اور آپ کو عملی مسائل کو حل کرنے میں اس کے لیے قطعی اطلاق ملے گا۔ keyvaluemapTreeMapTreeMap