نحن نعلم أن جدول التجزئة عبارة عن بنية بيانات فعالة للغاية ، وأن تصميمًا ممتازًا لوظيفة التجزئة يمكن أن يجعل عمليات الإضافة والحذف والتعديل والبحث عليها تصل إلى مستوى O (1). توفر لنا Java بنية تجزئة جاهزة ، أي فئة HashMap. في المقالة السابقة ، قدمت فئة HashMap وأعلنت أن جميع أساليبها لم تتم مزامنتها ، لذلك فهي ليست آمنة في بيئة متعددة الخيوط. تحقيقًا لهذه الغاية ، توفر لنا Java فئة أخرى من الهاش ، وهي بسيطة للغاية وخام في التعامل مع المزامنة متعددة الخيوط ، أي لقفل جميع أساليبها باستخدام الكلمة الرئيسية المتزامنة استنادًا إلى hashmap. على الرغم من أن هذه الطريقة بسيطة ، إلا أنها تؤدي إلى مشكلة ، أي أن موضوع واحد فقط يمكنه تشغيل جدول التجزئة في نفس الوقت. حتى إذا كانت هذه الخيوط هي عمليات القراءة فقط ، فيجب أن تكون قائمة الانتظار ، والتي تؤثر بشكل كبير على الأداء في بيئات متعددة الخيوط تنافسية للغاية. و concurrenthashmap المقدمة في هذه المقالة هو حل هذه المشكلة. يستخدم أقفال مجزأة لتخليص الأقفال ، بحيث يمكن لخيوط متعددة تشغيل جدول التجزئة في نفس الوقت ، مما يحسن الأداء بشكل كبير. الشكل التالي هو رسم تخطيطي لهيكله الداخلي.
1. ما هي متغيرات الأعضاء التي يمتلكها ConcurrenthashMap؟
// قدرة التهيئة الافتراضية ثابتة int int default_initial_capacity = 16 ؛ // عامل التحميل الافتراضي ثابت ، Final Float default_load_factor = 0.75f ؛ min_segress_table_capacity = 2 ؛ // أقصى عدد من أقفال القطاع الثابتة النهائية int max_segments = 1 << 16 ؛ // عدد عمليات إعادة المحاكاة قبل قفل int int static int static_before_lock = 2 ؛ // قناع قيمة قفل القفل النهائي int segmentsk ؛
قبل قراءة هذا المقال ، أعتقد أنه لا يمكن للقراء فهم المعنى المحدد ووظيفة متغيرات الأعضاء هذه ، ولكن يُنصح القراء بالقراءة بصبر. سيتم تقديم دور هذه المتغيرات الأعضاء واحدة تلو الأخرى في السيناريوهات المحددة لاحقًا. هنا يحتاج القراء فقط إلى ترك نظرة مألوفة على متغيرات الأعضاء هذه. ومع ذلك ، لا تزال هناك بعض المتغيرات التي نحتاج إلى معرفتها الآن. على سبيل المثال ، يمثل صفيف القطاع مجموعة من أقفال القطاع ، ويمثل مستوى التزامن عدد أقفال القطاع (وهو ما يعني أيضًا عدد المواضيع التي يمكن أن تعمل في نفس الوقت) ، وتمثل سعة التهيئة سعة الحاوية بأكملها ، ويمثل عامل التحميل مستوى مدى امتلاء عناصر الحاوية.
2. ما هو الهيكل الداخلي لقفل القطاع؟
// قفل القطاع الجزء الثابت فئة نهائية <k ، v> يمتد reentrantlock الأدوات التسلسلية {// الحد الأقصى رقم الدوران static int int max_scan_retries = runtime.getRuntime (). 64: 1 ؛ // hast table transient hashentry <k ، v> [] table ؛ // إجمالي عدد العناصر العابرة لعدد الباحث ؛ // عدد التعديلات العابرة int modcount ؛ // عتبة عنصر عابرة العابرة ؛ // عامل التحميل float loadfactor ؛ // حذف المحتوى التالي ...}الجزء هو فئة داخلية ثابتة من concurrenthashmap ، يمكنك أن ترى أنها ترث من reentrantlock ، لذلك هو في الأساس قفل. إنه يحمل صفيف التجزئة (جدول التجزئة) داخليًا ، ويضمن أن جميع طرق إضافة وحذف وتعديل الصفيف آمنًا للمعلومات. سيتم مناقشة التنفيذ المحدد لاحقًا. يمكن تكليف جميع العمليات المتعلقة بإضافة وحذف وتعديل وفحص ConcurrentHashMap إلى القطاع ، لذلك يمكن أن يضمن ConcurrenthashMap أنها آمنة في بيئة متعددة الخيوط. أيضًا ، نظرًا لأن الأجزاء المختلفة عبارة عن أقفال مختلفة ، يمكن أن تعمل أشكال MultiThreads على تشغيل شرائح مختلفة في نفس الوقت ، مما يعني أنه يمكن أن تعمل Multithreads على concurrenthashmap في نفس الوقت ، والتي يمكن أن تتجنب عيوب التجزئة وتحسين الأداء بشكل كبير.
3. ماذا تهيئة ConcurrentHashMap؟
// Core ConstructorSuppressWarnings ("Unchected") concurrenthashmap العامة (int initialcapacity ، float loadfactor ، int concrencylevel) {if (! (loadfactor> 0) || initialCapacity <0 || concrencylevel <= 0) {throw infrensexpiceexpiceexpice () ؛ } // تأكد من أن مستوى التزامن ليس أكبر من الحد (concurrencyLevel> max_segments) {concurrencylevel = max_segments ؛ } int sshift = 0 ؛ int ssize = 1 ؛ // تأكد من أن ssize هي قوة 2 ، وهي أقرب عدد أكبر من أو يساوي مستوى التزامن بينما (ssize <concrencylevel) {++ sshift ؛ ssize << = 1 ؛ } // حساب قيمة التحول لقفل القطاع this.segressshift = 32 - sshift ؛ // احسب قيمة القناع لقفل القطاع this.segmentmask = ssize - 1 ؛ // لا يمكن أن تكون السعة الإجمالية الأولية أكبر من قيمة الحد إذا (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity ؛ } // احصل على السعة الأولية لكل قفل قطاع int c = initialCappacity /ssize ؛ // لا يقل مجموع سعة القفل المجزأة من السعة الإجمالية الأولية إذا (c * ssize <initialCapacity) {++ c ؛ } int cap = min_segment_table_capacity ؛ // تأكد من أن CAP هو قوة 2 ، وهو أقرب رقم أكبر من أو يساوي C بينما (Cap <c) {cap << = 1 ؛ } // قم بإنشاء قطاع قالب كائن قطاع جديد <k ، v> s0 = شريحة جديدة <k ، v> (loadfactor ، (int) (cap * loadfactor) ، (hashentry <k ، v> []) new hashentry [cap]) ؛ // قم بإنشاء مجموعة قفل قطاع جديدة من قطاع الحجم المحدد <k ، v> [] ss = (القطاع <k ، v> []) قطاع جديد [ssize] ؛ // استخدم غير آمن لتعيين العنصر 0 من الصفيف غير آمن. putorderededObject (SS ، SBase ، S0) ؛ this.segments = ss ؛}يحتوي ConcurrentHashMap على عدة مُنشئين ، ولكن ما تم نشره أعلاه هو مُنشئها الأساسي ، والمنشدات الأخرى تكمل التهيئة عن طريق تسميتها. يحتاج المُنشئ الأساسي إلى تمرير ثلاثة معلمات ، أي السعة الأولية وعامل التحميل ومستوى التزامن. عند تقديم متغيرات الأعضاء في وقت سابق ، يمكننا أن نعلم أن السعة الأولية الافتراضية هي 16 ، وعامل التحميل هو 0.75F ، ومستوى التزامن هو 16. الآن نرى رمز المنشئ الأساسي. أولاً ، نحسب ssize من خلال concurrencylevel الواردة. ssize هو طول صفيف القطاع. يجب أن تكون مضمونة أن تكون قوة 2. وبهذه الطريقة ، يمكن حساب ترجمة القطاع المقفل في الصفيف بواسطة التجزئة و ssize-1. نظرًا لأنه لا يمكن ضمان أن يكون مستوى التزامن الوارد ليكون قوة 2 ، فلا يمكن استخدامه مباشرة مثل طول صفيف القطاع. لذلك ، نحتاج إلى إيجاد قوة من بين الأقرب إلى مستوى التزامن واستخدامها كطول الصفيف. إذا تم تمرير ConcurrencyLevel = 15 الآن ، يمكن أن يحسب الكود أعلاه ssize = 16 و sshift = 4. بعد ذلك ، يمكنك حساب SegmentShift على الفور = 16 و SegmentMask = 15. لاحظ أن SegmentShift هنا هو قيمة التحول لقفل القطاع ، و SegmentMask هي قيمة قناع قفل القطاع. يتم استخدام هاتين القيمتين لحساب قفل القطاع في المصفوفة ، والتي سنتحدث عنها أدناه. بعد حساب عدد أقفال القطاع SSIZE ، يمكن حساب سعة كل قفل قطاع بناءً على إجمالي السعة الواردة ، وقيمتها C = أولية/ssize. قدرة قفل القطاع هي طول صفيف التجزئة ، ويجب أيضًا ضمان أن تكون قوة 2. لا يمكن أن تضمن قيمة C المحسوبة أعلاه ذلك ، لذلك لا يمكن استخدام C مباشرة كطول صفيف التجزئة. تحتاج إلى العثور على قوة أخرى من الأقرب إلى C ، وتعيين هذه القيمة إلى الحد الأقصى ، ثم استخدام CAP كطول صفيف التجزئة. الآن بعد أن أصبح لدينا ssize و cap ، يمكننا إنشاء جزء جديد من صفيف قفل القفل [] و hashentry صفيف العناصر []. لاحظ أنه على عكس JDK1.6 ، تم إنشاء صفيف القطاع فقط في JDK1.7 ولم تتم تهيئته. تم ترك تشغيل تهيئة القطاع إلى عملية الإدراج.
4. كيفية تحديد موقع الأقفال وتحديد العناصر؟
// الحصول على أقفال القطاع بناءً على رمز التجزئة suppresswarnings ("غير محدد") القطاع الخاص <k ، v> segmentForHash (int h) {long u = (((h >>> segmentShift) & segmentmask) << sshift) + sbase ؛ Return (Segment <K ، V>) Unsafe.getObjectVolatile (Segments ، u) ؛} // Get element على أساس رمز التجزئة suppressWarnings ("غير محدد") Final STATIC <K ، V> HASHENTRY <K ، V> ENTROMFORHASH (SEGS <K ، V> SEG ، int h) {HASHENTRY <K ، V ؛ العودة (seg == null || (tab = seg.table) == null)؟ NULL: (hashentry <k ، v>) unfafe.getObjectVolatile (tab ، ((long) ((tab.length - 1) & h)) << tshift) + tbase) ؛} في JDK1.7 ، يتم استخدام غير آمن للحصول على عناصر صفيف ، لذلك فيما يلي بعض الرموز لحساب إزاحة عنصر الصفيف من JDK1.6. لن نولي اهتمامًا لهذه الرموز في الوقت الحالي. الآن نحتاج فقط إلى معرفة النقطتين التاليتين:
أ. احسب مجموعة المقطع المقفلة في المصفوفة من خلال رمز التجزئة: (H >>> SegmentShift) و SegmentMask.
ب. احسب مجموعة العناصر الموجودة في الصفيف بواسطة رمز التجزئة: (Tab.Length - 1) & h.
الآن دعنا نفترض أن المعلمتين الذي تم تمريره إلى المُنشئ هما OriulalCappacity = 128 ، ConcrencyLevel = 16. وفقًا للحساب ، يمكننا الحصول على ssize = 16 ، sshift = 4 ، segmentShift = 28 ، SegmentMask = 15. وبالمثل ، يتم حساب طول صفيف التجزئة في كل قفل قطاع ليكون 8 ، لذلك Tab.Length-1 = 7. بناءً على هذه القيم ، نوضح كيفية تحديد موقع أقفال وعناصر القطاع بناءً على نفس رمز التجزئة من خلال الشكل أدناه.
يمكن ملاحظة أن قفل القطاع وتحديد موقع العناصر يتم تحديده بواسطة رمز تجزئة العنصر. قفل مقطع تحديد المواقع هو القيمة العالية لرمز التجزئة (بدءًا من 32 بت) ، وعنصر تحديد المواقع هو القيمة المنخفضة لرمز التجزئة. الآن هناك سؤال. يبدأون من الطرف الأيسر من 32 بت والنهاية اليمنى من 32 بت. هل سيكون هناك صراعات في مرحلة ما؟ يمكننا العثور على Maximum_Capacity = 1 << 30 ، max_segments = 1 << 16 في متغير العضو ، مما يعني أن العدد الإجمالي للبتات المستخدمة في أقفال قطاع تحديد المواقع وعناصر تحديد المواقع لا يتجاوز 30 ، لذلك لن يكون هناك أي حجارة.
5. كيف تجد العناصر على وجه التحديد؟
// Get Valuepublic v get (Object Key) {Segment <K ، V> s ؛ hashentry <k ، v> [] tab ؛ // حساب رمز التجزئة باستخدام دالة التجزئة int h = مفتاح) ؛ // احسب فهرس قفل القطاع استنادًا إلى رمز التجزئة Long u = (((H >>> SegmentShift) و SegmentMask) << sshift) + SBase ؛ // احصل على قفل القطاع وجدول التجزئة المقابل إذا ((s = (القطعة <k ، v>) غير آمن. (hashentry <k ، v>) غير آمن. // اتبع قيمة العنصر المقابل وفقًا للمفتاح والتجزئة وإرجاع القيمة إذا ((k = e.key) == مفتاح || (e.hash == h && key.equals (k))) {return e.value ؛ }}} إرجاع فارغ ؛}في JDK1.6 ، تصل طريقة GET لقفل القطاع عن عناصر المصفوفة من خلال المشتركين ، بينما في JDK1.7 ، تتم قراءة العناصر الموجودة في الصفيف من خلال طريقة GetObjectVolatile غير الآمنة. لماذا هذا؟ نحن نعلم أنه على الرغم من أن مرجع صفيف التجزئة الذي يحتفظ به كائن القطاع من النوع المتقلبة ، فإن مراجع العناصر في الصفيف ليست من نوع متقلبة ، لذلك فإن التعديلات متعددة القراءة لعناصر الصفيف غير آمنة وقد تقرأ الكائنات التي لم يتم بناؤها بعد في الصفيف. في JDK1.6 ، يضمن القراءة الثانية أن تكون آمنة ، وفي JDK1.7 ، فإن القراءة من خلال طريقة GetObjectVolatile غير الآمنة هي أيضًا التأكد من ذلك. تتطلب قراءة عناصر الصفيف باستخدام طريقة getObjectVolatile أولاً الحصول على إزاحة العنصر في الصفيف. هنا ، وفقًا لرمز التجزئة ، فإن إزاحة قفل القطاع في الصفيف هو U ، ثم يتم استخدام الإزاحة U لمحاولة قراءة قفل القطاع. نظرًا لعدم تهيئة صفيف قفل القطاع أثناء البناء ، قد تتم قراءة قيمة فارغة ، لذلك يلزم الحكم أولاً. بعد التأكيد على أن قفل القطاع وجدول التجزئة الداخلي ليس فارغًا ، تتم قراءة عناصر صفيف التجزئة من خلال رمز التجزئة. وفقًا لمخطط الهيكل أعلاه ، يمكنك أن ترى أنه يتم الحصول على عقدة رأس القائمة المرتبطة في هذا الوقت. ثم اجتياز وابحث في القائمة المرتبطة من البداية إلى النهاية. إذا تم العثور على القيمة المقابلة ، فسيتم إرجاعها ، وإلا فسيتم إرجاعها الفارغة. ما سبق هو العملية بأكملها لإيجاد عناصر.
6. كيفية تنفيذ عنصر الإدراج؟
// أضف أزواج القيمة الرئيسية إلى المجموعة (استبدال إذا كان هناك) suppressWarnings ("unchecked") public v (k key ، v value) {segment <k ، v> s ؛ // لا يمكن أن تكون القيمة التي تم تمريرها فارغة إذا كانت (value == null) رمي nullpointerxception () جديدة ؛ // احسب رمز التجزئة باستخدام دالة التجزئة int int = مفتاح) ؛ . // حاول الحصول على قفل القطعة استنادًا إلى المُخبر إذا ((s = (القطعة <k ، v>) unfafe.getObject (شرائح ، (j << sshift) + sbase)) == null) {// إذا كان قفل القطعة الذي تم الحصول عليه فارغًا ، فبناء s = undrexturt (j) ؛ }. // لا يمكن أن تكون القيمة التي تم تمريرها فارغة إذا كانت (value == null) رمي nullpointerxception () جديدة ؛ // احسب رمز التجزئة مع التجزئة = مفتاح) ؛ . // حاول الحصول على قفل القطاع استنادًا إلى التراجع إذا ((s = (القطعة <k ، v>) غير آمن. } // Calendar طريقة وضع قفل القطاع إرجاع S.Put (المفتاح ، التجزئة ، القيمة ، صواب) ؛}هناك طريقتان في concurrenthashmap لإضافة أزواج القيمة الرئيسية. إذا كان موجودًا ، فسيتم الكتابة فوقه عند إضافته من خلال طريقة PUT. تتم إضافة طريقة ifabsent من خلال طريقة وضع ifabsent ، لن يتم الكتابة عليها. كلتا الطريقتين تستدعي طريقة وضع قفل القطاع لإكمال العملية ، ولكن المعلمة الأخيرة التي تم تمريرها مختلفة. في الكود أعلاه ، يمكننا أن نرى ذلك أولاً ، نحسب المفرد لقفل القطاع في المصفوفة استنادًا إلى رمز التجزئة للمفتاح ، ثم نستخدم طريقة getObject الفئة غير الآمنة لقراءة قفل القطاع وفقًا للمشاركة. نظرًا لعدم تهيئة العناصر الموجودة في صفيف القطاع عند إنشاء concurrenthashmap ، قد تتم قراءة قيمة فارغة ، وسيتم إنشاء قفل قطاع جديد من خلال طريقة الإثبات. بعد الحصول على قفل القطاع ، اتصل بأسلوبه لإكمال عملية الإضافة. دعونا نلقي نظرة على كيفية تشغيله.
// أضف أزواج القيمة الرئيسية النهائية v (مفتاح k ، int hash ، v value ، boolean omsifabsent) {// حاول الحصول على القفل ، إذا فشل ، تدور hashentry <k ، v> node = trylock ()؟ NULL: SCANANDLOCKForput (المفتاح ، التجزئة ، القيمة) ؛ v oldvalue ؛ حاول {hashentry <k ، v> [] tab = table ؛ // حساب index int index int of element = (tab.length - 1) & hash ؛ // احصل على عقدة الرأس للقائمة المرتبطة استنادًا إلى hashentry التراكمي <k ، v> first = intplatat (علامة التبويب ، الفهرس) ؛ لـ (hashentry <k ، v> e = first ؛؛) {// transf القائمة المرتبطة للعثور على العنصر ، وإذا (e! = null) {k k ؛ if ((k = e.key) == key || (e.hash == hash && key.equals (k))))) {oldvalue = // تقرر ما إذا كان سيتم استبدال القيمة القديمة بناءً على المعلمات إذا (! فقط efabsent) {e.value = value ؛ ++ modcount ؛ } استراحة؛ } e = e.next ؛ // إذا لم يتم العثور عليها ، أضف عقدة إلى القائمة المرتبطة} ell {// أدخل عقدة العقدة في رأس القائمة المرتبطة if (node! = null) {node.setNext (أولاً) ؛ } else {node = new hashentry <k ، v> (hash ، key ، value ، first) ؛ } // بعد إدخال العقدة ، أضف دائمًا 1 int c = count + 1 ؛ // إذا كان العنصر يتجاوز العتبة ، فقم بتوسيع السعة إذا (C> عتبة && tab.length <maximum_capacity) {إعادة صياغة (عقدة) ؛ // خلاف ذلك ، استبدل جدول التجزئة المحدد بعقدة node} آخر {setentryat (علامة التبويب ، الفهرس ، العقدة) ؛ } ++ modcount ؛ العد = ج ؛ oldvalue = فارغة ؛ استراحة؛ }}} أخيرًا {inlock () ؛ } إرجاع Oldvalue ؛}لضمان سلامة مؤشرات الترابط ، يجب وضع العمليات في الأقفال المجزأة ، بحيث يحصل مؤشر الترابط على القفل في البداية ، ويستمر في التنفيذ إذا نجحت عملية الاستحواذ. إذا فشل عملية الاستحواذ ، اتصل بطريقة ScanAndlockForput للدوران. أثناء عملية الدوران ، قم بفحص جدول التجزئة للعثور على المفتاح المحدد. إذا لم يكن المفتاح موجودًا ، فسيتم إنشاء hasshentry جديد ، بحيث لا توجد حاجة لإنشاءه مرة أخرى بعد الحصول على القفل. من أجل القيام ببعض الأشياء أثناء انتظار القفل ، لن يضيع الوقت دون جدوى. هذا يدل على النوايا الحسنة للمؤلف. سنشرح طريقة الدوران المحددة بالتفصيل لاحقًا. الآن ، اسحب التركيز أولاً. بعد أن يكتسب مؤشر الترابط القفل بنجاح ، سيحصل على عنصر الحكماء المحدد استنادًا إلى المُخطط المحسوب. في هذا الوقت ، يتم الحصول على عقدة الرأس للقائمة المرتبطة. إذا لم تكن عقدة الرأس فارغة ، فسيتم اجتياز القائمة المرتبطة والتفتيش. بعد العثور عليه ، قرر ما إذا كان سيتم استبداله بناءً على قيمة المعلمة الوحيدة. إذا لم يتم العثور على اجتياز ، فسيشير التجزئة الجديدة إلى عقدة الرأس. في هذا الوقت ، إذا تم إنشاء هشنتيري أثناء الدوران ، ثم توجه مباشرة بجانب عقدة الرأس الحالية. إذا لم يتم إنشاء الدوران ، فسيتم إنشاء hashentry جديد هنا والإشارة إلى عقدة الرأس. بعد إضافة عناصر إلى القائمة المرتبطة ، تحقق مما إذا كان العدد الإجمالي للعناصر يتجاوز العتبة. إذا تجاوزت ، اتصل بإعادة التوسع. إذا لم يتجاوز ذلك ، فارجع مباشرة إلى عنصر التراجع المقابل للمصفوفة إلى العقدة المضافة حديثًا. تقوم طريقة setentryat بتغيير مرجع عنصر الصفيف عن طريق استدعاء طريقة PutorderedObject الخاصة بـ Unsafe ، مما يضمن أن مؤشرات الترابط الأخرى يمكنها قراءة أحدث قيمة عند القراءة.
7. كيفية تنفيذ حذف العناصر؟
// حذف العنصر المحدد (حذف مباشرة بعد العثور على العنصر المقابل) V Public V (مفتاح الكائن) {// استخدم وظيفة التجزئة لحساب رمز التجزئة int ins = hash (مفتاح) ؛ // الحصول على فهرس قفل القطاع استنادًا إلى قطاع رمز التجزئة <k ، v> s = SegmentForHash (hash) ؛ // تقويم طريقة إزالة قفل القطاع إرجاع s == null؟ NULL: S.Remove (المفتاح ، التجزئة ، الفارغ) ؛} // حذف العنصر المحدد (يزيل القيمة المساوية للقيمة المعطاة) إزالة منطقية عامة (مفتاح الكائن ، قيمة الكائن) {// استخدم وظيفة التجزئة لحساب رمز التجزئة int = مفتاح) ؛ الجزء <k ، v> s ؛ يمكن أن يتأكد // من أن قفل القطاع ليس فارغًا قبل استدعاء قيمة إرجاع طريقة الإزالة! = null && (s = segmentforhash (hash))! = null && s.remove (المفتاح ، التجزئة ، القيمة)! = null ؛}يوفر ConcurrentHashMap عمليتين للحذف ، والآخر هو حذفه مباشرة بعد العثور عليه ، والآخر هو مقارنتها أولاً ثم حذفها بعد العثور عليها. كل من هذه الأساليب الحذف هي العثور على قفل القطاع المقابل استنادًا إلى رمز التجزئة للمفتاح ، ثم أكمل عملية الحذف عن طريق استدعاء طريقة إزالة قفل القطاع. دعنا نلقي نظرة على طريقة إزالة قفل القطاع.
// حذف العنصر المحدد النهائي V (مفتاح الكائن ، التجزئة int ، قيمة الكائن) {// حاول الحصول على القفل ، إذا فشل ، تدور إذا (! trylock ()) {scanandlock (المفتاح ، التجزئة) ؛ } v oldvalue = null ؛ حاول {hashentry <k ، v> [] tab = table ؛ // حساب index int index int of element = (tab.length - 1) & hash ؛ // احصل على عنصر الصفيف وفقًا لعقدة رأس قائمة الارتباطات) Hashentry <k ، v> e = entryat (علامة التبويب ، الفهرس) ؛ hashentry <k ، v> pred = null ؛ // نقل القائمة المرتبطة للعثور على العنصر المراد حذفه بينما (e! = null) {k k ؛ // النقاط التالية إلى عقدة الخلف من hashentry العقدة الحالية <k ، v> next = e.next ؛ // ابحث عن العقدة المقابلة استنادًا إلى المفتاح وتجمع إذا ((k = e.key) == مفتاح || (e.hash == hash && key.equals (k))) {v v = e.value ؛ // تخطي القيمة التي تم تمريرها إذا لم تكن مساوية لـ v ، وحذفها في حالات أخرى إذا (value == null || value == v || value.equals (v)) {// إذا كانت Pred فارغة ، فهذا يعني أن العقدة المراد حذفها هي عقدة الرأس إذا (pred == null) {// reped the header node of the list list levenat (tab ، elex ، elex ، } آخر {// قم بتعيين خلافة عقدة pred إلى العقدة التالية pred.setNext (التالي) ؛ } ++ modcount ؛ --عدد؛ // سجل قيمة حذف العنصر oldvalue = v ؛ } استراحة؛ } // إذا لم تكن E هي العقدة التي تبحث عنها ، فقم بإشارة مرجع pred إلى pred = e ؛ // تحقق من العقدة التالية e = التالي ؛ }} أخيرًا {inlock () ؛ } إرجاع Oldvalue ؛}عند حذف العناصر في أقفال القطاع ، تحتاج إلى الحصول على القفل أولاً. إذا فشل عملية الاستحواذ ، اتصل بالطريقة Scanandlock للدوران. إذا نجحت عملية الاستحواذ ، قم بتنفيذ الخطوة التالية. احسب أولاً ترجمة الصفيف ثم الحصول على عناصر صفيف التجزئة من خلال المنصب الفردي. هنا يتم الحصول على عقدة الرأس للقائمة المرتبطة. بعد ذلك ، اجتياز وابحث في القائمة المرتبطة. قبل ذلك ، استخدم المؤشر التالي لتسجيل عقدة الخلف للعقدة الحالية ، ثم قارن المفتاح والتجزئة لمعرفة ما إذا كانت العقدة التي تبحث عنها. إذا كان الأمر كذلك ، قم بإجراء الحكم التالي إذا كان الحكم. إذا كانت القيمة فارغة أو كانت القيمة مساوية للقيمة الحالية للعقدة ، فستدخل عبارة IF للحذف ، وإلا سيتم تخطيها مباشرة. هناك حالتان عند إجراء عملية حذف في بيان if. إذا كانت العقدة الحالية عبارة عن عقدة رأس ، فقم بتعيين العقدة التالية مباشرة كعقدة الرأس. إذا لم تكن العقدة الحالية عقدة رأس ، فقم بتعيين خليفة عقدة Pred على العقدة التالية. تمثل عقدة pred هنا سلف العقدة الحالية. في كل مرة قبل التحقق من العقدة التالية ، يتم توجيه PRES إلى العقدة الحالية ، مما يضمن أن عقدة PRET هي دائمًا سلف العقدة الحالية. لاحظ أنه على عكس JDK1.6 ، في JDK1.7 ، فإن المتغير التالي لكائن Hashentry ليس نهائيًا ، بحيث يمكنك حذف العنصر عن طريق تعديل القيمة المشار إليها مباشرةً. نظرًا لأن المتغير التالي من النوع المتقلب ، يمكن لخيط القراءة قراءة أحدث القيمة على الفور.
8. كيف يتم تنفيذ عناصر الاستبدال على وجه التحديد؟
. // تأكد من أن OldValue و NewValue ليست فارغة إذا (oldvalue == null || newValue == null) رمي nullpointerxception () ؛ // احصل على فهرس قفل القطاع استنادًا إلى قطاع رمز التجزئة <k ، v> s = SegmentForHash (hash) ؛ // استدعاء طريقة الاستبدال لإرجاع قفل القطاع s! = null && s.replace (المفتاح ، التجزئة ، Oldvalue ، newValue) ؛} // استبدال تشغيل العناصر (عملية CAS) النهائي المنطقي النهائي (k key ، int hash ، v oldvalue ، v newvalue) {// حاول الحصول على القفل ، إذا فشلت إذا! } استبدال منطقي = خطأ ؛ حاول {hashentry <k ، v> e ؛ // ابحث عن عقدة الرأس مباشرة من خلال التجزئة ثم اجتياز القائمة المرتبطة بـ (e = entryforhash (هذا ، التجزئة) ؛ e! = null ؛ e = e.next) {k k ؛ // ابحث عن العقدة المراد استبدالها بناءً على المفتاح وتجزئة إذا ((k = e.key) == مفتاح || (e.hash == hash && key.equals (k))) {// إذا كانت القيمة الحالية المحددة صحيحة ، استبدل if (oldvalue.equals (e.value)) { ++ modcount ؛ استبدال = صحيح ؛ } // خلاف ذلك ، إذا لم يتم تنفيذ أي عملية ، فترسة العودة ؛ }}} أخيرًا {inlock () ؛ } عودة استبدال ؛}يوفر ConcurrentHashMap أيضًا عمليتين بديلتين ، إحداهما هي استبدالها مباشرة بعد العثور عليها ، والآخر هو المقارنة أولاً ثم استبداله (عملية CAS). إن تنفيذ هاتين العمليتين هو نفسه تقريبًا ، باستثناء أن عملية CAS لديها طبقة إضافية من عمليات المقارنة قبل الاستبدال ، لذلك نحتاج فقط إلى فهم أحد العمليات بإيجاز. هنا نستخدم عمليات CAS للتحليل ، والذي لا يزال روتينًا قديمًا. أولاً ، ابحث عن قفل القطاع المقابل استنادًا إلى رمز التجزئة للمفتاح ، ثم استدعاء طريقة استبداله. بعد إدخال طريقة استبدال في قفل القطاع ، تحتاج إلى الحصول على القفل أولاً. إذا فشل الاستحواذ ، قم بتدويره. إذا نجحت عملية الاستحواذ ، فانتقل إلى الخطوة التالية. أولاً ، احصل على عقدة الرأس للقائمة المرتبطة وفقًا لرمز التجزئة ، ثم اجتياز وبحث وفقًا للمفتاح والتجزئة. بعد العثور على العنصر المقابل ، قارن ما إذا كان Oldvalue المعطى هو القيمة الحالية. إذا لم يكن الأمر كذلك ، فاخلي على التعديل ، وإذا كان الأمر كذلك ، استبدله بالقيمة الجديدة. نظرًا لأن حقل القيمة لكائن hashentry هو من النوع المتقلبة ، يمكن استبداله مباشرة.
9. ماذا فعلت بالضبط عند الدوران؟
// تدور في انتظار الحصول على قفل (تشغيل التشغيل) التجزئة الخاصة <k ، v> scanandlockforput (مفتاح k ، int hash ، v value) {// الحصول على عقدة الرأس وفقًا لرمز hash <k ، v> first = entryforhash (هذا ، hash) ؛ hashentry <k ، v> e = first ؛ hashentry <k ، v> node = null ؛ int recepties = -1 ؛ // تدور بينما (! trylock ()) {hashentry <k ، v> f ؛ إذا كانت (Retries <0) {// إذا كانت عقدة الرأس فارغة ، فقم بإنشاء عقدة جديدة إذا (e == null) {if (node == null) {node = new hashentry <k ، v> (hash ، key ، value ، null) ؛ } recepties = 0 ؛ // خلاف ذلك ، اجتياز القائمة المرتبطة لتحديد موقع العقدة} if (key.equals (e.key)) {recondies = 0 ؛ } آخر {e = e.next ؛ }. استراحة؛ // عندما تكون إعادة المحاكاة أرقامًا ، حدد ما إذا كان الأول قد تم تغييره} آخر إذا ((Retries & 1) == 0 && (f = Entryforhash (هذا ، التجزئة))! = أولاً) {e = first = f ؛ Retries = -1 ؛ }} return node ؛} // spin في انتظار الحصول على قفل (إزالة واستبدال العمليات) private void scanandlock (مفتاح الكائن ، int hash) {// الحصول على عقدة الرأس للقائمة المرتبطة وفقًا لرمز التجزئة <k ، v> first = intringforhash (this ، this) ؛ hashentry <k ، v> e = first ؛ int recepties = -1 ؛ // تدور بينما (! trylock ()) {hashentry <k ، v> f ؛ if (Retries <0) {// نقل القائمة المرتبطة بتحديد موقع العقدة if (e == null || key.equals (e.key)) {receptires = 0 ؛ } آخر {e = e.next ؛ }. استراحة؛ // عندما تكون إعادة المحاكاة أرقامًا ، حدد ما إذا كان الأول قد تم تغييره} آخر إذا ((Retries & 1) == 0 && (f = Entryforhash (هذا ، التجزئة))! = أولاً) {e = first = f ؛ Retries = -1 ؛ }}}كما ذكرنا سابقًا ، يتطلب وضع وإزالة واستبدال العمليات في الأقفال المجزأة الحصول على القفل أولاً. فقط بعد الحصول على القفل بنجاح يمكن تنفيذ العملية التالية. إذا فشل عملية الاستحواذ ، فسيتم تنفيذ الدوران. تتم إضافة عملية الدوران أيضًا في JDK1.7. من أجل تجنب التعليق المتكرر والاستيقاظ من المواضيع ، يمكن أن يحسن الأداء أثناء العمليات المتزامنة. يتم استدعاء ScanAndlockForput في طريقة PUT ، ويتم استدعاء ScanAndlock في الأساليب إزالة واستبدال. إن طريقتان الدوران متماثلان تقريبًا ، هنا نقوم فقط بتحليل طريقة ScanAndlockForput. بادئ ذي بدء ، يجب عليك الحصول على عقدة الرأس للقائمة المرتبطة بناءً على رمز التجزئة. ثم سيدخل مؤشر الترابط حلقة أثناء تنفيذها. الطريقة الوحيدة للخروج من الحلقة هي الحصول على القفل بنجاح ، ولن يتم تعليق الخيط خلال هذه الفترة. عندما يتم إدخال الحلقة للتو ، تكون قيمة إعادة المحاولة -1. في هذا الوقت ، لن يحاول الخيط الحصول على القفل على الفور. بدلاً من ذلك ، ستجد أولاً العقدة المقابلة للمفتاح (إذا لم يتم العثور عليها ، فسيتم إنشاء واحدة جديدة) ، ثم ضبط إعادة المحاولة على 0. بعد ذلك ، ستحاول الحصول على القفل مرارًا وتكرارًا. سيتم أيضًا إضافة قيمة إعادة المحاكاة المقابلة 1 في كل مرة حتى يتجاوز الحد الأقصى لعدد المحاولات الحد الأقصى لعدد المحاولات. إذا لم يتم الحصول على القفل ، فسيتم استدعاء طريقة القفل لحظرها والحصول عليها. أثناء محاولة الحصول على القفل ، سيتحقق مما إذا كانت عقدة الرأس قد تم تغييرها في كل مرة (إعادة المحاولة). إذا تم تغييره ، فأعد ضبط إعادة المحاولة إلى -1 ، ثم كرر العملية الآن. هذا ما يفعله الخيط عند الدوران. تجدر الإشارة إلى أنه إذا تم اكتشاف عقدة الرأس ليتم تغييرها أثناء الدوران ، فسيتم تمديد وقت الدوران للخيط.
10. ما هي العمليات التي يتم القيام بها عند توسيع جدول التجزئة؟
// hash مرة أخرى suppresswarnings ("غير محدد") إعادة صياغة باطلة خاصة (hashentry <k ، v> node) {// احصل على المرجع إلى hashentry table hash القديم <k ، v> [] oldtable = table ؛ // احصل على قدرة جدول التجزئة القديم int oldcapacity = oldtable.length ؛ // احسب قدرة جدول التجزئة الجديد (2 أضعاف جدول التجزئة القديم) int newCapacity = OldCapacity << 1 ؛ // حساب عتبة العنصر الجديدة عتبة = (int) (newCapacity * loadFactor) ؛ // قم بإنشاء hashentry مجموعة جديدة <k ، v> [] newtable = (hashentry <k ، v> []) new hashentry [newCapacity] ؛ // إنشاء قيمة قناع جديدة int sizemask = newCapacity - 1 ؛ // tranquility من خلال جميع عناصر الجدول القديم لـ (int i = 0 ؛ i <oldcapacity ؛ i ++) {// احصل على عقدة الرأس من hashentry القائمة المرتبطة <k ، v> e = oldtable [i] ؛ if (e! = null) {hashentry <k ، v> next = e.next ؛ // حساب فهرس العنصر في الجدول الجديد int idx = e.hash & sizemask ؛ . } آخر {hashentry <k ، v> lastrun = e ؛ int lastidx = idx ؛ // ضع عقدة lastrun ووضع العقدة مباشرة بعد lastrun في الجدول الجديد لـ (hashentry <k ، v> last = next ؛ last! = null ؛ last = last.next) {int k = last.hash & sizemask ؛ if (k! = lastIdx) {lastidx = k ؛ لاستون = الماضي ؛ }} newtable [lastidx] = lastrun ؛ // نقل العناصر قبل عقدة lastrun للقائمة المرتبطة ، نسخها إلى الجدول الجديد بدوره (hashentry <k ، v> p = e ؛ p! = lastrun ؛ p = p.next) {v v = p.value ؛ int h = p.hash ؛ int k = h & sizemask ؛ hashentry <k ، v> n = newtable [k] ؛ Newtable [k] = new hashentry <k ، v> (h ، p.key ، v ، n) ؛ }}} ستر // أضف العقدة الواردة إلى عقدة الرأس من القائمة المرتبطة node.setNext (newtable [nodeindex]) ؛ // مبادلة الجدول الجديد المحدد عنصر التراجع مع العقدة الواردة newtable [nodeIndex] = العقدة ؛ // نقطة مرجع جدول التجزئة إلى جدول الجدول الجديد = newtable ؛}تسمى طريقة إعادة الصياغة في طريقة وضع. نعلم أنه عند وضع طريقة وضع ، سيتم إنشاء العنصر الجديد وإضافته إلى صفيف التجزئة. كلما زاد احتمال حدوث تعارضات التجزئة ، زاد أداء جدول التجزئة. لذلك ، في كل مرة يقوم فيها بتشغيل التشغيل ، سوف تحقق ما إذا كان العدد الإجمالي للعناصر يتجاوز العتبة. إذا تجاوزت العتبة ، فسيتم استدعاء طريقة إعادة صياغة لتوسيع القدرة. نظرًا لأنه لم يعد من الممكن تغيير طول الصفيف بمجرد تحديده ، يجب إنشاء صفيف جديد لاستبدال الصفيف الأصلي. من الكود ، يمكنك معرفة أن الصفيف الذي تم إنشاؤه حديثًا هو ضعف طول المصفوفة الأصلية (OldCapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.