كيف تعمل جافا هاشماب

يستخدم معظم مطوري Java الخريطة ، وخاصة hashmap. HashMap هي وسيلة بسيطة ولكنها قوية للتخزين والحصول على البيانات. ولكن كم عدد المطورين يعرفون كيف يعمل Hashmap داخليًا؟ قبل بضعة أيام ، قرأت الكثير من كود المصدر لـ java.util.hashmap (بما في ذلك Java 7 و Java 8) لاكتساب فهم عميق لهيكل البيانات الأساسي. في هذا المنشور ، سأشرح تنفيذ java.util.hashmap ، وصف الميزات الجديدة المضافة في تنفيذ Java 8 ، ومناقشة الأداء والذاكرة وبعض المشكلات المعروفة عند استخدام HashMap.

التخزين الداخلي

تنفذ فئة Java Hashmap واجهة الخريطة <K ، V>. تشمل الطرق الرئيسية في هذه الواجهة:

 v put (k key ، v value) v get (مفتاح الكائن) v إزالة (مفتاح الكائن) containskey (مفتاح الكائن)

يستخدم HashMap إدخال الفئة الداخلية <K ، V> لتخزين البيانات. هذه الفئة الداخلية عبارة عن زوج بسيط القيمة الرئيسية مع بيانات إضافية:

إشارة إلى إدخال آخر ، بحيث يمكن لـ HashMap تخزين كائنات مثل قوائم الارتباطات.
قيمة التجزئة المستخدمة لتمثيل المفتاح. يمكن أن يمنع تخزين هذه القيمة hashmap من تجديد قيمة التجزئة المقابلة للمفتاح في كل مرة تكون هناك حاجة إليها.
فيما يلي جزء من رمز الإدخال <K ، V> تحت Java 7:

 إدخال فئة ثابتة <k ، v> ينفذ map.entry <k ، v> {final k key ؛ v value ؛ entry <k ، v> next ؛ int hash ؛ ...}

يقوم HashMap بتخزين البيانات في قوائم متعددة أحادية الاتجاه (تسمى أحيانًا الدلاء أو الحاويات orbins). يتم تسجيل جميع القوائم في صفيف الدخول (إدخال <k ، v> [] صفيف) ، والطول الافتراضي لهذه الصفيف الداخلي هو 16.

يصف الشكل التالي التخزين الداخلي لمثيل hashmap ، والذي يحتوي على مجموعة من الكائنات الباطئة. كل كائن متصل بكائن آخر ، وبالتالي تشكيل قائمة مرتبطة.

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

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

في حالة الاتصال GET () ، سيقوم البرنامج بإرجاع كائن الإدخال المقابل للقيمة (في حالة وجود كائن الإدخال).

بالنسبة للمكالمة (Key Key ، V Value) ، إذا كان كائن الإدخال موجودًا بالفعل ، فسيحل البرنامج محل القيمة بقيمة جديدة ، وإلا فإن البرنامج سيقوم بإنشاء إدخال جديد (مفتاح وقيمة في المعلمة) في رأس القائمة المرتبطة بالدورة الواحدة.

يتم إنشاء فهرس الدلو (القائمة المرتبطة) من خلال 3 خطوات من الخريطة:

احصل أولاً على رمز التجزئة للمفتاح.

يكرر البرنامج رمز التجزئة لمنع وظائف التجزئة السيئة للمفاتيح ، لأن هذا لديه القدرة على وضع جميع البيانات على نفس الفهرس (دلو) من الصفيف الداخلي.
يأخذ البرنامج رمز التجزئة المكررة ويستخدم مخيلة bitmas من طول الصفيف (الحد الأدنى 1) لذلك. تضمن هذه العملية ألا يكون الفهرس أكبر من حجم الصفيف. يمكنك التفكير في الأمر كدالة معامل محسّنة محسوبة.

فيما يلي الرمز المصدر لإنشاء الفهرس:

 . 0.

للعمل بشكل أكثر كفاءة ، يجب أن يكون حجم الصفيف الداخلي قوة 2. دعنا نرى لماذا:

على افتراض أن طول الصفيف هو 17 ، فإن قيمة القناع هي 16 (طول الصفيف 1). التمثيل الثنائي لـ 16 هو 0 ... 010000 ، بحيث يكون نتيجة "H & 16" بالنسبة لأي قيمة H ، وهذا يعني أن صفائف الطول 17 لا يمكن تطبيقها إلا على دلاءتين: واحد هو 0 والآخر 16 ، وهو ليس فعالًا للغاية. ولكن إذا قمت بتعيين طول الصفيف على قوة 2 ، على سبيل المثال 16 ، فإن فهرسة bitwise تعمل على "H&15". التمثيل الثنائي لـ 15 هو 0 ... 001111 ، ويمكن أن يتراوح إخراج القيمة بواسطة صيغة الفهرس من 0 إلى 15 ، بحيث يمكن استخدام مجموعة من الطول 16 بالكامل. على سبيل المثال:

إذا كان H = 952 ، فإن تمثيله الثنائي هو 0..01110111000 ، والفهرس المقابل هو 0 ... 01000 = 8
إذا كان H = 1576 ، فإن تمثيله الثنائي هو 0..011000101000 ، والفهرس المقابل هو 0 ... 01000 = 8
إذا كان H = 12356146 ، فإن تمثيله الثنائي هو 0..010111100101010010 ، فهرس المقابل هو 0 ... 00010 = 2
إذا كان H = 59843 ، فإن تمثيله الثنائي هو 0..0111010011100000011 ، فهرسه المقابل هو 0 ... 00011 = 3
هذه الآلية شفافة للمطور: إذا اختار Hashmap بطول 37 ، فسيتحدد الخريطة تلقائيًا قيمة الطاقة التالية التي تزيد عن 37 (64) كطول الصفيف الداخلي.

تغيير الحجم تلقائيا

بعد الحصول على الفهرس ، سيصل طرق GET () أو PUT () أو إزالة () إلى القائمة المرتبطة المقابلة لمعرفة ما إذا كان كائن الإدخال الخاص بالمفتاح المحدد موجودًا بالفعل. بدون تعديل ، قد تتسبب هذه الآلية في مشاكل في الأداء ، حيث تتطلب هذه الطريقة التكرار على القائمة بأكملها لمعرفة ما إذا كان كائن الإدخال موجودًا. افترض أن طول الصفيف الداخلي يأخذ القيمة الافتراضية البالغة 16 ، وتحتاج إلى تخزين 2،000،000 سجل. في أفضل الحالة ، سيكون هناك 125000 كائن دخول لكل قائمة مرتبطة (2،000،000/16). تتطلب أساليب GET () ، وإزالة () و PUT () 125000 تكرار في كل مرة يتم تنفيذها. لتجنب ذلك ، يمكن لـ HashMap زيادة طول الصفيف الداخلي ، وبالتالي ضمان الاحتفاظ ببعض كائنات الدخول فقط في القائمة المرتبطة.

عندما تقوم بإنشاء hashmap ، يمكنك تحديد طول أولي وعملية التحميل من خلال المُنشئ التالي:

 </pre> hashmap العامة (int initialcapacity ، float loadFactor) <pre>

إذا لم تحدد المعلمات ، فإن القيمة الافتراضية الأولية هي 16 ، وقيمة LoadFactor الافتراضية هي 0.75. تمثل SITIONCAPACITY طول القائمة المرتبطة بالمصفوفة الداخلية.

عند استخدام طريقة PUT (...) لإضافة زوج جديد من قيمة المفاتيح إلى الخريطة ، تتحقق الطريقة مما إذا كان طول المصفوفة الداخلية يحتاج إلى زيادة. لتحقيق ذلك ، تخزن الخريطة بيانات 2:

حجم الخريطة: يمثل عدد السجلات في HashMap. نقوم بتحديث القيمة عند إدراجها أو حذفها في HashMap.

العتبة: إنها تساوي طول الصفيف الداخلي*loadFactor ، وسيتم تحديث هذه العتبة أيضًا في نفس الوقت في كل مرة يتم فيها ضبط طول الصفيف الداخلي.

قبل إضافة كائن إدخال جديد ، تتحقق طريقة PUT (...) ما إذا كان حجم الخريطة الحالية أكبر من العتبة. إذا كان أكبر من العتبة ، فإنه يخلق صفيفًا جديدًا مع ضعف طول الصفيف الداخلي الحالي. نظرًا لأن حجم الصفيف الجديد قد تغير ، فإن وظيفة الفهرس (أي ، تتغير عملية تشغيل البتات التي تُرجع أيضًا "قيمة التجزئة للمفتاح و (طول الصفيف -1)"). قم بتغيير حجم الصفيف ينشئ دلوتين جديدتين (قوائم مرتبطة) ويعيد تعيين جميع كائنات الإدخال الحالية إلى الدلو. الهدف من ضبط حجم الصفيف هو تقليل حجم القائمة المرتبطة ، مما يقلل من وقت تنفيذ BUT () ، إزالة () والحصول على () الأساليب. بالنسبة لجميع كائنات الإدخال المقابلة للمفاتيح ذات قيمة التجزئة نفسها ، يتم تخصيصها لنفس الدلو بعد تغيير الحجم. ومع ذلك ، إذا كانت قيم التجزئة لكائنات الإدخال مختلفة ، لكنها كانت على نفس الدلو من قبل ، ثم بعد التعديل ، لا يوجد أي ضمان بأنهما لا يزالون على نفس الدلو.

تصف هذه الصورة موقف المصفوفات الداخلية قبل التعديل وما بعد التعديل. قبل ضبط طول الصفيف ، من أجل الحصول على كائن الإدخال E ، تحتاج الخريطة إلى التكرار عبر قائمة مرتبطة تحتوي على 5 عناصر. بعد ضبط طول الصفيف ، تحتاج طريقة GOT () نفسها فقط إلى اجتياز قائمة مرتبطة تحتوي على عنصرين ، وبالتالي يتم زيادة سرعة تشغيل طريقة GET () بعد ضبط طول الصفيف بمقدار مرتين.

السلامة الموضوع

إذا كنت على دراية بالفعل بـ Hashmap ، فأنت تعلم بالتأكيد أنه ليس مؤلمًا ، ولكن لماذا؟ على سبيل المثال ، افترض أن لديك مؤشر ترابط الكاتب الذي سيقوم فقط بإدخال البيانات الموجودة في الخريطة ، وهو مؤشر ترابط القارئ الذي سيقرأ البيانات من الخريطة ، فلماذا لا يعمل؟

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

في أسوأ الحالات ، عندما تقوم 2 مؤشرات ترابط بإدخال بيانات في نفس الوقت ، ستبدأ مكالمات 2 PUT () في نفس الوقت وسيتم تغيير حجم الصفيف تلقائيًا. نظرًا لأن ترابطين يعدلان القائمة المرتبطة في نفس الوقت ، فمن الممكن أن تخرج الخريطة في الحلقة الداخلية للقائمة المرتبطة. إذا حاولت الحصول على بيانات من قائمة مع حلقة داخلية ، فلن تنتهي طريقة GET () أبدًا.

يوفر Hashtable تطبيقًا آمنًا مؤشر ترابط يمنع ما سبق من الحدوث. ومع ذلك ، نظرًا لأن جميع عمليات Crud المتزامنة بطيئة جدًا. على سبيل المثال ، إذا احصلت مكالمات الموضوع 1 على (key1) ، ثم تحصل مكالمات الموضوع 2 على (key2) ، ومكالمات الخيط 2 (key3) ، ثم في وقت محدد ، يمكن أن يحصل مؤشر ترابط واحد فقط على قيمته ، ولكن يمكن لجميع مؤشرات الترابط الثلاثة الوصول إلى هذه البيانات في نفس الوقت.

منذ Java 5 ، لدينا تطبيق HashMap أفضل وأمان مؤشر الترابط: ConcurrentHashMap. بالنسبة إلى ConcurrentMap ، تتم مزامنة الدلاء فقط ، بحيث إذا لم تستخدم مؤشرات ترابط متعددة نفس الدلو أو تغيير حجم الصفيف الداخلي ، فيمكنهم استدعاء طرق GET () أو إزالة () أو وضع () في نفس الوقت. في تطبيق متعدد مؤشرات الترابط ، هذا النهج هو خيار أفضل.

ثبات السندات

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

دعونا نلقي نظرة على حالات الاستخدام التالية:

لديك مفتاح القيمة الداخلية هي "1".

إذا قمت بإدخال كائن في hashmap ، فإن مفتاحه هو "1".

يقوم HashMap بإنشاء قيم التجزئة من رمز التجزئة للمفتاح (أي "1").

مخازن الخريطة هذه قيمة التجزئة في السجل الذي تم إنشاؤه حديثًا.

يمكنك تغيير القيمة الداخلية للمفتاح وتغييره إلى "2".

تم تغيير قيمة التجزئة للمفتاح ، لكن HashMap لا تعرف ذلك (لأن قيمة التجزئة القديمة مخزنة).

تحاول الحصول على الكائن المقابل بواسطة المفتاح المعدل.

تقوم MAP بحساب قيمة التجزئة للمفتاح الجديد (أي "2") للعثور على القائمة المرتبطة (دلو) حيث يوجد كائن الإدخال.

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

الحالة 2: أنت محظوظ لأن الدلو الذي تم إنشاؤه بواسطة المفتاح المعدل والدلو الذي تم إنشاؤه بواسطة المفتاح القديم هو نفسه. ستجتاز الخريطة بعد ذلك القائمة المرتبطة وتم العثور على كائن إدخال بنفس المفتاح. ولكن من أجل العثور على المفتاح ، ستقارنة MAP أولاً قيمة التجزئة للمفتاح عن طريق استدعاء طريقة متساوٍ (). نظرًا لأن المفتاح المعدل سيقوم بإنشاء قيم تجزئة مختلفة (يتم تخزين قيم التجزئة القديمة في السجل) ، فإن الخريطة لا تحتوي على طريقة للعثور على كائن الإدخال المقابل في القائمة المرتبطة.

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

 الطبقة العامة mutableKeyTest {public static void main (string [] args) {class mykey {Integer i ؛ public void seti (integer i) {this.i = i ؛} public mykey (integer i) {this.i = i ؛}@overridepublic mykey) {return i.equals (((mykey) obj) .i) ؛} elsereturn false ؛}} خريطة <mykey ، string> mymap = new hashmap <> () ؛ mykey key1 = new mykey (1) ؛ mykey key2 = new mykey (2) ؛ mymap.put (key1 ، key1key1.seti (3) ؛ string test1 = mymap.get (key1) ؛ string test2 = mymap.get (key2) ؛ system.out.println ("test1 =" + test1 + "test2 =" + test2) ؛}}

إخراج الكود أعلاه هو "test1 = null test2 = test 2". كما نتوقع ، لا تملك MAP القدرة على الحصول على السلسلة 1 المقابلة للمفتاح المعدل 1.

التحسينات في جافا 8

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

فيما يلي جزء من الكود الذي ينفذ العقدة في Java 8:

 عقدة الفئة الثابتة <k ، v> تنفذ map.entry <k ، v> {final int hash ؛ final k key ؛ v value ؛ node <k ، v> next ؛

إذن ما هو الفرق الكبير مقارنة بجافا 7؟ حسنًا ، يمكن تمديد العقدة إلى treenode. Treenode هو بنية بيانات لشجرة حمراء وسوداء يمكنها تخزين المزيد من المعلومات ، حتى نتمكن من إضافة عنصر أو حذفه أو الحصول عليه تحت تعقيد O (log (n)). يصف المثال التالي جميع المعلومات التي تم حفظها بواسطة Treenode:

 فئة نهائية ثابتة treenode <k ، v> يمتد linkedhashmap.entry <k ، v> {Final int hash ؛ // الموروثة من العقدة <k ، v> النهائي k المفتاح ؛ // الموروث من العقدة <k ، v> v value ؛ // الموروث من العقدة <k ، v> node <k ، v> next ؛ // الموروثة من العقدة <k ، v> إدخال <k ، v> قبل ، بعد ؛ // الموروث من linkedhashmap.entry <k ، v> parent ؛ treenode <k ، v> left ؛ treenode <k ، v> right ؛ treenode <k ، v> prev ؛ boolean red ؛

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

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

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

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

تصف هذه الصورة صفيفًا داخليًا في Java 8 HashMap ، والذي يحتوي على كل من الشجر (دلو 0) وقوائم مرتبطة (دلو 1 و 2 و 3). دلو 0 هو بنية شجرة لأنه يحتوي على أكثر من 8 عقد.

الذاكرة النفقات العامة

جافا 7

باستخدام hashmap يستهلك بعض الذاكرة. في Java 7 ، يقوم HashMap بتغليف أزواج قيمة المفاتيح في كائنات الإدخال ، يحتوي كائن الإدخال على المعلومات التالية:

إشارة إلى السجل التالي قيمة التجزئة المحسوبة مسبقا (عدد صحيح)
إشارة إلى مفتاح ومرجع إلى قيمة

بالإضافة إلى ذلك ، يستخدم HashMap في Java 7 مجموعة داخلية من كائنات الدخول. لنفترض أن Java 7 Hashmap يحتوي على عناصر N ولديه صفيفها الداخلي ، ثم يكون استهلاك الذاكرة الإضافي حول:

sizeof (integer)* n + sizeof (المرجع)* (3* n + c)

في:

حجم عدد صحيح هو 4 بايت

يعتمد حجم المرجع على JVM ، ونظام التشغيل ، والمعالج ، ولكن عادة ما يكون 4 بايت.

هذا يعني أن إجمالي النفقات العامة للذاكرة هو عادة 16 * n + 4 * بايت السعة.

ملاحظة: بعد تغيير حجم الخريطة تلقائيًا ، تكون قيمة السعة هي أصغر طاقة تصل إلى 2 أكبر من N.

ملاحظة: بدءًا من Java 7 ، يعتمد Hashmap آلية تحميل كسول. هذا يعني أنه حتى إذا قمت بتحديد حجم HashMap ، فإن الصفيف الداخلي المستخدم (استهلاك بايت 4*سعة) لم يتم تخصيصه في الذاكرة قبل استخدام طريقة PUT () أولاً.

جافا 8

في تطبيقات Java 8 ، يصبح استخدام الذاكرة أكثر تعقيدًا لأن العقدة قد تخزن نفس البيانات مثل الإدخال ، أو إضافة 6 مراجع وخاصية منطقية (تحديد ما إذا كانت treenode).

إذا كانت جميع العقد مجرد عقد ، فإن الذاكرة التي تستهلكها Java 8 HashMap هي نفسها التي تستهلكها Java 7 HashMap.

إذا كانت جميع العقد treenode ، فإن الذاكرة التي تستهلكها Java 8 Hashmap تصبح:

 n * sizeof (integer) + n * sizeof (boolean) + sizeof (Reference) * (9 * n + cource)

في معظم JVMs القياسية ، تكون نتيجة الصيغة أعلاه 44 * n + 4 * بايت السعة.

قضايا الأداء

hashmap غير المتماثل مقابل hashmap متوازن

في أفضل الحالة ، كل من أساليب GET () و PUT () لها فقط التعقيد O (1). ومع ذلك ، إذا كنت لا تهتم بوظيفة التجزئة للمفتاح ، فقد يتم تنفيذ أساليب PUT () و GET () ببطء شديد. يعتمد التنفيذ الفعال لطرق PUT () و () على البيانات التي يتم تخصيصها إلى فهارس مختلفة من الصفيف الداخلي (دلو). إذا لم يتم تصميم وظيفة التجزئة للمفتاح بشكل صحيح ، فستحصل على قسم غير متماثل (بغض النظر عن حجم البيانات الداخلية). ستستخدم جميع أساليب PUT () و GET () أكبر قائمة مرتبطة ، والتي ستكون بطيئة في التنفيذ لأنها تتطلب التكرار على جميع السجلات في القائمة المرتبطة. في أسوأ الحالات (إذا كانت معظم البيانات على نفس الدلو) ، يصبح تعقيد الوقت الخاص بك O (N).

هنا مثال بصري. يصف الرسم البياني الأول hashmap غير المتماثل ويصف الرسم البياني الثاني hashmap المعادلة.

Skewedhashmap

في هذا hashmap غير المتماثل ، سيستغرق الأمر وقتًا لتشغيل أساليب GET () و PUT () على دلو 0. الحصول على سجل k يأخذ 6 تكرارات.

في هذا hashmap المتوازن ، لا يتطلب الأمر سوى 3 تكرارات للحصول على السجل K. يخزن هاتان hashmaps نفس كمية البيانات والصفائف الداخلية هي نفس الحجم. الفرق الوحيد هو وظيفة التجزئة للمفتاح ، والتي يتم استخدامها لتوزيع السجلات على دلاء مختلفة.

فيما يلي مثال متطرف مكتوب في Java ، حيث أستخدم وظيفة التجزئة لوضع جميع البيانات في نفس القائمة المرتبطة (دلو) ثم أضفت 2،000،000 قطعة من البيانات.

 اختبار الفئة العامة {public static void main (string [] args) {class mykey {Integer i ؛ public mykey (integer i) {this.i = i ؛}@overridepublic int hashcode ( HashMap <> (2_500_000،1) ؛ for (int i = 0 ؛ i <2_000_000 ؛ i ++) {mymap.put (new mykey (i) ، "test"+i) ؛

تكوين الجهاز الخاص بي هو CORE I5-2500K @ 3.6G ، ويستغرق تشغيل أكثر من 45 دقيقة تحت Java 8U40 (توقفت عن العملية بعد 45 دقيقة). إذا قمت بتشغيل نفس الرمز ، لكني أستخدم وظيفة التجزئة مثل هذا:

 Overridepublic int hashcode () {int key = 2097152-1 ؛ إرجاع مفتاح+2097152*i ؛}

يستغرق تشغيله 46 ثانية ، وهو أفضل بكثير من ذي قبل! تكون وظيفة التجزئة الجديدة أكثر منطقية من وظيفة التجزئة القديمة عند معالجة أقسام التجزئة ، لذا فإن استدعاء طريقة PUT () أسرع. إذا قمت بتشغيل نفس الرمز الآن ، ولكن استخدم وظيفة التجزئة أدناه ، فإنها توفر قسم تجزئة أفضل:

 OverRidepublic int hashcode () {return i ؛}

الآن يستغرق فقط ثانيتين!

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

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

تغيير حجم النفقات العامة

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

إذا لم تقم بذلك ، فستستخدم الخريطة الحجم الافتراضي ، أي 16 ، وقيمة الحمولة هي 0.75. ستكون الطريقة الـ 11 الأولى لـ PUT () سريعة جدًا ، لكن المكالمة 12 (16*0.75) ستنشئ صفيفًا داخليًا جديدًا بطول 32 (والقائمة المرتبطة المقابلة) ، وسيتم تعيين المكالمة من 13 إلى 22 إلى وضع () بسرعة كبيرة ، لكن ستتماثل المكالمات 23 (32*0.75) (مرة أخرى) ، وسوف تكون مكالمة متدربة جديدة ، وسيتم الطول. بعد ذلك ، سيتم تشغيل عملية تغيير الحجم الداخلية عندما تسمى طريقة PUT () 48 ، 96 ، 192 ... إذا لم تكن كمية البيانات كبيرة ، فستكون تشغيل الصفيف الداخلي سريعًا للغاية ، ولكن عندما تكون كمية البيانات كبيرة ، قد يتراوح الوقت الذي تقضيه من ثوان إلى دقائق. من خلال تحديد الحجم المطلوب للخريطة أثناء التهيئة ، يمكنك تجنب الاستهلاك الناجم عن تغيير حجم العمليات.

ولكن هناك أيضًا عيبًا هنا: إذا قمت بتعيين الصفيف ليكون كبيرًا جدًا ، على سبيل المثال 2^28 ، لكنك تستخدم فقط 2^26 دلو في الصفيف ، فستضيع الكثير من الذاكرة (حوالي 2^30 بايت في هذا المثال).

ختاماً

لحالات الاستخدام البسيطة ، لا تحتاج إلى معرفة كيفية عمل HashMap ، لأنك لن ترى الفرق بين O (1) و O (n) و o (log (n)). ولكن من المفيد دائمًا فهم الآلية الكامنة وراء بنية البيانات المستخدمة بشكل متكرر. بالإضافة إلى ذلك ، هذا سؤال مقابلة نموذجي لمواقع مطور Java.

بالنسبة لأحجام البيانات الكبيرة ، يصبح من المهم للغاية أن نفهم كيف يعمل hashmap وفهم أهمية وظيفة التجزئة للمفاتيح.

آمل أن يساعدك هذا المقال في الحصول على فهم عميق لتنفيذ HashMap.