ميزات TreeMap في جافا

إذا كنت تقرأ هذه المقالة، فمن المحتمل أنك على دراية بواجهة الخريطة واستخداماتها. إذا لم يكن كذلك، ثم هنا تذهب. سنتحدث اليوم عن ميزات تنفيذ TreeMap، وبشكل أكثر تحديدًا، كيف يختلف عن HashMap وكيفية استخدامه بشكل صحيح.

مقارنة TreeMap وHashMap وLinkedHashMap

التطبيق الأكثر استخدامًا لواجهة الخريطة هو HashMap . إنه سهل الاستخدام ويضمن الوصول السريع إلى البيانات، مما يجعله المرشح الأفضل لمعظم المهام. معظم، ولكن ليس كل شيء. في بعض الأحيان يكون من الضروري تخزين البيانات في شكل منظم مع إمكانية التنقل خلالها. في هذه الحالة، يأتي تنفيذ آخر لواجهة الخريطة للإنقاذ - TreeMap . يقوم TreeMap بتطبيق واجهة NavigableMap ، التي ترث من SortedMap ، والتي ترث بدورها من واجهة الخريطة . من خلال تنفيذ واجهات 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 عنصرًا، هذا ليس أمرًا بالغ الأهمية، فعند العمل مع مليون سنواجه مشاكل كبيرة. لحل مثل هذه المشاكل، يستخدم المبرمجون هياكل بيانات أكثر تعقيدًا قليلاً. لذلك، تعرف على الشجرة الحمراء السوداء!

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

يبدأ البحث عن العنصر المطلوب من جذر الشجرة، وهو في حالتنا 61. وبعد ذلك، يتم إجراء المقارنة مع القيمة المطلوبة. إذا كانت قيمتنا أقل، نتجه إلى اليسار، وإذا كانت أكثر، نتجه إلى اليمين. يحدث هذا حتى نجد القيمة المطلوبة أو نضرب عنصرًا بقيمة null(ورقة شجرة). يتم استخدام اللونين الأحمر والأسود لتسهيل التنقل والتوازن في الشجرة. هناك قواعد يجب اتباعها دائمًا عند بناء شجرة حمراء سوداء:

• يجب أن يكون لون الجذر أسود.
• يجب أن تكون أوراق الشجرة سوداء.
• يجب أن تحتوي العقدة الحمراء على عقدتين تابعتين باللون الأسود.
• يمكن أن تحتوي العقدة السوداء على أي عقد فرعية.
• يجب أن يحتوي المسار من العقدة إلى أوراقها على نفس عدد العقد السوداء.
• تتم إضافة العقد الجديدة بدلا من الأوراق.

إذا نظرت إلى القواعد 3 و4 و5 معًا، فيمكنك فهم كيف تعمل عقد التلوين على تسريع التنقل عبر الشجرة: يكون المسار عبر العقد السوداء دائمًا أقصر من المسار عبر العقد الحمراء. ولذلك، يتم تحديد الحجم الإجمالي للشجرة من خلال عدد العقد السوداء، ويسمى هذا الحجم "الارتفاع الأسود". يتم تنفيذ الشجرة ذات اللون الأحمر والأسود بلغات برمجة مختلفة. هناك الكثير من تطبيقات Java على الإنترنت، لذلك لن نتناولها لفترة طويلة، ولكننا سنستمر في التعرف على وظائفها 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 أكبر من أو يساوي المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع null؛
• floorKey(K obj): إرجاع أكبر مفتاح k أقل من أو يساوي المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع null؛
• lowerKey(K obj): إرجاع أكبر مفتاح k أصغر من مفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع null؛
• higherKey(K obj): إرجاع أصغر مفتاح k أكبر من مفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع null؛
• ceilingEntry(K obj): يشبه طريقة السقف Key(K obj)، ولكنه يُرجع زوجًا من القيمة الرئيسية (أو خاليًا)؛
• floorEntry(K obj): يشبه طريقة FloorKey(K obj)، ولكنه يُرجع زوجًا من القيمة الرئيسية (أو خاليًا)؛
• lowerEntry(K obj): يشبه الأسلوب LowerKey(K obj)، ولكنه يُرجع زوجًا من القيمة الرئيسية (أو خاليًا)؛
• higherEntry(K obj): يشبه الأسلوب HighKey(K obj)، ولكنه يُرجع زوجًا من القيمة الرئيسية (أو خاليًا)؛
• descendingKeySet(): إرجاع NavigableSet الذي يحتوي على جميع المفاتيح مرتبة بترتيب عكسي؛
• descendingMap(): إرجاع NavigableMap الذي يحتوي على جميع الأزواج مرتبة بترتيب عكسي؛
• navigableKeySet(): يُرجع كائن NavigableSet الذي يحتوي على جميع المفاتيح بترتيب التخزين؛
• headMap(K upperBound, boolean incl): تقوم بإرجاع خريطة تحتوي على أزواج من البداية إلى العنصر العلوي. تحدد الوسيطة incl ما إذا كان يجب تضمين عنصر UpperBound في الخريطة التي تم إرجاعها؛
• tailMap(K lowerBound, boolean incl): الوظيفة مشابهة للطريقة السابقة، ويتم إرجاع الأزواج فقط من LowerBound إلى النهاية؛
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): كما هو الحال في الطرق السابقة، يتم إرجاع الأزواج من LowerBound إلى UpperBound، وتشير الوسيطتان 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مكان keyوجود شخص معين، valueوعدد مرات ظهور الإعلان هذا الشهر. في المُنشئ، نمرر مُقارنًا يقوم بفرز الأشخاص حسب العمر. املأ mapبالقيم العشوائية. نحتاج الآن إلى الحصول على إشارة إلى أول شخص بالغ في مخزن البيانات المصغر الخاص بنا. نحن نقوم بذلك باستخدام Stream API. بعد ذلك نحصل على خريطتين مستقلتين، نمررهما إلى طرق عرض الإعلانات. هناك العديد والعديد من الطرق التي يمكن من خلالها حل هذه المشكلة. تتيح لك ترسانة الأساليب الخاصة بالفصل TreeMapابتكار حلول تناسب جميع الأذواق. ليس من الضروري أن تتذكرها جميعًا، لأنه يمكنك دائمًا استخدام الوثائق أو التلميحات من بيئة التطوير. هذا كل شئ! أتمنى أن يكون الفصل الآن TreeMapواضحًا لك، وأن تجد تطبيقًا دقيقًا له في حل المشكلات العملية.