TreeMap ב-Java

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

השוואת TreeMap, HashMap ו-LinkedHashMap

המימוש הנפוץ ביותר של ממשק Map הוא 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 האלמנטים כדי למצוא אותו. עבור 13 אלמנטים, זה לא עניין גדול, אבל כשעובדים עם מיליון, יהיו לנו בעיות גדולות. כדי לפתור את הבעיות הללו, מתכנתים משתמשים במבני נתונים קצת יותר מורכבים. כאן נכנס העץ האדום-שחור לבמה! חיפוש אלמנט מתחיל בשורש העץ, שבמקרה שלנו הוא 61. לאחר מכן נשווה את ערכי הצומת עם הערך שאנו מחפשים. אם הערך שלנו פחות, אז אנחנו הולכים שמאלה; אם הוא גדול יותר, אז אנחנו הולכים ימינה. תהליך זה חוזר על עצמו עד שאנו מוצאים את הערך הרצוי או נתקלים באלמנט שערכו ריק (עלה של העץ). הצבעים אדום ושחור משמשים כדי לפשט את הניווט ואיזון העץ. ישנם כללים שתמיד יש להקפיד עליהם בעת בניית עץ אדום-שחור:

• השורש חייב להיות שחור.
• עלי העץ חייבים להיות שחורים.
• לצומת אדום חייבים להיות שני צמתים צאצאים שחורים.
• לצומת שחור יכולים להיות צמתים צאצאים בכל צבע.
• נתיב מצומת לעלים שלו חייב להכיל את אותו מספר של צמתים שחורים.
• צמתים חדשים מתווספים לעלים.

אם תחשבו על כללים 3, 4 ו-5 ביחד, תוכלו להבין כיצד צבע הצמתים מאפשר לנו לנווט בעץ מהר יותר: נתיב דרך צמתים שחורים תמיד קצר יותר מאשר דרך צמתים אדומים. בהתאם לכך, הגודל הכולל של העץ נקבע על פי מספר הצמתים השחורים, הנקרא "הגובה השחור". מבנה נתוני העץ האדום-שחור מיושם בשפות תכנות שונות. יש הרבה יישומי Java באינטרנט, אז לא נתעכב כאן. במקום זאת, בואו נמשיך להכיר את הפונקציונליות של TreeMap.

שיטות המגיעות מהממשקים SortedMap ו-NavigableMap

כמו HashMap, TreeMap מיישמת את ממשק Map, מה שאומר של-TreeMap יש את כל השיטות הקיימות ב-HashMap. אבל TreeMap מיישמת גם את ממשקי SortedMap ו- NavigableMap , וכך מרוויחה מהם פונקציונליות נוספת. SortedMap הוא ממשק שמרחיב את מפה ומוסיף שיטות רלוונטיות למערך נתונים ממוין:

• firstKey() : מחזיר את המפתח של האלמנט הראשון במפה
• lastKey() : מחזירה את המפתח של האלמנט האחרון
• headMap(K end) : מחזירה מפה המכילה את כל הרכיבים של המפה הנוכחית, מההתחלה ועד האלמנט עם סוף המפתח
• tailMap(K start) : מחזירה מפה המכילה את כל הרכיבים של המפה הנוכחית, מאלמנט ההתחלה ועד הסוף
• subMap(K start, K ​​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() : מחזירה NavigableSet המכיל את כל המפתחות ממוינים בסדר הפוך
• descendingMap() : מחזירה מפת Navigable שמכילה את כל הזוגות ממוינים בסדר הפוך
• navigableKeySet() : מחזירה אובייקט NavigableSet המכיל את כל המפתחות בסדר שבו הם מאוחסנים
• headMap(K upperBound, boolean incl) : מחזירה מפה המכילה זוגות מההתחלה לאלמנט upperBound. הפרמטר incl מציין אם לכלול את האלמנט upperBound במפה המוחזרת
• tailMap(K lowerBound, boolean incl) : פונקציונליות דומה לשיטה הקודמת, מחזירה רק זוגות מהגבול התחתון עד הסוף
• subMap(K lowerBound, Boolean lowIncl, K upperBound, Boolean highIncl) : כמו בשיטות הקודמות, מחזירה זוגות מהגבול התחתון ל-UpperBound; הארגומנטים lowIncl ו-highIncl מציינים אם לכלול את רכיבי הגבול במפה החדשה.

בנוסף לבנאים הרגילים, ל-TreeMap יש בנאי נוסף שמקבל מופע של משווה. המשווה הזה אחראי לסדר שבו מאוחסנים אלמנטים.

דוגמאות של TreeMap

השפע הזה של שיטות נוספות עשוי להיראות מיותר, אבל הן מתבררות כמועילות הרבה יותר ממה שאתה עשוי להבין במבט ראשון. בואו נחקור יחד את הדוגמה הבאה. תארו לעצמכם שאנחנו עובדים במחלקת השיווק של חברה גדולה, ויש לנו מאגר של אנשים להם אנחנו רוצים להציג מודעות. יש לזכור שני פרטים:

• עלינו לעקוב אחר מספר ההופעות של כל אדם
• האלגוריתם להצגת מודעות לקטינים שונה.

בואו ניצור כיתת אדם , שתשמור את כל המידע הרלוונטי על כל אדם:

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;
   }
}

אנו מיישמים את ההיגיון במחלקה הראשית :

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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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, שבה כל מפתח מייצג אדם ספציפי, וכל ערך הוא מספר הופעות המודעה החודש. אנחנו מעבירים את הקונסטרוקטור משווה שממיין אנשים לפי גיל. אנו ממלאים את המפה בערכים שרירותיים. כעת אנו רוצים לקבל התייחסות למבוגר הראשון במאגר הנתונים הקטן שלנו. אנו עושים זאת באמצעות ה-API של Stream. לאחר מכן נקבל שתי מפות נפרדות, אותן אנו מעבירים לשיטות שמציגות מודעות. יש הרבה מאוד דרכים שיכולנו לבצע את המשימה הזו. ארסנל השיטות של מחלקת TreeMap מאפשר לנו ליצור פתרונות מותאמים אישית לכל צורך. אתה לא צריך לזכור את כולם, כי אתה תמיד יכול להשתמש בתיעוד או בטיפים מה-IDE שלך. כדי לחזק את מה שלמדת, אנו מציעים לך לצפות בשיעור וידאו מקורס Java שלנו זה הכל לעת עתה! אני מקווה ששיעור TreeMap ברור לך עכשיו, ושתיישם אותו כראוי בפתרון משימות קידוד מעשיות.