كيف يعمل HashMap في جافا

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

1. الجواب الوحيد الممكن.
2. ما هو التجزئة.
3. قليلا عن الفصل Entry.
4. ماذا يكون ال put().
5. كيف تعمل الطريقة get().
6. ملحوظات

الجواب الوحيد الممكن

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

ما هو التجزئة

التجزئة في أبسط أشكالها هي طريقة لتحويل أي متغير/كائن إلى رمز فريد بعد تطبيق أي صيغة/خوارزمية على خصائصه. يجب أن تتبع دالة التجزئة الحقيقية القاعدة التالية: يجب أن تقوم دالة التجزئة بإرجاع نفس رمز التجزئة كلما تم تطبيقه على نفس الكائنات أو كائنات متساوية. بمعنى آخر، يجب أن يُرجع كائنان متطابقان نفس رموز التجزئة بدورها. يمكنك قراءة المزيد عن هذا هنا: العمل مع طريقة 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)، يتم وضع القيمة في الجدول عند الموضع صفر لأن رمز التجزئة للقيمة هو null.это – всегда 0


• في الخطوة التالية، يتم حساب قيمة التجزئة باستخدام رمز التجزئة للمفتاح الذي تم الحصول عليه عن طريق استدعاء الطريقة hashCode(). يتم استخدام قيمة التجزئة هذه لحساب الموضع في المصفوفة حيث سيتم وضع الكائن Entry. افترض مصممو JDK أن الوظيفة المكتوبة بشكل سيئ hashCode()يمكن أن تُرجع قيمة تجزئة مرتفعة جدًا أو منخفضة جدًا. لحل هذه المشكلة، قدموا 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على رموز تجزئة متشابهة، لكن الطريقة 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
• رمز التجزئة للمفاتيح ذات القيمة nullهو دائمًا 0. وسيتم دائمًا تخزين مثل هذا الكائن Entryفي الموضع الصفري للمصفوفة.

آمل أن أكون قد نقلت أفكاري بشكل صحيح في هذا المقال. إذا وجدت أخطاء أو لديك أسئلة، يرجى تركها في التعليقات. تعلم سعيد!