HashMap الداخلية في جافا

[ملاحظة من مؤلف الترجمة] تمت الترجمة لاحتياجات المرء الخاصة ، ولكن إذا تبين أنها مفيدة لشخص ما ، فقد أصبح العالم على الأقل قليلاً ، ولكنه أفضل! المقالة الأصلية - العمل الداخلي لـ HashMap في Java

في هذه المقالة ، سنرى كيف تعمل طرق الحصول على المعلومات ووضعها في مجموعة HashMap داخليًا. ما العمليات التي يتم تنفيذها. كيف يحدث التجزئة. كيف يتم استرداد القيمة عن طريق المفتاح. كيف يتم تخزين أزواج القيمة الرئيسية؟

كما في المقالة السابقة ، تحتوي HashMap على مجموعة من العقدة ويمكن أن تمثل العقدة فئة تحتوي على الكائنات التالية:

1. Int - تجزئة
2. K هو المفتاح
3. V هي القيمة
4. العقدة - العنصر التالي

الآن سنرى كيف يعمل كل شيء. أولاً ، سنلقي نظرة على عملية التجزئة.

التجزئة

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

هنا أستخدم فئة المفاتيح الخاصة بي وبهذه الطريقة يمكنني تجاوز طريقة hashCode () لعرض البرامج النصية المختلفة. فئة My Key:

//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } } 

هنا ، ترجع طريقة hashCode () التي تم تجاوزها رمز ASCII للحرف الأول من السلسلة. وبالتالي ، إذا كانت الأحرف الأولى من السلسلة هي نفسها ، فستكون رموز التجزئة هي نفسها. لا تستخدم منطق مماثل في برامجك.

هذا الرمز هو لأغراض العرض التوضيحي فقط. نظرًا لأن HashCode يقبل مفتاحًا فارغًا ، فسيكون رمز التجزئة الفارغ دائمًا صفرًا.

أسلوب HashCode ()

يتم استخدام الأسلوب hashCode () للحصول على رمز التجزئة للكائن. ترجع طريقة hashCode () لفئة الكائن مرجع ذاكرة صحيح (رمز تجزئة الهوية ). توقيع طريقة public native hashCode() . هذا يشير إلى أن الطريقة يتم تنفيذها على أنها أصلية ، لأنه في جافا لا توجد طريقة للحصول على مرجع إلى الكائن. يُسمح بتعريف تنفيذك لطريقة hashCode (). في فئة HashMap ، يتم استخدام طريقة hashCode () لحساب المجموعة وبالتالي حساب الفهرس.

طريقة يساوي ()

يتم استخدام الأسلوب يساوي لاختبار شيئين للمساواة. يتم تنفيذ الطريقة في فئة الكائن. يمكنك تجاوزه في صفك. في فئة HashMap ، تُستخدم طريقة equals () للتحقق من المساواة الرئيسية. في حالة تساوي المفاتيح ، ترجع طريقة يساوي () صواب ، وإلا تكون خاطئة.

سلال

دلو هو العنصر الوحيد في صفيف HashMap. يتم استخدامه لتخزين العقد (العقد). يمكن أن تحتوي العقدتان أو أكثر على نفس الدلو. في هذه الحالة ، يتم استخدام بنية بيانات قائمة مرتبطة لربط العقد. تختلف الدلاء في السعة (خاصية السعة). العلاقة بين الدلو والسعة هي كما يلي:

 capacity = number of buckets * load factor 

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

حساب مؤشر HashMap

يمكن أن يكون رمز تجزئة المفتاح كبيرًا بما يكفي لإنشاء مصفوفة. يمكن أن يكون رمز التجزئة الذي تم إنشاؤه في نطاق نوع صحيح وإذا أنشأنا صفيفًا من هذا الحجم ، فيمكننا بسهولة الحصول على outOfMemoryException. لذلك ، نقوم بإنشاء فهرس لتقليل حجم المصفوفة. في جوهرها ، يتم تنفيذ العملية التالية لحساب الفهرس:

 index = hashCode(key) & (n-1). 

حيث n تساوي عدد المجموعة أو قيمة طول المصفوفة. في مثالنا ، أعتبر n القيمة الافتراضية لـ 16.

• علامة التجزئة فارغة في البداية: حجم تجزئة هنا هو 16:

 HashMap map = new HashMap(); 

هاشماب:

• insert pairs Key - Value: add one pair key - value to the end of HashMap

 map.put(new Key("vishal"), 20); 

خطوات:

1. احسب القيمة الرئيسية {"vishal"}. سيتم إنشاؤه كـ 118.

   
   

2. احسب الفهرس باستخدام طريقة index التي ستكون 6.

   
   

3. إنشاء كائن عقدة.

   
   

    { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null } 

   
   

4. ضع الكائن في موضعه باستخدام الفهرس 6 ، إذا كانت المساحة خالية.

   
   

يبدو HashMap الآن مثل هذا:

• إضافة زوج آخر ذي قيمة رئيسية: الآن أضف زوجًا آخر

 map.put(new Key("sachin"), 30); 

خطوات:

1. احسب القيمة الرئيسية {"sachin"}. سيتم إنشاؤه كـ 115.

   
   

2. احسب الفهرس باستخدام طريقة index التي ستكون 3.

   
   

3. إنشاء كائن عقدة.

   
   

    { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null } 

   
   

4. ضع الكائن في موضعه باستخدام الفهرس 3 ، إذا كانت المساحة خالية.

   
   

يبدو HashMap الآن مثل هذا:

• في حالة حدوث تصادمات: أضف الآن زوجًا آخر

 map.put(new Key("vaibhav"), 40); 

خطوات:

1. احسب القيمة الرئيسية {"vaibhav"}. سيتم إنشاؤه كـ 118.

   
   

2. احسب الفهرس باستخدام طريقة index التي ستكون 6.

   
   

3. إنشاء كائن عقدة.

   
   

    { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null } 

   
   

4. ضع الكائن في موضعه باستخدام الفهرس 6 ، إذا كانت المساحة خالية.

   
   

5. في هذه الحالة ، يوجد كائن آخر بالفعل في الموضع مع الفهرس 6 ، وتسمى هذه الحالة بالاصطدام.

   
   

6. في هذه الحالة ، يتحقق من طريقتي hashCode () و يساوي () أن كلا المفتاحين متماثلان.

   
   

7. إذا كانت المفاتيح هي نفسها ، فاستبدل القيمة الحالية بقيمة جديدة.

   
   

8. وإلا ، قم بربط الكائنات الجديدة والقديمة باستخدام بنية بيانات "القائمة المرتبطة" عن طريق تحديد ارتباط إلى الكائن التالي في الكائن الحالي وحفظهما تحت الفهرس 6.

   
   

يبدو HashMap الآن مثل هذا:

[ملاحظة من مؤلف الترجمة] الصورة مأخوذة من المقالة الأصلية وتحتوي في البداية على خطأ. المرجع إلى الكائن التالي في كائن vishal مع الفهرس 6 ليس فارغًا ، بل يحتوي على مؤشر إلى كائن vaibhav.

• نحصل على القيمة بمفتاح ساشين:

 map.get(new Key("sachin")); 

خطوات:

1. حساب كود التجزئة للكائن {{sachin »}. تم إنشاؤه كـ 115.

   
   

2. احسب الفهرس باستخدام طريقة index التي ستكون 3.

   
   

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

   
   

4. في حالتنا ، تم العثور على العنصر وقيمة الإرجاع 30.

   
   

• نحصل على القيمة عن طريق مفتاح vaibahv:

 map.get(new Key("vaibhav")); 

خطوات:

1. احسب كود التجزئة للكائن {"vaibhav"}. تم إنشاؤه كـ 118.

   
   

2. احسب الفهرس باستخدام طريقة index التي ستكون 6.

   
   

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

   
   

4. في هذه الحالة ، لم يتم العثور عليه وكائن العقدة التالي ليس فارغًا.

   
   

5. إذا كان كائن العقدة التالي فارغًا ، فارجع فارغًا.

   
   

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

   
   

 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } } 

الخلاصة:

 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40 

التغييرات في جافا 8

كما نعلم بالفعل في حالة حدوث تصادمات ، يتم تخزين كائن العقدة في بنية بيانات "القائمة المرتبطة" ويتم استخدام طريقة يساوي () لمقارنة المفاتيح. هذه مقارنات للعثور على المفتاح الصحيح في قائمة مرتبطة - عملية خطية ، وفي أسوأ الحالات ، يكون التعقيد هو O (n) .

لإصلاح هذه المشكلة في Java 8 ، بعد الوصول إلى حد معين ، يتم استخدام الأشجار المتوازنة بدلاً من القوائم المرتبطة. هذا يعني أن HashMap في البداية يحفظ الكائنات في قائمة مرتبطة ، ولكن بعد أن يصل عدد العناصر في التجزئة إلى حد معين ، يحدث انتقال إلى الأشجار المتوازنة. مما يحسن الأداء في أسوأ الحالات من O (n) إلى O (log n).

نقطة مهمة

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