תכונות של TreeMap ב-Java

אם אתה קורא מאמר זה, רוב הסיכויים שאתה מכיר את ממשק המפה והשימושים בו. אם לא, אז הנה. היום נדבר על תכונות היישום של TreeMap, וליתר דיוק, כיצד היא שונה מ- HashMap וכיצד להשתמש בה נכון.

השוואה בין TreeMap, HashMap ו-LinkedHashMap

היישום הנפוץ ביותר של ממשק Map הוא HashMap . זה קל לשימוש ומבטיח גישה מהירה לנתונים, מה שהופך אותו למועמד הטוב ביותר עבור רוב המשימות. רוב, אבל לא כולם. לפעמים יש צורך לאחסן נתונים בצורה מובנית עם יכולת לנווט בהם. במקרה זה, יישום נוסף של ממשק Map מגיע לעזרה - 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 האלמנטים כדי למצוא אותו. עבור 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): דומה לשיטת 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(): מחזירה סט Navigable שמכיל את כל המפתחות ממוינים בסדר הפוך;
• descendingMap(): מחזירה מפת ניווט המכילה את כל הזוגות ממוינים בסדר הפוך;
• navigableKeySet(): מחזיר אובייקט NavigableSet המכיל את כל המפתחות בסדר אחסון;
• headMap(K upperBound, boolean incl): מחזירה מפה המכילה זוגות מההתחלה לאלמנט upperBound. הארגומנט 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בערכים אקראיים. כעת עלינו לקבל התייחסות למבוגר הראשון במאגר הנתונים המיני שלנו. אנו עושים זאת באמצעות ה-API של Stream. לאחר מכן, נקבל שתי מפות עצמאיות, אותן אנו מעבירים לשיטות המציגות פרסום. יש הרבה מאוד דרכים בהן ניתן לפתור את הבעיה הזו. ארסנל השיטות של הכיתה TreeMapמאפשר להמציא פתרונות שיתאימו לכל טעם. אין צורך לזכור את כולם, כי תמיד אפשר להשתמש בתיעוד או ברמזים מסביבת הפיתוח. זה הכל! אני מקווה שהשיעור TreeMapברור לך כעת, ותמצא יישום מדויק עבורו בפתרון בעיות מעשיות.