Java - HashMap Internals

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

Key Value הוא המבנה הבסיסי שעליו מבוסס ה HashMap. במקום לשמור פריטים ברשימה רגילה לפי אינדקס מספרי רגיל (כמו 0, 1, 2), אנחנו שומרים זוגות של מידע שבהם כל נתון מנוהל באמצעות מזהה ייחודי.

הצמד מורכב משני חלקים:

• Key: המזהה הייחודי שאיתו אנחנו ניגשים לשלוף או לשמור את הנתונים (למשל: תעודת זהות, כתובת אימייל או שם משתמש).

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

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

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

מבנה הנתונים הבסיסי מאחורי הקלעים

בבסיסו, HashMap מורכב ממערך של צמתים (Array of Nodes / Buckets). כל תא במערך הזה נקרא Bucket, ובתוכו נשמרים האובייקטים (Key Value).

כשאנחנו יוצרים HashMap, מוקצה ב Heap מערך ברירת מחדל (לרוב בגודל התחלתי של 16 תאים). לכל תא במערך יש אינדקס מספרי שנקבע על בסיס פונקציית גיבוב (Hash Function) של המפתח.

איך עובדות הפעולות המרכזיות?

פעולת ההכנסה put(K key, V value)

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

• חישוב Hash: ה JVM קורא למתודת hashCode של ה Key. כדי למנוע התנגשויות שנובעות ממימוש גרוע של hashCode, Java מפעילה פונקציית פיזור נוספת (Perturbation function) כדי לערבב את הביטים.
• מציאת אינדקס (Bucket Index): כדי לדעת באיזה תא במערך לשמור את הנתונים, המערכת מבצעת פעולת ביטוי בינארי: hash & (capacity - 1). פעולה זו ממפה את ה Hash בדיוק לטווח האינדקסים של המערך הקיים.
• בדיקת התנגשויות (Collision):
  • אם ה Bucket פנוי לחלוטין, נוצר צומת (Node) חדש והוא נשמר שם.
  • אם כבר קיים אובייקט באותו תא (כלומר, שני מפתחות שונים ייצרו בדיוק את אותו אינדקס במערך), תיווצר התנגשות.

איך הנתונים נשמרים באותו תא? (ההבדל בין גרסאות Java):

ב Java 7 ומטה:

הנתונים באותו תא אורגנו בתוך Linked List. כל צומת הצביע לצומת הבא אחריו. הבעיה הייתה שאם נוצר מצב קיצוני עם המון התנגשויות באותו תא, ה HashMap נאלץ לעבור אחד אחד על כל הרשימה (חיפוש לינארי), מה שהאט את הביצועים לזמן ריצה גרוע של O(n).

מ Java 8 ואילך:

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

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

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

פעולת השליפה get(K key)

• ה JVM מחשב מחדש את ה Hash של המפתח ומזהה את האינדקס במערך.
• הוא ניגש ל Bucket המתאים.
• אם יש שם רק אובייקט אחד, הוא משווה את המפתחות בעזרת מתודת equals(). אם יש התאמה, הוא מחזיר את הערך.
• אם יש מספר אובייקטים באותו Bucket (עקב התנגשות), הוא עובר עליהם אחד אחד ובודק באמצעות equals() עד שהוא מוצא את המפתח המבוקש.

האם תמיד חייבים לממש את המטודות hashCode() ו equals()?

מתי אין צורך לממש ידנית? כש key הוא מחלקה קיימת של Java

אם אנחנו משתמשים במחלקות סטנדרטיות של Java בתור key כמו String, Integer, Long, או Double לא צריכים לממש כלום.

מתי חובה לממש? כשה key הוא מחלקה מותאמת אישית שאנחנו כתבנו

אם אנחנו יוצרים מחלקה משלנו (למשל Employee, Product, UserId) ורוצים להשתמש באובייקטים ממנה בתור key ב HashMap (או כ value ב HashSet), אז ורק אז אנחנו חייבים לבצע override ולממש את שתי המתודות (hashCode ו equals).

למה? כי ברירת המחדל של Java למחלקות שאנחנו כותבים מבוססת על כתובת הזיכרון (Memory Address). אם ניצור שני אובייקטים נפרדים עם בדיוק אותו תוכן (למשל שני משתמשים עם ID 1), Java תתייחס אליהם כאל שתי ישויות זרות לחלוטין כי הם יושבים במקומות שונים ב Heap.

מימוש equals() בלבד (השארת hashCode מקורי)

אם נעשה override רק על equals כדי להשוות אובייקטים לפי התוכן העסקי שלהם (למשל לפי ID או אימייל), אבל נשאיר את ה hashCode המקורי של Java:

מה שקורה מאחורי הקלעים: ה hashCode המקורי מבוסס על כתובת הזיכרון (Memory Address) של האובייקט ב Heap. המשמעות היא ששני אובייקטים שונים לחלוטין בזיכרון, גם אם הם מכילים בדיוק את אותם נתונים בדיוק, יקבלו ערכי Hash שונים לחלוטין.

התוצאה ב HashMap:

• נכניס אובייקט key ל Map (map.put(key1, value);). הוא יישמר ב Bucket מסוים לפי ה hashCode שלו.
• ננסה לשלוף את ה value באמצעות אובייקט שני שזהה בתוכן שלו (map.get(key2);).
• ה HashMap יחשב ל key2 את ה hashCode שלו (ששונה מזה של key1 כי הם יושבים בכתובות זיכרון אחרות), יחפש ב Bucket הלא נכון, ויחזיר null. נרגיש כאילו הנתון "נעלם" מהזיכרון.

מימוש hashCode() בלבד (השארת equals מקורי)

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

מה שקורה מאחורי הקלעים: מתודת ה equals המקורית של Java משווה אך ורק את כתובת הזיכרון באמצעות האופרטור ==.

התוצאה ב HashMap:

• שני אובייקטים נפרדים בזיכרון (שזהים בתוכן העסקי שלהם) עשויים אמנם להגיע לאותו Bucket (בזכות ה hashCode המשותף).
• אולם, כאשר ה HashMap ינסה לאתר את ה key המדויק בתוך התא, הוא יפעיל את מתודת ה equals. מכיוון שלא כתבנו override עליה, היא תבצע השוואת כתובות זיכרון ותחזיר false.
• ה Map יתייחס אליהם כאל שני keys שונים לחלוטין, ויאפשר לנו להכניס כפילויות של keys שנראים לנו אותו הדבר.

דוגמא למימוש

import java.util.Objects;
import java.util.HashMap;
import java.util.Map;

class Employee {
    private int id;
    private String email;

    public Employee(int id, String email) {
        this.id = id;
        this.email = email;
    }

    // 1. Implementing equals to compare business equality based on id and email
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id == employee.id && Objects.equals(email, employee.email);
    }

    // 2. Implementing hashCode consistently using the exact same fields to maintain the contract
    @Override
    public int hashCode() {
        return Objects.hash(id, email);
    }
}

public class HashCodeEqualsDemo {
    public static void main(String[] args) {
        Map employeeRoles = new HashMap<>();

        Employee emp1 = new Employee(101, "alice@company.com");
        Employee emp2 = new Employee(101, "alice@company.com"); // Different object instance, but logically equal

        // Putting data into the map using emp1
        employeeRoles.put(emp1, "Software Engineer");

        // Retrieving data using emp2 (which is logically equal to emp1)
        // Because equals() and hashCode() are properly aligned, this will successfully return "Software Engineer"
        String role = employeeRoles.get(emp2);

        System.out.println("Employee Role: " + role); // Output: Software Engineer
    }
}