HashMap هي أيضًا مجموعة نستخدمها كثيرًا. إنه تطبيق لواجهة الخريطة يعتمد على جداول التجزئة ويوجد في شكل قيمة رئيسية. في hashmap ، تتم دائمًا معالجة قيمة المفاتيح ككل. سيقوم النظام بحساب موقع التخزين لقيمة المفاتيح بناءً على خوارزمية التجزئة. يمكننا دائمًا تخزين القيمة واستردادها من خلال المفتاح. دعنا نحلل الوصول إلى HashMap.
1. التعريف
HashMap ينفذ واجهة الخريطة ويرث الخريطة الملخص. تحدد واجهة MAP قواعد تعيين المفاتيح إلى القيم ، وتوفر فئة AbstractMAP تنفيذ العمود الفقري لواجهة الخريطة لتقليل العمل المطلوب لتنفيذ هذه الواجهة. في الواقع ، نفذت فئة AbstractMap Map. أعتقد أنه يجب أن يكون أكثر وضوحًا وضع علامة على MAP LZ هنا!
الطبقة العامة hashmap <k ، v> يمتد الملخصات <k ، v> تنفيذ خريطة <k ، v> ، استنساخ ، قابلة للتسلسل
2. وظيفة المنشئ
يوفر HashMap ثلاثة منشئين:
HashMap (): يبني hashmap فارغ مع السعة الأولية الافتراضية (16) وعامل التحميل الافتراضي (0.75).
HashMap (int initialCappacity): يقوم بإنشاء hashmap فارغة ذات سعة أولية محددة وعامل التحميل الافتراضي (0.75).
HashMap (int initialcapacity ، float loadfactor): يقوم ببناء hashmap فارغ مع سعة أولية محددة وعامل التحميل.
تم ذكر معلمتين هنا: السعة الأولية ، عامل التحميل. هاتان المعلمتان هما معلمات مهمة تؤثر على أداء hashmap. تمثل السعة عدد الدلاء في جدول التجزئة. السعة الأولية هي القدرة عند إنشاء جدول التجزئة. عامل التحميل هو مقياس يمكن أن يصل إليه جدول التجزئة قبل زيادة قدرته تلقائيًا. يقيس درجة استخدام مساحة جدول التجزئة. كلما زاد عامل التحميل ، كلما زادت درجة التحميل لجدول التجزئة ، والعكس بالعكس. بالنسبة لجداول التجزئة باستخدام طريقة القائمة المرتبطة ، فإن متوسط الوقت للعثور على عنصر هو O (1+A). لذلك ، إذا كان عامل التحميل أكبر ، فسيتم استخدام المساحة بشكل كامل ، ولكن النتيجة هي انخفاض في كفاءة البحث ؛ إذا كان عامل التحميل صغيرًا جدًا ، فستكون بيانات جدول التجزئة متناثرة للغاية ، مما يسبب نفايات خطيرة على المساحة. عامل التحميل الافتراضي للنظام هو 0.75 ، ولا نحتاج عمومًا إلى تعديله.
HashMap هي بنية بيانات تدعم الوصول السريع. لفهم أدائها ، يجب أن تفهم بنية البيانات الخاصة بها.
ثالثا. بنية البيانات
نحن نعلم أن الهياكل الأكثر استخدامًا في Java هي المصفوفات والمؤشرات المحاكاة (المراجع). يمكن تنفيذ جميع هياكل البيانات تقريبًا بالاشتراك مع هذين ، وينطبق الشيء نفسه على hashmap. في الواقع ، HashMap عبارة عن "تجزئة قائمة مرتبطة" ، كما يلي بنية البيانات الخاصة بها:
من الشكل أعلاه ، يمكننا أن نرى ما إذا كان التنفيذ الأساسي لـ HashMap هو أو صفيف ، ولكن كل عنصر في الصفيف عبارة عن سلسلة. تمثل المعلمة initialCappacity طول الصفيف. ما يلي هو الكود المصدري لمنشئ HashMap:
hashmap العامة (int initialcapacity ، float loadfactor) {// السعة الأولية لا يمكن أن تكون <0 إذا (initialCapacity <0) رمي غير alficalaRgumentException جديد ("السعة الأولية غير القانونية:" + initialCapacity) ؛ // لا يمكن للسعة الأولية> الحد الأقصى لقيمة السعة ، فإن الحد الأقصى لسعة hashMap هو 2^30 إذا (initialCapacity> maximum_capacity) partycapacity = maximum_capacity ؛ // لا يمكن أن يكون عامل التحميل <0 إذا كان (loadfactor <= 0 || float.isnan (loadFactor)) رمي غير alfictalargumentexception ("عامل التحميل غير القانوني:" + loadfactor) ؛ // احسب قيمة الطاقة N لأصغر 2 أكبر من القدرة الأولية. السعة int = 1 ؛ بينما (السعة <initialCapacity) السعة << = 1 ؛ this.loadFactor = loadFactor ؛ // تعيين حد السعة من hashmap. عندما تصل قدرة hashmap إلى هذا الحد ، سيتم تنفيذ عملية توسيع السعة عتبة = (int) (السعة * loadFactor) ؛ // تهيئة جدول صفيف الجدول = إدخال جديد [السعة] ؛ init () ؛ } كما يتضح من الكود المصدري ، سيتم تهيئة صفيف الجدول في كل مرة يتم فيها إنشاء HashMap جديد. عنصر صفيف الجدول هو عقدة دخول.
إدخال الفئة الثابت <K ، V> ينفذ map.entry <k ، v> {Final K Key ؛ V قيمة ؛ الدخول <K ، V> التالي ؛ التجزئة النهائية. /*** يخلق دخول جديد. */ entry (int h ، k k ، v v ، entry <k ، v> n) {value = v ؛ التالي = ن ؛ المفتاح = k ؛ التجزئة = ح ؛ } .....}من بينها ، الدخول هو الفئة الداخلية لـ HashMap ، والتي تحتوي على مفتاح المفتاح ، وقيمة القيمة ، والعقدة التالية ، وقيمة التجزئة. هذا مهم جدا. وذلك على وجه التحديد لأن الإدخال يشكل عناصر صفيف الجدول كقائمة مرتبطة.
يحلل المذكورة أعلاه باختصار بنية بيانات hashmap ، و أدناه سوف يستكشف كيفية تنفيذ HashMap للوصول السريع.
4. تنفيذ التخزين: PUT (KEY ، VLAUE)
أولاً ، دعونا نلقي نظرة على الكود المصدري
public v put (k key ، v value) {// عندما يكون المفتاح فارغًا ، استدعاء طريقة putfornullkey لحفظ الموضع الأول من NULL والجدول. هذا هو السبب في أن hashmap يسمح فارغة إذا (المفتاح == null) return putfornullkey (القيمة) ؛ // احسب قيمة التجزئة للتجزئة int المفتاح = key.hashCode ()) ؛ ----- (1) // حساب موضع قيمة تجزئة المفتاح في صفيف الجدول int i = indexfor (hash ، table.length) ؛ ----- (2) // تكرار من i وابحث عن الموقع الذي يتم فيه حفظ المفتاح لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ // احكم على ما إذا كانت هناك نفس قيمة التجزئة على السلسلة (المفتاح هو نفسه) // في حالة وجود نفس ، قم بكتابة القيمة مباشرةً وإرجاع القيمة القديمة إذا (e.hash == hash && ((k = e.key) == Key || key.equals (k))) {v oldvalue = e.value ؛ // القيمة القديمة = قيمة جديدة e.value = value ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ // return old value}} // زيادة عدد التعديلات بمقدار 1 modcount ++ ؛ // إضافة مفتاح وقيمة إلى Addentry Position I (التجزئة ، المفتاح ، القيمة ، i) ؛ العودة لاغية. }من خلال رمز المصدر ، يمكننا أن نرى بوضوح أن عملية حفظ بيانات HashMap هي: أولاً تحديد ما إذا كان المفتاح لاغية. إذا كان NULL ، اتصل مباشرة بالطريقة Putfornullkey. إذا لم يكن فارغًا ، فقم أولاً بحساب قيمة التجزئة للمفتاح ، ثم ابحث عن موضع الفهرس في صفيف الجدول وفقًا لقيمة التجزئة. إذا كان هناك عنصر في هذا الموضع ، قارن ما إذا كان هناك نفس المفتاح. إذا كان موجودًا ، قم بالكتابة فوق قيمة المفتاح الأصلي ، وإلا احفظ العنصر على رأس السلسلة (يتم وضع العنصر الأول المحفوظ في نهاية السلسلة). إذا لم يكن للجدول عناصر هناك ، فسيتم حفظه مباشرة. تبدو هذه العملية بسيطة ، ولكن لديها في الواقع معلومات داخلية عميقة. هناك عدة نقاط على النحو التالي:
1. دعونا نلقي نظرة على التكرار أولاً. سبب التكرار هنا هو منع وجود نفس القيمة الرئيسية. إذا تم العثور على قيمتين (مفاتيح) هما على نفس المنوال ، فإن طريقة معالجة HashMap هي استبدال القيمة القديمة بالقيمة الجديدة. لا تتم معالجة المفتاح هنا ، وهو ما يوضح أنه لا يوجد مفتاحان متطابقان في HashMap.
2. في العرض (1) و (2). هذا هو جوهر hashmap. بادئ ذي بدء ، هناك طريقة التجزئة ، وهي حساب رياضي نقي ، وهو حساب قيمة التجزئة لـ H.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12) ؛ إرجاع H ^ (H >>> 7) ^ (H >>> 4) ؛ }نحن نعلم أنه بالنسبة لجداول HashMap ، يجب أن يكون توزيع البيانات حتى (من الأفضل أن يكون لديك عنصر واحد فقط لكل عنصر ، بحيث يمكن العثور عليه مباشرة). لا يمكن أن يكون ضيقًا جدًا أو فضفاضًا جدًا. الضيق للغاية سوف يؤدي إلى سرعة استعلام بطيئة ، وسوء الفضفاضة سوف تهدر مساحة. بعد حساب قيمة التجزئة ، كيف يمكننا التأكد من توزيع عناصر الجدول بالتساوي؟ سوف نفكر في عملية الاستحواذ على العفن ، ولكن نظرًا لأن عملية الاستحواذ على العفن تستهلك الكثير ، فإن HashMap يعالجها مثل هذا: استدعاء طريقة الفهرس.
static int indexfor (int h ، int) {return h & (length-1) ؛ }طول المصفوفة الأساسية من hashmap هو دائمًا في طاقة N من 2 ، وهو موجود في المُنشئ: السعة << = 1 ؛ يمكن أن يضمن القيام بذلك دائمًا أن يكون طول المجموعة الأساسية من hashmap في طاقة N 2. عندما يكون الطول إلى N n من 2 ، H & (الطول - 1) يعادل أخذ معامل الطول ، والسرعة أسرع بكثير من أخذ المعامل مباشرة. هذا هو تحسين hashmap من حيث السرعة. أما السبب في أن 2 إلى القوة التاسعة ، فإن التفسير التالي هو.
دعنا نعود إلى طريقة الفهرس ، التي تحتوي على بيان واحد فقط: H & (الطول - 1). بالإضافة إلى عملية المعامل المذكورة أعلاه ، تتحمل هذه الجملة أيضًا مسؤولية مهمة للغاية: توزيع بيانات الجدول بالتساوي والاستفادة الكاملة من المساحة.
هنا نفترض أن الطول هو 16 (2^n) و 15 ، و h هو 5 و 6 و 7.
عندما ن = 15 ، تكون نتائج 6 و 7 هي نفسها ، مما يعني أن مواقعهم المخزنة في الجدول هي نفسها ، أي حدوث تصادم ، وسيشكل 6 و 7 قائمة مرتبطة في موقع واحد ، مما سيؤدي إلى انخفاض في سرعة الاستعلام. صحيح أنه يتم تحليل ثلاثة أرقام فقط هنا ، ولكن ليس الكثير ، لذلك دعونا ننظر إلى 0-15.
من الرسم البياني أعلاه ، نرى ما مجموعه 8 تصادمات ، وفي الوقت نفسه ، نجد أن المساحة الضائعة كبيرة جدًا ، مع عدم وجود سجلات في 1 و 3 و 5 و 7 و 9 و 11 و 13 و 15 مكانًا ، أي لا توجد بيانات. هذا لأنه عندما يقومون بأداء وتشغيل مع 14 ، فإن آخر جزء من النتيجة التي يحصلون عليها ستكون دائمًا 0 ، أي أنه من المستحيل تخزين البيانات في مواقع 0001 و 0011 و 0101 و 0111 و 1001 و 1011 و 1101 و 1111 و 1111. سيتم تقليل المساحة ، وسيتم زيادة فرصة التصادم بشكل إضافي ، والتي ستؤدي إلى سرعة التحويل البطيئة. عندما يكون الطول = 16 ، الطول 1 = 15 هو 1111. ثم عند إجراء البت المنخفض والتشغيل ، تكون القيمة دائمًا هي نفس قيمة التجزئة الأصلية ، وعند تنفيذ العملية عالية بت ، تكون قيمتها تساوي قيمتها المنخفضة بت. لذلك ، عندما يكون الطول = 2^n ، يكون احتمال الاصطدام بين قيم التجزئة المختلفة صغيرة نسبيًا ، مما سيجعل البيانات موزعة بالتساوي في صفيف الجدول وسرعة الاستعلام أسرع.
هنا نراجع عملية PUT: عندما نريد إضافة زوج من القيم الرئيسية إلى hashmap ، سيقوم النظام أولاً بحساب قيمة التجزئة للمفتاح ، ثم تأكيد الموقع المخزن في الجدول بناءً على قيمة التجزئة. إذا لم يكن هناك عنصر في هذا الموقف ، أدخله مباشرة. خلاف ذلك ، تكرار قائمة العناصر في تلك المرحلة وقارن قيمة التجزئة الخاصة به وفقًا لذلك. إذا كانت قيمتي التجزئة متساوية وكانت قيم المفاتيح متساوية (e.hash == hash && ((k = e.key) == مفتاح || key.equals (k))) ، تتم كتابة قيمة العقدة الأصلية مع قيمة الإدخال الجديد. إذا كانت قيمتي التجزئة متساوية ولكن قيم المفاتيح ليست متساوية ، فقم بإدخال العقدة في رأس القائمة المرتبطة. للاطلاع على عملية التنفيذ المحددة ، راجع طريقة الإضافة ، على النحو التالي:
addentry void (int hash ، k ، value v ، int bucketIndex) {// احصل على إدخال الإدخال <k ، v> e = table [bucketIndex] ؛ // ضع الإدخال الذي تم إنشاؤه حديثًا في فهرس BucketIndex واترك نقطة الإدخال الجديدة إلى جدول الإدخال الأصلي [bucketIndex] = إدخال جديد <K ، V> (التجزئة ، المفتاح ، القيمة ، E) ؛ // إذا تجاوز عدد العناصر الموجودة في HashMap الحد ، فستكون السعة ضعف حجمها (Size ++> = Threshold) (2 * table.length) ؛ }هناك نقطتان يجب ملاحظتهما في هذه الطريقة:
واحد هو توليد السلاسل. هذا تصميم أنيق للغاية. يضيف النظام دائمًا كائن إدخال جديد إلى BucketIndex. إذا كان هناك كائن في BucketIndex ، فسيشير كائن الإدخال الذي تمت إضافته حديثًا إلى كائن الإدخال الأصلي ، مما يشكل سلسلة إدخال. ومع ذلك ، إذا لم يكن هناك كائن إدخال في BucketIndex ، فهذا هو ، e == null ، فإن كائن الإدخال المضافة حديثًا إلى خالية ، ولن يتم إنشاء سلسلة إدخال.
2. توسيع القدرة.
مع زيادة عدد العناصر في hashmap ، يصبح احتمال الاصطدام أكبر وأكبر ، وسيصبح طول قائمة الارتباطات التي تم إنشاؤها أطول وأطول. هذا سيؤثر حتما على سرعة hashmap. من أجل ضمان كفاءة hashmap ، يجب على النظام توسيع السعة في نقطة حرجة معينة. هذه النقطة الحرجة هي عندما يكون عدد العناصر في HashMap مساوياً لعامل تحميل صفيف الجدول*. لكن القياس هو عملية تستغرق وقتًا طويلاً لأنها تتطلب إعادة حساب موقع هذه البيانات في صفيف الجدول الجديد ونسخها. لذلك إذا توقعنا عدد العناصر في HashMap ، فيمكن أن يحسن عدد العناصر المسبقة بشكل فعال أداء HashMap.
5. تنفيذ القراءة: GET (مفتاح)
بالمقارنة مع تخزين hashmap ، فإن الانسحاب بسيط نسبيًا. ابحث عن الإدخال في الفهرس في صفيف الجدول من خلال قيمة التجزئة للمفتاح ، ثم إرجاع القيمة المقابلة للمفتاح.
public v get (مفتاح الكائن) {// إذا كانت null ، اتصل بـ getFornullkey طريقة لإرجاع القيمة المقابلة إذا كانت (key == null) return getFornullkey () ؛ . // قم بإخراج القيمة في الفهرس المحدد في صفيف الجدول لـ (الإدخال <k ، v> e = table [indexfor (hash ، table.length)] ؛ e! = null ؛ e = e.next) {object k ؛ // إذا كان المفتاح الذي تم تفتيشه هو نفسه مفتاح البحث ، فأرجع القيمة المقابلة إذا ( } إرجاع فارغ ؛ } هنا ، لا يمكن فصل القيمة التي يمكن استردادها بسرعة بناءً على المفتاح فقط من بنية البيانات الخاصة بـ HashMap ، ولكن لها أيضًا الكثير لتفعله مع الدخول. كما ذكرنا سابقًا ، لا يقوم HashMap بتخزين المفتاح والقيمة بشكل منفصل في الإجراء المخزن ، ولكن تتم معالجته كقوة مفتاح كاملة ، وهو كائن الإدخال. في الوقت نفسه ، فإن القيمة تعادل فقط مرفق المفتاح. أثناء عملية التخزين ، يحدد النظام موقع تخزين الإدخال في صفيف الجدول استنادًا إلى علامة التجزئة للمفتاح ، وفي عملية الجلب ، يتم إخراج كائن الإدخال المقابل أيضًا وفقًا لرمز المفتاح.
الرابط الأصلي: http://www.cnblogs.com/chenssy/p/3521565.html
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.