جاوا ۾ TreeMap جون خاصيتون

جيڪڏهن توهان هي مضمون پڙهي رهيا آهيو، موقعا آهن ته توهان نقشي جي انٽرفيس ۽ ان جي استعمالن کان واقف آهيو. جيڪڏهن نه، ته هتي وڃو. اڄ اسان TreeMap جي عمل درآمد جي خاصيتن بابت ڳالهائينداسين، ۽ خاص طور تي، اهو ڪيئن HashMap کان مختلف آهي ۽ ان کي ڪيئن استعمال ڪجي.

TreeMap، HashMap ۽ LinkedHashMap جو مقابلو

نقشي جي انٽرفيس جو سڀ کان عام استعمال ٿيل عمل آھي HashMap . اهو استعمال ڪرڻ آسان آهي ۽ ڊيٽا تائين تيز پهچ جي ضمانت ڏئي ٿو، ان کي اڪثر ڪمن لاءِ بهترين اميدوار بڻائيندي. گهڻا، پر سڀ نه. ڪڏهن ڪڏهن اهو ضروري آهي ته ڊيٽا کي هڪ منظم فارم ۾ ذخيرو ڪرڻ جي صلاحيت سان گڏ ان جي ذريعي نيوڻ جي صلاحيت سان. انهي صورت ۾، نقشي جي انٽرفيس جو هڪ ٻيو عمل بچاء لاء اچي ٿو - TreeMap . TreeMap NavigableMap انٽرفيس کي لاڳو ڪري ٿو ، جيڪو SortedMap مان ورثي ۾ ملي ٿو ، جيڪو بدلي ۾ Map انٽرفيس مان ورثي ۾ ملي ٿو . NavigableMap ۽ SortedMap انٽرفيس کي لاڳو ڪرڻ سان ، TreeMap اضافي ڪارڪردگي حاصل ڪري ٿو جيڪا HashMap نه ٿي ڪري ، پر ڪارڪردگي جي لحاظ کان اها قيمت اچي ٿي. هتي هڪ LinkedHashMap ڪلاس پڻ آهي ، جيڪو توهان کي ڊيٽا کي هڪ خاص ترتيب ۾ ذخيرو ڪرڻ جي اجازت ڏئي ٿو - ترتيب ۾ اهي شامل ڪيا ويا آهن. توھان جي مدد ڪرڻ لاءِ انھن ٽنھي طبقن جي وچ ۾ فرق سمجھڻ ۾ ، ھن جدول کي ڏسو: جئين توهان ڏسي سگهو ٿا، انهن طبقن ۾ تمام گهڻو عام آهي، پر ڪجهه اختلاف پڻ آهن. جيتوڻيڪ ڪلاس TreeMapتمام گھڻا ڪم ڪندڙ آھي، ان کي ھميشه nullچاٻي جي طور تي ذخيرو نٿو ڪري سگھجي. ان کان علاوه، TreeMap عناصر تائين رسائي جو وقت تمام ڊگهو ٿيندو. تنهن ڪري، جيڪڏهن توهان کي ترتيب ڏنل فارم ۾ ڊيٽا کي ذخيرو ڪرڻ جي ضرورت ناهي، اهو استعمال ڪرڻ بهتر آهي HashMapيا LinkedHashMap.

ڳاڙهي آبنوس جو وڻ

جيئن توهان شايد محسوس ڪيو آهي، هود جي هيٺان TreeMapاهو ڊيٽا جي جوڙجڪ استعمال ڪري ٿو جنهن کي ڳاڙهي-ڪارو وڻ سڏيو ويندو آهي. اهو هن ڍانچي ۾ ڊيٽا جي اسٽوريج آهي جيڪا انهي ترتيب کي يقيني بڻائي ٿي جنهن ۾ ڊيٽا محفوظ ڪئي وئي آهي. هي وڻ ڇا آهي؟ اچو ته ان جو اندازو لڳايو! تصور ڪريو ته توھان کي ذخيرو ڪرڻ جي ضرورت آھي نمبر-اسٽرنگ جوڙو. نمبر 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.

ترتيب ڏنل ميپ ۽ نيويگيبل ميپ انٽرفيس مان نڪتل طريقا

جهڙوڪ 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): ڏي ٿو سڀ کان وڏي ڪي ڪي ڪي جيڪا ڪيئي اعتراض کان ننڍي آهي. جيڪڏهن ڪا به اهڙي ڪيڏي نه آهي، واپسي null؛
• higherKey(K obj): واپس ڪري ٿو ننڍي ڪيئي k جيڪا ڪيئي اعتراض کان وڏي آهي. جيڪڏهن ڪا به اهڙي ڪيڏي نه آهي، واپسي null؛
• ceilingEntry(K obj): ceilingKey (K obj) طريقي سان ملندڙ، پر واپسي هڪ اهم-قدر جوڙو (يا null)؛
• floorEntry(K obj): فرش ڪيئي (K obj) طريقي سان ملندڙ، پر واپسي هڪ اهم-قدر جوڙو (يا null)؛
• lowerEntry(K obj): لوئر ڪيئي (ڪي آبج) جي طريقي سان ملندڙ، پر هڪ اهم-قدر جوڙو موٽائي ٿو (يا null)؛
• higherEntry(K obj): مماثلت HighKey(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 استعمال ڪرڻ جا مثال

اهڙي قسم جي اضافي طريقن جي گهڻائي غير ضروري لڳي سگهي ٿي، پر گهڻو ڪري اهي گهڻو ڪري وڌيڪ ڪارائتو ٿي ويندا آهن ان کان وڌيڪ شروعاتي طور تي. اچو ته هن مثال کي توهان سان گڏ ڏسو. تصور ڪريو ته اسان هڪ وڏي ڪمپني جي مارڪيٽنگ ڊپارٽمينٽ ۾ ڪم ڪريون ٿا، ۽ اسان وٽ ماڻهن جو ڊيٽابيس آهي، جن کي اسان اشتهار ڏيکارڻ چاهيون ٿا. ان ۾ ٻه nuances آهن:

• اسان کي هر شخص جي نقوش جي تعداد جي ٽريڪ رکڻ جي ضرورت آهي؛
• نابالغ لاءِ اشتهار ڏيکارڻ جو الگورتھم مختلف آھي.

اچو ته هڪ ڪلاس ٺاهيون 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، keyهڪ مخصوص ماڻهو ڪٿي آهي، ۽ valueهن مهيني اشتهارن جي نقوش جو تعداد آهي. تعمير ڪندڙ ۾ اسان ھڪڙو موازنہ پاس ڪريون ٿا جيڪو ماڻھن کي عمر جي لحاظ کان ترتيب ڏيندو. بي ترتيب قدرن سان ڀريو map. هاڻي اسان کي اسان جي مني ڊيٽا اسٽور ۾ پهريون بالغ جو حوالو حاصل ڪرڻ جي ضرورت آهي. اسان اهو ڪريون ٿا اسٽريم API استعمال ڪندي. ان کان پوء، اسان ٻه آزاد نقشا حاصل ڪندا آهيون، جن کي اسين انهن طريقن ڏانهن منتقل ڪندا آهيون جيڪي اشتهارن کي ظاهر ڪن ٿا. اتي ڪيترائي، ڪيترائي طريقا آھن جن ۾ ھن مسئلي کي حل ڪري سگھجي ٿو. طريقن جي طبقي جو هٿيار TreeMapتوهان کي هر ذائقي مطابق حل ڪرڻ جي اجازت ڏئي ٿو. اهو ضروري ناهي ته انهن سڀني کي ياد رکڻ لاء، ڇو ته توهان هميشه ترقي جي ماحول مان دستاويز يا اشارو استعمال ڪري سگهو ٿا. اهو ئي سڀ ڪجهه آهي! مون کي اميد آهي ته ڪلاس هاڻي TreeMapتوهان لاءِ واضح ٿي چڪو آهي، ۽ توهان عملي مسئلن کي حل ڪرڻ ۾ ان لاءِ صحيح درخواست ڳوليندا.