تحليل مبدأ hashmap في جافا

دعونا نلقي نظرة أولاً على سؤال المقابلة:

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

تم تقديم عينة من الكود والإجابات في المقالة ، ولكن لم يتم تقديم تفسير حول مبدأ HashMap.

1. الميزات

يمكننا استخدام أي فئة كمفتاح hashmap ، ولكن ما هي القيود المفروضة على هذه الفئات؟ دعونا نلقي نظرة على الكود التالي:

 شخص فئة عامة {اسم السلسلة الخاصة ؛ الشخص العام (اسم السلسلة) {this.name = name ؛ }} خريطة <شخص ، سلسلة> testmap = new hashmap <> () ؛ testmap.put (شخص جديد ("Hello") ، "World") ؛ TestMap.get (شخص جديد ("Hello")) ؛ // ---> خالية

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

2. مبدأ

أولاً ، دعونا نلقي نظرة على حل تنفيذ HashMap بسيط في "التفكير في Java":

 //: حاويات/simplehashmap.java // عرض توضيحي map.import java.util.*؛ استيراد net.mindview.util. // لا يمكن أن يكون لديك مجموعة مادية من الأدوية الجيرية ، ولكن يمكنك الحصول على واحد إلى واحد: suppressWarnings ("غير محدد") LinkedList <mapentry <k ، v >> [] duckets = new LinkedList [size] ؛ public v put (k key ، v value) {v oldvalue = null ؛ int index = math.abs (key.hashcode ()) ٪ size ؛ if (دلاء [index] == null) دلاء [index] = new LinkedList <mapentry <k ، v >> () ؛ LinkedList <mapentry <k ، v >> bucket = buckets [index] ؛ mapentry <k ، v> pair = new mapentry <k ، v> (المفتاح ، القيمة) ؛ عثر على منطقية = خطأ ؛ ListIratorator <mapentry <k ، v >> it = bucket.ListIrator () ؛ بينما (it.hasnext ()) {mapentry <k ، v> ipair = it.next () ؛ if (ipair.getKey (). يساوي (مفتاح)) {oldvalue = ipair.getValue () ؛ it.set (زوج) ؛ // استبدال Old بـ New Found = true ؛ استراحة؛ }} if (! found) buckets [index] .add (pair) ؛ إرجاع Oldvalue ؛ } public v get (مفتاح الكائن) {int index = math.abs (key.hashcode ()) ٪ ؛ if (دلاء [الفهرس] == null) إرجاع فارغ ؛ لـ (mapentry <k ، v> ipair: buckets [index]) if (ipair.getKey (). equals (key)) return ipair.getValue () ؛ العودة لاغية. } المجموعة العامة <map.entry <k ، v >> entrySet () {set <map.entry <k ، v >> set = new hashset <map.entry <k ، v >> () ؛ لـ (LinkedList <mapentry <k ، v >> bucket: buckets) {if (bucket == NULL) متابعة ؛ لـ (mapentry <k ، v> mpair: bucket) set.add (mpair) ؛ مجموعة العودة ؛ } public static void main (string [] args) {simplehashMap <string ، string> m = new SimpleHashMap <string ، string> () ؛ M.Putall (Country.capitals (25)) ؛ System.out.println (M) ؛ System.out.println (M.Get ("Eritrea")) ؛ System.out.println (M.EntrySet ()) ؛ }}

SimplehashMap يبني جدول التجزئة لتخزين المفاتيح. وظيفة التجزئة هي حجم المعامل Math.ABS (key.hashcode ()) ٪ ، ويتم حل تعارض التجزئة باستخدام طريقة القائمة المرتبطة ؛ كل فتحة من خريطة مخازن الجرافات.

مبدأ التنفيذ لـ JDK's HashMap يشبه ذلك ، والذي يستخدم جدول التجزئة لعنوان السلسلة لتخزين Map.entry:

 /*** الجدول ، تغيير حجمه حسب الضرورة. يجب أن يكون الطول دائمًا قوة اثنين. */إدخال عابر <k ، v> [] table = (إدخال <k ، v> []) فارغة _table ؛ إدخال فئة ثابتة <k ، v> تنفذ map.entry <k ، v> {final k key ؛ V قيمة ؛ الدخول <K ، V> التالي ؛ التجزئة ...}

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

 public v get (مفتاح الكائن) {if (key == null) return getFornullKey () ؛ الإدخال <k ، v> entry = getentry (مفتاح) ؛ إرجاع فارغ == الدخول؟ NULL: ENTROM.GETVALUE () ؛} الإدخال النهائي <k ، v> getentry (مفتاح الكائن) {if (size == 0) {return null ؛ } int hash = (key == null)؟ 0: التجزئة (المفتاح) ؛ لـ (الإدخال <k ، v> e = table [indexfor (hash ، table.length)] ؛ e! = null ؛ e = e.next) {object k ؛ if ( } إرجاع فارغ ؛}

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