streamalism.org

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

במאמר זה, אנו הולכים לחקור את היישום הפופולרי ביותר של מַפָּה ממשק ממסגרת אוספי Java בפירוט רב יותר, תוך שהוא מפסיק מהמקום שבו הפסיק מאמר המבוא שלנו.

לפני שנתחיל עם היישום, חשוב לציין שהראשוני רשימה ו מַעֲרֶכֶת ממשקי האיסוף מתרחבים אוסף אבל מַפָּה לא.

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

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

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

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

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

2. ה לָשִׂים() ממשק API

כדי לאחסן ערך במפת hash, אנו קוראים לָשִׂים API שלוקח שני פרמטרים; מפתח והערך המתאים:

V לשים (מקש K, ערך V);

כאשר ערך נוסף למפה מתחת למפתח, ה- hashCode () API של אובייקט המפתח נקרא כדי לאחזר את מה שמכונה ערך ה- hash הראשוני.

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

מחלקה ציבורית MyKey {מזהה פרטי פרטי; @Override int hashCode () {System.out.println ("קורא ל- hashCode ()"); החזר מזהה; } // קונסטרוקטור, סטרים וגטרים}

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

@Test ציבורי בטל כאשרHashCodeIsCalledOnPut_thenCorrect () {MyKey מפתח = MyKey חדש (1); מפת מפה = HashMap חדש (); map.put (מפתח, "val"); }

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

קורא ל- hashCode ()

לאחר מכן, בְּלִיל() API של מפת החשיש נקרא באופן פנימי כדי לחשב את ערך הגיבוב הסופי באמצעות ערך הגיבוב הראשוני.

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

ה בְּלִיל פונקציה של מפת גיבוב נראה ככה:

hash סופי int hash (מפתח Object) {int h; להחזיר (מפתח == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); }

מה שעלינו לציין כאן הוא רק השימוש בקוד ה- hash מאובייקט המפתח לחישוב ערך hash סופי.

תוך כדי לָשִׂים פונקציה, ערך החשיש הסופי משמש כך:

הצבת V ציבורית (מפתח K, ערך V) {להחזיר putVal (hash (מפתח), מפתח, ערך, שקר, נכון); }

שימו לב כי פנימי putVal הפונקציה נקראת וניתנת לערך ה- hash הסופי כפרמטר הראשון.

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

הסיבה היא ש מפות hash מאחסנות הן מפתח והן ערך במיקום הדלי כ- מפה. כניסה לְהִתְנַגֵד.

כפי שנדון קודם, כל ממשקי המסגרת של אוספי Java מתרחבים אוסף ממשק אבל מַפָּה לא. השווה את הכרזת ממשק המפה שראינו קודם לזו של מַעֲרֶכֶת מִמְשָׁק:

ממשק ציבורי סט מרחיב את האוסף

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

אז השיטות הגנריות של אוסף ממשק כגון לְהוֹסִיף, toArray לא הגיוני כשמדובר מַפָּה.

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

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

@Test public void givenNullKeyAndVal_whenAccepts_thenCorrect () {Map map = HashMap חדש (); map.put (null, null); }

כאשר נתקל מפתח אפס במהלך a לָשִׂים פעולה, זה מוקצה באופן אוטומטי ערך hash סופי של 0כלומר, הוא הופך להיות האלמנט הראשון במערך הבסיסי.

פירוש הדבר גם שכאשר המפתח אפס, אין פעולת גיבוב ולכן, hashCode API של המפתח אינו מופעל, ובסופו של דבר נמנע מחריג של מצביע אפס.

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

@Test הציבור בטל שניתןExistingKey_whenPutReturnsPrevValue_thenCorrect () {Map map = חדש HashMap (); map.put ("key1", "val1"); מחרוזת rtnVal = map.put ("key1", "val2"); assertEquals ("val1", rtnVal); }

אחרת, הוא חוזר ריק:

@Test public void givenNewKey_whenPutReturnsNull_thenCorrect () {Map map = HashMap חדש (); מחרוזת rtnVal = map.put ("key1", "val1"); assertNull (rtnVal); }

מתי לָשִׂים מחזיר null, זה יכול גם להיות שהערך הקודם המשויך למפתח הוא null, ולאו דווקא שמדובר במיפוי ערך מפתח חדש:

@Test public void givenNullVal_whenPutReturnsNull_thenCorrect () {Map map = חדש HashMap (); מחרוזת rtnVal = map.put ("key1", null); assertNull (rtnVal); }

ה containKey ניתן להשתמש ב- API כדי להבחין בין תרחישים כאלה כפי שנראה בסעיף המשנה הבא.

3. ה לקבל ממשק API

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

@ מבחן ציבורי בטל כאשר GetWorks_thenCorrect () {Map map = HashMap חדש (); map.put ("מפתח", "val"); מחרוזת val = map.get ("מפתח"); assertEquals ("val", val); }

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

@ מבחן ציבורי בטל כאשר HashCodeIsCalledOnGet_thenCorrect () {מפתח מפתח = מפתח חדש (1); מפת מפה = HashMap חדש (); map.put (מפתח, "val"); map.get (מפתח); }

הפעם, hashCode ממשק API של MyKey נקרא פעמיים; פעם אחת ל לָשִׂים ופעם אחת לקבל:

קורא ל- hashCode () קורא ל- hashCode ()

ערך זה נשטף מחדש על ידי קריאה פנימית בְּלִיל() ממשק API לקבלת ערך החשיש הסופי.

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

אובייקט הערך המאוחסן באותו מיקום מאוחזר ואז מוחזר לפונקציית הקריאה.

כאשר הערך המוחזר הוא null, פירוש הדבר שאובייקט המפתח אינו משויך לערך כלשהו במפת הגיבוב:

@Test הציבור בטל givenUnmappedKey_whenGetReturnsNull_thenCorrect () {Map map = חדש HashMap (); מחרוזת rtnVal = map.get ("key1"); assertNull (rtnVal); }

או שזה יכול פשוט אומר שהמפתח ממופה במפורש למופע ריק:

@Test public void givenNullVal_whenRetrieves_thenCorrect () {Map map = HashMap חדש (); map.put ("מפתח", null); מחרוזת val = map.get ("מפתח"); assertNull (val); }

כדי להבחין בין שני התרחישים, נוכל להשתמש ב- containKey API, אליו אנו מעבירים את המפתח והוא מחזיר נכון אם ורק אם נוצרה מיפוי עבור המפתח שצוין במפת hash:

@Test הציבור בטל כאשרContainsDistinguishesNullValues_thenCorrect () {Map map = חדש HashMap (); מחרוזת val1 = map.get ("מפתח"); valPresent בוליאני = map.containsKey ("מפתח"); assertNull (val1); assertFalse (valPresent); map.put ("מפתח", null); מחרוזת val = map.get ("מפתח"); valPresent = map.containsKey ("מפתח"); assertNull (val); assertTrue (valPresent); }

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

4. תצוגות אוסף ב מפת גיבוב

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

@ מבחן ציבורי בטל givenHashMap_whenRetrievesKeyset_thenCorrect () {מפה מפה = HashMap חדש (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); הגדר מקשים = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contains ("שם")); assertTrue (keys.contains ("סוג")); }

הסט מגובה במפה עצמה. כך כל שינוי שנעשה בערכה משתקף במפה:

@Test public void givenKeySet_whenChangeReflectsInMap_thenCorrect () {Map map = חדש HashMap (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); assertEquals (2, map.size ()); הגדר מקשים = map.keySet (); keys.remove ("שם"); assertEquals (1, map.size ()); }

אנחנו יכולים גם להשיג א תצוגת אוסף של הערכים:

@ מבחן הריק ציבורי givenHashMap_whenRetrievesValues_thenCorrect () {Map map = HashMap new (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); ערכי אוסף = map.values ​​(); assertEquals (2, values.size ()); assertTrue (values.contains ("baeldung")); assertTrue (values.contains ("בלוג")); }

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

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

@ מבחן חלל ציבורי givenHashMap_whenRetrievesEntries_thenCorrect () {Map map = HashMap new (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); מַעֲרֶכֶת ערכים = map.entrySet (); assertEquals (2, entries.size ()); עבור (ערך ה ': ערכים)}

זכור כי מפת hash מכילה במיוחד אלמנטים לא מסודרים, ולכן אנו מניחים כל סדר בעת בדיקת המפתחות והערכים של הערכים ב- לכל אחד לוּלָאָה.

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

רק זכרו שה- איטרטורים לכל התצוגות הנ"ל הם כישלון מהיר.

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

@Test (צפוי = ConcurrentModificationException.class) חלל ציבורי givenIterator_whenFailsFastOnModification_thenCorrect () {Map map = HashMap חדש (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); הגדר מקשים = map.keySet (); Iterator it = keys.iterator (); map.remove ("סוג"); בעוד (it.hasNext ()) {מפתח מחרוזת = it.next (); }}

היחיד שינוי מבני מותר הוא לְהַסִיר פעולה המבוצעת באמצעות האיטרטור עצמו:

חלל ציבורי givenIterator_whenRemoveWorks_thenCorrect () {Map map = חדש HashMap (); map.put ("שם", "באלדונג"); map.put ("סוג", "בלוג"); הגדר מקשים = map.keySet (); Iterator it = keys.iterator (); בעוד (it.hasNext ()) {it.next (); it.remove (); } assertEquals (0, map.size ()); }

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

איטרציה על מפת חשיש מתרחשת במקרה הגרוע ביותר עַל) כאשר n הוא סכום הקיבולת שלו ומספר הערכים.

5. ביצועי HashMap

הביצועים של מפת hash מושפעים משני פרמטרים: קיבולת ראשונית ו פקטור עומס. הקיבולת היא מספר הדליים או אורך המערך הבסיסי והקיבולת הראשונית היא פשוט הקיבולת במהלך היצירה.

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

קיבולת ההתחלה המוגדרת כברירת מחדל היא 16 וגורם העומס המוגדר כברירת מחדל הוא 0.75. אנו יכולים ליצור מפת hash עם ערכים מותאמים אישית עבור קיבולת ראשונית ו- LF:

מפה hashMapWithCapacity = HashMap חדש (32); מפה hashMapWithCapacityAndLF = HashMap חדש (32, 0.5f);

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

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

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

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

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

א יכולת התחלתית נמוכה טובה לכמה ערכים עם איטרציה רבה.

6. התנגשויות ב מפת גיבוב

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

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

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

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

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

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

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

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

מחלקה ציבורית MyKey {שם מחרוזת פרטי; מזהה פרטי פרטי; MyKey ציבורי (מזהה int, שם מחרוזת) {this.id = id; this.name = שם; } // getters וקובעים סטנדרטיים @Override public int hashCode () {System.out.println ("קורא ל- hashCode ()"); החזר מזהה; } // עקיפת toString לרישום יפה של @Override בוליאני ציבורי שווה (אובייקט obj) {System.out.println ("קריאה שווה () למפתח:" + obj); // יישום שנוצר}}

שימו לב איך אנחנו פשוט מחזירים את תְעוּדַת זֶהוּת תכונה כקוד החשיש - וכך לאלץ התנגשות להתרחש.

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

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

@Test הציבור בטל כאשר CallEqualsOnCollision_thenCorrect () {HashMap map = HashMap חדש (); MyKey k1 = MyKey חדש (1, "firstKey"); MyKey k2 = MyKey חדש (2, "secondKey"); MyKey k3 = MyKey חדש (2, "thirdKey"); System.out.println ("ערך אחסון ל- k1"); map.put (k1, "firstValue"); System.out.println ("ערך אחסון ל- k2"); map.put (k2, "secondValue"); System.out.println ("ערך אחסון ל- k3"); map.put (k3, "thirdValue"); System.out.println ("אחזור ערך עבור k1"); מחרוזת v1 = map.get (k1); System.out.println ("אחזור ערך עבור k2"); מחרוזת v2 = map.get (k2); System.out.println ("אחזור ערך עבור k3"); מחרוזת v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("thirdValue", v3); }

במבחן הנ"ל אנו יוצרים שלושה מקשים שונים - לאחד יש ייחודי תְעוּדַת זֶהוּת ולשניים האחרים אותו הדבר תְעוּדַת זֶהוּת. מאז אנחנו משתמשים תְעוּדַת זֶהוּת כערך החשיש הראשוני, בהחלט תהיה התנגשות במהלך אחסון ושליפה של נתונים באמצעות מפתחות אלה.

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

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

ערך אחסון עבור k1 חיוג ל- hashCode () ערך אחסון עבור k2 שיחת hashCode () ערך אחסון ל- k3 שיחת hashCode () שיחה שווה () למפתח: MyKey [שם = secondKey, id = 2] אחזור ערך עבור k1 קורא hashCode () ערך עבור k2 קריאה ל- hashCode () אחזור ערך ל- k3 קריאה ל- hashCode () קריאה שווה () למפתח: MyKey [name = secondKey, id = 2]

שימו לב שבמהלך פעולות האחסון, k1 ו k2 אווירה בהצלחה לערכים שלהם באמצעות קוד ה- Hash בלבד.

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

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

כמו כן, במהלך האחזור, k3 ו k2 היו שווים-השוואה לזיהוי המפתח הנכון שאת ערךו יש לאחזר.

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

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

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

7. מסקנה

במאמר זה, בדקנו מפת גיבוב יישום Java מַפָּה מִמְשָׁק.

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