لقد قمنا بتحليل مجموعتي ArrayList و LinkedList. نحن نعلم أنه يتم تنفيذ ArrayList على أساس المصفوفات ، ويتم تنفيذ LinkedList بناءً على قوائم مرتبطة. لكل منها مزاياها وعيوبها. على سبيل المثال ، سيكون ArrayList أفضل من LinkedList عند تحديد المواقع والبحث عن عناصر ، في حين أن LinkedList سيكون أفضل من ArrayList عند إضافة العناصر وإزالتها. يجمع HashMap الذي تم تقديمه في هذه المقالة بين مزايا كليهما. يتم تنفيذ طبقتها الأساسية بناءً على جدول التجزئة. إذا لم يتم النظر في تعارض التجزئة ، فإن تعقيد الوقت لـ HashMap بالإضافة إلى ذلك ، يمكن أن يصل عمليات الحذف والتعديل والبحث إلى O (1). دعونا نلقي نظرة أولاً على بنية جدول التجزئة الذي يستند إليه.
كما يتضح من الشكل أعلاه ، فإن جدول التجزئة عبارة عن هيكل يتكون من صفيف وقائمة مرتبطة. بالطبع ، الرقم أعلاه هو مثال سيء. يجب أن تحاول وظيفة التجزئة الجيدة متوسط توزيع العناصر في الصفيف ، وتقليل تعارضات التجزئة وتقليل طول القائمة المرتبطة. كلما طال طول القائمة المرتبطة أنه كلما زاد عدد العقد التي يجب اجتيازها أثناء البحث ، كان أداء جدول التجزئة أسوأ. بعد ذلك ، دعونا نلقي نظرة على بعض متغيرات الأعضاء في HashMap.
// السعة الافتراضية الأولية الثابتة int int default_initial_capacity = 1 << 4 ؛ // الحد الأقصى للسعة الافتراضية الثابتة النهائية int maximum_capacity = 1 << 30 ؛ // يشير عامل التحميل الافتراضي إلى الإدخال الفارغ الفارح <؟ الجدول عابر الإدخال <k ، v> [] table = (إدخال <k ، v> []) فارغ_ لآلية الفشل العابرة int modcount ؛ // استخدم العتبة الافتراضية للتجزئة البديلة int int alternative_hashing_threshold_default = integer.max_value ؛ // تساعد بذرة التجزئة العشوائية على تقليل عدد تصادمات التجزئة العابرة int int = 0 ؛
كما يتضح من متغيرات الأعضاء ، فإن السعة الأولية الافتراضية لـ HashMap هي 16 ، وعامل التحميل الافتراضي هو 0.75. العتبة هي عتبة زوج القيمة الرئيسية التي يمكن تخزينها في المجموعة. الافتراضي هو عامل التحميل الأولية*، أي 16*0.75 = 12. عندما يحتاج زوج القيمة الرئيسية إلى تجاوز العتبة ، فهذا يعني أن جدول التجزئة مشبع بالفعل في هذا الوقت. إذا تم استمرار إضافة العناصر ، فسيتم إضافة تعارض التجزئة ، مما سيؤدي إلى تدهور أداء HashMap. في هذا الوقت ، سيتم تشغيل آلية توسيع السعة التلقائية لضمان أداء HashMap. يمكننا أيضًا أن نرى أن جدول التجزئة هو في الواقع صفيف دخول ، وأن كل إدخال مخزّن في الصفيف هو عقدة الرأس للقائمة المرتبطة في اتجاه واحد. هذا الإدخال عبارة عن فئة داخلية ثابتة من HashMap ، دعنا نلقي نظرة على متغيرات الدخول الأعضاء.
إدخال الفئة الثابت <K ، V> ينفذ map.entry <k ، v> {Final K Key ؛ // مفتاح V قيمة ؛ // إدخال القيمة <K ، V> التالي ؛ // الإشارة إلى تجزئة ENT التالية ؛ // Histocode ... // حذف الكود التالي}مثيل الإدخال هو زوج قيمة مفتاح يحتوي على مفتاح وقيمة. كل مثيل إدخال لديه مرجع إلى مثيل الإدخال التالي. لتجنب الحسابات المتكررة ، يقوم كل مثيل إدخال أيضًا بتخزين رمز التجزئة المقابل. يمكن القول أن صفيف الدخول هو جوهر HashMap ، ويتم إجراء جميع العمليات لهذه الصفيف. نظرًا لأن رمز مصدر HashMap طويل نسبيًا ، فمن المستحيل تقديم جميع أساليبها بطريقة شاملة ، لذلك نركز فقط على النقاط الرئيسية لتقديمها. بعد ذلك ، سنكون موجهة نحو المشكلات ونستكشف الآلية الداخلية لـ HashMap بعمق للقضايا التالية.
1. ما هي العمليات التي تقوم بها Hashmap أثناء البناء؟
// مُنشئ ، تمرير في قدرة التهيئة وعامل الحمل hashmap (int inialcapacity ، float loadFactor) {if (initialCapacity <0) {رمي new internalargumentexception ("السعة الأولية غير القانونية:" + initialCapacity) ؛ } // إذا كانت سعة التهيئة أكبر من الحد الأقصى للسعة ، فقم بتعيينها على الحد الأقصى للسعة إذا (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity ؛ } // إذا كان عامل التحميل أقل من 0 أو عامل التحميل ليس رقمًا عائمًا ، فسيتم إلقاء استثناء إذا (loadFactor <= 0 || float.isnan (loadfactor)) {رمي جديد غير aluallargumentException ("عامل التحميل غير القانوني:" + loadfactor) ؛ } // قم بتعيين عامل التحميل this.loadFactor = loadFactor ؛ // العتبة هي عتبة سعة التهيئة = القدرة الأولية ؛ init () ؛} void init () {}جميع المنشئين سوف يطلقون على هذا المنشئ. في هذا المُنشئ ، نرى أنه بالإضافة إلى القيام ببعض التحقق من المعلمات ، فإنه يقوم بأمرين: اضبط عامل التحميل على عامل الحمل الوارد وتعيين العتبة على حجم التهيئة الواردة. طريقة init فارغة ولا تفعل شيئًا. لاحظ أنه في هذا الوقت ، لا يتم إنشاء مجموعة دخول جديدة بناءً على حجم التهيئة الواردة. إذن متى سننشئ صفيفًا جديدًا؟ استمر في القراءة.
2. ما هي العمليات التي سيتم تنفيذها عندما يضيف HashMap أزواج القيمة الرئيسية؟
// ضع أزواج القيمة الرئيسية في hashmap public v (مفتاح k ، v value) {// تهيئة if (table == فارغ_التابل) {// تهيئة جدول التجزئة (عتبة) ؛ } if (key == null) {return putfornullkey (value) ؛ } // حساب رمز التجزئة الخاص بـ int hash = مفتاح) ؛ // الموضع موقف جدول التجزئة وفقًا لرمز التجزئة int i = indexfor (hash ، table.length) ؛ لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ // إذا كان المفتاح المقابل موجودًا بالفعل ، استبدل قيمة القيمة الخاصة به وإرجاع القيمة الأصلية إذا ( e.value = القيمة ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ }} modcount ++ ؛ // إذا لم يكن هناك مفتاح مقابل ، فأضف إدخالًا إلى HashMap Addentry (Hash ، Key ، Value ، I) ؛ // Return Null Return Null ؛}يمكنك أن ترى أنه عند إضافة أزواج القيمة الرئيسية ، ستحقق أولاً ما إذا كان جدول التجزئة عبارة عن جدول فارغ ، وإذا كان جدولًا فارغًا ، فسيتم تهيئته. ثم قم بإجراء العمليات اللاحقة واتصل بوظيفة التجزئة لحساب رمز التجزئة للمفتاح الذي تم تمريره. ضع الفتحة المحددة لمجموعة الإدخال وفقًا لرمز التجزئة ، ثم اجتياز القائمة المرتبطة في اتجاه واحد من الفتحة. إذا تم تمريره بالفعل ، فسيتم إنشاء عملية بديلة ، وإلا سيتم إنشاء إدخال جديد وإضافته إلى جدول التجزئة.
3. كيف يتم تهيئة جدول التجزئة؟
// تهيئة جدول التجزئة وسوف تتوسع سعة جدول التجزئة ، لأنه من الممكن أن تكون السعة الواردة لا تملك قوة من الفراغ الخاصين الخاصين (int tosize) {// يجب أن تكون قدرة جدول التجزئة بمثابة قدرة من السعة 2 int = RoundupuptOpowOf2 (tosize) ؛ // قم بتعيين العتبة ، فيما يلي عمومًا عتبة loadFactor = (int) math.min (السعة * loadFactor ، maximum_capacity + 1) ؛ // إنشاء جدول تجزئة جديد مع جدول سعة محدد = إدخال جديد [السعة] ؛ // تهيئة بذرة التجزئة inithashseedasneeded (السعة) ؛}كما نعلم أعلاه ، عند إنشاء hashmap ، لن نقوم بإنشاء صفيف إدخال جديد ، ولكن تحقق مما إذا كان جدول التجزئة الحالي عبارة عن جدول فارغ أثناء تشغيل التشغيل. إذا كان جدولًا فارغًا ، فاتصل بالطريقة القابلة للتهيئة للتهيئة. تم نشر رمز هذه الطريقة أعلاه. يمكنك أن ترى أنه سيتم إعادة حساب سعة صفيف الدخول داخل الطريقة ، لأن حجم التهيئة الذي تم تمريره عند إنشاء HashMap قد لا يكون قوة 2 ، لذلك تحتاج إلى تحويل هذا الرقم إلى طاقة 2 ثم إنشاء صفيف إدخال جديد بناءً على السعة الجديدة. عند تهيئة جدول التجزئة ، أعد ضبط العتبة مرة أخرى ، والعتبة هي عمومًا سعة*loadFactor. بالإضافة إلى ذلك ، سيتم تهيئة بذرة التجزئة (Hassseed) عند تهيئة جدول التجزئة. يتم استخدام هذا التجزئة لتحسين وظيفة التجزئة. الافتراضي هو 0 ، ولا يتم استخدام خوارزمية تجزئة بديلة ، ولكن يمكنك أيضًا تعيين قيمة التجزئة بنفسك لتحقيق تأثير التحسين. سيتم مناقشة هذا بالتفصيل أدناه.
4. متى يحدد hashmap ما إذا كان يحتاج إلى توسيع السعة وكيف يوسع السعة؟
// أضف طريقة الإدخال وحدد أولاً ما إذا كنت تريد توسيع نطاق الإضافات الفاخرة للسعة (int hash ، k key ، v value ، int bucketIndex) {// إذا كان حجم hashmap أكبر من العتبة وقيمة الفتحة المقابلة لجدول التجزئة غير فارغ إذا (الحجم> = العتبة) && (null! عتبة ، يشير إلى أن تعارض التجزئة على وشك الحدوث ، لذلك قم بتوسيع نطاق تغيير حجم السعة (2 * Table.Length) ؛ hash = (null! = مفتاح)؟ التجزئة (مفتاح): 0 ؛ bucketIndex = indexfor (hash ، table.length) ؛ } // يظهر هنا أن حجم hashmap لا يتجاوز العتبة ، لذلك ليست هناك حاجة لتوسيع نطاق إنشاء السعة (التجزئة ، المفتاح ، القيمة ، bucketIndex) ؛} // تمديد تغيير حجم الفراغ جدول التجزئة (int newCapacity) {entable [] oldtable = table ؛ int oldcapacity = oldtable.length ؛ // إذا كانت السعة القصوى الحالية قيد الاستخدام بالفعل ، فيمكنك فقط زيادة العتبة إذا (oldcapacity == maximum_capacity) {threshold = integer.max_value ؛ يعود؛ } // خلاف ذلك ، قم بتوسيع إدخال السعة [] Newtable = إدخال جديد [NewCapacity] ؛ // طريقة نقل جدول التجزئة (newtable ، inithashseedasneeded (newCapacity)) ؛ // اضبط جدول التجزئة الحالي على جدول التجزئة الجديد = Newtable ؛ // تحديث عتبة جدول التجزئة = (int) math.min (newCapacity * loadFactor ، Maximum_Capacity + 1) ؛}عند استدعاء طريقة PUT لإضافة زوج من القيمة الرئيسية ، إذا لم يكن هناك مفتاح في المجموعة ، اتصل بطريقة الإضافة وإنشاء إدخال جديد. عندما ترى رمز الإضافة المنشور أعلاه ، قبل إنشاء إدخال جديد ، ستحدد أولاً ما إذا كان حجم عنصر المجموعة الحالي يتجاوز العتبة. إذا تجاوزت العتبة العتبة ، فاستدعاء تغيير الحجم للتوسع. السعة الجديدة التي تم تمريرها هو ضعف جدول التجزئة الأصلي. في طريقة تغيير الحجم ، سيتم إنشاء مجموعة دخول جديدة بسعة ضعف جدول التجزئة الأصلي. ثم يتم ترحيل جميع العناصر الموجودة في جدول التجزئة القديم إلى جدول التجزئة الجديد ، حيث يمكن إجراء إعادة صياغة ، وما إذا كان يتم إجراء إعادة صياغة وفقًا للقيمة التي تحسبها طريقة Inithashseedasneeded. بعد اكتمال ترحيل جدول التجزئة ، يتم استبدال جدول التجزئة الحالي بجهاز جديد ، وأخيراً تتم إعادة حساب قيمة عتبة HASHMAP بناءً على سعة جدول التجزئة الجديد.
5. لماذا يجب أن يكون حجم صفيف الدخول قوة 2؟
// إرجاع فهرس الصفيف المقابل لرمز التجزئة الثابتة int for (int h ، int) {return h & (length-1) ؛ }تحسب طريقة الفهرس المنسق المقابل في الصفيف بناءً على رمز التجزئة. يمكننا أن نرى أن المشغل (&) يستخدم داخل هذه الطريقة. تتمثل العملية في إجراء عمليات بت على اثنين من المعاملات. إذا كانت البتات المقابلة هي 1 ، فإن النتيجة هي 1 ، وإلا فهي 0. غالبًا ما يتم استخدام العمليات لإزالة قيم المعاملات عالية بت ، مثل: 01011010 & 00001111 = 00001010. دعنا نرجع إلى الكود ونرى ما تفعله H & (طول 1).
من المعروف أن الطول الذي تم تمريره هو طول صفيف الدخول. نحن نعلم أن تراكب المصفوفة يتم حسابه من 0 ، وبالتالي فإن الحد الأقصى لمصفيف الصفيف هو الطول 1. إذا كان الطول قوة 2 ، فإن البتات الثنائية ذات الطول 1 تتبعها 1. في هذا الوقت ، تتمثل وظيفة H & (Length-1) في إزالة القيمة العالية من H وترك قيمة H منخفضة فقط من H كـ The Proccist of the Array. من هذا يمكننا أن نرى أن حجم صفيف الدخول يتم تعريفه على أنه قوة 2 من أجل استخدام هذه الخوارزمية لتحديد مجموعة الصفيف.
6. كيف تحسب وظيفة التجزئة رمز التجزئة؟
// الوظيفة التي تنشئ رمز التجزئة النهائي int (الكائن k) {int h = hashseed ؛ // إذا كان المفتاح من نوع السلسلة ، فاستخدم خوارزمية تجزئة أخرى إذا (0! = H && k مثيل string) {return sun.misc.hashing.stringhash32 ((string) k) ؛ } h ^= k.hashCode () ؛ // دالة الاضطراب H ^ = (H >>> 20) ^ (H >>> 12) ؛ إرجاع H ^ (H >>> 7) ^ (H >>> 4) ؛}الخطان الأخيران من طريقة التجزئة هما الخوارزمية التي تحسب حقًا قيمة التجزئة. تسمى الخوارزمية التي تحسب رمز التجزئة وظيفة الاضطراب. تتمثل وظيفة الاضطراب المزعومة في مزج كل شيء معًا. يمكنك أن ترى أن أربع عمليات تحول من اليمين يتم استخدامها هنا. والغرض من ذلك هو مزج القيمة العالية لـ H والقيمة المنخفضة لزيادة العشوائية للقيمة المنخفضة. كما هو مذكور أعلاه ، نعلم أنه يتم تحديد ترجمة صفيف تحديد المواقع بناءً على القيمة المنخفضة البت لرمز التجزئة. يتم إنشاء رمز التجزئة الخاص بالمفتاح بواسطة طريقة HashCode ، وقد يكون للقيمة المنخفضة لرمز التجزئة الذي تم إنشاؤه بواسطة طريقة هزلية سيئة الكثير من التكرار. من أجل جعل رمز التجزئة تم تعيينه بشكل موحد نسبيًا على الصفيف ، تأتي وظيفة الاضطراب في متناول يدي ، مما يجمع بين خصائص القيمة العالية بت في القيمة المنخفضة بت ، مما يزيد من العشوائية في القيمة المنخفضة بت ، مما يجعل توزيع التجزئة أكثر فضفاضة ، وبالتالي تحسين الأداء. يعطي الشكل التالي مثالاً للمساعدة في الفهم.
7. ما الذي يحدث مع التجزئة البديلة؟
نرى أنه في طريقة التجزئة ، سيتم أولاً تعيين Hassheed إلى H. هذا التجزئة هو بذرة التجزئة ، وهي قيمة عشوائية ، وتستخدم للمساعدة في تحسين وظيفة التجزئة. Hassheed الافتراضي هو 0 ، مما يعني أن خوارزمية التجزئة البديلة لا يتم استخدامها افتراضيًا. إذن متى تستخدم هاشسي؟ أولاً ، تحتاج إلى تعيين التجزئة البديلة لتمكين ، وتعيين قيمة jdk.map.althashing.threshold في خاصية النظام. هذه القيمة هي -1 بشكل افتراضي في خاصية النظام. عندما يكون -1 ، فإن قيمة عتبة استخدام التجزئة البديلة هي integer.max_value. هذا يعني أيضًا أنه لا يمكنك أبدًا استخدام تجزئة بديلة. بالطبع ، يمكنك ضبط هذه العتبة أصغر قليلاً ، بحيث يتم إنشاء hashseed العشوائي عندما يصل العنصر المحدد إلى العتبة. هذا يزيد من العشوائية لوظيفة التجزئة. لماذا تستخدم التجزئة البديلة؟ عندما يصل العنصر المحدد إلى العتبة التي تحددها ، فهذا يعني أن جدول التجزئة مشبع نسبيًا ، وستزداد إمكانية وجود تعارضات التجزئة بشكل كبير. في هذا الوقت ، يمكن أن يؤدي استخدام وظيفة تجزئة عشوائية للعناصر المضافة إلى جعل العناصر المضافة أكثر توزيعًا بشكل عشوائي في جدول التجزئة.
ملاحظة: يعتمد جميع التحليلات المذكورة أعلاه على JDK1.7 ، وسيكون هناك تغييرات كبيرة بين الإصدارات المختلفة ، يحتاج القراء إلى الانتباه.