כיצד פועלת HashMap ב-Java

רובכם יסכימו שהיום HashMapהוא הנושא המועדף ביותר לדיון במהלך ראיונות. לפעמים היו לי דיונים דומים עם עמיתיי וזה מאוד עזר. עכשיו אני אקיים איתך דיון כזה. אני מניח שאם אתה מתעניין בחלק הפנימי והפעולה של HashMap, אז אתה כבר מכיר את היסודות של HashMap , אז אני אוותר על החלק הזה. אבל אם אתה חדש בזה, אני מציע לך לעבור לאתר Java Docs . לפני שנמשיך, אני ממליץ לך בחום לבדוק את המאמר הקודם שלי: עבודה עם hashCode ושיטת equals ב-Java. תוכן מאמר זה:

1. התשובה האפשרית היחידה.
2. מה זה האשינג.
3. קצת על הכיתה Entry.
4. מה עושה ה put().
5. איך השיטה עובדת get().
6. הערות

התשובה האפשרית היחידה

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

מה זה האשינג

Hashing בצורתו הפשוטה היא דרך להמיר כל משתנה/אובייקט לקוד ייחודי לאחר החלת כל נוסחה/אלגוריתם על המאפיינים שלו. פונקציית hash אמיתית חייבת לפעול לפי הכלל הבא: פונקציית hash חייבת להחזיר את אותו קוד hash בכל פעם שהיא מוחלת על אותם אובייקטים או שווים. במילים אחרות, שני אובייקטים זהים חייבים להחזיר את אותם קודי גיבוב בתורם. אתה יכול לקרוא עוד על זה כאן: עבודה עם hashCode ושיטת equals ב-Java

קצת על כיתת הכניסה

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

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

באופן טבעי, למחלקה Entryיש מפתח וערך המאוחסנים כתכונות. המפתח מסומן כ finalואנו רואים גם שני שדות נוספים: nextו hash. ננסה להבין את מטרת השדות הללו ככל שהמאמר יתקדם.

מה עושה שיטת Java put()?

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

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

עכשיו תסתכל על קוד יישום השיטה put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

בואו נבין את זה צעד אחר צעד:

• קודם כל בודקים אם המפתח קיים. אם המפתח אינו קיים ( null), הערך ממוקם בטבלה במיקום אפס מכיוון שקוד ה-hash עבור הערך הוא null, это – всегда 0.


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


• כעת הפונקציה נקראת indexFor(hash, table.length)לחשב את המיקום המדויק שבו האובייקט יוצב Entry.


• כאן מתחיל החלק העיקרי. כעת, בהתבסס על מה שאנו יודעים שלשני אובייקטים לא שווים יכולים להיות קודי גיבוב שווים, אנו שואלים את השאלה: האם שני אובייקטים שונים ימוקמו באותו מיקום במערך [דלי]? התשובה היא LinkedList. אם אתה זוכר, לכיתה Entryיש תכונה " next". תכונה זו תמיד מצביעה על האובייקט הבא בשרשרת. זו בדיוק ההתנהגות LinkedList.

אז, אובייקטים Entryמאוחסנים בטופס LinkedList. כאשר אובייקט Entryאמור להיות ממוקם במיקום מסוים, HashMap בודק אם יש כבר ערך במיקום זה. אם אין כניסה, אז האובייקט ממוקם במיקום זה. אם, לעומת זאת, יש כבר אובייקט במיקום זה, התכונה הבאה מסומנת. אם הוא חוזר nullוהאובייקט הנוכחי Entryהופך לקישור הבא ב- LinkedList. אם המשתנה הבא אינו null, ההליך חוזר על המשתנה הבא עד שהוא מוצא null. מה אם נשים אובייקט אחר עם ערך שונה אבל עם אותו מפתח כמו קודם? באופן הגיוני זה אמור לגרום להחלפת הערך הישן. איך זה קורה? באופן כללי, לאחר קביעת המיקום של אובייקט Entry, תוך כדי מעבר LinkedListלמיקום המחושב, HashMapהוא קורא לשיטת ההשוואה המפתח עבור כל אובייקט Entry. ייתכן שלכל Entryהאובייקטים הללו LinkedListיש קודי hash דומים, אבל השיטה equals()תבדוק אם יש דמיון אמיתי. זה יחליף רק את הערך בתוך ה- Entry. לפיכך, HashMap מבטיחה את הייחודיות של כל המפתחות.

כיצד פועלת שיטת Java get()?

כעת יש לנו מושג כיצד מאוחסנים צמדי מפתח-ערך ב- HashMap. השאלה הגדולה הבאה היא: מה קורה כאשר אובייקט מועבר מ-HashMap למתודה get()? כיצד נקבע ערכו של חפץ? אנחנו אמורים כבר לדעת את התשובה, כי לאופן שבו נקבעת הייחודיות של מפתח בשיטה put()יש אותו היגיון שהשיטה מיישמת get(). ברגע HashMapשהוא קובע את המפתח של האובייקט המועבר כארגומנט, הוא פשוט מחזיר את הערך של ה- Entry. אם לא נמצאו התאמות, השיטה get()תחזור null. בואו נסתכל על הקוד:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

הקוד למעלה דומה לשיטה put()עד לנקודה זו if (e.hash == hash && ((k = e.key) == key || key.equals(k))), לאחר מכן הוא פשוט מחזיר את הערך של האובייקט.

הערות

• מבנה הנתונים שיש לאחסן באובייקט Entryהוא מערך עם שם tableוסוג Entry.
• כל מיקום בודד במערך נקרא דלי מכיוון שהוא יכול להכיל את האלמנט הראשון LinkedListשל האובייקטים Entry.
• hashCode()המפתח נדרש כדי לחשב את מיקום האובייקט Entry.
• equals()המפתח משמש לבדיקת הייחודיות של המפתח במפה( map).
• hashCode()וערכים equals()אינם משמשים בשיטות get()וב- set().HashMap
• קוד ה-hash למפתחות עם ערך nullהוא תמיד 0. ואובייקט כזה Entryתמיד יישמר במיקום האפס של המערך.

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