المقدمة: هناك الكثير من الأشياء الجديدة المضافة بعد Java 8. لقد وجدت بعض المعلومات ذات الصلة عبر الإنترنت. بعد إساءة استخدام Hashmap ، قررت حل المعرفة ذات الصلة بنفسي. هذه المقالة للإشارة في الصورة وبعض المحتوى: http://www.vevb.com/article/80446.htm
يظهر الشكل في الشكل: إذا كان هناك أكثر من 8 عقد على دلو ، فإن بنية التخزين هي شجرة حمراء وسوداء ، وأقل من 8 هي قائمة مرتبطة في اتجاه واحد.
1: بعض خصائص hashmap
الطبقة العامة hashmap <k ، v> يمتد الملخص <k ، v> خريطة <k ، v> ، استنساخ ، قابلة للتسلسل {private static static fong serialversionuid = 36249882076318181265l ؛ 30 ؛ // عامل التعبئة الافتراضي (كانت الإصدارات السابقة تسمى أيضًا عامل التحميل) الثابتة النهائية العائمة default_load_factor = 0.75f ؛ // هذه عتبة. عندما يكون عدد القوائم المرتبطة على الدلو أكبر من هذه القيمة ، سيتم تحويله إلى شجرة حمراء وسوداء. يستخدم رمز طريقة PUT ثابتة int treeify_threshold = 8 ؛ // وهي أيضًا العتبة. عندما يكون عدد القوائم المرتبطة على الدلو أقل من هذه القيمة ، يتم تحويل الشجرة إلى قائمة مرتبطة ثابتة ثابتة int untreeify_threshold = 6 ؛ يتم تخزين مجموعة من العناصر ، ودائما مضاعفة لعقدة عابرة <k ، v> [] ؛ مجموعة عابرة <map.entry <k ، v >> إدخال ؛ // عدد العناصر المخزنة ، لاحظ أن هذا لا يساوي طول المصفوفة. حجم int العابر ؛ // العداد لكل تمدد وتغيير بنية الخريطة هو عابرة int modcount ؛ // يتم توسيع القيمة الحرجة عندما يتجاوز الحجم الفعلي (عامل ملء *) القيمة الحرجة ، يتم توسيع السعة العتبة الباحث ؛ // عامل التعويم النهائي للملء ؛2: طريقة بناء HashMap
// مُنشئ لتحديد السعة الأولية وعامل ملء hashmap العام (int initialcapity ، float loadfactor) {// السعة الأولية المحددة غير سالبة إذا (initialcapity <0) رمي غير شرعي جديد غير شرعي (قدرة أولية غير قانونية: +inialcapacity) ؛ // maximum_capacity ؛ // نسبة التعبئة إيجابية إذا (loadFactor <= 0 || float.isnan (loadFactor)) رمي غير alualtalargumentexception (عامل التحميل غير القانوني: +loadFactor) ؛ this.loadFactor = loadFactor ؛ // بعد تحديد السعة ، تحسب طريقة tablesistor القيمة الحرجة. إذا تم تجاوز القيمة عند وضع البيانات ، فسيتم توسيعها. القيمة هي بالتأكيد مضاعفة من 2.// لم يتم حفظ السعة الأولية المحددة ، ويستخدم فقط لإنشاء قيمة حرجة هذا. | = n >>> 1 ؛ n | = n >>> 2 ؛ n | = n >>> 4 ؛ n | = n >>> 8 ؛ n | = n >>> 16 ؛ // عودة متداخلة للمشغلين المثلثين (n <0)؟ 1: (n> = maximum_capacity)؟ Maximum_Capacity: n + 1 ؛} // constructor 2public HashMap (int inialCapacity) {this (initialCapacity ، default_load_factor) ؛} // constructor 3public hashmap () {this.loadfactor = default_load_factor ؛ // جميع الحقول الأخرى تخلفت}3: تحديد موضع العنصر في الصفيف عند الحصول عليه ووضعه
HAST Final int hash (مفتاح الكائن) {int h ؛ إرجاع (مفتاح == فارغ)؟ 0: (h = key.hashcode ()) ^ (H >>> 16) ؛}لتحديد الموقع
الخطوة الأولى: أول شيء هو حساب رمز التجزئة للمفتاح ، وهو رقم نوع int. فيما يلي H >>> 16 تعليقات رمز المصدر تقول: من أجل تجنب تصادم التجزئة ، ينتشر الموقف العالي إلى الموضع المنخفض ، والذي يتم بعد مراعاة العوامل المختلفة مثل السرعة والأداء.
الخطوة 2: H هي رمز التجزئة ، والطول هو طول المصفوفة [] أعلاه ، قم بنفس العملية H & (Length-1). نظرًا لأن الطول مضاعف 2 -1 ، فإن الكود الثنائي هو 1 ونتيجة 1 مع أرقام أخرى قد تكون 0 أو 1 ، وذلك لضمان التوحيد بعد العملية. أي أن طريقة التجزئة تضمن توحيد النتائج ، وهو أمر مهم للغاية وسيؤثر بشكل كبير على وضع HashMap والحصول عليه. انظر الصورة التالية للمقارنة:
الشكل 3.1 هو نتائج التجزئة غير المتماثلة
الشكل 3.2 هو نتيجة التجزئة المتوازنة
لا يوجد الكثير من البيانات في هاتين الرسوم البيانية. إذا كانت القائمة المرتبطة أطول من 8 ، فسيتم تحويلها إلى شجرة حمراء وسوداء. سيكون أكثر وضوحا في ذلك الوقت. لطالما كانت JDK8 قائمة مرتبطة من قبل. تعقيد استعلام القائمة المرتبطة هو O (n) وتعقيد الأشجار الحمراء والأسود بسبب خصائصها الخاصة هو O (log (n)). إذا كانت نتائج التجزئة غير متساوية ، فستؤثر بشكل كبير على تعقيد العملية. هناك <a href = "http://blog.chinaunix.net/uid-26575352-id-3061918.html"> مدونة المعرفة الأساسية للشجرة الحمراء والأسود </a> هناك مثال آخر على الإنترنت: يتم استخدام كائن مخصص لإنشاء مفاتيح ، وتعديل طريقة mashcode ().
الطبقة العامة mutableKeyTest {public static void main (string args []) {class mykey {integer i ؛ public void seti (integer i) {this.i = i ؛} public mykey (integer i) {this. يتم تنفيذها @Overridepublic Boolean يساوي (كائن obj) {if (obj extueof mykey) {return i.equals (((mykey) obj) .i) ؛} آخر {return false ؛ HashMap <> (25000،1) ؛ Date Begin = New Date () ؛ for (int i = 0 ؛ i <20000 ؛ i ++) {map.put (new mykey (i) ، "test" + i) ؛} date end = new date4: احصل على الطريقة
public v get (مفتاح الكائن) {node <k ، v> e ؛ return (e = getNode (hash (key) ، key)) == null؟ NULL: العقدة <k ، v> أولاً ، e ؛ int n ؛ k k ؛ // hash & (length -1) احصل على الموضع الجذر للشجرة الحمراء والأسود أو رأس القائمة المرتبطة if ((tab = table)! = null && (n = tab.length)> 0 && (first = tab [(n - 1) key.equals (k))))) مرة أخرى) hash && ((k = e.key) == مفتاح || (مفتاح! = null && key.equals (k)))) return e ؛} بينما ((e = e.next)! = null) ؛}} return null ؛}5: وضع الطريقة ، عند وضعها ، حدد موقع الدلو وفقًا لـ H & (الطول 1) ثم معرفة ما إذا كانت شجرة حمراء وسوداء أو قائمة مرتبطة و Putval
public v put (k key ، v value) {return putval (hash (key) ، key ، value ، false ، true) ؛} final v putval (int hash ، k key ، v value ، boolean omsifabsent ، boolean evict) {node <k ، v> [] tab ؛ العقدة <k ، v> p ؛ int n ، i ؛ // إذا كانت علامة التبويب فارغة أو أن يكون الطول 0 ، يتم تخصيص الذاكرة () if ((tab = table) == null || (n = tab.length) == 0) n = (tab = risze ()). length ؛ // (n - 1) & hash يجد الموضع المتوسط. إذا كان فارغًا ، putif مباشرة ((p = tab [i = (n - 1) & hash]) == null) tab [i] = newNode (hash ، key ، value ، null) ؛ else {node <k ، v> e ؛ k k ؛ // قيمة التجزئة للعقدة الأولى هي نفسها ، والقيمة الرئيسية هي نفس مفتاح الإدراج إذا (p.hash == hash && ((k = p.key) == مفتاح || (مفتاح! = null && key.equals (k))) e = p ؛ بعد Putval ، عليك اجتياز الشجرة بأكملها. عند الضرورة ، قم بتعديل القيمة لضمان خصائص الشجرة الحمراء والأسود e = (((TreeNode <k ، v>) p) .puttreeval (هذا ، علامة التبويب ، التجزئة ، القيمة ، القيمة) ؛ أخرى {// قائمة مرتبطة بـ (int bincount = 0 ؛ نهاية الجدول ، ثم قم بإنشاء عقدة جديدة hash && ((k = e.key) == مفتاح || (مفتاح! = null && key.equals (k))))) القيمة ؛ prefereAccess (e) ؛ return oldvalue ؛}} ++ modcount ؛ if (++ size> عتبة) تغيير حجم () ؛ بعد الظهر (إخلاء) ؛ إرجاع فارغ ؛}6: تغيير الحجم
العقدة النهائية <k ، v> [] تغيير حجم () {node <k ، v> [] oldtab = table ؛ int oldcap = (oldtab == null)؟ 0. && oldcap> = default_initial_capacity) newthr = oldthr << 1 ؛ // عتبة مزدوجة} آخر إذا تم وضع السعة الأولية في ThresholdNewCap = oldthr ؛ else {// Zero Zero inial Threshold باستخدام defaultNewCap = default_initial_capacity ؛ newThr = (int) (default_load_factor * default_initial_capacity) ؛ (تعويم) newcap * loadfactor ؛ newthr = (newCap <maximum_capacity && ft <(float) maximum_capacity؟ (int) ft: integer.max_value) ؛ (Node <k ، v> []) node node [newCap] ؛ table = newtab ؛ if (oldtab! = null) {for (int j = 0 ؛ j <oldcap ؛ ++ j) {node <k ، v> e ؛ 1)] = e ؛ el. if (e extueof treeNode) ((treenode <k ، v>) e) .split (هذا ، newtab ، j ، oldcap) ؛ else {// preserve ordernode <k ، v> lohead = null ، lotail = null ؛ node <k ، v> head = null = null = null ؛ node ؛ oldcap) == 0) {if (lotail == null) lohead = e ؛ elselotail.next = e ؛ otail = e ؛} else {if (hitail == null) hehead = e ؛ lohead ؛} if (hitail! = null) {hitail.next = null ؛ newtab [j + oldcap] = hihead ؛}}}}} return newtab ؛}ما سبق هو المعرفة ذات الصلة حول تحليل مبدأ التنفيذ لـ Java8 HashMap الذي قدمه لك المحرر. آمل أن يكون ذلك مفيدًا لك!