ניתוח מפורט של כיתת HashMap

לפני שנעבור לדיון מפורט בכיתה, בואו נתמקד במושגים הבסיסיים הקשורים לטבלאות חשיש. מאמר זה לא ידון בשיטות לעבודה עם מיפוי hash. רק פעולות ההכנסה, החיפוש והמחיקה יידונו בצורה ברורה ומפורטת. אני חושב שלא יהיה קשה לקרוא את התיאור של השיטות הזמינות עבור HashMap מאותה שילדט. אולי בעתיד אכתוב מאמר נוסף שיוקדש לשיטות כאלה, אבל לעת עתה זה בסימן שאלה. בהשוואה ל-Java 7, מחלקת HashMap ב-Java 8 עברה שינויים משמעותיים (+1000 שורות קוד). על ההטמעה ב-Java 7 תוכלו לקרוא כאן (אך כבר לא רלוונטי): habr טבלת hash היא מבנה נתונים המיישם את ממשק המערך האסוציאטיבי (מודל או ערך מופשט או ערך מפתח), המספק הכנסה וחיפוש מהירים מאוד: ללא קשר של רכיבי המספר הכנסה וחיפוש (ולפעמים מחיקה) מתבצעים בזמן הקרוב לקבוע - O(1). בעיקרו של דבר, זהו מערך רגיל, שבו המיקום של האלמנט תלוי בערך האלמנט עצמו. הקשר בין הערך של אלמנט לבין מיקומו בטבלת הגיבוב מוגדר על ידי פונקציית hash. פונקציית hash לוקחת נתון קלט, שאנו קוראים לו key , וכפלט היא מייצרת מספר שלם המכונה ערך hash (או קוד hash) . ערך ה-hash מקשר את המפתח שלנו לאינדקס טבלת גיבוב ספציפי. עבור הפעולות הבסיסיות: הכנסה, חיפוש ומחיקה, אנו משתמשים באותה פונקציית Hash, כך שפעולות אלו מבוצעות די מהר. מסיבה זו, חשוב שפונקציית ה-hash תתנהג באופן עקבי ותוציא את אותו אינדקס עבור אותם נתוני קלט. ראוי לציין שקוד ה-hash המתקבל יכול להיות ערך מספרי עצום, והמערך המקורי מתוכנן על תנאי ל-16 אלמנטים בלבד. למה לא ליצור מערך עם מיליארד אלמנטים כדי להוסיף רק עשרה? לכן, עלינו איכשהו להפוך את קוד ה-hash הזה לערכים מ-0 עד 15 (אם גודל המערך הוא 16). ולשם כך נעשה שימוש בטרנספורמציות נוספות. אז אנחנו יוצרים אינדקס כדי למזער את גודל המערך. לדוגמה, ב-HashMap לפני Java 8, נעשה שימוש בשיטה נוספת זו כדי למצוא את התא הרצוי:

static int indexFor(int h, int length) {
        return h & (length-1);
}

כקלט, הוא לקח את קוד ה-hash שהתקבל כתוצאה מהעבודה hashCode()ואת אורך המערך הפנימי (מספר התאים). וזה החזיר את התוצאה "קוד hash" -> "AND" -> (אורך מערך - 1). המחלקה HashMapיורשת מהמחלקה AbstractMapומיישמת את הממשקים הבאים: Map, Cloneable, Serializable. ה-.method אחראי על פונקציית ה-hash ב-Java hashCode(). יישום ברירת המחדל hashCode()מחזיר ערך שנקרא קוד ה-hash identity . גם אם מחלקה עוקפת את hashCode(), תמיד תוכל לקבל את ה-hash של ה-ID של האובייקט על ידי קריאה ל- System.identityHashCode(Object o). למימוש ברירת המחדל hashCode()ב-OpenJDK אין שום קשר לכתובת הזיכרון, כפי שחושבים לפעמים. פרטים נוספים כאן: habr ב-HashMap , טבלת הגיבוב מיושמת על בסיס מערך (או ליתר דיוק, דינמי, מכיוון שהטבלה יכולה להתרחב) של רשימות מקושרות בודדות. בעיקרו של דבר, אנו משיגים את קוד ה-hash של המפתח כתוצאה מהשיטה hashCode(), אשר לאחר מכן משתנה (כפי שנשקול בהמשך), ובפנים, באמצעות שיטה נוספת, הערכים המתקבלים מופצים לתאים הנדרשים. רכיבי מערך (תאים) נקראים גם דליים , המשמשים לאחסון צמתים בודדים. כל דלי הוא אוסף (רשימה או עץ). צומת הוא אובייקט של מחלקה מקוננת Node(או TreeNodeבמבנה עץ). למעשה, בתוך תא המערך שוכנת LinkedListרק רשימה מקושרת בודדת, או עץ אדום-שחור, העומד בבסיס היישום של מחלקה אחרת - TreeMap. האפשרות עם עץ אדום-שחור לא עולה כל כך הרבה (איך, מה ואיפה - למטה), ומבנה זה די קשה להבנה, ולכן הדגש יהיה על צומת מסוג Node. Node הוא מחלקה מקוננת HashMapשבתוכה יש את השדות הבאים:

• final int hash- ה-hash של האלמנט הנוכחי, שאנו מקבלים כתוצאה מה-hash של המפתח;
• final K key- המפתח של האלמנט הנוכחי. כאן נכתב מה שאתה מציין כאובייקט הראשון בשיטה put();
• V value- הערך של האלמנט הנוכחי. ומה שאתה מציין כאובייקט השני בשיטה כתוב כאן put();
• Node < K, V> next- קישור לצומת הבא בתוך אותו סל. הרשימה מחוברת, אז היא צריכה קישור לא לצומת הבא, אם יש כזה.

עכשיו בואו נסתכל על השדות של מחלקת HashMap עצמה:

• transient Node < K, V> [] table– טבלת הגיבוב עצמה, המיושמת על בסיס מערך, לאחסון צמדי מפתח-ערך בצורה של צמתים. כאן מאוחסנים הצמתים שלנו;
• transient int size- מספר זוגות מפתח-ערך;
• int threshold- המספר המרבי של אלמנטים, כאשר מגיעים אליו גודל טבלת הגיבוב מוכפל. מחושב באמצעות הנוסחה (קיבולת * loadFactor);
• final float loadFactor- פרמטר זה קובע באיזו דרגת עומס צריך טבלת הגיבוב הנוכחית כדי ליצור טבלת גיבוב חדשה, כלומר. ברגע שטבלת הגיבוב תהיה מלאה ב-75%, תיווצר טבלת גיבוב חדשה והאלמנטים הנוכחיים יועברו לתוכה (פעולה יקרה, שכן יש לשחזר את כל האלמנטים);
• transient Set< Map.Entry< K,V>> entrySet- מכיל קובץ שמור entrySet(), שאיתו נוכל לבצע איטרציה HashMap.

וקבועים:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4- קיבולת טבלת גיבוב ברירת מחדל (16);
• static final int MAXIMUM_CAPACITY = 1 << 30- הקיבולת המרבית האפשרית של טבלת הגיבוב (כמיליארד);
• static final float DEFAULT_LOAD_FACTOR = 0.75f- גורם עומס ברירת מחדל;
• static final int TREEIFY_THRESHOLD = 8הוא ה"סף" של מספר האלמנטים בדלי אחד, כאשר הרשימה המקושרת הפנימית תומר למבנה עץ (עץ אדום-שחור).
• static final int UNTREEIFY_THRESHOLD = 6- אם מספר האלמנטים בסל אחד יורד ל-6, אז יתרחש מעבר הפוך מעץ לרשימה מקושרת;
• static final int MIN_TREEIFY_CAPACITY = 64- הקיבולת המינימלית (מספר הדליים) של טבלת גיבוב שבה אפשרי מעבר למבנה עץ. הָהֵן. אם יש לפחות 64 דליים בטבלת הגיבוב ויש 8 אלמנטים או יותר בדלי אחד, אז יתרחש מעבר למבנה עץ.

בוני מחלקות:

1. public HashMap()- יוצר תצוגת hash כברירת מחדל: לפי נפח (capacity) = 16ועם מקדם עומס (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)- יוצר מיפוי גיבוב המאוחל על ידי האלמנטים של מיפוי נתון אחר עם הקיבולת הראשונית המספיקה כדי להכיל את האלמנטים של מיפוי אחר;
3. public HashMap(int initialCapacity)- יוצר מפת גיבוב עם קיבולת התחלתית נתונה. כדי ש-HashMap יפעל בצורה נכונה ונכונה, גודל המערך הפנימי חייב להיות בחזקת שתיים (כלומר 16, 64, 128 וכו');
4. public HashMap(int initialCapacity, float loadFactor)— יוצר מפת גיבוב עם הפרמטרים שצוינו: קיבולת התחלתית ומקדם עומס.

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

1. ערך הגיבוב של המפתח של האובייקט שהוזן מחושב. ה-hash המפתח מחושב על ידי שיטה static final int hash(Object key)שכבר ניגשת hashCode()לשיטת המפתח שאנו מכירים. hashCode()לשם כך, נעשה שימוש בשיטה שנדחתה או ביישום ברירת המחדל שלה. שינויים נוספים בשיטה hash():

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

   Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash

   где n – длина массива.

3. Создается an object Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Теперь к очень подробному примеру.

   1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

   2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

   3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

   4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

   5. במקביל, אנו מחשבים את אינדקס הדלי בו יונח החפץ שלנו ובודקים האם יש בו כבר אלמנטים. אנו מחשבים:

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4

      חשבון:

      
      if ((p = tab[i = (n - 1) & hash]) == null)

   6. מכיוון שכתוצאה מהבדיקה אנו מקבלים אמת (אין אלמנטים ב-bucket), יווצר אובייקט Node עם השדות הבאים:

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      אובייקט ה-Node שנוצר שלנו יתווסף לדלי תחת אינדקס [4]:

      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()היא שיטה שפשוט מחזירה אובייקט של המחלקה Node.

   7. לאחר ההוספה, תיעשה בדיקה כדי לראות אם מספר האלמנטים הנוכחי חורג מהפרמטר threshold:

      if (++size > threshold)
          resize();

      אם חורג, תיקרא שיטה resize()להגדלת גודל טבלת הגיבוב.

      בשלב זה, השיטה putVal()(ו, בהתאמה put()) תשלים את עבודתה.

      ניתן להציג את התוצאה בצורה גרפית באופן הבא:

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

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

• שרשור חיצוני או שיטת שרשור (מיושם ב-HashMap) - כלומר. התא למעשה מכיל רשימה (שרשרת). והרשימה עשויה כבר להכיל מספר ערכים (לא בהכרח עם אותו קוד hash).
• שיטת חיטוט ליניארית או כתובת פתוחה (מיושם ב-IdentityHashMap) - מורכבת מחיפוש התא הריק הראשון אחרי זה שמצביע עליו פונקציית ה-hash;

על התנגשויות תוכלו לקרוא כאן: קליק

1. באמצעות השיטה, put()נוסיף זוג מפתח-ערך נוסף למיפוי ה-hash:

   map.put("BLAKE", 10);

2. אנו מחשבים את ה-"hash ראשוני" - 63281361. אנו משנים אותו וכתוצאה מכך נקבל את קוד ה-hash הסופי - 63281940.

3. מכיוון שהבדיקה הראשונה של "ריקות" תחזיר כעת false (אין צורך ליצור טבלה), אנו מיד מחשבים את האינדקס של הדלי שבו האובייקט שלנו ימוקם:

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4

4. הדלי באינדקס שצוין נבדק על נוכחותם של אלמנטים בו, ומכיוון שהתנאי if ((p = tab[i = (n - 1) & hash]) == null)לא מתקיים במקרה זה (יש כבר אלמנט בדלי), אז אנחנו הולכים לבלוק else.

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

   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:

   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }

   В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };

   Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

   Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))

   Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

   После добавления второго element наш an object HashMap графически выглядит так:

   В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

   • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
   • если ключи одинаковы, заменить текущее meaning новым.
   • иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

   for (int binCount = 0; ; ++binCount)

   До тех пор, пока их количество не станет равно or больше 7:

   binCount >= TREEIFY_THRESHOLD – 1

   В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

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

   בקצרה, מבלי להיכנס לפרטים על מבנה העץ האדום-שחור, קורה הדברים הבאים:

   1. האלמנט הראשון ברשימה כתוב כשורש העץ כולו (שחור):

      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }

   2. עבור אלמנטים אחרים:

      להפיץ אותם לשמאל או לימין בהתאם לערך הגיבוב:

      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;

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

   3. אם לשני אלמנטים יש את אותם גיבובים ולא ניתן להשוות אותם בשום דרך אחרת (הם לא מיישמים את הממשק Comparable), אנו קוטעים את בניית העץ וקוראים לשיטה tieBreakOrder(), אשר בתורה משתמשת בשיטה המקורית System.identityHashCode()כדי לחשב קוד חשיש ייחודי גלובלי .

      פרטים נוספים כאן: קישור למאמר

   4. אנו בודקים את רכיבי העץ (אובייקטים TreeNode) עד שנמצא אלמנט אפס בן (משמאל או ימין).

      if ((p = (dir <= 0) ? p.left : p.right) == null)

   5. הוסף צומת צאצא (משמאל או ימין בהתאם ל-dir):

      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;

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

      root = balanceInsertion(root, x);

      אתה יכול לקרוא על איזון ה-CCH כאן: habr

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

      moveRootToFront(tab, root)

      ניתן לראות בבירור כיצד בנוי עץ אדום-שחור ומאזן את עצמו כאן: הדמיה

זה הכל, באופן עקרוני, ובאמצעות דוגמה, נניח שאנחנו רוצים להוסיף את השמות הבאים כמפתחות: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. ונניח שיש לנו לפחות 64 דליים בטבלת האש, וכל האלמנטים האלה הצטברו בדלי אחד. מבחינה מבנית, הדלי הזה ייראה כך (האלמנטים ממוינים לפי קוד hash): סוג CCHD: מבט בתוך הדלי: אחזור אלמנטים (שליפת ערך לפי מפתח) לגבי פעולת ההוספה, זה די פשוט. ניתן לכתוב את האלגוריתם (כאשר יש רשימה מקושרת בדלי) כך:

1. חשב את קוד הגיבוב של המפתח.
2. חשב את מדד הדלי.
3. עברו על האינדקס והשוו את המפתח של האלמנט הראשון לערך הקיים. אם הם שווים, החזר את הערך, אחרת בדוק את האלמנט הבא, אם הוא קיים.
4. אם אובייקט ה-Node הבא הוא null, החזר null.
5. אם אובייקט ה-Node הבא אינו null, עבור אליו וחזור על שלושת השלבים הראשונים עד שהאלמנט נמצא או שאובייקט ה-Node הבא יהיה null.

באמצעות השיטה, get()אנו מקבלים את הערך עבור מפתח "KING":

map.get("KING");

בפנים, השיטה נקראת getNode(int hash, Object key), אליה מועברים המפתח עצמו ("KING") וה-hash שלו (2306996), אשר מחושב מראש באותו אופן כמו במהלך הפעולה put().

1. אנחנו בודקים:

   1. האם בכלל קיימת טבלת גיבוב:(tab = table) != null

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

   2. אם הביטוי הקודם מחזיר true, עליך לוודא שאורך המערך הפנימי גדול מ-0:(n = tab.length) > 0;

   3. אם גם הביטוי הקודם מחזיר נכון, עבור אל הדלי במדד (במקרה שלנו 4), שחושב בעבר, ובדקו את נוכחותם של אלמנטים:

      (first = tab[(n - 1) & hash]) != null)

   4. אנו משווים את המפתח שאנו מחפשים למפתח של האלמנט הראשון ברשימה בתוך הדלי, שכן ברוב הדליים יהיה (לא בכל מקום שיש לנו התנגשויות) רק אלמנט אחד (המקרה שלנו). כמו במקרה של השיטה put(), ה-hash מושווה, ואם הם תואמים, המפתחות מושווים לפי הפניה, ורק אז לפי equals().

      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))

      מכיוון שבמקרה שלנו, המפתח "KING" יקדים את המפתח "BLAKE" (בתוך רשימה מקושרת, מוסיפים אלמנטים חדשים לסוף, ו-KING נוסף ראשון), נעצור בשלב זה ונחזיר את האובייקט הראשון של הקלידו Node למתודה get() ש"חוטפת" ממנו שדה עם הערך (100):

      return (e = getNode(hash(key), key)) == null ? null : e.value;

2. אם יש יותר מאלמנט אחד בתוך הדלי, אז:

   1. אם הדלי הוא רשימה מקושרת, אנו עוברים על הרשימה דרך כל אחד מהאלמנטים בלולאה do – whileעד שנמצא התאמה:

      do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      } while ((e = e.next) != null);

   2. אם הדלי הוא מבנה עץ, השיטה נקראת בנוסף getTreeNode(), אשר בתורה משתמשת בשיטה כדי למצוא את המפתח הדרוש find(). אנו מבצעים חיפוש עצים - השוואה בין הגיבובים ונקבע צומת השורש השמאלי או הימני לחיפוש. אם המפתחות שווים (על ידי הפניה או על ידי equals), החזר את הצומת הזה. אם צמתי הילד השמאלי או הימני הם null, אנו משווים בנוסף את המפתחות באמצעות compareTo (אם המפתחות מיישמים את הממשק Comparable), אחרת אנו מבצעים חיפוש רקורסיבי דרך העץ (תת-עץ ימני או שמאלי) עד שנמצא התאמה.

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

• ללכת לדלי הרצוי (שוב, זה מחושב מראש);

• אם יש רק אובייקט אחד ב-bucket (אנחנו בודקים את מצביע ה-null שלו) אנחנו משווים גיבוב, קישורים ו equals(אם פתאום הגיבובים לא שווים). מצאתם התאמה? מעולה, זה המפתח שלנו - מחק אותו (=null) והחזר את הערך של המפתח הזה.

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

• אם האלמנט לא נמצא, נחזיר null.

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