عند تطبيق HashMap في بيئة Java متعددة الخيوط، توجد بشكل أساسي الخيارات التالية: استخدم java.util.Hashtable الآمن لمؤشر الترابط كبديل، استخدم أسلوب java.util.Collections.synchronizedMap لالتفاف كائن HashMap الموجود كمؤشر ترابط. -آمن. استخدم فئة java.util.concurrent.ConcurrentHashMap كبديل، والتي تتمتع بأداء جيد جدًا.
تستخدم جميع الطرق المذكورة أعلاه أقفال كائن المزامنة (mutex lock) بشكل أو بآخر في تفاصيل التنفيذ المحددة. سوف تتسبب أقفال Mutex في حظر الخيط وتقليل كفاءة التشغيل وقد تتسبب في سلسلة من المشكلات مثل حالة الجمود وتقلب الأولوية.
CAS (المقارنة والمبادلة) هي وظيفة توفرها الأجهزة الأساسية، والتي يمكنها تجزئة عملية الحكم على القيمة وتغييرها.
العمليات الذرية في جاوة
في الحزمة java.util.concurrent.atomic، توفر لنا Java العديد من الأنواع الذرية الملائمة، والتي تعتمد بالكامل على عمليات CAS.
على سبيل المثال، إذا أردنا تنفيذ عداد عام عالمي، فيمكننا:
انسخ رمز الكود كما يلي:
PrivateAtomicInteger counter =newAtomicInteger(3);
publicvoidaddCounter() {
ل(؛؛) {
intoldValue = counter.get();
intnewValue = oldValue +1;
إذا (counter.compareAndSet(oldValue, newValue))
يعود؛
}
}
من بينها، تتحقق طريقة CompareAndSet مما إذا كانت قيمة العداد الحالية هي oldValue. إذا كان الأمر كذلك، فسيتم تعيينها على القيمة الجديدة newValue.
عند حساب قيمة العداد الجديدة، إذا غيرت مؤشرات الترابط الأخرى قيمة العداد، فسوف تفشل CompareAndSwap. في هذه المرحلة، نحتاج فقط إلى إضافة طبقة من التكرار بالخارج والاستمرار في تجربة هذه العملية، ثم سننجح في النهاية في زيادة قيمة العداد بمقدار 1. (في الواقع، قام AtomicInteger بالفعل بتعريف أساليب incrementAndGet وdecrementAndGet لعمليات +1/-1 شائعة الاستخدام. نحتاج فقط إلى استدعائهما في المستقبل)
بالإضافة إلى AtomicInteger، توفر الحزمة java.util.concurrent.atomic أيضًا أنواع AtomicReference وAtomicReferenceArray، التي تمثل المراجع الذرية والمصفوفات المرجعية الذرية (مصفوفات المراجع) على التوالي.
تنفيذ قائمة مرتبطة خالية من القفل
قبل تنفيذ HashMap بدون قفل، دعونا نلقي نظرة أولاً على طريقة التنفيذ البسيطة نسبيًا للقائمة المرتبطة الخالية من القفل.
خذ عملية الإدراج كمثال:
نحتاج أولاً إلى العثور على العقدة A أمام الموضع المراد إدراجه والعقدة B خلفه.
ثم قم بإنشاء عقدة جديدة C وجعل المؤشر التالي يشير إلى العقدة B. (انظر الشكل 1)
أخيرًا، اجعل المؤشر التالي للعقدة A يشير إلى العقدة C. (انظر الشكل 2)
ومع ذلك، أثناء العملية، من الممكن أن تقوم سلاسل رسائل أخرى بإدخال بعض العقد مباشرة في A و B (من المفترض أن تكون D). إذا لم نصدر أي حكم، فقد يتسبب ذلك في فقدان العقد التي تم إدراجها بواسطة سلاسل رسائل أخرى. (انظر الشكل 3) يمكننا استخدام عملية CAS لتحديد ما إذا كان المؤشر التالي للعقدة A لا يزال يشير إلى B عند تعيين قيمة. إذا تغير المؤشر التالي للعقدة A، أعد محاولة عملية الإدراج بأكملها. الرمز التقريبي هو كما يلي:
انسخ رمز الكود كما يلي:
PrivatevoidlistInsert(Node head, Node c) {
ل(؛؛) {
العقدة a = findInsertionPlace(head)، b = a.next.get();
c.next.set(b);
إذا (a.next.compareAndSwap(b,c))
يعود؛
}
}
(الحقل التالي لفئة العقدة هو من النوع AtomicReference<Node>، وهو مرجع ذري يشير إلى نوع العقدة)
لا تختلف عملية البحث في القائمة المرتبطة الخالية من القفل عن عملية البحث في القائمة المرتبطة العادية. تتطلب عملية الحذف العثور على العقدة A أمام العقدة المراد حذفها والعقدة B خلفها، واستخدام عملية CAS للتحقق من المؤشر التالي للعقدة A وتحديثه بحيث يشير إلى العقدة B.
الصعوبات والاختراقات في HashMap الخالية من القفل
يحتوي HashMap بشكل أساسي على أربع عمليات أساسية: الإدراج والحذف والبحث وReHash. يستخدم تطبيق HashMap النموذجي مصفوفة، وكل عنصر في المصفوفة عبارة عن قائمة مرتبطة من العقد. بالنسبة لهذه القائمة المرتبطة، يمكننا استخدام طرق التشغيل المذكورة أعلاه لإجراء عمليات الإدراج والحذف والبحث، ولكن عملية ReHash أكثر صعوبة.
كما هو موضح في الشكل 4، أثناء عملية ReHash، تتمثل العملية النموذجية في اجتياز كل عقدة في الجدول القديم، وحساب موضعها في الجدول الجديد، ثم نقلها إلى الجدول الجديد. خلال هذه الفترة نحتاج إلى التعامل مع المؤشر ثلاث مرات:
المؤشر التالي للنقطة A إلى D
مؤشر النقطة B التالي للنقطة C
مؤشر النقطة C التالي إلى E
يجب إكمال عمليات المؤشر الثلاثة هذه في نفس الوقت لضمان ذرية عملية النقل. ولكن ليس من الصعب أن نرى أن عملية CAS يمكنها فقط التأكد من التحقق من قيمة متغير واحد وتحديثها ذريًا في كل مرة، ولا يمكنها تلبية الحاجة إلى التحقق من ثلاثة مؤشرات وتحديثها في نفس الوقت.
لذلك قد نغير تفكيرنا أيضًا نظرًا لأن عملية نقل العقد صعبة للغاية، فيمكننا إبقاء جميع العقد في حالة مرتبة في جميع الأوقات، وبالتالي تجنب عملية النقل. في تطبيق HashMap النموذجي، يظل طول المصفوفة دائمًا 2i، وعملية تعيين قيمة التجزئة إلى رمز المصفوفة المنخفض تؤدي ببساطة عملية modulo على طول المصفوفة (أي، فقط البتات i الأخيرة من ثنائي التجزئة هي محتفظ بها). عند ReHash، يتم مضاعفة طول المصفوفة إلى 2i+1، ويتم نقل كل عقدة في قائمة القلادة j-th للمصفوفة القديمة إما إلى العنصر j-th في المصفوفة الجديدة، أو نقلها إلى j+2i-th العنصر في المصفوفة الجديدة، والفرق الوحيد يكمن في البت i+1 من قيمة التجزئة (إذا كانت البتة i+1 هي 0، فإنها لا تزال العنصر jth، وإلا فهي العنصر j+2th).
كما هو موضح في الشكل 5، نقوم بترتيب جميع العقد بترتيب تصاعدي وفقًا للترتيب المقلوب لقيمة التجزئة (مثل 1101->1011). عندما يكون حجم المصفوفة 8، 2 و18 يكونان في مجموعة واحدة؛ 3، 11 و27 يكونان في مجموعة أخرى. في بداية كل مجموعة، يتم إدخال عقدة حارسة لتسهيل العمليات اللاحقة. من أجل ترتيب العقدة الحارسة بشكل صحيح في مقدمة المجموعة، قمنا بتعيين أعلى بت من تجزئة العقدة العادية (التي تصبح أدنى بت بعد التقليب) على 1، في حين أن العقدة الحارسة لا تقوم بتعيين هذا البت.
عندما يتم توسيع المصفوفة إلى 16 (انظر الشكل 6)، يتم تقسيم المجموعة الثانية إلى مجموعة تحتوي على 3 فقط ومجموعة تحتوي على 11 و27، ولكن الترتيب النسبي بين العقد لم يتغير. بهذه الطريقة، لا نحتاج إلى نقل العقد أثناء ReHash.
تفاصيل التنفيذ
نظرًا لأن نسخ المصفوفة يستغرق الكثير من الوقت أثناء التوسيع، فإننا هنا نعتمد طريقة تقسيم المصفوفة بأكملها إلى كتل وإنشائها بتكاسل. بهذه الطريقة، عند الوصول إلى رمز منخفض معين، ما عليك سوى الحكم على ما إذا كانت الكتلة التي يوجد بها الرمز قد تم إنشاؤها (إذا لم يكن الأمر كذلك، فقم بإنشائها).
بالإضافة إلى ذلك، يتم تعريف الحجم على أنه النطاق المنخفض المستخدم حاليًا، وقيمته الأولية هي 2. عند توسيع المصفوفة، يجب مضاعفة الحجم فقط، ويتم تحديد العدد لتمثيل العدد الإجمالي للعقد المضمنة حاليًا في HashMap ( دون احتساب العقد الحارسة).
في البداية، تكون كافة العناصر الموجودة في المصفوفة باستثناء العنصر 0 فارغة. يشير العنصر 0 إلى قائمة مرتبطة تحتوي على عقدة خافرة واحدة فقط، تمثل نقطة البداية للسلسلة بأكملها. تظهر الصورة الكاملة الأولية في الشكل 7، حيث يمثل اللون الأخضر الفاتح النطاق المنخفض غير المستخدم حاليًا، وتمثل الأسهم المنقطة كتلًا موجودة منطقيًا ولكنها لم يتم إنشاؤها فعليًا.
تهيئة العملية المنخفضة
تعتبر العناصر الفارغة في المصفوفة في حالة غير مهيأة. إن تهيئة رمز منخفض معين يعني إنشاء العقدة الحارسة المقابلة لها. يتم إجراء التهيئة بشكل متكرر، أي أنه إذا لم تتم تهيئة الحرف الأصلي الخاص به، فسيتم تهيئة الحرف الأصلي الخاص به أولاً. (الحرف الأصلي للمنخفض هو الحرف الذي تم الحصول عليه عن طريق إزالة أعلى بت ثنائي.) الرمز التقريبي هو كما يلي:
انسخ رمز الكود كما يلي:
PrivatevoidinitializeBucket(intbucketIdx) {
intparentIdx = BucketIdx ^ Integer.highestOneBit(bucketIdx);
إذا (getBucket(parentIdx) ==null)
تهيئةBucket(parentIdx);
Node dummy =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
من بينها، getBucket هي طريقة مغلفة للحصول على محتوى منخفض معين في المصفوفة، وsetBucket هو نفسه. سيقوم listInsert بإدراج العقدة المحددة في الموضع المناسب بدءًا من الموضع المحدد. إذا كانت العقدة التي لها نفس التجزئة موجودة بالفعل في القائمة المرتبطة، فسوف تُرجع العقدة الموجودة، وإلا فإنها ستعيد العقدة المُدرجة حديثًا.
عملية إدراج
أولاً، استخدم حجم HashMap لتعديل رمز التجزئة للمفتاح للحصول على رمز الصفيف المنخفض الذي يجب إدراجه.
ثم حدد ما إذا كان الحرف المنخفض خاليًا، وإذا كان خاليًا، فقم بتهيئة الحرف المنخفض.
أنشئ عقدة جديدة وأدخلها في الموضع المناسب. لاحظ أن قيمة التجزئة في العقدة يجب أن تكون قيمة رمز التجزئة الأصلي بعد قلب البت وتعيين أدنى موضع على 1.
أضف 1 إلى عداد رقم العقدة إذا كان هناك عدد كبير جدًا من العقد بعد إضافة 1، فأنت بحاجة فقط إلى تغيير الحجم إلى الحجم*2، مما يعني توسيع المصفوفة (ReHash).
البحث عن العملية
ابحث عن فهرس العقدة التي سيتم العثور عليها في المصفوفة.
تحديد ما إذا كان الحرف المنخفض فارغًا أم لا، فسيتم إرجاع فشل البحث.
أدخل القائمة المرتبطة من الموضع المقابل وابحث بشكل تسلسلي حتى يتم العثور على العقدة التي سيتم العثور عليها أو تتجاوز نطاق مجموعة العقد هذه.
عملية الحذف
ابحث عن فهرس العقدة في المصفوفة التي يجب حذفها.
تحديد ما إذا كان الحرف المنخفض خاليًا، وإذا كان خاليًا، قم بتهيئة الحرف المنخفض.
ابحث عن العقدة المراد حذفها واحذفها من القائمة المرتبطة. (لاحظ أنه نظرًا لوجود العقدة الحارسة، تتم الإشارة إلى أي عنصر عادي فقط من خلال العقدة السابقة له فقط. ولا يوجد موقف حيث تتم الإشارة إليه بواسطة العقدة السابقة والمؤشر في المصفوفة في نفس الوقت، لذلك هناك لا حاجة لتعديل مؤشرات متعددة في نفس الوقت.)
قم بتقليل عداد رقم العقدة بمقدار 1.