כיצד HashMaps של Java עובדים – הסברים על מנגנונים פנימיים

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

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

מהו HashMap ב-Java?

HashMap מממש את הממשק Map, שהוא חלק ממסגרת האוספים של Java. הוא מבוסס על הקונספט של גיבוב.

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

פעולות נפוצות

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

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

הוספה

• שיטה זו מוסיפה זוג מפתח-ערך חדש ל-HashMap.

• מסדר ההכנסה של זוגות המפתח-ערך אינו נשמר.

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

• ניתן להכניס רק מפתח נול מינוס אחד ל־HashMap, אך ניתן להיות מספר ערכים נול מינוס.

החתימה של השיטה עבור הפעולה הזו מופיעה להלן, ולאחריה דוגמה:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

בקוד למעלה, יש לנו דוגמה של מפתח מסוג String וערך מסוג Integer שנוספים ל־HashMap.

השליפה:

• משיג את הערך המקושר עם המפתח הנתון.

• מחזיר null אם המפתח לא קיים ב־HashMap.

החתימה של השיטה עבור הפעולה הזו מופיעה להלן, ולאחריה דוגמה:

public V get(Object key)

Integer value = map.get("apple"); // מחזיר 1

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

פעולות נפוצות נ

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

• containsKey: בדיקה אם מפתח ספציפי נמצא בHashMap.

• containsValue: בדיקה אם הערך הספציפי נמצא בHashMap.

מבנה פנימי של HashMap

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

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

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

מדובר בשדה הבאים במבנה המוסדה Node:

• hash: מתייחסת לhashCode של המפתח.

• key: מתייחסת למפתח של הפעמון.

• value: מתייחסת לערך הקשור במפתח.

• next: פועל כהפניה לשורש הבא.

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

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

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

בואו ננסה עכשיו להבין איך הפעולות הבסיסיות, put ו-get, פועלות ב- HashMap.

פונקציית האש

בזמן ההכנסה (`put`) של זוג מפתח-ערך, ה `HashMap` ראשית מחשבת את הקוד ההאש של המפתח. אחר כך, הפונקציה הקדומה למפתח מחשבת מספר אינטגרלי עבור המפתח. מושגים יכולים להשתמש בשיטת ההאש של המושגים (`hashCode`) של המושג `Object` או לשנות את השיטה הזו ולספק את הייצוג המקורי שלהם. (קראו על הבריט האש הזה כאן). אחר כך, הקוד ההאש מועבר בשימוש בפעולה הביטיסית XOR (eXclusive OR) עם 16 הביטים העליונים שלו (h >> 16) כדי להשיג התפלגה יותר אחידה.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

הפעולה XOR היא פעולה ביטותית שמשווה שני ביטים, ומקבלת 1 אם הביטים שונים ו0 אם הם אותה. בהקשר הזה, ביצוע פעולת הביטים XOR בין קוד ההאש ו16 הביטים העליונים שלו (שמקבלים בעזרת משנה ימינה לשמאל לא מוסקבת >>>) עוזרת לערבב את הביטים, להביא לקוד ההאש שלו להתפלגה יותר אחידה.

מעלה, אתם יכולים לראות את שיטת ההאש הסטטית של המושג `HashMap`.

חישוב המפתח

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

int index = (n - 1) & hash;

כאן, אנחנו מחשבים את המפתח בו n הוא אורכת הכיס המייצג.

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

• הרשמה/קישור: כל כיס במערך הוא רשת ערים של ענינים. אם מפתח קיים כבר במקום מסויים ומפתח נוסף מועבר לאותה מידה, הוא מוסף לרשת.

• עילוי/עירומה: אם מספר הענינים עובר מספר מסויים גבוה, הרשת הזו מועברת לעץ (זה נובע ב-Java 8).

static final int TREEIFY_THRESHOLD = 8;

זוהי המפתח שקובעת את העילוי.

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

הפעילויות החיבור (get) וההסרה (remove) עובדות דומה לפעילות ההכנסה (put). כך זה עובד:

• ההבאה (get): מחשב את הקוד המפתח בעזרת הפונקציית האש ->

• השימוש בפונקציה remove: מחשבת את הקוד ההאש בעזרת הפונקציה המיוחדת לקוד -> מחשבת את המפת בעזרת הקוד ההאש -> מסירה את הנודע מהרשימה או העץ.

מערכת הזמן

הפעלויות הבסיסיות של HashMap, כמו put, get ו remove, מעניקות בד "" כ ביצועים בזמן קביע של O(1), מניחה שהמפתרמים מופץים באופן אחיד. במקרים בהם יש פציעה גרעינית בהפצת המפתרמים וקוליסיונים רבים, הפעלויות אלה עשויות להדלק למערכת זמן linear O(n).

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

הסינכרון

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

בכדי למנוע זאת, תוכלו ליצור אינסטנציאשן של ߛתוך שימוש בשיטת Collections.synchronizedMap.

סיכוי

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