حددها ، وفي الوقت نفسه ، يمكنك الجمع بين الأساليب Hashcode () بشكل جيد. Hashcode () ليس متساويًا ، يجب أن يكون مختلفًا أيضًا لتكون قادرًا على استنتاج المساواة () ؛
لأنه عندما يحصل hashmap ، قارن أولاً hashcode ، ثم قارن بين المساواة ، hashcode == && equals ، كلاهما صحيح ، لذلك يعتبر نفس المفتاح
1. نظرة عامة على هاشماب:
HashMap هو تطبيق غير متزامن لواجهة الخريطة استنادًا إلى جدول التجزئة. يوفر هذا التنفيذ جميع عمليات رسم الخرائط الاختيارية ويسمح باستخدام القيم الخالية والمفاتيح الخالية. لا يضمن هذا الفصل ترتيب التعيينات ، خاصة أنه لا يضمن استمرار الطلب.
2. بنية بيانات Hashmap:
في لغة برمجة Java ، هناك هيكلان أساسيان ، أحدهما عبارة عن صفيف والآخر هو مؤشر محاكاة (مرجع). HashMap هو في الواقع هيكل بيانات "قائمة مرتبطة" ، أي مزيج من المصفوفات والقوائم المرتبطة.
كما يتضح من الشكل أعلاه ، فإن الطبقة الأساسية من hashmap هي بنية صفيف ، وكل عنصر في الصفيف هو قائمة أخرى مرتبطة. عند إنشاء هاشماب جديد ، سيتم تهيئة صفيف.
رمز المصدر كما يلي:
/ ** الجدول ، يجب أن يكون الطول دائمًا. V Value ؛
يمكن ملاحظة أن الإدخال هو العنصر في الصفيف.
3. تطبيق الوصول إلى HashMap:
1) التخزين:
Public v put (k key ، v value) {// hashmap يسمح مفاتيح فارغة وقيم خالية. // عندما يكون المفتاح فارغًا ، اتصل بطريقة Putfornullkey ووضع القيمة في الموضع الأول من الصفيف. إذا كان (مفتاح == NULL) إرجاع putfornullkey (القيمة) ؛ int hash = key.hashcode ()) ؛ int i = indexfor (hash ، table.length) ؛ لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ ||. أن هذا لا يوجد دخول بعد. ModCount ++ ؛ Addentry (التجزئة ، القيمة ، i) ؛ من رمز المصدر أعلاه ، يمكننا أن نرى أنه عندما نضع العنصر في hashmap ، نقوم أولاً بإعادة حساب قيمة التجزئة بناءً على رمز التجزئة للمفتاح ، ووفقًا لقيمة التجزئة ، فإن موضع هذا العنصر في المصفوفة (على سبيل المثال ، Corpcript ) ، إذا كانت الصفيف عبارة عن عناصر أخرى مخزنة بالفعل في الموضع ، فسيتم تخزين العناصر الموجودة في هذا الموضع في شكل قائمة مرتبطة ، يتم وضع العناصر المضافة حديثًا على رأس السلسلة ، والأول المضافة يتم وضع تلك في نهاية السلسلة. إذا لم يكن هناك عنصر في هذا الموضع في الصفيف ، فضع العنصر مباشرة في هذا الموضع في المصفوفة.
تضع طريقة الإضافة (التجزئة ، المفتاح ، القيمة ، I) زوج القيمة الرئيسية في فهرس I لجدول الصفيف بناءً على قيمة التجزئة المحسوبة. Addentry هي طريقة لأذونات الوصول إلى الحزمة التي توفرها HashMap ، والرمز كما يلي:
addentry void (int hash ، k ، vale ، int bucketindex) {// احصل على الإدخال في إدخال BucketIndex المحدد <k ، v> e = table [bucketIndex] ؛ فهرسة ودع الإدخال الجديد إلى جدول الإدخال الأصلي [bucketIndex] = إدخال جديد <k ، v> (التجزئة ، المفتاح ، e) ؛ (Size ++> = عتبة) // قم بتوسيع طول كائن الجدول إلى ضعف الكائن الأصلي. تغيير الحجم (2 * الطول) ؛ عندما يقرر النظام تخزين زوج القيمة الرئيسية في hashmap ، لا يتم النظر في القيمة في الإدخال على الإطلاق ، ويحسب ببساطة ويحدد موقع تخزين كل إدخال بناءً على المفتاح. يمكننا التعامل تمامًا مع القيمة في مجموعة الخريطة كمرفق بالمفتاح.
تقوم طريقة التجزئة (int h) بإعادة حساب التجزئة مرة واحدة استنادًا إلى علامة التجزئة للمفتاح. تضيف هذه الخوارزمية حسابات عالية بت لمنع تعارض التجزئة التي تسببها عندما يظل البت المنخفض دون تغيير وعندما يتغير ارتفاع بت.
static int hash (int h) {h ^ = (h >> 20) ^ (h >>> 12) ؛ يمكننا أن نرى أنه لإيجاد عنصر في HashMap ، نحتاج إلى العثور على الموضع المقابل في الصفيف بناءً على قيمة التجزئة للمفتاح. كيفية حساب هذا الموقف هو خوارزمية التجزئة. كما ذكرنا سابقًا ، فإن بنية بيانات HashMap هي مزيج من المصفوفات والقوائم المرتبطة ، لذلك بالطبع نأمل أن يتم توزيع مواقع العناصر في هذا hashmap بالتساوي قدر الإمكان ، بحيث يكون عدد العناصر في كل موقف فقط واحد ثم عندما نستخدم خوارزمية التجزئة للعثور عليها عند استخدام هذا الموقف ، يمكنك على الفور أن تعرف أن العناصر في الموضع المقابل هي ما نريد كفاءة الاستعلام.
بالنسبة لأي كائن معين ، طالما أن قيمة الإرجاع HashCode () هي نفسها ، فإن قيمة رمز التجزئة المحسوبة بواسطة البرنامج الذي يستدعي طريقة التجزئة (int h) هي نفسها دائمًا. أول شيء نفكر فيه هو أن يكون Modulo قيمة التجزئة إلى طول الصفيف ، بحيث يكون توزيع العناصر موحدًا نسبيًا. ومع ذلك ، فإن عملية "Modulo" تستهلك الكثير ، ويتم ذلك في HashMap: استدعاء طريقة INDEXFOR (int h ، int) لحساب الفهرس الذي يجب تخزين الكائن في صفيف الجدول.
رمز طريقة الفهرس (int h ، طول int) هي كما يلي:
static int indexfor (int h ، int) {return h & (length-1) ؛هذه الطريقة ذكية للغاية. شروط السرعة. في مُنشئ HashMap ، هناك الرمز التالي:
السعة int = 1 ؛
يضمن هذا الرمز أن تكون قدرة hashmap دائمًا في قوة n 2 أثناء التهيئة ، أي أن طول الصفيف الأساسي هو دائمًا في قوة n 2.
عندما يكون الطول دائمًا إلى طاقة N 2 ، تكون عملية H & (الطول 1) تعادل طول Modulo ، أي طول H ٪ ، ولكن لديها كفاءة أعلى من ٪.
هذا يبدو بسيطًا للغاية ، لكنه غامض للغاية.
على افتراض أن أطوال الصفيف هي 15 و 16 ، وأن رموز التجزئة المحسنة هي 8 و 9 ، على التوالي ، ثم النتيجة بعد وعملية هي كما يلي:
H & (Table.Length-1) Hash Table.Length-1
8 & (15-1): 0100 و 1110 = 0100
9 & (15-1): 0101 و 1110 = 0100
------------------------------------------------- ------------------------------------------------- ---------------------------- ----------------------- ------------------------------------------------- ------------------------------------------------- ------ -------------------------------------------- ------------------------------------------------- ---------------------------------
8 & (16-1): 0100 و 1111 = 0100
9 & (16-1): 0101 و 1111 = 0101
كما يتضح من المثال أعلاه: عندما تكون "مع" مع 15-1 (1110) ، يتم إنتاج نفس النتيجة ، أي أنها سيتم وضعها في نفس الموقف في المصفوفة ، مما يخلق تصادمًا ، 8 وسيتم وضع 9 في نفس الموقف في الصفيف لتشكيل قائمة مرتبطة ثم عند الاستعلام ، تحتاج إلى اجتياز القائمة المرتبطة للحصول على 8 أو 9 ، مما يقلل من كفاءة الاستعلام. في الوقت نفسه ، يمكننا أيضًا أن نجد أنه عندما يكون طول الصفيف 15 ، ستكون قيمة التجزئة "مع" مع 15-1 (1110) ، ثم سيكون البت الأخير دائمًا 0 و 0001 و 0011 و 0101 و 1001 ، 1011 ، 0111 ، 0111 ، 1101 لا يمكن أن تخزن العناصر ، والمساحة تضيع كثيرًا. تزداد فرصة التصادم وكفاءة الاستعلام البطيئة! عندما يكون طول الصفيف 16 ، أي ، عندما يكون ذلك إلى قوة N من 2 ، فإن القيمة على كل جزء من الرقم الثنائي الذي تم الحصول عليه بواسطة 2n-1 هو 1 ، مما يجعل الجزء المنخفض من مجموع التجزئة الأصلية متى إنه وعلى البت المنخفض ، بحيث يزيد الجزء المنخفض من تجزئة المبلغ الذي تم الحصول عليه ، إلى جانب طريقة التجزئة (int h) بشكل أكبر من رمز التجزئة للمفتاح ويضيف حسابات عالية بت ، بحيث تكون قيمتان فقط من نفس قيمة التجزئة سيتم وضعها في نفس الموضع في الصفيف لتشكيل قائمة مرتبطة.
لذلك ، عندما يكون طول الصفيف قوى N من 2 ، فإن احتمال أن تكون المفاتيح المختلفة يمكن أن تحسب الفهرس نفسه أصغر ، لذلك سيتم توزيع البيانات بالتساوي على الصفيف ، مما يعني أن احتمال الاصطدام صغير ، نسبي ، استعلام في هذه المرة ، ليس عليك اجتياز القائمة المرتبطة في موقع معين ، وبالتالي فإن كفاءة الاستعلام ستكون أعلى.
وفقًا للرمز المصدري لطريقة PUT أعلاه ، عندما يحاول البرنامج وضع زوج من القيمة الرئيسية في hashmap ، يحدد البرنامج أولاً موقع التخزين للإدخال بناءً على قيمة إرجاع HashCode () للمفتاح: إذا مفتاح اثنين من الإدخال قيمة عودة hashcode () هي نفسها ، وموقع التخزين الخاص بهم هو نفسه. إذا كانت مفاتيح إرجاع هذين الإدخالين صحيحين من خلال مقارنة متساوية ، فإن قيمة الإدخال المضافة حديثًا ستتجاوز قيمة الإدخال الأصلي في المجموعة ، لكن المفتاح لن يتغلب عليه. إذا كانت مفاتيح إرجاع هذين الإدخالين خاطئة من خلال مقارنة متساوية ، فسيشكل الإدخال المضافة حديثًا سلسلة إدخال مع الإدخال الأصلي في المجموعة ، ويتم إدخال الإدخال المضافة حديثًا على رأس سلسلة الإدخال - تابع التفاصيل لترى وصف طريقة addentry ().
2) اقرأ:
public get (مفتاح الكائن) {if (key == null) return getFornullkey () ؛ الطول) ؛ إرجاع E.Value ؛ مع خوارزمية التجزئة المخزنة أعلاه كأساس ، من السهل فهم هذا الرمز. من رمز المصدر أعلاه ، يمكننا أن نرى أنه عند الحصول على عنصر في hashmap ، احسب أولاً رمز التجزئة للمفتاح ، والعثور على عنصر في الموضع المقابل في الصفيف ، ثم ابحث عن العنصر المطلوب في القائمة المرتبطة بالموضع المقابل من خلال طريقة متساوية من المفتاح.
3) لتلخيص ، يعالج HashMap قيمة المفتاح ككل في الأسفل ، وهذا كله هو كائن إدخال. يستخدم HashMap الأساسي إدخال [] لتخزين جميع أزواج القيمة الرئيسية. طريقة متساوية.
4. تغيير حجم Hashmap (إعادة صياغة):
نظرًا لوجود المزيد والمزيد من العناصر في هاشماب ، فإن فرصة تعارض التجزئة ترتفع وأعلى ، لأن طول الصفيف ثابت. لذلك ، من أجل تحسين كفاءة الاستعلام ، يجب توسيع عملية توسيع حجم الصفيف. يظهر: يجب إعادة حساب البيانات الموجودة في الصفيف الأصلي ووضعها في الصفيف الجديد ، والذي يتم تغيير حجمه.
إذن متى سيتم توسيع هاشماب؟ عندما يتجاوز عدد العناصر في HashMap حجم الصفيف *loadFactor ، يتم توسيع المصفوفة. وهذا يعني ، بشكل افتراضي ، حجم الصفيف هو 16. ثم عندما يتجاوز عدد العناصر في hashmap 16*0.75 = 12 ، يتم توسيع حجم الصفيف إلى 2*16 = 32 ، أي ، ضعف الحجم ، ثم إعادة حسابه. .
5. معلمات أداء HashMap:
يحتوي HashMap على المُنشئين التاليين:
HashMap (): قم بإنشاء hashmap بسعة أولية قدرها 16 وعامل تحميل قدره 0.75.
HashMap (int initialcapacity): قم ببناء hashmap بسعة أولية وعامل تحميل قدره 0.75.
HashMap (int initialcapacity ، float loadfactor): ينشئ hashmap مع السعة الأولية المحددة وعامل التحميل المحدد.
يحتوي مُنشئ HashMap الأساسي ، HashMap (int initialcappacity ، float loadfactor) ، على معلمتين ، وهما السعة الأولية الأولية وعامل التحميل.
سعة الأولي: الحد الأقصى لسعة hashmap ، أي طول الصفيف الأساسي.
LoadFactor: يتم تعريف عامل تحميل LoadFactor على النحو التالي: العدد الفعلي لعناصر جدول التجزئة (N)/سعة جدول التجزئة (M).
عامل التحميل يقيس درجة استخدام جدول التجزئة. بالنسبة لجداول التجزئة باستخدام طريقة قائمة المرتبطة ، فإن متوسط الوقت لإيجاد عنصر هو (1+أ) يكون عامل التحميل أيضًا صغيرًا ، فستكون بيانات جدول التجزئة متناثرة للغاية ، مما يسبب مضيعة خطيرة للمساحة.
في تنفيذ hashmap ، يتم تحديد الحد الأقصى لسعة hashmap بواسطة حقل العتبة:
نسخة الكود كما يلي:
عتبة = (int) (السعة * loadFactor) ؛
استنادًا إلى صيغة تعريف عامل التحميل ، يمكن ملاحظة أن العتبة هي الحد الأقصى لعدد العناصر المسموح به وفقًا لـ LoadFactor والقدرة. عامل التحميل الافتراضي 0.75 هو خيار متوازن للكفاءة المكانية والزمنية. عندما تتجاوز السعة هذه السعة القصوى ، تكون سعة hashmap غير المقيدة ضعف السعة:
if (size ++> = عتبة) تغيير حجم (2 * table.length) ؛
6. آلية فاشلة:
نحن نعلم أن java.util.hashmap ليس آمنًا لخيط الخيط ، لذلك إذا قامت مؤشرات الترابط الأخرى بتعديل الخريطة أثناء عملية استخدام Iterator ، فسيتم إلقاء ConcurrentModificationException ، وهي ما يسمى الاستراتيجية الفاشلة.
يتم تنفيذ هذه الاستراتيجية في حقل ModCount. ITerator's المتوقع.
Hashiterator () {المتوقع ؛ أثناء عملية التكرار ، حدد ما إذا كان ModCount و EnterainModcount متساويين.
لاحظ أن ModCount تم الإعلان عنه على أنه متقلب ، مما يضمن رؤية التعديلات بين المواضيع.
الإدخال النهائي <k ، v> nextentry () {if (modCount! = expectedModCount) رمي جديد convalentModificationException () ؛ في واجهة برمجة تطبيقات Hashmap ، تم ذكره:
تفشل المتكررون الذي تم إرجاعه بواسطة "طريقة عرض المجموعة" لجميع فئات HashMap: بعد إنشاء التكرار ، إذا تم تعديل التعيين من الهيكل ، ما لم يتم تمريره من خلال طريقة إزالة التكرار ، أي طريقة أخرى رمي ConcurrentModificationexception إذا تم إجراء التعديل. لذلك ، في مواجهة التعديلات المتزامنة ، سيفشل المتكرر قريبًا تمامًا دون المخاطرة بالسلوك غير المؤكد التعسفي في أوقات غير مؤكدة في المستقبل.
لاحظ أنه لا يمكن ضمان سلوك الفشل السريع للمؤلف. FAST FAIL ITERATOR يلقي مجموعة متزامنة adidification عندما تعمل بشكل أفضل. لذلك ، من الخطأ كتابة البرامج التي تعتمد على هذا الاستثناء ، والطريقة الصحيحة هي: يجب استخدام سلوك الفشل السريع للتكرار فقط للكشف عن أخطاء البرنامج.