تحليل شامل لفئة hashmap في جافا

Hashmap و Hashset هما عضوان مهمان في إطار مجموعة Java. HashMap هي فئة تنفيذ شائعة لواجهة الخريطة ، و Hashset هي فئة تنفيذ شائعة لواجهة SET. على الرغم من اختلاف مواصفات الواجهة التي تنفذها HashMap و Hashset ، فإن آلية تخزين التجزئة الأساسية الخاصة بها هي نفسها تمامًا ، وحتى Hashset نفسها تستخدم HashMap لتنفيذها.
في الواقع ، هناك العديد من أوجه التشابه بين hassset و hashmap. بالنسبة إلى Hashset ، يستخدم النظام خوارزمية التجزئة لتحديد موقع التخزين لعناصر التجميع ، وذلك لضمان تخزين عناصر التجميع واستعادتها بسرعة ؛ بالنسبة إلى HashMap ، تتم معالجة قيمة مفتاح النظام ككل ، ويحسب النظام دائمًا موقع تخزين القيمة الرئيسية استنادًا إلى خوارزمية التجزئة ، بحيث يمكن تخزين أزواج القيمة الرئيسية للخريطة واستعادتها بسرعة.
قبل تقديم تخزين المجموعة ، يجب الإشارة إلى أنه على الرغم من أن المجموعة تدعي تخزين كائنات Java ، إلا أنها لا تضع في الواقع كائنات Java في المجموعة المحددة ، ولكنها تحتفظ فقط بالإشارات إلى هذه الكائنات في المجموعة المحددة. وهذا يعني أن مجموعة Java هي في الواقع مجموعة من المتغيرات المرجعية المتعددة التي تشير إلى كائن Java الفعلي.

1. الميزات الأساسية للهاشماب

بعد قراءة التعليقات في كود المصدر JDK hashmap.class ، يمكنك تلخيص العديد من ميزات hashmap.

يسمح HashMap بأن يكون كل من المفتاح والقيمة لاغية ، في حين أن Hashtable لا.

hashmap هو عائق الخيط ، في حين أن علامة التجزئة آمنة الخيط

ترتيب العناصر في hashmap ليس هو نفسه دائمًا ، وقد يتغير موضع نفس العنصر أيضًا مع مرور الوقت (حالة التغيير حجم)

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

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

2. تحليل بنية بيانات جدول التجزئة

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

كما هو موضح في الشكل أدناه ، يحصل المفتاح على موضع فهرس من الدلاء من خلال وظيفة التجزئة.

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

Open Operating: الفكرة الأساسية لهذه الطريقة هي مسح المواضع تحت الجدول بالتسلسل عند مواجهة التعارضات ، وملء ما إذا كان هناك أي منها حرة. لن يتم شرح الخوارزمية المحددة بعد الآن ، ما يلي هو مخطط تخطيطي:

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

طريقة حل النزاعات في HashMap في JDK هي استخدام طريقة التسلسل المنفصلة.

3. تحليل رمز المصدر HashMap (JDK1.7)

1. Hashmap قراءة وكتابة عناصر

دخول
العناصر المخزنة في hashmap هي من نوع الدخول. يرد أدناه رمز الإدخال المصدر في الرمز المصدر:

 إدخال الفئة الثابت <K ، V> ينفذ map.entry <k ، v> {Final K Key ؛ V قيمة ؛ الدخول <K ، V> التالي ؛ التجزئة إدخال (int h ، k k ، v v ، entry <k ، v> n) {value = v ؛ التالي = ن ؛ المفتاح = k ؛ التجزئة = ح ؛ } // طرق Get and Set للمفتاح ، يتم حذف القيمة ، وسيتم استخدام العمليات GET and SET في التكرار اللاحق ... Bublic Boolean Equals (كائن O) {if (! (o eastyof map.entry)) map.entry e = (map.entry) o ؛ الكائن k1 = getKey () ؛ كائن k2 = e.getKey () ؛ if (k1 == k2 || (k1! = null && k1.equals (k2))) {object v1 = getValue () ؛ كائن v2 = e.getValue () ؛ if (v1 == v2 || (v1! = null && v1.equals (v2))) return true ؛ } إرجاع خطأ ؛ } // هنا ، قم بعمل أو تشغيل Hashcode للمفتاح ورمز HashCode للحصول على hashcode من الإدخال العام النهائي int hashcode () {return objects.hashcode (getKey ()) ^ objects.hashCode (getValue ()) ؛ } السلسلة النهائية العامة tostring () {return getKey () + "=" + getValue () ؛ } /** * يتم استدعاء هذه الطريقة كلما تم كتابة القيمة الموجودة في الإدخال * من خلال استدعاء PUT (K ، V) لمفتاح K الذي هو بالفعل * في HashMap. * / void RecordAccess (HashMap <k ، v> m) {} / ** * يتم استدعاء هذه الطريقة عند إزالة الإدخال من الجدول. */ void RecordRemoval (HashMap <k ، v> m) {}}

يتضمن الإدخال المفتاح والقيمة والتجزئة والإشارة إلى الإدخال التالي. من الواضح أن هذه قائمة واحدة مرتبطة ، والتي تنفذ واجهة الخريطة.

لا يتم تطبيق RecordAcess (HashMap <K ، V> و RecordRemoval (hashmap <k ، v>) في hashmap. ومع ذلك ، يتم استخدام طريقتين من LinkedHashMap لتنفيذ خوارزمية LRU.

الحصول على: اقرأ عناصر للحصول على الإدخال المقابل من HashMap. ما يلي هو رمز الحصول على الحصول على:

 public v get (مفتاح الكائن) {// الموقف الذي يكون فيه المفتاح فارغًا إذا كان (key == null) إرجاع getFornullkey () ؛ // البحث عن إدخال استنادًا إلى إدخال إدخال المفتاح <k ، v> entry = getentry (مفتاح) ؛ إرجاع فارغ == الدخول؟ NULL: intrad.getValue () ؛ }

GetFornullkey كود المصدر

 private v getFornullKey () {if (size == 0) {return null ؛ } // tronstraighten سلسلة الصراع لـ (الإدخال <k ، v> e = table [0] ؛ e! = null ؛ e = e.next) {if (e.key == null) return } إرجاع فارغ ؛ }

يتم تخزين الدخول باستخدام مفتاح فارغ في الجدول [0] ، لكن سلسلة الصراع في الجدول [0] لا تحتوي بالضرورة على مفتاح فارغ ، لذلك يجب اجتيازه.

احصل على الدخول وفقًا للمفتاح:

 الإدخال النهائي <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 ( } إرجاع فارغ ؛ }

ما سبق هو عملية HashMap قراءة إدخال ورمز المصدر الخاص به. تعقيد الوقت O (1)

وضع: كتابة عناصر
عملية PUT في hashmap معقدة نسبيا لأنه سيكون هناك عملية توسيع hashmap أثناء عملية PUT.
عند كتابة عنصر جديد ، إذا كان هناك مفتاح لكتابة العنصر في HashMap ، يتم تنفيذ عملية استبدال القيمة ، وهو ما يعادل التحديث. هنا هو رمز المصدر وضع:

 public v put (k key ، v value) {// إذا كان الجدول فارغًا ، املأ if (table == frant_table) وفقًا لعتبة الحجم {Offtable (عتبة) ؛ } // املأ الإدخال بالمفتاح على أنه فارغ إذا (المفتاح == null) return putfornullkey (القيمة) ؛ // إنشاء التجزئة للحصول على رسم خرائط للفهرس int hash = مفتاح) ؛ int i = indexfor (hash ، table.length) ؛ // تحويل سلسلة الصراع في الفهرس الحالي للعثور على ما إذا كان هناك مفتاح مقابل لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ // إذا كان المفتاح المقابل موجودًا ، استبدل OldValue وأرجع oldvalue if ( e.value = القيمة ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ }} // مفتاح الإدخال المكتوب حديثًا غير موجود في سلسلة الصراع modcount ++ ؛ // أدخل إضافة إدخال جديد (التجزئة ، المفتاح ، القيمة ، i) ؛ العودة لاغية. }

Addentry و CreateEntry Code:

 addentry void (int hash ، k key ، v value ، int bucketIndex) {// قبل إدخال إدخال جديد ، تحكم أولاً على حجم hashmap الحالي وحجم عتبةه ، واختر ما إذا كان يجب التوسع إذا ((الحجم> = العتبة) hash = (null! = مفتاح)؟ التجزئة (مفتاح): 0 ؛ bucketIndex = indexfor (hash ، table.length) ؛ } createentry (hash ، key ، value ، bucketIndex) ؛ } void createentry (int hash ، k key ، v value ، int bucketIndex) {entry <k ، v> e = table [bucketIndex] ؛ // طريقة إدخال الرأس ، يتم إدراج الإدخال المكتوب حديثًا في مقدمة الإدخال الأول في سلسلة الصراع في موضع الفهرس الحالي. الجدول [bucketIndex] = إدخال جديد <> (التجزئة ، المفتاح ، القيمة ، E) ؛ حجم ++ ؛ }

ما سبق هو عملية كتابة إدخال إلى hashmap ورمز المصدر الخاص به. تعقيد الوقت O (1)

إزالة العنصر:

 الإدخال النهائي <k ، v> removeentryforkey (مفتاح الكائن) {if (size == 0) {return null ؛ } // حساب قيمة التجزئة وفقًا للمفتاح واحصل على فهرس int hash = (المفتاح == فارغ)؟ 0: التجزئة (المفتاح) ؛ int i = indexfor (hash ، table.length) ؛ // حذف القائمة المرتبطة ، وتحديد مؤشرين ، يمثل مسبقًا إدخال السلف <k ، v> prev = table [i] ؛ الدخول <k ، v> e = prev ؛ // transtraight سلسلة الصراع وحذف كل المفتاح بينما (e! = null) {intern <k ، v> next = e.next ؛ كائن ك ؛ // إذا تم العثور عليها (e.hash == hash && ((k = e.key) == مفتاح || (المفتاح! = null && key.equals (k)))) {modcount ++ ؛ مقاس--؛ // العثور على العقدة الأولى هي العقدة التي يتم حذفها إذا (PRIME == e) جدول [i] = التالي ؛ آخر prev.next = التالي ؛ e.RecordRemoval (هذا) ؛ إرجاع ه ؛ } prev = e ؛ ه = التالي ؛ } إرجاع e ؛ }

ما سبق هو عملية HashMap حذف إدخال ورمز المصدر الخاص به. تعقيد الوقت O (1)

2. مبدأ هاشماب (وظيفة التجزئة)

يتم تنفيذ وظيفة التجزئة في hashmap من خلال التجزئة (الكائن k) و indexfor (int h ، طول int). دعونا نلقي نظرة على الرمز المصدر أدناه:

 HING int hash (Object k) {int h = hashseed ؛ if (0! = h && k eastyof string) {return sun.misc.hashing.stringhash32 ((string) k) ؛ } h ^= k.hashCode () ؛ // تضمن هذه الوظيفة أن الترميزات التي تختلف فقط عن طريق // مضاعفات ثابتة في كل موضع بت لها عدد من الاصطدامات // (حوالي 8 في عامل التحميل الافتراضي). // من أجل تقليل فرصة الصراع H ^ = (H >>> 20) ^ (H >>> 12) ؛ إرجاع H ^ (H >>> 7) ^ (H >>> 4) ؛ }

احصل على رمز مصدر الفهرس:

 static int indexfor (int h ، int) {// assert integer.bitcount (length) == 1: "يجب أن يكون الطول قوة غير صفرية 2" ؛ إرجاع H & (length-1) ؛ }

خرائط HashMap مفاتيح للفهارس داخل الفاصل [0 ، Table.Length] من خلال وظيفة التجزئة. هناك عمومًا نوعان من طرق الفهرسة:

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

التجزئة (مفتاح) و (Table.Length - 1) حيث يجب أن يكون الطول إلى 2 القوة الأسية. يستخدم HashMap في JDK طريقة التنفيذ هذه.
نظرًا لأن حجم الطول هو مرتين أسيين ، سيكون التجزئة (مفتاح) و (Table.Length - 1) دائمًا بين [0 ، الطول - 1]. ومع ذلك ، إذا قمت بذلك بمفردك ، فستكون هناك مشكلة كبيرة في الصراع ، لأن قيمة Hashcode في Java هي 32 بت. عندما تكون قدرة hashmap صغيرة ، على سبيل المثال ، عندما تكون 16 ، عند القيام بعملية XOR ، يتم التخلص من البت المرتفع دائمًا ، ولكن بعد تشغيل البت المنخفض ، يزداد احتمال الصراع.

لذلك ، من أجل تقليل احتمال حدوث الصراع ، يتم إجراء العديد من عمليات البتات والعمليات الحصرية أو العمليات في الكود.

3. استراتيجية تخصيص الذاكرة HashMap

السعة المتغيرة للأعضاء و loadfactor
السعة المطلوبة هي مضاعف أسي من 2 في hashmap ، والقدرة الافتراضية هي 1 << 4 = 16. هناك أيضًا عامل توازن (loadFactor) في hashmap. العوامل العالية المفرطة ستقلل من مساحة التخزين ، ولكن الوقت للبحث (البحث ، بما في ذلك PUT والحصول على الأساليب في HASHMAP) سيزداد. القيمة الافتراضية لـ LoadFactor هي 0.75 ، وهي القيمة المثلى المعطاة من خلال وزن تعقيد الوقت وتعقيد الفضاء.

 ثابت نهائي int default_initial_capacity = 1 << 4 ؛ // aka 16 static Final int maximum_capacity = 1 << 30 ؛ ثابت Float Default_load_factor = 0.75f ​​؛

مُنشئ هاشماب
بناء hashmap هو تحديد السعة والقيمة الأولية لـ LoadFactor

 HASHMAP العام (int initialcapacity ، float loadFactor) {if (initialCapacity <0) رمي غير alfictalargumentException ("السعة الأولية غير القانونية:" + initialCapacity) ؛ إذا (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity ؛ if (loadFactor <= 0 || float.isnan (loadFactor)) رمي غير alficalaRgumentException جديد ("عامل التحميل غير القانوني:" + loadFactor) ؛ this.loadFactor = loadFactor ؛ عتبة = طاقة initial ؛ init () ؛ }

لقد قلت قبل هذه الصفة في هاشماب يجب أن تكون أوقاتًا أسية 2 ، ولا يوجد حد في المُنشئ. إذن ، كيف تضمن أن قيمة السعة هي أوقات أسية 2؟
أثناء التشغيل ، سيحدد رمز المصدر ما إذا كان جدول التجزئة الحالي هو جدول فارغ. إذا كان الأمر كذلك ، استدعاء القابلين للتطهير (int tosize)

 private void efantable (int tosize) {// ابحث عن قوة 2> = tosize int السعة = rounduptopowerof2 (tosize) ؛ عتبة = (int) math.min (السعة * loadFactor ، maximum_capacity + 1) ؛ جدول = إدخال جديد [السعة] ؛ inithashseedasneeded (السعة) ؛ }

حيث يكون RounduptOpowerOF2 هو الحصول على قوة N أكبر من أو تساوي المعلمة المحددة

 int static int routuptopowerof2 (int number) {// assert number> = 0: "يجب أن يكون الرقم غير سالب" ؛ رقم الإرجاع> = Maximum_Capacity؟ maximum_capacity: (رقم> 1)؟ integer.highestonebit ((رقم - 1) << 1): 1 ؛ }

integer.hightestonebit (int) هي عملية تحتفظ بأعلى جزء من معلمة معينة وتغير 0 المتبقية. ببساطة ، هو تغيير المعلمة int إلى n powers أقل من أو تساوي الحد الأقصى 2.

إذا كان الرقم هو طاقة N 2 ، فإن أعلى بت هو في الجزء الثاني الأصلي المرتفع بعد الانخفاض 1 ، ثم يتحول 1 بت إلى ما زال يضع في أعلى موضع بت. إذا لم يكن الرقم n طاقة 2 ، فإن أعلى عدد لا يزال هو أعلى عدد أصلي بعد انخفاض 1 بت لتغيير 1 بت ليكون

توسيع السعة:
سيكون لدى HashMap سلوك تغيير حجمه عند تشغيله. رمز المصدر المحدد هو كما يلي:

 void تغيير حجم (int newCapacity) {entry [] oldtable = table ؛ int oldcapacity = oldtable.length ؛ // وصل جدول التجزئة إلى الحد الأقصى لسعةه ، 1 << 30 إذا (oldcapacity == maximum_capacity) {threshold = integer.max_value ؛ يعود؛ } الإدخال [] newtable = إدخال جديد [newCapacity] ؛ . الجدول = newtable ؛ // إعادة حساب عتبة عتبة = (int) math.min (newCapacity * loadFactor ، Maximum_Capacity + 1) ؛ } نقل void (إدخال [] newtable ، boolean refrash) {int newCapacity = newtable.length ؛ // transweep Oldtable لـ (الإدخال <k ، v> e: table) {// transweep conflict chain (null! = e) {entry <k ، v> next = e.next ؛ if (refrash) {// إعادة حساب قيمة التجزئة e.hash = null == e.key؟ 0: التجزئة (E.Key) ؛ } int i = indexfor (E.Hash ، newCapacity) ؛ // أدخل العنصر في الرأس ، طريقة إدراج الرأس e.next = newtable [i] ؛ Newtable [i] = e ؛ ه = التالي ؛ }}}

ما سبق هو العملية الكاملة لتخصيص ذاكرة HashMap. باختصار ، عندما يضع HashMap إدخالًا ، فإنه سيتحقق من السعة الحالية وحجم العتبة لتحديد ما إذا كان سيتم توسيع السعة. حجم كل توسع هو 2 * TABLE.LENGTH. خلال فترة التوسع ، سيحدد ما إذا كانت قيمة التجزئة تحتاج إلى إعادة حساب بناءً على inithashseedasneeded.

4

يعتمد كل من التكرارات مثل ValueIrator و KeyIterator و EntpliTerator وغيرها في HashMap على Hashiterator. لنلقي نظرة على رمز المصدر الخاص به:

 تفاصيل فئة مجردة خاصة <e> تنفذ iterator <e> {entry <k ، v> next ؛ // الإدخال التالي لإرجاع int equiredModCount ؛ // لمؤشر INT السريع ؛ // الفتحة الحالية ، إدخال فهرس الجدول <K ، V> الحالي ؛ // الإدخال الحالي hashiterator () {expectmodcount = modCount ؛ // ابحث عن الإدخال الأول في جدول التجزئة if (size> 0) {entry [] t = table ؛ بينما (الفهرس <t.length && (التالي = t [index ++]) == null) ؛ }} public boolean hasnext () {return next! = null ؛ } الإدخال النهائي <k ، v> nextentry () {// hashmap غير آمن ، وعند العبور ، لا يزال يحدد ما إذا كان هناك أي تعديل لهيكل الجدول إذا (modCount! = المتوقع) يرمي convintmodification () الدخول <k ، v> e = التالي ؛ إذا (e == null) رمي nosuchelementException () ؛ if ((next = e.next) == null) {// ابحث عن إدخال الإدخال التالي [] t = table ؛ بينما (الفهرس <t.length && (التالي = t [index ++]) == null) ؛ } الحالي = هـ ؛ إرجاع ه ؛ } public void remove () {if (current == null) رمي جديد alficalstateException () ؛ if (modCount! = المتوقع remoDcount) رمي New ConvalEdificationException () ؛ كائن k = current.key ؛ الحالي = فارغ ؛ HashMap.This.RemoveentryForkey (K) ؛ المتوقع expectModCount = modCount ؛ }}

يتم تغليف التكرارات الثلاثة ، المفتاح ، القيمة ، والإدخال ، ويصبحون ثلاثة منظورات جمع: مفاتيح ، القيم ، ودخول. تدعم منظورات التجميع الثلاثة هذه عمليات إزالة وإزالة وتوضيح عمليات HashMap ، ولا تدعم عمليات Add و Addall.