شرح مفصل لمبدأ التنفيذ لجافا هاشماب

HashMap هو تطبيق واجهة MAP يعتمد على جداول التجزئة ، ويوفر جميع عمليات رسم الخرائط الاختيارية ، والسماح للقيم الفارغة والبناء الخالي ، خارج المزامنة وعدم ضمان ترتيب رسم الخرائط. دعنا نسجل مبدأ التنفيذ في HashMap.

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

في hashmap ، يتم تخزين جميع علاقات الزوج ذات القيمة الرئيسية عن طريق الحفاظ على مجموعة من الجدول المتغيرات الفورية (المعروف أيضًا باسم الجرافة). الدلو هو مجموعة من كائنات الدخول. يمكن تغيير حجم حجم الجرافة حسب الحاجة ، ويجب أن يكون الطول قوة 2. الرمز التالي:

 / *** صفيف إدخال فارغ ، القيمة الافتراضية للدلو*/ الإدخال النهائي الثابت <؟ ،؟> [] فارغ_table = {} ؛ / *** دلو ، تغيير حجمه حسب الحاجة ، ولكن يجب أن تكون قوة إدخال 2*/ عابرة <k ، v> [] table = (إدخال <k ، v> []) فارغ_

السعة الأولية وعامل الحمل

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

دلو يشبه دلو يخزن الماء. سعة التخزين الأولية الافتراضية هي 16 وحدة من الماء. عندما يتم سكب الماء إلى 16*0.75 ، سيتم توسيع السعة أولاً إلى 32 وحدة عند إضافة البيانات في المرة القادمة. 0.75 هو عامل التحميل ، ويمكن ضبط السعة الأولية وعامل التحميل عند إنشاء دلو. الحد الأقصى لسعة الدلو هو وحدتين من الماء إلى طاقة 30. عندما يكون عدد إعدادات السعة الأولية أكبر من الحد الأقصى للسعة ، يجب أن تسود الحد الأقصى للسعة. عند التوسع ، سيتم إرجاعه مباشرة إذا كان أكبر من أو يساوي الحد الأقصى للسعة.

ما يلي جزء من رمز المصدر لـ HashMap ، والذي يحدد السعة الأولية الافتراضية وعامل التحميل وبعض الثوابت الأخرى:

 / ** * يجب أن تكون السعة الأولية الافتراضية هي قوة 2. */ static int default_initial_capacity = 1 << 4 ؛ // AKA 16/ *** السعة القصوى ، إذا كانت السعة الأولية أكبر من الحد الأقصى للسعة من خلال معلمة المنشئ ، فسيتم استخدام السعة أيضًا كطاقة أولية* يجب أن تكون قوة 2 وأقل من أو تساوي القدرة الثلاثين من 2*/ static int maximum_capacity = 1< 30 ؛ / *** يمكن تحديد عامل التحميل الافتراضي بواسطة المُنشئ*/ ثابت Float Default_load_factor = 0.75f ​​؛ / *** جدول صفيف فارغ ، عندما لا يتم تهيئة الدلو*/ الإدخال النهائي الثابت <؟ ،؟> [] فارغ _table = {} ؛ / *** دلو ، يخزن جميع إدخالات زوج القيمة الرئيسية ، ويمكن تغيير حجمها حسب الحاجة ، ويجب أن يكون الطول قوة إدخال 2*/ عابرة <k ، v> [] table = (الإدخال <k ، v> []) فارغة. /*** عدد أزواج القيمة الرئيسية في الخريطة ، سيكون الحجم +1 أو -1 عملية في كل مرة يتم إضافتها أو حذفها. */ عابرة الحجم الباحث ؛ /** * القيمة الحرجة لقيمة التحميل ، والتي تحتاج إلى تغيير حجمها هي: (عامل السعة * التحميل). بعد كل تغيير حجم ، سيتم حساب السعة الجديدة باستخدام السعة الجديدة. * serial */ // إذا كان الجدول == فارغًا _table ، فهذه هي السعة الأولية التي سيتم فيها إنشاء الجدول // عند تضخيمها. عتبة int / ** * عامل التحميل ، إن لم يتم تحديده في المنشئ ، يتم استخدام عامل التحميل الافتراضي ، * * serial */ final float loadFactor ؛ /** * عدد مرات تعديلات هيكل hashmap ، قم بتغيير عدد الخرائط في hashmap أو تعديل بنيته الداخلية عند تعديل الهيكل (على سبيل المثال ، طريقة إعادة صياغة * ، إعادة بناء بنية البيانات الداخلية). يتم استخدام هذا الحقل في * تتم معالجة التكرارات التي تم إنشاؤها على طريقة عرض مجموعة HashMap في Fast Fanced */transient int modcount ؛

القدرة الأولية وتعديل أداء عامل التحميل

عادةً ما يبحث عامل التحميل الافتراضي (0.75) عن حل وسط في تكاليف الزمان والمكان. على الرغم من أن عامل التحميل مرتفع للغاية ، إلا أنه يزيد من تكلفة الاستعلام (ينعكس هذا في معظم عمليات HashMap ، بما في ذلك عمليات Get and Put). عند تحديد السعة الأولية ، يجب أخذ عدد الإدخالات المطلوبة في الخريطة وعامل التحميل الخاص بها في الاعتبار من أجل تقليل عدد عمليات إعادة الصياغة. إذا كانت السعة الأولية أكبر من الحد الأقصى لعدد الإدخالات مقسومة على عامل التحميل ، فلن تحدث عملية إعادة صياغة.

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

فيما يلي رمز إعادة بناء بنية بيانات HashMap:

 void تغيير حجم (int newCapacity) {entry [] oldtable = table ؛ int oldcapacity = oldtable.length ؛ إذا كانت (oldcapacity == maximum_capacity) {// إذا كانت السعة قد وصلت إلى الحد الأقصى ، فقم بتعيين قيمة التحميل والعودة مباشرة إلى العتبة = integer.max_value ؛ يعود؛ } // إنشاء جدول جديد لتخزين إدخال البيانات [] Newtable = إدخال جديد [NewCapacity] ؛ // نقل البيانات من الجدول القديم إلى الجدول الجديد ، ستستغرق هذه الخطوة الكثير من الوقت للنقل (Newtable ، inithashseedasneeded (NewCapacity)) ؛ الجدول = newtable ؛ // أخيرًا قم بتعيين قيمة التحميل لعتبة تغيير الحجم التالية = (int) math.min (newCapacity * loadFactor ، Maximum_Capacity + 1) ؛}

طريقة البناء hashmap

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

 /** * يبني فارغًا <tt> hashmap </tt> مع السعة الأولية الافتراضية * (16) وعامل التحميل الافتراضي (0.75). */ public hashmap () {this (default_initial_capacity ، default_load_factor) ؛ } /** * يبني فارغًا <tt> hashmap </tt> مع السعة الأولية المحددة * وعامل التحميل الافتراضي (0.75). * * param initialCapacity السعة الأولية. * therws alfictalargumentException إذا كانت السعة الأولية سلبية. */ hashmap العامة (int initialCapacity) {this (initialCapacity ، default_load_factor) ؛ } /** * يقوم بإنشاء <tt> hashmap </tt> مع السعة الأولية * المحددة وعامل التحميل. * * param initialcapacity السعة الأولية * param loadfactor عامل التحميل * athrows alficalArgumentException إذا كانت السعة الأولية سلبية * أو أن عامل التحميل غير إيجابي */ hashmap العام (int initialcapacity ، float loadfactor) {if (initialcapacity <0) ream newalargumentexception ( إذا (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity ؛ if (loadFactor <= 0 || float.isnan (loadFactor)) رمي غير alficalaRgumentException جديد ("عامل التحميل غير القانوني:" +loadFactor) ؛ this.loadFactor = loadFactor ؛ عتبة = طاقة initial ؛ init () ؛ }

كما يتضح من ما سبق ، في المُنشئ ، إذا كانت السعة الأولية أكبر من الحد الأقصى للسعة ، فسيتم استبدال الحد الأقصى للسعة مباشرة.

وضع الطريقة

بعد ذلك ، دعونا نلقي نظرة على الأجزاء الأكثر أهمية من HashMap

 /*** في هذه الخريطة ، ترتبط القيمة المحددة والبناء المحدد. إذا كانت الخريطة تحتوي مسبقًا على علاقة رسم خرائط للمفتاح ، فسيتم استبدال القيمة القديمة** param بتحديد المفتاح المراد ارتباطه* param يحدد القيمة المراد ارتباطها* @RETURN بالقيمة القديمة المرتبطة بالمفتاح ، إذا لم يكن المفتاح لا يوجد لديه علاقة تعيين ، فإنه يرجع فارغًا ({kable = {value) نفخ (عتبة) ؛ } if (key == null) return putfornullkey (value) ؛ int hash = hash (مفتاح) ؛ int i = indexfor (hash ، table.length) ؛ لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ if ( e.value = القيمة ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ }} modcount ++ ؛ addentry (التجزئة ، المفتاح ، القيمة ، i) ؛ العودة لاغية. }

1. أولاً ، في طريقة PUT ، حدد أولاً ما إذا كان الدلو في حالة الافتراضي غير المعدلة. إذا لم تتم تهيئته ، فاتصل بالطريقة القابلة للتطهير لتهيئتها ، ثم تحديد ما إذا كان مفتاح المعلمة فارغًا. إذا كان NULL ، اتصل بـ PUTFORNullkey خصيصًا لوضع البيانات بمفتاح كخلفي. إن طريقة Putfornullkey هي في الواقع نفس الخطوة 3 التالية ، باستثناء أن موقع التخزين الافتراضي للبيانات باستخدام مفتاح مثل NULL هو الأول ، أي أن The Default Screcips هو 0.

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

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

4. زيادة عدد التعديلات الهيكلية بمقدار 1

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

 addentry void (int hash ، k key ، v value ، int bucketIndex) {if ((size> = threshold) && (null! = table [bucketIndex])) {تغيير حجم (2 * table.length) ؛ 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) ؛ حجم ++ ؛ } /*** طريقة منشئ الدخول لإنشاء إدخال جديد. */ entry (int h ، k k ، v v ، entry <k ، v> n) {value = v ؛ التالي = ن ؛ المفتاح = k ؛ التجزئة = ح ؛ }

6. في طريقة Createentry ، احصل أولاً على الإدخال في الموقع المحدد ، ثم قم بإنشاء إدخال جديد. عند إنشاء الإدخال ، قم بتخزين الإدخال الأصلي في الخاصية التالية للإدخال الذي تم إنشاؤه حديثًا (راجع طريقة إنشاء الإدخال) ، واستبدل الإدخال في الموقع المحدد مع الإدخال الذي تم إنشاؤه حديثًا.

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

احصل على الطريقة

أولاً ، دعونا نلقي نظرة على الكود المصدري لطريقة GET:

 /*** إرجاع القيمة المعينة بواسطة المفتاح المحدد ؛ إذا كانت هذه الخريطة لا تحتوي على أي علاقة رسم خرائط لهذا المفتاح ، فإنها تُرجع NULL * إرجاع قيمة فارغة لا يعني بالضرورة أن الخريطة لا تحتوي على رسم خرائط للمفتاح ، وقد يغير أيضًا التعيين إلى NULL. يمكنك استخدام عملية ConteKekey للتمييز بين هاتين الحالتين * see #put (كائن ، كائن) */ public v get (مفتاح الكائن) {if (key == null) return getFornullKey () ؛ الإدخال <k ، v> entry = getentry (مفتاح) ؛ إرجاع فارغ == الدخول؟ NULL: intrad.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 ( } إرجاع فارغ ؛}

طريقة GET بسيطة للتنفيذ ، وما يلي هي خطوات قليلة:

1. أولاً ، حدد ما إذا كان المفتاح لاغ. إذا كان NULL ، فاتصل بطريقة getFornullkey للحصول عليها. إذا لم يكن فارغًا ، فاتصل بطريقة getentry للحصول عليها. إن طريقة getFornullkey هي نفسها في الأساس مثل Getentity ، ولكن هناك خطوة واحدة فقط مفقودة ، أي موقع التخزين حيث يكون المفتاح الافتراضي هو الأول ، أي ، المُخبر هو 0 ، والموقع غير محسوب.
2. تحسب طريقة getentity قيمة التجزئة بناءً على المفتاح ، ثم تحسب موقع التخزين باستخدام قيمة التجزئة وطول الدلو.
3. احصل على إدخال في الموقع المحدد كبداية للتجاوز ، وتكرار من خلال القائمة المرتبطة المفردة التالية للإدخال. إذا كانت قيمة التجزئة للإدخال متسقة مع قيمة التجزئة المحسوبة وكان مفتاح الإدخال مساوياً للذات المحددة ، فإنه يعيد الإدخال إذا كانت قيمة التجزئة للإدخال هي نفس قيمة التجزئة المحسوبة وكان مفتاح الإدخال مساوياً للمادة المحددة.
4. وفقًا للقيمة التي تم إرجاعها بواسطة Getentity ، تقوم طريقة GET بإرجاع القيمة المقابلة.

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

كائن مخصص كمفتاح لـ HashMap

 مستخدم فئة {// رقم المعرف المحمي int idnumber ؛ المستخدم العام (int id) {idnumber = id ؛ }} الفئة العامة testuser {public static void main (string [] args) {map <user ، string> map = new hashmap <user ، string> () ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {map.put (مستخدم جديد (i) ، "الاسم:"+i) ؛ } system.out.println ("اسم user3:" + map.get (مستخدم جديد (3))) ؛ }} الإخراج: user3 الاسم: فارغ

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

يجب أن تفي طريقة Equals () الصحيحة بالشروط الخمسة التالية: --- الرجوع إلى "أفكار برمجة Java" -صفحة 489

1. انعكاس. لأي x ، يجب أن يعود x.equals (x)
2. التماثل. لأي x و y ، إذا كان y.equals (x) إرجاع صحيح ، فإن x.equals (y) يعيد أيضًا صحيحًا.
3. متعدية. بالنسبة لأي x ، y ، z ، إذا كان x.equals (y) يرجع true و y.equals (z) إرجاع صحيح ، ثم x.equals (z) يجب أن يعود صحيح.
4. الاتساق ، لأي x و y ، إذا لم تتغير المعلومات المستخدمة للمقارنة المكافئة في الكائن ، ثم بغض النظر عن عدد المرات التي يتم فيها تسمية x.equals (y) ، يجب أن تكون النتيجة التي تم إرجاعها متسقة ، سواء كانت صحيحة أو خاطئة.
5. لأي X ليس فارغًا ، يجب أن يعود X.equals (NULL)

مرة أخرى : الكائن الافتراضي. لذلك ، إذا كنت ترغب في استخدام الفصل الخاص بك كمفتاح HashMap ، فيجب عليك تحميل كل من hashcode () و equals ().

يعمل الرمز التالي بشكل طبيعي:

 مستخدم فئة {// رقم المعرف المحمي int idnumber ؛ المستخدم العام (int id) {idnumber = id ؛ } Override public int hashcode () {return idnumber ؛ } Override Public Boolean يساوي (كائن OBJ) {return obj extleof user && (idnumber == ((user) obj) .idnumber) ؛ }} الفئة العامة testuser {public static void main (string [] args) {map <user ، string> map = new hashmap <user ، string> () ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {map.put (مستخدم جديد (i) ، "الاسم:"+i) ؛ } system.out.println ("اسم user3:" + map.get (مستخدم جديد (3))) ؛ }} الإخراج: اسم المستخدم: الاسم: 3

ما سبق يعيد ببساطة IdNumber باعتباره التمييز الوحيد في Hashcode ، ويمكن للمستخدمين أيضًا تنفيذ أساليبهم الخاصة وفقًا لأعمالهم الخاصة. في طريقة متساوية ، سوف تحقق مثيل HAVEL بهدوء ما إذا كان الكائن فارغًا. إذا كانت المعلمة على يسار مثيل extrlef فارغًا ، فسيتم إرجاع خطأ. إذا لم تكن معلمة متساوية () لاغية والنوع صحيحة ، فستستند المقارنة إلى عدد IdNumber الفعلي في كل كائن. كما يتضح من الإخراج ، فإن الطريقة الحالية صحيحة.

الرجوع إلى:

"أفكار برمجة جافا"

JDK 1.6 دليل المساعدة الصينية

ما سبق هو كل محتوى هذه المقالة. آمل أن يكون محتوى هذه المقالة من بعض المساعدة في دراسة أو عمل الجميع. آمل أيضًا دعم wulin.com أكثر!