streamalism.org

1. סקירה כללית

במאמר זה נראה כיצד להשתמש מפת גיבוב בג'אווה, ונבדוק איך זה עובד באופן פנימי.

כיתה דומה מאוד ל מפת גיבוב הוא טבלת גיבוב. אנא עיין בכמה מאמרים אחרים שלנו כדי ללמוד עוד על ה- java.util. השבת המעמד עצמו וההבדלים בין מפת גיבוב ו טבלת גיבוב.

2. שימוש בסיסי

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

אפשר לשאול מדוע פשוט לא להוסיף את הערך לרשימה. מדוע אנו צריכים א מפת גיבוב? הסיבה הפשוטה היא ביצועים. אם אנו רוצים למצוא אלמנט ספציפי ברשימה, מורכבות הזמן היא עַל) ואם הרשימה ממוינת, היא תהיה O (יומן n) באמצעות, למשל, חיפוש בינארי.

היתרון של א מפת גיבוב הוא שמורכבות הזמן להכניס ולאחזר ערך היא O (1) בממוצע. נבדוק כיצד ניתן להשיג זאת בהמשך. בואו נסתכל תחילה כיצד להשתמש מפת גיבוב.

2.1. להכין

בואו ניצור כיתה פשוטה בה נשתמש לאורך המאמר:

מוצר בכיתה ציבורית {שם מחרוזת פרטי; תיאור מחרוזת פרטי; תגי רשימה פרטיים; // getters / סטרים סטנדרטיים / בונים ציבוריים addTagsOfOtherProdcut (מוצר מוצר) מוצר {this.tags.addAll (product.getTags ()); להחזיר את זה; }}

2.2. לָשִׂים

כעת אנו יכולים ליצור מפת גיבוב עם מפתח הסוג חוּט ואלמנטים מהסוג מוצר:

מיפוי productsByName = HashMap חדש (); 

והוסף מוצרים שלנו מפת גיבוב:

מוצר eBike = מוצר חדש ("אופניים אלקטרוניים", "אופניים עם סוללה"); מוצר roadBike = מוצר חדש ("אופני כביש", "אופניים לתחרות"); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 

2.3. לקבל

אנו יכולים לאחזר ערך מהמפה באמצעות המפתח שלה:

המוצר nextPurchase = productsByName.get ("אופניים אלקטרוניים"); assertEquals ("אופניים עם סוללה", nextPurchase.getDescription ());

אם ננסה למצוא ערך עבור מפתח שלא קיים במפה, נקבל ריק ערך:

המוצר nextPurchase = productsByName.get ("רכב"); assertNull (NextPurchase);

ואם נכניס ערך שני עם אותו מפתח, נקבל רק את הערך האחרון שהוכנס עבור אותו מפתח:

מוצר newEBike = מוצר חדש ("אופניים אלקטרוניים", "אופניים עם סוללה טובה יותר"); productsByName.put (newEBike.getName (), newEBike); assertEquals ("אופניים עם סוללה טובה יותר", productsByName.get ("אופניים אלקטרוניים"). getDescription ());

2.4. אפס כמפתח

מפת גיבוב גם מאפשר לנו לקבל ריק כמפתח:

מוצר ברירת מחדל מוצר = מוצר חדש ("שוקולד", "לפחות קנה שוקולד"); productsByName.put (null, defaultProduct); המוצר nextPurchase = productsByName.get (null); assertEquals ("לפחות קנה שוקולד", nextPurchase.getDescription ());

2.5. ערכים עם אותו מפתח

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

productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("שוקולד"));

2.6. הסר ערך

אנו יכולים להסיר מיפוי של ערך מפתח מה- מפת גיבוב:

productsByName.remove ("אופניים אלקטרוניים"); assertNull (productsByName.get ("אופניים אלקטרוניים"));

2.7. בדוק אם קיים מפתח או ערך במפה

כדי לבדוק אם קיים מפתח במפה, נוכל להשתמש ב- containKey () שיטה:

productsByName.containsKey ("אופניים אלקטרוניים");

לחלופין, כדי לבדוק אם קיים ערך במפה, נוכל להשתמש ב- containValue () שיטה:

productsByName.containsValue (eBike);

שתי שיחות השיטה יחזרו נָכוֹן בדוגמה שלנו. למרות שהם נראים דומים מאוד, יש הבדל חשוב בביצועים בין שתי שיחות השיטה הללו. המורכבות לבדוק אם קיים מפתח היא O (1), בעוד המורכבות לבדוק אלמנט היא עַל), מכיוון שיש צורך לעבור על כל האלמנטים במפה.

2.8. מתבוסס מעל א מפת גיבוב

ישנן שלוש דרכים בסיסיות לחזור על כל זוגות ערכי המפתח ב- מפת גיבוב.

אנו יכולים לחזור על קבוצה של כל המקשים:

עבור (מפתח מחרוזת: productsByName.keySet ()) {Product product = productsByName.get (key); }

לחלופין נוכל לחזור על קבוצה של כל הערכים:

עבור (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); מפתח מחרוזת = entry.getKey (); // לעשות משהו עם המפתח והערך}

לבסוף, אנו יכולים לחזור על כל הערכים:

רשימת מוצרים = ArrayList חדש (productsByName.values ​​());

3. המפתח

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

HashMap priceByProduct = HashMap חדש (); priceByProduct.put (eBike, 900);

בואו ליישם את שווים() ו hashCode () שיטות:

@ עקוף בוליאני ציבורי שווה (Object o) {if (this == o) {return true; } אם (o == null || getClass ()! = o.getClass ()) {return false; } מוצר מוצר = (מוצר) o; להחזיר Objects.equals (שם, product.name) && Objects.equals (תיאור, מוצר.תיאור); } @Override public int hashCode () {return Objects.hash (שם, תיאור); }

ציין זאת hashCode () ו שווים() צריך לעקוף רק עבור שיעורים שאנו רוצים להשתמש כמפתחות מפה, ולא עבור מחלקות המשמשות רק כערכים במפה. נראה מדוע זה הכרחי בסעיף 5 למאמר זה.

4. שיטות נוספות החל מג'אווה 8

Java 8 הוסיפה מספר שיטות בסגנון פונקציונלי מפת גיבוב. בחלק זה נבחן כמה משיטות אלה.

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

מכיוון ששיטות אלה פשוטות למדי, לא נבחן דוגמאות מפורטות יותר.

4.1. לכל אחד()

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

productsByName.forEach ((מפתח, מוצר) -> {System.out.println ("מפתח:" + מפתח + "מוצר:" + product.getDescription ()); // לעשות משהו עם המפתח והערך}); 

לפני Java 8:

עבור (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); מפתח מחרוזת = entry.getKey (); // לעשות משהו עם המפתח והערך}

מדריך המאמרים שלנו ל- Java 8 לכל אחד מכסה את לכל אחד לולאה בפירוט רב יותר.

4.2. getOrDefault ()

משתמש ב getOrDefault () בשיטה, אנו יכולים לקבל ערך מהמפה או להחזיר אלמנט ברירת מחדל למקרה שאין מיפוי למפתח הנתון:

שוקולד מוצר = מוצר חדש ("שוקולד", "משהו מתוק"); מוצר defaultProduct = productsByName.getOrDefault ("כרכרת סוסים", שוקולד); אופני מוצר = productsByName.getOrDefault ("אופניים אלקטרוניים", שוקולד);

לפני Java 8:

מוצר bike2 = productsByName.containsKey ("אופניים אלקטרוניים")? productsByName.get ("אופניים אלקטרוניים"): שוקולד; מוצר defaultProduct2 = productsByName.containsKey ("כרכרת סוסים")? productsByName.get ("כרכרת סוסים"): שוקולד; 

4.3. putIfAbsent ()

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

productsByName.putIfAbsent ("אופניים אלקטרוניים", שוקולד); 

לפני Java 8:

if (productsByName.containsKey ("אופניים אלקטרוניים")) {productsByName.put ("אופניים אלקטרוניים", שוקולד); }

המאמר שלנו מיזוג שתי מפות עם Java 8 בוחן מקרוב את השיטה הזו.

4.4. לְמַזֵג()

ועם לְמַזֵג(), אנו יכולים לשנות את הערך עבור מפתח נתון אם קיים מיפוי, או להוסיף ערך חדש אחרת:

מוצר eBike2 = מוצר חדש ("אופניים אלקטרוניים", "אופניים עם סוללה"); eBike2.getTags (). add ("ספורט"); productsByName.merge ("אופניים אלקטרוניים", eBike2, מוצר :: addTagsOfOtherProdcut);

לפני Java 8:

if (productsByName.containsKey ("אופניים אלקטרוניים")) {productsByName.get ("אופניים אלקטרוניים"). addTagsOfOtherProdcut (eBike2); } אחר {productsByName.put ("אופניים אלקטרוניים", eBike2); } 

4.5. לְחַשֵׁב()

עם ה לְחַשֵׁב() בשיטה, אנו יכולים לחשב את הערך עבור מפתח נתון:

productsByName.compute ("אופניים אלקטרוניים", (k, v) -> {if (v! = null) {return v.addTagsOfOtherProdcut (eBike2);} אחר {להחזיר eBike2;}});

לפני Java 8:

אם (productsByName.containsKey ("אופניים אלקטרוניים")) {productsByName.get ("אופניים אלקטרוניים"). addTagsOfOtherProdcut (eBike2); } אחר {productsByName.put ("אופניים אלקטרוניים", eBike2); } 

ראוי לציין כי ה שיטות לְמַזֵג() ו לְחַשֵׁב() די דומים. ה שיטת חישוב () מקבל שני טיעונים: ה מַפְתֵחַ ו BiFunction למיפוי מחדש. וגם לְמַזֵג() מקבל שלושה פרמטרים: ה- מַפְתֵחַ, א ערך ברירת מחדל להוסיף למפה אם המפתח עדיין לא קיים, ו BiFunction למיפוי מחדש.

5. מפת גיבוב פנימיות

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

כפי שראינו, אנו יכולים לשלוף אלמנט מ- a מפת גיבוב לפי המפתח שלה. גישה אחת תהיה להשתמש ברשימה, לחזור על כל האלמנטים ולחזור כאשר אנו מוצאים אלמנט שהמפתח תואם אליו. מורכבות הזמן והמרחב של גישה זו תהיה עַל).

עם מפת גיבובאנו יכולים להשיג מורכבות זמן ממוצעת של O (1) בשביל ה לָשִׂים ו לקבל פעולות ומורכבות החלל של עַל). בואו נראה איך זה עובד.

5.1. קוד האש ושווה

במקום לחזור על כל מרכיביו, מפת גיבוב מנסה לחשב את מיקום הערך על סמך המפתח שלו.

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

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

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

כאשר אנו מכניסים ערך למפה, המפתח hashCode () נעשה שימוש בשיטה לקביעת הדלי בו יאוחסן הערך.

כדי לאחזר את הערך, מפת גיבוב מחשבת את הדלי באותו אופן - באמצעות hashCode (). ואז זה חוזר דרך האובייקטים שנמצאים בדלי הזה ומשתמש במפתחות שווים() שיטה כדי למצוא את ההתאמה המדויקת.

5.2. Immutability של מפתחות

ברוב המקרים, עלינו להשתמש במקשים ללא שינוי. או לפחות, עלינו להיות מודעים להשלכות השימוש במפתחות משתנים.

בואו נראה מה קורה כאשר המפתח שלנו משתנה לאחר שהשתמשנו בו לאחסון ערך במפה.

לדוגמא זו, ניצור את ה- MutableKey:

מחלקה ציבורית MutableKey {שם מחרוזת פרטי; // קונסטרוקטור סטנדרטי, גטר וקובע @Override בוליאני ציבורי שווה (Object o) {if (this == o) {return true; } אם (o == null || getClass ()! = o.getClass ()) {return false; } MutableKey זה = (MutableKey) o; להחזיר Objects.equals (שם, that.name); } @Override ציבורי int hashCode () {להחזיר Objects.hash (שם); }}

והנה המבחן:

מפתח MutableKey = חדש MutableKey ("ראשוני"); פריטי מפה = HashMap חדש (); items.put (מפתח, "הצלחה"); key.setName ("השתנה"); assertNull (items.get (key));

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

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

5.3. התנגשויות

כדי שזה יעבוד כראוי, מקשים שווים חייבים להיות בעלי אותו חשיש, אולם מקשים שונים יכולים להיות בעלי אותו חשיש. אם לשני מקשים שונים יש אותו חשיש, שני הערכים השייכים להם יאוחסנו באותו דלי. בתוך דלי, הערכים נשמרים ברשימה ומאוחזרים על ידי לולאה על כל האלמנטים. העלות של זה היא עַל).

החל ב- Java 8 (ראה JEP 180), מבנה הנתונים בו מאוחסנים הערכים בתוך דלי אחד משתנה מרשימה לעץ מאוזן אם דלי מכיל 8 ערכים ומעלה, והוא מוחזר לרשימה אם, ב בשלב מסוים, רק 6 ערכים נותרו בדלי. זה משפר את הביצועים להיות O (יומן n).

5.4. גורם קיבולת ועומס

כדי להימנע מכך שדליים רבים בעלי ערכים מרובים, הקיבולת מוכפלת אם 75% (גורם העומס) מהדליים אינם ריקים. ערך ברירת המחדל עבור מקדם העומס הוא 75%, וקיבולת ההתחלה המוגדרת כברירת מחדל היא 16. ניתן להגדיר את שניהם בבנאי.

5.5. סיכום של לָשִׂים ו לקבל פעולות

בואו נסכם כיצד ה לָשִׂים ו לקבל עבודות פעולות.

כאשר אנו מוסיפים אלמנט למפה,מפת גיבוב מחשבת את הדלי. אם הדלי כבר מכיל ערך, הערך מתווסף לרשימה (או העץ) השייכת לאותו דלי. אם גורם העומס הופך לגדול יותר מפקטור העומס המרבי של המפה, הקיבולת מוכפלת.

כשאנחנו רוצים לקבל ערך מהמפה,מפת גיבוב מחשבת את הדלי ומקבלת את הערך עם אותו מפתח מהרשימה (או העץ).

6. מסקנה

במאמר זה ראינו כיצד להשתמש ב- מפת גיבוב ואיך זה עובד באופן פנימי. ביחד עם רשימת מערך, מפת גיבוב הוא אחד ממבני הנתונים הנפוצים ביותר ב- Java, ולכן זה מאוד שימושי שיש לך ידע טוב כיצד להשתמש בו וכיצד הוא עובד מתחת למכסה המנוע. המאמר שלנו The Java HashMap Under the Hood מכסה את הפנימיות של מפת גיבוב בפירוט רב יותר.

כרגיל, קוד המקור השלם זמין ב- Github.