تحليل مفصل لفئة HashMap

قبل الانتقال إلى مناقشة تفصيلية للفصل، دعونا نركز على المفاهيم الأساسية المرتبطة بجداول التجزئة. لن تناقش هذه المقالة طرق العمل مع تعيين التجزئة. سيتم فقط مناقشة عمليات الإدراج والبحث والحذف بشكل واضح وبالتفصيل. أعتقد أنه لن يكون من الصعب قراءة وصف الطرق المتاحة لـ HashMap من نفس Schildt. ربما سأكتب في المستقبل مقالًا آخر مخصصًا لمثل هذه الأساليب، لكن هذا موضع شك في الوقت الحالي. بالمقارنة مع Java 7، خضعت فئة HashMap في Java 8 لتغييرات كبيرة (+1000 سطر من التعليمات البرمجية). يمكنك أن تقرأ عن التنفيذ في Java 7 هنا (لكنه لم يعد ذا صلة): جدول التجزئة عبارة عن بنية بيانات تنفذ واجهة المصفوفة النقابية (نموذج أو إدخال مجردة لقيمة المفتاح)، والتي توفر إدراجًا وبحثًا سريعًا للغاية: بغض النظر يتم إجراء عمليات الإدراج والبحث عن العناصر الرقمية (وأحيانًا الحذف) في وقت قريب من الثابت - O(1). في الأساس، هذه مصفوفة عادية، حيث يعتمد موقع العنصر على قيمة العنصر نفسه. يتم تحديد العلاقة بين قيمة العنصر وموضعه في جدول التجزئة بواسطة دالة التجزئة. تأخذ دالة التجزئة جزءًا من البيانات المدخلة، والتي نسميها مفتاحًا ، وكمخرجات تنتج عددًا صحيحًا يعرف باسم قيمة التجزئة (أو رمز التجزئة) . تقوم قيمة التجزئة بعد ذلك بربط مفتاحنا بفهرس جدول تجزئة محدد. بالنسبة للعمليات الأساسية: الإدراج والبحث والحذف، نستخدم نفس وظيفة التجزئة، لذلك يتم تنفيذ هذه العمليات بسرعة كبيرة. لهذا السبب، من المهم أن تتصرف وظيفة التجزئة بشكل متسق وتخرج نفس الفهرس لنفس بيانات الإدخال. تجدر الإشارة إلى أن رمز التجزئة الناتج يمكن أن يكون ذا قيمة رقمية ضخمة، والمصفوفة الأصلية مصممة بشكل مشروط لـ 16 عنصرًا فقط. لماذا لا يتم إنشاء مصفوفة تحتوي على مليار عنصر لإضافة عشرة فقط؟ لذلك، يجب علينا بطريقة أو بأخرى تحويل رمز التجزئة هذا إلى قيم من 0 إلى 15 (إذا كان حجم المصفوفة 16). ولهذا، يتم استخدام تحويلات إضافية. لذلك نقوم بإنشاء فهرس لتقليل حجم المصفوفة. على سبيل المثال، في HashMap قبل Java 8، تم استخدام هذه الطريقة الإضافية للعثور على الخلية المطلوبة:

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

كمدخل، تم أخذ رمز التجزئة الذي تم الحصول عليه نتيجة للعمل hashCode()وطول المصفوفة الداخلية (عدد الخلايا). وأعاد النتيجة "رمز التجزئة" -> "AND" -> (طول المصفوفة - 1). يرث الفصل HashMapمن الفصل AbstractMapوينفذ الواجهات التالية: Map, Cloneable, Serializable. الطريقة . هي المسؤولة عن وظيفة التجزئة في Java hashCode(). يُرجع التنفيذ الافتراضي hashCode()قيمة تسمى رمز تجزئة الهوية . حتى لو تم تجاوز فئة ما hashCode()، يمكنك دائمًا الحصول على تجزئة معرف الكائن عن طريق استدعاء System.identityHashCode(Object o). التنفيذ الافتراضي hashCode()في OpenJDK لا علاقة له بعنوان الذاكرة، كما يُعتقد أحيانًا. مزيد من التفاصيل هنا: habr في HashMap ، يتم تنفيذ جدول التجزئة بناءً على مصفوفة (أو بشكل أكثر دقة، ديناميكي، حيث يمكن توسيع الجدول) من القوائم المرتبطة بشكل فردي. في الأساس، نحصل على رمز التجزئة للمفتاح نتيجة للطريقة hashCode()، والتي يتم تعديلها بعد ذلك (كما سنرى لاحقًا)، وداخليًا، باستخدام طريقة إضافية، يتم توزيع القيم الناتجة على الخلايا المطلوبة. تسمى عناصر المصفوفة (الخلايا) أيضًا بالدلاء ، والتي تُستخدم لتخزين العقد الفردية. كل دلو عبارة عن مجموعة (قائمة أو شجرة). العقدة هي كائن من فئة متداخلة Node(أو TreeNodeفي بنية شجرة). في الواقع، يوجد داخل خلية المصفوفة LinkedListقائمة مرتبطة بشكل فردي فقط، أو شجرة ذات لون أحمر وأسود، والتي تكمن وراء تنفيذ فئة أخرى - TreeMap. لا ينشأ خيار الشجرة ذات اللون الأحمر والأسود كثيرًا (كيف وماذا وأين - أدناه)، ومن الصعب جدًا فهم هذا الهيكل، لذلك سيكون التركيز على عقدة من نوع العقدة. العقدة هي فئة متداخلة بداخلها HashMapتحتوي على الحقول التالية:

• final int hash— تجزئة العنصر الحالي، والتي نحصل عليها نتيجة تجزئة المفتاح؛
• final K key— مفتاح العنصر الحالي. هذا هو المكان الذي تتم فيه كتابة ما تحدده ككائن أول في الطريقة put()؛
• V value— قيمة العنصر الحالي. وما تحدده ككائن ثانٍ في الطريقة مكتوب هنا put()؛
• Node < K, V> next- الارتباط بالعقدة التالية داخل نفس السلة. القائمة متصلة، لذا فهي تحتاج إلى رابط ليس للعقدة التالية، إذا كان هناك واحد.

الآن دعونا نلقي نظرة على حقول فئة HashMap نفسها:

• transient Node < K, V> [] table- جدول التجزئة نفسه، الذي يتم تنفيذه على أساس مصفوفة، لتخزين أزواج القيمة الرئيسية في شكل عقد. هذا هو المكان الذي يتم فيه تخزين عقدنا؛
• transient int size- عدد أزواج القيمة الرئيسية؛
• int threshold— الحد الأقصى لعدد العناصر، والذي عند الوصول إليه يتضاعف حجم جدول التجزئة. يتم حسابها باستخدام الصيغة (السعة * عامل التحميل)؛
• 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- أقصى سعة ممكنة لجدول التجزئة (حوالي 1 مليار)؛
• 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()— إنشاء عرض تجزئة بشكل افتراضي: من حيث الحجم (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. يتم حساب قيمة التجزئة لمفتاح الكائن الذي تم إدخاله. يتم حساب تجزئة المفتاح بطريقة 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. نظرًا لأنه نتيجة للتحقق، أصبحنا صحيحين (لا توجد عناصر في المجموعة)، سيتم إنشاء كائن عقدة يحتوي على الحقول التالية:

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

      ستتم إضافة كائن العقدة الذي تم إنشاؤه إلى المجموعة الموجودة ضمن الفهرس [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()) ستكمل عملها.

      ويمكن تمثيل النتيجة بيانيا على النحو التالي:

      بشكل عام، هذا هو ما تبدو عليه إضافة عقدة (زوج قيمة المفتاح) إلى جدول التجزئة إذا كانت المجموعة المطلوبة فارغة . الآن دعونا نحاول إضافة عنصر يؤدي إلى الاصطدام (عندما يكون هناك أكثر من عنصر في مجموعة واحدة).

القليل عن الاصطدامات يُطلق على الموقف عندما تنتهي المفاتيح المختلفة في نفس المجموعة (حتى مع وجود تجزئات مختلفة) اسم الاصطدام أو الاصطدام. حتى لو كان جدول التجزئة أكبر من مجموعة البيانات وتم اختيار وظيفة تجزئة جيدة، فإن هذا لا يضمن عدم حدوث تصادمات. وتقتصر قيمة التجزئة على نطاق قيم int (حوالي 4 مليارات). يجب أيضًا كتابة القيمة الجديدة الناتجة في مكان ما، ولهذا تحتاج إلى تحديد مكان كتابتها بالضبط. وهذا ما يسمى حل الصراع. هناك نهجان:

• طريقة التسلسل أو التسلسل الخارجي (يتم تنفيذها في HashMap) - أي. تحتوي الخلية بالفعل على قائمة (سلسلة). وقد تحتوي القائمة بالفعل على عدة قيم (ليس بالضرورة بنفس رمز التجزئة).
• طريقة الفحص الخطي أو طريقة العنونة المفتوحة (المطبقة في IdentityHashMap) - تتكون من البحث عن الخلية الفارغة الأولى بعد الخلية المشار إليها بواسطة وظيفة التجزئة؛

يمكنك أن تقرأ عن الاصطدامات هنا: انقر

1. باستخدام هذه الطريقة، put()سنضيف زوجًا آخر من المفاتيح والقيمة إلى تعيين التجزئة:

   map.put("BLAKE", 10);

2. نقوم بحساب "التجزئة الأولية" – 63281361. نقوم بتعديلها ونتيجة لذلك نحصل على رمز التجزئة النهائي – 63281940.

3. نظرًا لأن التحقق الأول من "الفراغ" سيعيد الآن خطأ (ليست هناك حاجة لإنشاء جدول)، فإننا نحسب على الفور فهرس الدلو الذي سيتم وضع الكائن فيه:

   
   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()لزيادة حجم جدول التجزئة وإعادة توزيع العناصر. 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 مجموعة في جدول التجزئة، وقد تراكمت كل هذه العناصر في مجموعة واحدة. من الناحية الهيكلية، ستبدو هذه المجموعة كما يلي (يتم فرز العناصر حسب رمز التجزئة): نوع CCHD: عرض داخل الدلو: استرجاع العناصر (استرجاع القيمة عن طريق المفتاح) فيما يتعلق بعملية الإضافة، فهي بسيطة للغاية. يمكن كتابة الخوارزمية (عندما تكون هناك قائمة مرتبطة في المجموعة) على النحو التالي:

1. حساب رمز التجزئة للمفتاح.
2. احسب مؤشر الدلو.
3. انتقل إلى الفهرس وقارن مفتاح العنصر الأول بالقيمة الموجودة. إذا كانا متساويين، قم بإرجاع القيمة، وإلا تحقق من العنصر التالي، إذا كان موجودًا.
4. إذا كان كائن العقدة التالي فارغًا، فسيتم إرجاعه فارغًا.
5. إذا لم يكن كائن العقدة التالي فارغًا، فانتقل إليه وكرر الخطوات الثلاث الأولى حتى يتم العثور على العنصر أو يصبح كائن العقدة التالي خاليًا.

باستخدام الطريقة get()نحصل على قيمة المفتاح "KING":

map.get("KING");

في الداخل، تسمى الطريقة getNode(int hash, Object key)، والتي يتم تمرير المفتاح نفسه ("KING") والتجزئة الخاصة به (2306996)، والتي يتم حسابها مسبقًا بنفس الطريقة التي يتم بها أثناء العملية put().

1. نحن نفحص:

   1. هل يوجد جدول تجزئة حتى:(tab = table) != null

      اسمحوا لي أن أذكرك أنه عند إنشاء HashMap، لا يتم إنشاء مصفوفة للجدول في المُنشئ؛ يحدث هذا لاحقًا في الطريقة resize()، والتي يتم استدعاؤها دائمًا عند إضافة العنصر الأول إلى جدول التجزئة. لذلك، إذا لم تتم إضافة أي عناصر إلى HashMap، فلن يكون هناك ببساطة مصفوفة داخلية لتخزين العناصر.

   2. إذا كان التعبير السابق صحيحًا، فستحتاج إلى التأكد من أن طول المصفوفة الداخلية أكبر من 0:(n = tab.length) > 0;

   3. إذا كان التعبير السابق أيضًا صحيحًا، فانتقل إلى المجموعة الموجودة في الفهرس (في حالتنا 4)، والتي تم حسابها مسبقًا، وتحقق من وجود العناصر:

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

   4. نقوم بمقارنة المفتاح الذي نبحث عنه مع مفتاح العنصر الأول في القائمة داخل المجموعة، لأنه في معظم المجموعات سيكون هناك (وليس في كل مكان لدينا تصادمات) عنصر واحد فقط (حالتنا). كما في حالة الطريقة put()، تتم مقارنة التجزئات، وإذا تطابقت، تتم مقارنة المفاتيح حسب المرجع، وعندها فقط بواسطة 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)، قم بإرجاع هذه العقدة. إذا كانت العقد الفرعية اليسرى أو اليمنى فارغة، فإننا نقارن المفاتيح أيضًا باستخدام CompareTo (إذا كانت المفاتيح تنفذ الواجهة Comparable)، وإلا فإننا نقوم بإجراء بحث متكرر عبر الشجرة (الشجرة الفرعية اليمنى أو اليسرى) حتى يتم العثور على تطابق.

إزالة الكائنات من HashMap نظرًا لنفاد المساحة في المقالة، سأصف بإيجاز كيفية حدوث الحذف عن طريق المفتاح. الخوارزمية متشابهة جدًا:

• انتقل إلى الجرافة المطلوبة (مرة أخرى، يتم حسابها مسبقًا)؛

• إذا كان هناك كائن واحد فقط في المجموعة (نتحقق من مؤشره الفارغ) فإننا نقارن التجزئات والروابط equals(إذا كانت التجزئات غير متساوية فجأة). العثور على المباراة؟ عظيم، هذا هو مفتاحنا - احذفه (=خالي) وأعد قيمة هذا المفتاح.

• إذا كان هناك أكثر من عنصر واحد في المجموعة، فإننا نتحقق من كل عنصر في حلقة حتى نجد العنصر أو نصل إلى نهاية القائمة.

• إذا لم يتم العثور على العنصر، نعود فارغة.

في حالة الشجرة، يوجد تنفيذ صعب إلى حد ما، ومن الأفضل عدم معرفته والنوم بشكل سليم (يشير وصف الطريقة إلى أن التنفيذ أكثر تعقيدًا من عملية الحذف العادية باللون الأحمر والأسود شجرة). علاوة على ذلك، عند الحذف، يمكن أن يعود عدد العقد في مجموعة واحدة إلى 6، ثم سيتم إعادة بناء الشجرة مرة أخرى في القائمة المرتبطة. إذا لم تكن مطورًا يتمتع بسنوات عديدة من الخبرة، فليس من الضروري على الإطلاق معرفة هذا وفهمه (وببساطة ليس ضروريًا).