نظرة عامة على هاشماب
HashMap هو تطبيق غير متزامن لواجهة الخريطة استنادًا إلى جدول التجزئة. يوفر هذا التنفيذ جميع عمليات رسم الخرائط الاختيارية ويسمح باستخدام القيم الخالية والمفاتيح الخالية. لا يضمن هذا الفصل ترتيب التعيينات ، خاصة أنه لا يضمن استمرار الطلب.
بنية بيانات HashMap
في لغة برمجة Java ، هناك هيكلان أساسيان ، أحدهما صفيف والآخر هو مؤشر محاكاة (مرجع). يمكن بناء جميع هياكل البيانات باستخدام هذين الهيكلين الأساسيين ، و HashMap ليس استثناء. HashMap هي في الواقع هيكل بيانات "قائمة مرتبطة" ، أي هيكل المصفوفات والقوائم المرتبطة ، ولكن في JDK1.8
يضاف تنفيذ الشجرة الحمراء والأسود. عندما يكون طول القائمة المرتبطة أكبر من 8 ، يتم تحويله إلى بنية الشجرة الحمراء والأسود.
كما يتضح من الشكل أعلاه ، يستخدم HashMap طريقة عنوان السلسلة في Java. طريقة عنوان الارتباط ، ببساطة ، هي مزيج من المصفوفات والقوائم المرتبطة. هناك بنية قائمة مرتبطة على كل عنصر صفيف. عندما يتم تجزئة البيانات ، يتم الحصول على ترجمة الصفيف ويتم وضع البيانات في القائمة المرتبطة بالعناصر التراكمية المقابلة.
*/ عقدة الفئة الثابتة <k ، v> تنفذ map.entry <k ، v> {final int hash ؛ // المستخدمة لتحديد موضع مفتاح k النهائي ind index ؛ V قيمة ؛ العقدة <k ، v> next ؛ // العقدة التالية في عقدة القائمة المرتبطة (int hash ، k key ، v value ، node <k ، v> next) {this.hash = hash ؛ this.key = المفتاح ؛ this.value = القيمة ؛ this.next = التالي ؛ }العقدة هي فئة داخلية من hashmap ، والتي تنفذ واجهة الخريطة. ، والتي هي في الأساس خريطة (زوج القيمة الرئيسية).
في بعض الأحيان يتم وضع مفتاحين في نفس الموقف ، مما يشير إلى حدوث تصادم التجزئة. بالطبع ، كلما كانت نتائج حساب خوارزمية التجزئة أكثر اتساقًا ، كانت احتمال تصادم التجزئة أصغر ، وكلما زادت كفاءة الوصول إلى الخريطة.
هناك حقل مهم للغاية في فئة HashMap ، وهو جدول العقدة [] ، أي صفيف دلو التجزئة. من الواضح أنها مجموعة من العقد.
إذا كانت صفيف دلو التجزئة كبيرًا ، فستكون خوارزمية التجزئة الفقيرة أكثر انتخابًا. إذا كانت صفيف صفيف دلو التجزئة صغيرًا ، فسيكون حتى خوارزمية تجزئة جيدة أكثر تصادمًا ، لذلك من الضروري وزن تكلفة المساحة وتكلفة الوقت. في الواقع ، هو تحديد حجم صفيف دلو التجزئة بناءً على الموقف الفعلي ، وعلى هذا الأساس ، ستقلل خوارزمية التجزئة المصممة من تصادم التجزئة. فكيف يمكننا التحكم في الخرائط لجعل احتمال تصادمات التجزئة صغيرة ، ومصفوفات دلو التجزئة (الجداول []) تشغل مساحة أقل؟ الجواب هو خوارزمية تجزئة جيدة وآلية توسيع السعة.
قبل فهم التجزئة وعملية التوسع ، نحتاج إلى فهم العديد من مجالات HashMap. من مدونة المصدر للمصمم الافتراضي لشركة HashMap ، يمكن ملاحظة أن المُنشئ يهيئة الحقول التالية ، فإن الكود المصدري هو كما يلي:
عتبة int // القيمة الرئيسية التي يمكن استيعابها هي Ultimate Float LoadFactor ؛ // عامل تحميل int modcount ؛ حجم int
أولاً ، طول التهيئة لجدول العقدة [] (القيمة الافتراضية هو 16) ، عامل التحميل هو عامل التحميل (القيمة الافتراضية هي 0.75) ، والعتبة هي عدد العقدة (أزواج القيمة الرئيسية) لمبلغ البيانات القصوى التي يمكن أن تستوعبها HashMap. عتبة = طول * عامل التحميل. وهذا يعني ، بعد أن حدد الصفيف طوله ، كلما زاد عامل التحميل ، زادت أزواج القيمة الرئيسية التي يمكن أن تستوعبها.
استنادًا إلى صيغة تعريف عامل التحميل ، يمكن ملاحظة أن العتبة هي الحد الأقصى لعدد العناصر المسموح به وفقًا لعامل التحميل هذا وطوله (طول الصفيف). إذا تجاوز هذا الرقم هذا ، فإن تغيير الحجم (سعة التكبير). سعة hashmap الموسعة هي ضعف السعة السابقة. عامل التحميل الافتراضي 0.75 هو خيار متوازن للمساحة والوقت. يوصى بعدم تعديله إلا في حالة الوقت والمساحة الخاصة ، إذا كان هناك الكثير من مساحة الذاكرة ومتطلبات كفاءة الوقت العالية ، يمكن تقليل قيمة عامل تحميل عامل التحميل ؛ على العكس من ذلك ، إذا كانت مساحة الذاكرة ضيقة ولم تكن متطلبات الكفاءة الزمنية مرتفعة ، فيمكن زيادة قيمة عامل تحميل عامل التحميل ، والتي يمكن أن تكون أكبر من 1.
من السهل فهم حقل الحجم ، وهو عدد أزواج القيمة الرئيسية الموجودة بالفعل في HashMap. لاحظ الفرق بين طول الجدول وعدد العتبات التي تستوعب أقصى أزواج القيمة الرئيسية. يستخدم حقل ModCount بشكل أساسي لتسجيل عدد التغييرات في الهيكل الداخلي لـ HashMap ، ويستخدم بشكل أساسي للفشل السريع للتكرار. للتأكيد ، تشير التغييرات في الهيكل الداخلي إلى التغييرات في الهيكل ، مثل وضع أزواج قيمة مفتاحية جديدة ، ولكن يتم كتابة القيمة المقابلة للمفتاح ولا تنتمي إلى تغييرات هيكلية.
في hashmap ، يجب أن يكون طول جدول مجموعة دلو التجزئة في طاقة N 2 (يجب أن يكون رقمًا مركبًا). هذا تصميم غير تقليدي. التصميم التقليدي هو تصميم حجم الدلو كرقم رئيسي. نسبيا ، فإن احتمال الصراع الناجم عن الأعداد الأولية أصغر من احتمال الأرقام المركبة. للحصول على أدلة محددة ، يرجى الرجوع إلى //www.vevb.com/article/100911.htm. يقوم علامة التجزئة بتهيئة حجم الجرافة إلى 11 ، وهو تطبيق حجم الجرافة المصمم كأعداد رئيسية (لا يمكن ضمان علامة التجزئة لتكون أعدادًا رئيسية بعد التوسع). يعتمد Hashmap هذا التصميم غير التقليدي ، وذلك بشكل أساسي لتحسين عندما يكون Modulo والتوسع. في الوقت نفسه ، لتقليل النزاعات ، يضيف HashMap أيضًا عملية المشاركة العالية في الحوسبة عند تحديد موقع فهرس دلو التجزئة.
هناك مشكلة هنا. حتى إذا تم تصميم عامل التحميل وخوارزمية التجزئة بشكل معقول ، فسيكون هناك حتما وضعًا يكون فيه السوستة طويلة جدًا. بمجرد أن تكون السوستة طويلة جدًا ، فإنها ستؤثر بشكل خطير على أداء HashMap. لذلك ، في إصدار JDK1.8 ، تم تحسين بنية البيانات وتم تقديم الشجرة الحمراء والأسود. عندما يكون طول القائمة المرتبطة طويلة جدًا (يكون الافتراضي أكثر من 8) ، يتم تحويل القائمة المرتبطة إلى شجرة حمراء وسوداء. سيتم استخدام خصائص الشجرة الحمراء والأسود الإضافة والحذف والتعديلات وعمليات البحث لتحسين أداء hashmap. سيتم استخدام الإدراج والحذف والبحث عن الأشجار الحمراء والأسود لإدراج خوارزميات وحذفها وبحثها مثل الشجرة الحمراء والأسود.
تحديد موضع فهرس صفيف دلو التجزئة
تنفيذ الكود:
// الطريقة 1: تجزئة int نهائية ثابتة (مفتاح الكائن) {//jdk1.8 & jdk1.7 int h ؛ // h = key.hashcode () يحصل على قيمة hashcode للخطوة الأولى // h ^ (h >> 16) المشاركة في تشغيل الخطوة الثانية (المفتاح == فارغ)؟ 0: (h = key.hashcode ()) ^ (h >>> 16) ؛} // الطريقة 2: int index for (int h ، int length) {//jdk1.7 رمز المصدر ، jdk1.8 لا يحتوي على هذه الطريقة ، لكن مبدأ التنفيذ هو نفس الإرجاع h & (length-1) ؛ // الخطوة الثالثة تأخذ عملية المعامل}خوارزمية التجزئة هنا هي في الأساس ثلاث خطوات: أخذ قيمة Hashcode للعملية الرئيسية ، والتشغيل العالي بت ، والمعامل.
بالنسبة لأي كائن معين ، طالما أن قيمة عودة HashCode () هي نفسها ، فإن رمز التجزئة المحسوب بواسطة طريقة استدعاء البرنامج هو نفسه دائمًا. أول شيء نفكر فيه هو أن يكون Modulo قيمة التجزئة إلى طول الصفيف ، بحيث يكون توزيع العناصر موحدًا نسبيًا. ومع ذلك ، فإن استهلاك عمليات المعامل كبيرة نسبيا. يتم ذلك في HashMap: طريقة الاتصال الثانية لحساب الفهرس الذي يجب تخزين الكائن في صفيف الجدول.
هذه الطريقة ذكية جدا. إنه يحصل على أجزاء محفوظة من الكائن من خلال H & (table.length -1) ، وطول الصفيف الأساسي من hashmap هو دائمًا إلى قوة n 2 ، وهو تحسين hashmap من حيث السرعة. عندما يكون الطول دائمًا إلى طاقة N 2 ، تكون عملية H & (الطول 1) تعادل طول Modulo ، أي طول H ٪ ، ولكن لديها كفاءة أعلى من ٪.
في تنفيذ JDK1.8 ، يتم تحسين خوارزمية العمليات عالية بت ، وتنفيذ XOR منخفضة 16 بت 16 بت من Hashcode (): (H = K.HashCode ()) ^ (H >>> 16) ، والذي يعتبر أساسًا من السرعة والكفاءة والجودة. يمكن أن يضمن ذلك أنه عندما يكون طول جدول الصفيف صغيرًا نسبيًا ، يمكنه أيضًا التأكد من أن البتات متورطة في حسابات التجزئة مع مراعاة منخفضة منخفضة ، ولن يكون هناك أي عام مفرط.
فيما يلي مثال ، N هو طول الجدول.
HashMap وضع تطبيق طريقة
الفكرة العامة لوظيفة PUT هي:
يتم تنفيذ الرمز المحدد على النحو التالي:
public v put (k key ، v value) {return putval (hash (key) ، key ، value ، false ، true) ؛ } / ***طريقة لإنشاء hash* / static final int hash (مفتاح الكائن) {int h ؛ العودة (المفتاح == فارغ)؟ 0: (h = key.hashcode ()) ^ (h >>> 16) ؛ } Final v putval (int hash ، k key ، v value ، boolean omsifabsent ، evict boolean) {node <k ، v> [] tab ؛ العقدة <k ، v> p ؛ int n ، i ؛ // الحكم على ما إذا كان الجدول فارغًا ، إذا ((Tab = table) == null || (n = tab.length) == 0) n = (tab = resize ()). إذا كان الجدول [i] == NULL ، قم بإنشاء عقدة جديدة مباشرة وأضف إذا (p = tab [i = (n - 1) & hash]) == null) tab [i] = newNode (hash ، key ، value ، null) ؛ آخر {// إذا كانت العقدة المقابلة لها عقدة <k ، v> e ؛ ك ك ؛ // تحكم على ما إذا كان العنصر الأول من الجدول [i] هو نفسه المفتاح ، إذا كان الأمر نفسه ، فأخذ مباشرة القيمة إذا (p.hash == hash && ((k = p.key) == مفتاح || (المفتاح! = null && key.equals (k))) e = p ؛ // احكم على ما إذا كان الجدول [i] عبارة عن treenode ، أي ما إذا كان الجدول [i] شجرة أسود حمراء. إذا كانت شجرة أسود أحمر ، فقم بإدخال زوج القيمة المفاتيح مباشرة في الشجرة الأخرى إذا كان (p exateof treenode) e = ((treenode <k ، v>) p) .puttreeval (هذا ، علامة التبويب ، التجزئة ، المفتاح ، القيمة) ؛ // هذه السلسلة عبارة عن قائمة مرتبطة أخرى {// transipate من خلال الجدول [i] لتحديد ما إذا كان طول القائمة المرتبطة أكبر من treeify_threshold (القيمة الافتراضية هي 8). إذا كان أكبر من 8 ، فقم بتحويل القائمة المرتبطة إلى شجرة أسود حمراء وقم بتنفيذ عملية الإدراج في شجرة السوداء الحمراء. خلاف ذلك ، يتم تنفيذ تشغيل الإدراج للقائمة المرتبطة ؛ إذا تبين أن المفتاح لديه بالفعل قيمة الكتابة المباشرة أثناء عملية اجتياز ؛ لـ (int bincount = 0 ؛ ؛ ++ bincount) {if ((e = p.next) == null) {p.next = newNode (hash ، key ، value ، null) ؛ if (bincount> = treeify_threshold - 1) // -1 for 1st treeifybin (علامة التبويب ، التجزئة) ؛ استراحة؛ } if ( P = ه ؛ }} // اكتب if (e! = null) {// mapping for key v oldvalue = e.value ؛ if (! omsifabsent || oldvalue == null) e.value = value ؛ postodeaccess (e) ؛ إرجاع Oldvalue ؛ }} ++ modcount ؛ // بعد نجاح الإدراج ، حدد ما إذا كان العدد الفعلي لأزواج القيمة الرئيسية يتجاوز الحد الأقصى لحالة السعة. إذا تجاوزت السعة ، فتوسيع إذا كان (++ حجم> عتبة) تغيير حجم () ؛ بعد الظهر (إخلاء) ؛ العودة لاغية. }HashMap الحصول على تنفيذ الطريقة
الفكرة هي كما يلي:
1. العقدة الأولى في الدلو ، ضرب مباشرة ؛
2. إذا كان هناك تعارض ، استخدم المفتاح.
إذا كانت شجرة ، فابحث في الشجرة من خلال key.equals (k) ، o (logn) ؛
إذا كانت قائمة مرتبطة ، فابحث من خلال key.equals (k) في القائمة المرتبطة ، o (n).
public v get (Object Key) {node <k ، v> e ؛ إرجاع (e = getNode (hash (مفتاح) ، مفتاح)) == فارغ؟ NULL: E.Value ؛ } العقدة النهائية <k ، v> getNode (int hash ، مفتاح الكائن) {node <k ، v> [] tab ؛ العقدة <k ، v> أولاً ، e ؛ int n ؛ ك ك ؛ if ((tab = table)! = null && (n = tab.length)> 0 && (first = tab [(n - 1) & hash])! = null) {// hit مباشرة if (first.hash == hash && / / in in checked in in in in in ؛ // غاب if ((e = first.next)! = null) {// get if (first extimentof treenode) return ((treenode <k ، v>) first) .getTreeNode (hash ، key) ؛ // get do {if (E.Hash == hash && ((k = } بينما ((e = e.next)! = null) ؛ }} الإرجاع null ؛ }آلية توسيع القدرات
تغيير الحجم يعني إعادة حساب القدرة وإضافة عناصر باستمرار إلى كائن hashmap. عندما لا يستطيع الصفيف داخل كائن HashMap تحميل المزيد من العناصر ، يحتاج الكائن إلى توسيع طول الصفيف بحيث يمكن تحميل المزيد من العناصر. بالطبع ، لا يمكن توسيع المصفوفات في Java تلقائيًا. تتمثل الطريقة في استخدام صفيف جديد بدلاً من المصفوفات الموجودة بسعة صغيرة ، تمامًا مثلما نستخدم دلوًا صغيرًا لملء الماء. إذا كنا نريد ملء المزيد من الماء ، فيجب علينا استبداله بدلاء كبير.
نقوم بتحليل رمز المصدر للتغيير حجم. بالنظر إلى أن JDK1.8 يدمج الأشجار الحمراء والأسود ، فهو أكثر تعقيدًا. من أجل تسهيل الفهم ، ما زلنا نستخدم رمز JDK1.7 ، وهو أمر أسهل في الفهم. هناك اختلاف ضئيل في الجوهر. دعنا نتحدث عن الاختلافات المحددة لاحقًا.
void تغيير حجم (int newCapacity) {// الإيقاف الإيقاف السعة الجديدة [] oldtable = table ؛ // الرجوع إلى صفيف الدخول قبل التوسع int oldcapacity = oldtable.length ؛ إذا (oldcapacity == maximum_capacity) {// إذا كان حجم الصفيف قبل التوسع قد وصل إلى الحد الأقصى (2^30) عتبة = integer.max_value ؛ // تعديل العتبة إلى الحد الأقصى لقيمة int (2^31-1) ، بحيث لن يتم توسيع السعة في العائد المستقبلي ؛ } الإدخال [] newtable = إدخال جديد [newCapacity] ؛ // تهيئة نقل صفيف الدخول الجديد (Newtable) ؛ //! ! نقل البيانات إلى جدول صفيف الإدخال الجديد = Newtable ؛ // تشير سمة جدول HashMap إلى عتبة صفيف الإدخال الجديدة = (int) (NewCapacity * loadFactor) ؛ // تعديل العتبة}نستخدم هنا صفيفًا بسعة أكبر بدلاً من الصفيف الموجود بسعة أصغر. تقوم طريقة النقل () بنسخ عناصر صفيف الإدخال الأصلي إلى صفيف الدخول الجديد.
نقل void (إدخال [] newtable) {entry [] src = table ؛ // يشير SRC إلى صفيف الدخول القديم int newCapacity = newtable.length ؛ لـ (int j = 0 ؛ j <src.length ؛ j ++) {// tranquility من خلال إدخال صفيف الإدخال القديم <k ، v> e = src [j] ؛ // احصل على كل عنصر من عناصر صفيف الإدخال القديم إذا كان (e! = null) {src [j] = null ؛ // قم بإطلاق مرجع كائن صفيف الإدخال القديم (بعد الحلقة for ، لم يعد صفيف الإدخال القديم يشير إلى أي كائن) do {entry <k ، v> next = e.next ؛ int i = indexfor (E.Hash ، newCapacity) ؛ //! ! إعادة حساب موضع كل عنصر في الصفيف e.next = newtable [i] ؛ // tag [1] newtable [i] = e ؛ // ضع العنصر على الصفيف E = التالي ؛ // الوصول إلى العنصر في سلسلة الإدخال التالية} بينما (e! = null) ؛ }}}يتم تعيين الإشارة إلى NewTable [i] إلى E.Next ، مما يعني أن طريقة إدخال الرأس في قائمة مرتبطة واحدة تستخدم. سيتم دائمًا وضع عناصر جديدة في نفس الموقف على رأس القائمة المرتبطة ؛ وبهذه الطريقة ، سيتم وضع العناصر الموضوعة على الفهرس في نهاية المطاف في نهاية سلسلة الدخول (في حالة حدوث تعارض التجزئة). هذا يختلف عن JDK1.8 ، والذي تم شرحه بالتفصيل أدناه. يمكن وضع عناصر على نفس سلسلة الدخول في الصفيف القديم في مواقع مختلفة في الصفيف الجديد بعد إعادة حساب موضع الفهرس.
فيما يلي مثال لتوضيح عملية توسيع السعة. افترض أن خوارزمية التجزئة الخاصة بنا تستخدم ببساطة mod مفتاح للحصول على حجم الجدول (أي طول الصفيف). حجم جدول صفيف دلو التجزئة = 2 ، وبالتالي المفتاح = 3 ، 7 ، 5 ، وترتيب وضع 5 و 7 و 3. بعد MOD 2 ، يكون الصراع في الجدول [1]. هنا ، من المفترض أن يكون عامل التحميل loadfactor = 1 ، أي عندما يكون الحجم الفعلي لزوج القيمة الرئيسية أكبر من الحجم الفعلي للجدول ، يتم توسيعه. الخطوات الثلاث التالية هي عملية تغيير حجم مجموعة دلو التجزئة إلى 4 ، ثم إعادة صياغة جميع العقد.
دعنا نوضح ما هي التحسينات التي تم إجراؤها في JDK1.8. بعد الملاحظة ، يمكننا أن نجد أننا نستخدم قوة التوسع (في إشارة إلى طول المرتين الأصل) ، وبالتالي فإن موضع العنصر إما في الموضع الأصلي أو يحرك موضع قوة اثنين مرة أخرى في الموضع الأصلي. بالنظر إلى الشكل أدناه ، يمكنك فهم معنى هذه الجملة. ن هو طول الجدول. يمثل الشكل (أ) مثالًا لموضع الفهرس للمفتاحين اللذين يحددان موضع الفهرس للمفتاح 1 و Key2 قبل التوسع. يمثل الشكل (ب) مثالًا لموضع الفهرس لـ Key1 و Key2 بعد التوسع. حيث HASH1 هي نتيجة تشغيل التجزئة والعالي بتات المقابلة لـ KEY1.
بعد أن يعيد العنصر إعادة حساب التجزئة ، نظرًا لأن N يصبح مرتين ، فإن نطاق قناع N-1 هو 1 بت (أحمر) عند النقطة العالية ، وبالتالي فإن الفهرس الجديد سيتغير مثل هذا:
لذلك ، عندما نوسع hashmap ، لا نحتاج إلى إعادة حساب التجزئة مثل تنفيذ JDK1.7. نحتاج فقط إلى معرفة ما إذا كانت الإضافات إلى قيمة التجزئة الأصلية هي 1 أو 0. إذا كانت 0 ، فإن الفهرس لم يتغير. إذا كان 1 ، يصبح الفهرس "INDEX Original + Oldcap". يمكنك رؤية الرقم التالي على أنه مخطط تغيير حجمه مع توسيع 16 إلى 32:
هذا التصميم ذكي بالفعل ، والذي لا يوفر الوقت فقط لإعادة حساب قيمة التجزئة ، ولكن أيضًا ، نظرًا لأن 1Bit المضافة حديثًا هي 0 أو 1 ، يمكن اعتبارها عشوائية ، وبالتالي فإن عملية تغيير الحجم توزع بالتساوي العقد السابقة المتضاربة على الدلو الجديد. هذه هي نقطة التحسين الجديدة التي تمت إضافتها بواسطة JDK1.8. هناك القليل من الاهتمام للفرق. عند إعادة صياغة في JDK1.7 ، عندما تقوم القوائم المرتبطة القديمة بترحيل القوائم المرتبطة الجديدة ، إذا كان موضع فهرس الصفيف للجدول الجديد هو نفسه ، فلن يتم قلب عناصر القائمة المرتبطة ، ولكن كما يمكن رؤيتها من الشكل أعلاه ، فلن يتم قلب JDK1.8. يمكن للطلاب المهتمين دراسة رمز المصدر المصدر من JDK1.8 ، وهو أمر جيد جدًا ، على النحو التالي:
العقدة النهائية <k ، v> [] تغيير حجم () {node <k ، v> [] oldtab = table ؛ int oldcap = (oldtab == null)؟ 0: oldtab.length ؛ int oldthr = عتبة ؛ int newcap ، newthr = 0 ؛ إذا كانت (OldCap> 0) {// إذا تجاوزت القيمة القصوى ، فلن يتم توسيعها بعد الآن ، لذلك يجب أن أصطدم معك إذا (oldcap> = maximum_capacity) {threshold = integer.max_value ؛ إرجاع Oldtab. } // إذا لم يتم تجاوز القيمة القصوى ، فسيتم توسيعها إلى مرتين الأصل IF ((NewCap = Oldcap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newthr = oldthr << 1 ؛ // عتبة مزدوجة} آخر إذا تم وضع السعة الأولية (Oldther> 0) // في عتبة NewCap = Oldthr ؛ تشير العتبة الأولية {Zero // Zero إلى استخدام الافتراضات NewCap = default_initial_capacity ؛ newthr = (int) (default_load_factor * default_initial_capacity) ؛ }. newthr = (newCap <maximum_capacity && ft <(float) maximum_capacity؟ (int) ft: integer.max_value) ؛ } عتبة = newthr ؛ suppressWarnings ({"rawtypes" ، "unched"}) العقدة <k ، v> [] newtab = (node <k ، v> []) node [newCap] ؛ الجدول = نيوتاب ؛ if (oldtab! = null) {// انقل كل دلو إلى الدلاء الجديدة لـ (int j = 0 ؛ j <oldcap ؛ ++ j) {node <k ، v> e ؛ if ((e = oldtab [j])! = null) {oldtab [j] = null ؛ if ( آخر إذا (e extureof treenode) ((treenode <k ، v>) e) .split (هذا ، Newtab ، J ، Oldcap) ؛ Else {// Preserve Order Node <k ، v> lohead = null ، lotail = null ؛ العقدة <k ، v> hihead = null ، hitail = null ؛ العقدة <k ، v> التالية ؛ do {next = e.next ؛ // الفهرس الأصلي if ((e.hash & oldcap) == 0) {if (lotail == null) lohead = e ؛ آخر lotail.next = e ؛ lotail = e ؛ } // الفهرس الأصلي + oldcap آخر {if (hitail == null) hihead = e ؛ آخر hitail.next = e ؛ hitail = e ؛ }} بينما ((e = التالي)! = null) ؛ // ضع الفهرس الأصلي في الدلو if (lotail! = null) {lotail.next = null ؛ Newtab [j] = loead ؛ } // ضع الفهرس الأصلي + oldcap في الجرافة إذا (hitail! = null) {hitail.next = null ؛ Newtab [j + oldcap] = hihead ؛ }}}}} إرجاع newtab ؛}لخص
يمكننا الآن الإجابة على العديد من الأسئلة في البداية لتعميق فهمنا للهاشماب:
1. متى سيتم استخدام Hashmap؟ ما هي خصائصه؟
يعتمد على تنفيذ واجهة الخريطة. عند تخزين أزواج القيمة الرئيسية ، يمكن أن تتلقى قيم مفتاح فارغة ، وهو غير متزامن. HashMap Stores Entry (Hash ، Key ، Value ، Next) Objects.
2. هل تعرف كيف يعمل hashmap؟
من خلال طريقة التجزئة ، يتم تخزين الكائنات والحصول عليها من خلال put and get. عند تخزين كائن ، عندما نمرر K/V إلى طريقة PUT ، فإنه يستدعي HashCode لحساب التجزئة للحصول على موقع الجرافة وتخزينه بشكل أكبر. ستقوم HashMAP تلقائيًا بضبط السعة وفقًا لمهنة الجرافة الحالية (إذا تجاوزت تحميل Facotr ، فإن تغيير الحجم هو ضعف الأصل). عند الحصول على الكائن ، نقوم بتمرير K ، الذي يستدعي HashCode لحساب التجزئة للحصول على موضع الجرافة ، ومكالمات إضافية على طريقة متساوية () لتحديد زوج القيمة الرئيسية. في حالة حدوث تصادم ، ينظم HashMap العناصر التي تولد تعارضات تصادم من خلال القائمة المرتبطة. في Java 8 ، إذا تجاوزت العناصر التي تصطدم في دلو حد معين (الافتراضي هو 8) ، يتم استخدام شجرة حمراء وسوداء لاستبدال القائمة المرتبطة لزيادة السرعة.
3. هل تعرف مبادئ الحصول على وتوضع؟ ما هي وظائف equals () و hashcode ()؟
عن طريق تجزئة الرمز البري () للمفتاح وحساب المُخبر (N-1 & hash) ، يتم الحصول على موضع الدلاء. في حالة حدوث تصادم ، استخدم طريقة key.equals () للبحث عن العقدة المقابلة في القائمة أو الشجرة المرتبطة
4. هل تعرف تنفيذ التجزئة؟ لماذا أحتاج إلى القيام بذلك؟
في تنفيذ Java 1.8 ، يتم تنفيذها من خلال X-X-OR عالية 16 بت من Hashcode (): (H = K.HashCode ()) ^ (H >>> 16) ، والتي تعتبر أساسًا من السرعة والكفاءة والجودة. يمكن أن يضمن ذلك أنه عندما يكون N للدلو صغيرًا نسبيًا ، يمكنه أيضًا التأكد من أن كل من البتات العالية والمنخفضة متورطة في حساب التجزئة ، ولن يكون هناك أي عام مفرط.
5. ماذا لو تجاوز حجم hashmap السعة المحددة بواسطة عامل التحميل؟
إذا تم تجاوز عامل التحميل (افتراضي 0.75) ، فسيتم تغيير حجم HashMap مع ضعف الطول الأصلي وسيتم استدعاء طريقة التجزئة مرة أخرى.
تم وصف ورقة الغش حول مجموعات Java على النحو التالي:
مجموعة دلو التجزئة التي تم تنفيذها باستخدام صفيف الإدخال [] ، ويمكن استخدام قيمة التجزئة للمفتاح للحصول على ترجمة الصفيف.
عند إدخال عنصر ما ، إذا سقط مفتاحان في نفس الدلو (على سبيل المثال ، بعد قيم التجزئة 1 و 17 هما Modulo 16 ، كلاهما ينتمي إلى دلو التجزئة الأول) ، يستخدم الإدخال خاصية التالية لتنفيذ إدخال متعددة في قائمة مرتبطة في اتجاه واحد ، والإدخال الذي يدخل نقاط الدلو بجوار الإدخال الحالي للجرافة.
عند البحث عن مفتاح ذي قيمة تجزئة قدرها 17 ، حدد موقع دلو التجزئة الأول أولاً ، ثم تكرار جميع العناصر في الدلو مع قائمة مرتبطة ، وقارن قيمها الرئيسية واحدة تلو الأخرى.
عندما يصل عدد الدخول إلى 75 ٪ من الدلاء (تشير العديد من المقالات إلى أن عدد الدلاء المستخدمة يصل إلى 75 ٪ ، ولكن وفقًا للرمز ، سيتم توسيع مجموعة الجرافات بشكل كبير وسيتم إعادة تعيين جميع الإدخال الأصلي ، لذلك من الأفضل أن يكون لها قيمة تقديرية هنا.
ستكون عملية البتات (التجزئة و (ArrayLength-1)) أسرع ، وبالتالي فإن حجم الصفيف دائمًا إلى طاقة N 2.
يعبر ITerator () على طول مجموعة دلو التجزئة ، والتي تبدو وكأنها خارج الترتيب.
6. ماذا يحدث عندما يكون رمز هش في كائنين هو نفسه؟
نظرًا لأن رمز الهاش هو نفسه ، فإن موضع الجرافة هو نفسه ، وسيحدث "تصادم". نظرًا لأن HashMap يستخدم قائمة مرتبطة لتخزين الكائنات ، يتم تخزين هذا الإدخال (الخريطة. كائن entry الذي يحتوي على أزواج قيمة المفاتيح) في القائمة المرتبطة.
7. إذا كان رمز hashcode من مفتاحين هو نفسه ، فكيف تحصل على كائن القيمة؟
بعد العثور على موقع الجرافة ، سيتم استدعاء طريقة المفاتيح. لذلك ، عند تصميم النوع الرئيسي من hashmap ، إذا تم الإعلان عن كائن غير قابل للتغيير على أنه نهائي وسيتم استخدام أساليب الهاوية () و hashcode () ، سيتم تقليل حدوث تصادمات وسيتم تحسين الكفاءة. لا يمكن للتأثير ذاكرة التخزين المؤقت لمفاتيح مختلفة ، مما سيزيد من سرعة الحصول على الكائن بأكمله. يعد استخدام فئات Wrapper مثل String و Interger As Keys اختيارًا جيدًا جدًا.
8. ماذا لو تجاوز حجم hashmap السعة المحددة بواسطة عامل التحميل؟
حجم عامل التحميل الافتراضي هو 0.75. وهذا يعني أنه عندما تملأ الخريطة 75 ٪ من الدلاء ، مثل فئات التجميع الأخرى (مثل ArrayList ، وما إلى ذلك) ، سيتم إنشاء مجموعة دلو التي يبلغ حجمها ضعف حجم hashmap الأصلي لتغيير حجم الخريطة ووضع الكائن الأصلي في مجموعة الجرافة الجديدة. تسمى هذه العملية إعادة صياغة لأنها تسمي طريقة التجزئة للعثور على موقع الجرافة الجديد
9. هل تفهم ما هو الخطأ في تغيير حجم hashmap؟
عند تغيير حجم HashMap ، هناك بالفعل منافسة مشروطة ، لأنه إذا وجد كلا الموضوعين أن HashMap يحتاج إلى تغيير حجمه ، فسوف يحاولان تغيير الحجم في نفس الوقت. أثناء عملية تغيير الحجم ، سيتم عكس ترتيب العناصر المخزنة في القائمة المرتبطة ، لأنه عند الانتقال إلى وضع الجرافة الجديد ، لا يضع HashMap العناصر في نهاية القائمة المرتبطة ، ولكن في الرأس ، وهو تجنب عبور الذيل. إذا حدثت منافسة مشروطة ، فهناك دورة مفرغة. لذلك ، في بيئة متزامنة ، نستخدم CurrentHashMap لاستبدال hashmap
10. لماذا فئات الغلاف مثل String و Interger مناسبة كمفاتيح؟
لأن السلسلة غير قابلة للتغيير والنهائي ، وتم إعادة كتابة أساليب المساواة () و HashCode (). فصول غلاف أخرى لديها أيضا هذه الميزة. التثبيت ضروري لأنه من أجل حساب Hashcode () ، يجب أن تمنع القيمة الرئيسية من التغيير. إذا كانت قيمة المفتاح تُرجع رمزًا مختلفًا عند وضعه والحصول عليه ، فلا يمكنك العثور على الكائن الذي تريده من HashMap. الثبات له مزايا أخرى مثل سلامة الخيط. إذا كان بإمكانك ضمان عدم تغيير رمز hashcode بمجرد إعلان حقل كنهائي ، فيرجى القيام بذلك. نظرًا لأن أساليب المساواة () و hashcode () يتم استخدامها عند الحصول على الكائنات ، من المهم جدًا إعادة كتابة هاتين الطريقتين بشكل صحيح. إذا عاد كائنان غير متكافئين إلى هاشكات مختلفة ، فستكون فرصة الاصطدام أصغر ، مما سيحسن أداء hashmap
شكرا لك على القراءة ، آمل أن تساعدك. شكرا لك على دعمك لهذا الموقع!