خريطة متزامنة في جافا

يُعرّف إطار عمل مجموعات جافا ( Java Collections Framework) في الإصدار 1.5 والإصدارات اللاحقة من لغة البرمجة جافا ، ويُنفّذ الخرائط الأصلية العادية أحادية الخيوط، بالإضافة إلى خرائط جديدة آمنة للخيوط تُنفّذ الواجهة، من بين واجهات متزامنة أخرى. ^{[ 1 ]} في جافا 1.6، أُضيفت الواجهة، مُوسّعةً الواجهة ، وأُضيفت الواجهة كمجموعة واجهات فرعية.java.util.concurrent.ConcurrentMapjava.util.NavigableMapjava.util.SortedMapjava.util.concurrent.ConcurrentNavigableMap

يأخذ مخطط واجهة الإصدار 1.8 java.util.Map<K, V>الشكل الموضح أدناه. يمكن اعتبار المجموعات حالات فرعية من الخرائط المقابلة، حيث تكون القيم دائمًا ثابتة معينة يمكن تجاهلها، على الرغم من أن java.util.Set<E>واجهة برمجة التطبيقات تستخدم طرقًا مقابلة ولكن بأسماء مختلفة. في الأسفل يوجد عنصر java.util.concurrent.ConcurrentNavigableMap<K, V>، وهو عبارة عن وراثة متعددة.

• java.util.Collection
  • java.util.Map
    • java.util.SortedMap
      • java.util.NavigableMap
        • java.util.concurrent.ConcurrentNavigableMap
    • java.util.concurrent.ConcurrentMap
      • java.util.concurrent.ConcurrentNavigableMap

إحدى المشكلات التي حلتها java.util.concurrent<K, V>حزمة Java 1.5 هي مشكلة التعديل المتزامن. يمكن استخدام فئات المجموعات التي توفرها بشكل موثوق من قبل عدة java.lang.Threadمستخدمين.

يجب أن تستخدم جميع الخرائط غير المتزامنة المشتركة بين الخيوط، بالإضافة إلى المجموعات الأخرى، شكلاً من أشكال التأمين الصريح، مثل التزامن الأصلي، لمنع التعديل المتزامن، أو أن تكون هناك طريقة لإثبات استحالة التعديل المتزامن من منطق البرنامج. قد يؤدي التعديل المتزامن لخريطة java.lang.Map<K, V>بواسطة خيوط متعددة إلى الإخلال بالاتساق الداخلي لهياكل البيانات داخلها java.lang.Map<K, V>، مما ينتج عنه أخطاء نادرة الظهور أو غير متوقعة، ويصعب اكتشافها وإصلاحها. كذلك، قد يؤدي التعديل المتزامن بواسطة خيط واحد مع إمكانية الوصول للقراءة بواسطة خيط آخر أو عدة خيوط إلى نتائج غير متوقعة للقارئ، على الرغم من عدم الإخلال بالاتساق الداخلي للخريطة. يزيد استخدام منطق البرنامج الخارجي لمنع التعديل المتزامن من تعقيد الكود، ويخلق خطرًا غير متوقع لحدوث أخطاء في الكود الحالي والمستقبلي، على الرغم من أنه يُمكّن من استخدام المجموعات غير المتزامنة. مع ذلك، لا يمكن للتأمين أو منطق البرنامج تنسيق الخيوط الخارجية التي قد تتصل بالخريطة java.util.Collection<E>.

public V put ( K key , V value ) { synchronized ( mutex ) { return m . put ( key , value ); } }

استيراد java.util.Collections ؛ استيراد java.util.Map ؛Map < String , String > wrappedMap = Collections.synchronizedMap ( map ) ;​synchronized ( wrappedMap ) { for ( String s : wrappedMap . keySet ()) { // عملية قد تكون طويلة يتم تنفيذها ربما // مرات عديدة، مما يؤدي إلى تأخير جميع عمليات الوصول الأخرى } }

استيراد java.util.HashMap ؛ استيراد java.util.Map ؛Map < String , String > map = new HashMap <> ();// الخيط أ // استخدم الخريطة نفسها كقفل. يمكن استخدام أي كائن متفق عليه بدلاً من ذلك. synchronized ( map ) { map . put ( "key" , "value" ); }// Thread B synchronized ( map ) { String result = map . get ( "key" ); // ... }// Thread C synchronized ( map ) { for ( Map . Entry < String , String > s : map . entrySet ()) { /*  * عملية قد تكون بطيئة، مما يؤدي إلى تأخير جميع العمليات الأخرى التي يُفترض أنها سريعة.  * لا يمكن التزامن في التكرارات الفردية.  */ // ... } }

استيراد java.util.Map ؛ استيراد java.util.concurrent.locks.ReadWriteLock ؛ استيراد java.util.concurrent.locks.ReentrantReadWriteLock ؛final ReentrantReadWriteLock lock = new ReentrantReadWriteLock ( ); final ReadWriteLock readLock = lock.readLock ( ); final ReadWriteLock writeLock = lock.writeLock ( ) ;// Thread A try { writeLock.lock ( ); map.put ( " key" , "value" ); } finally { writeLock.unlock ( ) ; }// Thread B try { readLock.lock (); String s = map.get ( " key" ) ; } finally { readLock.unlock ( ) ; }// Thread C try { readLock.lock ( ) ; for ( Map.Entry < String , String > s : map.entrySet ( ) ) { /*  * عملية قد تكون بطيئة، مما يؤخر جميع العمليات الأخرى التي يُفترض أنها سريعة. *  لا يمكن التزامن في التكرارات الفردية.  */ // ... } } finally { readLock.unlock ( ) ; }

يُعاني الاستبعاد المتبادل من مشكلة تراكم الأقفال ، حيث قد تتراكم الخيوط على القفل، مما يُجبر آلة جافا الافتراضية (JVM) على الاحتفاظ بقوائم انتظار مكلفة و"إيقاف" الأقفال المنتظرة java.lang.Thread. يُعد إيقاف java.lang.Threadالأقفال وإلغاء إيقافها عملية مكلفة، وقد يحدث تبديل سياق بطيء . تتطلب عمليات تبديل السياق من ميكروثانية إلى ميلي ثانية، بينما تستغرق العمليات الأساسية للخريطة عادةً نانوثانية. قد ينخفض ​​الأداء إلى جزء صغير من java.lang.Threadإنتاجية القفل الواحد مع ازدياد التنافس. عندما لا يكون هناك تنافس أو يكون التنافس على القفل ضئيلاً، يكون تأثير الأداء ضئيلاً، باستثناء اختبار التنافس على القفل. تقوم آلات جافا الافتراضية الحديثة بتضمين معظم كود القفل، مما يقلله إلى بضع تعليمات فقط، ويحافظ على سرعة عالية في حالة عدم وجود تنافس. java.util.concurrent.locks.ReentrantReadWriteLockمع ذلك، فإن تقنيات إعادة الدخول، مثل التزامن الأصلي، تُضيف عبئًا إضافيًا يُقلل الأداء في الحفاظ على عمق إعادة الدخول، مما يؤثر على حالة عدم وجود تنافس أيضًا. يبدو أن مشكلة التزامن تتلاشى مع بيئات JVM الحديثة، ولكن يمكن إخفاؤها عن طريق تبديل السياق البطيء: في هذه الحالة، سيزداد زمن الاستجابة، لكن الإنتاجية ستظل مقبولة. مع مئات من عمليات java.lang.Threadتبديل السياق، ينتج عن زمن تبديل سياق قدره 10 مللي ثانية زمن استجابة بالثواني.

تفشل حلول الاستبعاد المتبادل في الاستفادة الكاملة من القدرة الحاسوبية لنظام متعدد النوى، إذ لا java.lang.Threadيُسمح إلا لنواة واحدة بالعمل داخل java.util.Map<K, V>الكود في كل مرة. تستفيد تطبيقات الخرائط المتزامنة الخاصة التي يوفرها إطار عمل مجموعات جافا (JCF) وغيرها أحيانًا من النوى المتعددة باستخدام تقنيات البرمجة غير المُقفلة . تستخدم هذه التقنيات عمليات مثل compareAndSet()الدالة المضمنة المتوفرة في العديد من فئات جافا AtomicReferenceلإجراء تحديثات مشروطة لبعض البنى الداخلية للخريطة بشكل ذري. compareAndSet()يتم تعزيز هذه الدالة في فئات JCF بواسطة كود أصلي يُمكنه إجراء عملية المقارنة والتعيين على أجزاء داخلية خاصة من بعض الكائنات لبعض الخوارزميات (باستخدام وصول غير آمن). تتسم هذه التقنيات بالتعقيد، إذ تعتمد غالبًا على قواعد الاتصال بين الخيوط التي توفرها المتغيرات المتقلبة، وعلاقة "يحدث قبل"، وأنواع خاصة من "حلقات إعادة المحاولة" غير المُقفلة (والتي تختلف عن أقفال الدوران في أنها تُحرز تقدمًا دائمًا). كما compareAndSet()تعتمد على تعليمات خاصة بالمعالج. يمكن لأي كود جافا استخدام هذه compareAndSet()الطريقة لأغراض أخرى على مختلف الفئات المتزامنة لتحقيق التزامن بدون تأمين أو حتى بدون انتظار، مما يوفر زمن استجابة محدودًا. تُعدّ تقنيات التزامن بدون تأمين بسيطة في العديد من الحالات الشائعة ومع بعض المجموعات البسيطة مثل المكدسات.

يوضح الرسم البياني كيف أن التزامن باستخدام Collections.synchronizedMap(java.util.Map)تغليف جدول عادي HashMap(باللون الأرجواني) قد لا يكون بنفس كفاءة الجدول ConcurrentHashMapالعادي (باللون الأحمر). أما الجداول الأخرى فهي جداول مرتبة java.util.concurrent.ConcurrentNavigableMap<K, V>( java.util.concurrent.AirConcurrentMap<K, V>باللون الأزرق) وجداول java.util.concurrent.ConcurrentSkipListMap<K, V>CSLM (باللون الأخضر). (قد تكون المناطق المستوية عبارة عن عمليات إعادة تجزئة تُنتج جداول أكبر من حجم الحضانة، وتستهلك java.util.concurrent.ConcurrentHashMap<K, V>مساحة أكبر. لاحظ أن المحور الرأسي يجب أن يُشير إلى "وضع K". النظام عبارة عن معالج i7 ثماني النواة بتردد 2.5  جيجاهرتز، مع خيار -Xms5000m لمنع جمع البيانات المهملة). يُغير جمع البيانات المهملة وتوسيع عملية JVM المنحنيات بشكل كبير، كما أن بعض تقنيات عدم وجود قفل داخلية تُنتج بيانات مهملة عند التنازع.

من المشاكل الأخرى المتعلقة بأساليب الاستبعاد المتبادل أن افتراض الذرية الكاملة الذي تتبناه بعض التعليمات البرمجية أحادية الخيوط يُؤدي إلى تأخيرات متقطعة طويلة بشكل غير مقبول بين الخيوط في بيئة متزامنة. على وجه الخصوص، putAll()قد تستغرق عمليات التكرار والعمليات المجمعة، مثل عمليات التجميع، وقتًا يتناسب مع حجمها java.util.Map<K, V>، مما يُؤخر العمليات الأخرى التي تتوقع زمن استجابة منخفضًا بشكل متوقع للعمليات غير المجمعة. على سبيل المثال، لا يُمكن لخادم ويبjava.lang.Thread متعدد الخيوط السماح بتأخير بعض الاستجابات بسبب تكرارات طويلة الأمد لخيوط أخرى تُنفذ طلبات أخرى تبحث عن قيمة معينة. يرتبط بهذا حقيقة أن العمليات التي تُقفل لا يُشترط عليها التخلي عن القفل، وقد تُؤدي حلقة لا نهائية في العملية المالكة إلى انتشار الحظر الدائم إلى العمليات الأخرى . قد تتعرض العمليات المالكة البطيئة للمقاطعة أحيانًا. كما أن خرائط التجزئة عُرضة لتأخيرات تلقائية أثناء إعادة التجزئة.java.lang.Threadjava.util.Map<K, V>Threadjava.lang.Threadjava.lang.Thread

تتضمن حلول الحزم java.util.concurrentلمشكلة التعديل المتزامن، ومشكلة القافلة، ومشكلة زمن الاستجابة المتوقع، ومشكلة المعالجات متعددة النوى، خيارًا معماريًا يُسمى الاتساق الضعيف. يعني هذا الخيار أن عمليات القراءة get(java.lang.Object)لن تتوقف حتى أثناء التحديثات الجارية، ويُسمح حتى بتداخل التحديثات مع نفسها ومع عمليات القراءة. يسمح الاتساق الضعيف، على سبيل المثال، java.util.concurrent.ConcurrentMap<K, V>بتغيير محتويات سجل أثناء تكرار واحد له java.lang.Thread. ^{[ 7 ]} صُممت المُكرِّرات ليتم استخدامها بواسطة مُكرِّر واحد java.lang.Threadفي كل مرة. لذا، على سبيل المثال، Mapقد يرى قارئ سجلًا يحتوي على مدخلين مترابطين بطريقة غير متسقة Threadأثناء تعديله بواسطة مُكرِّر آخر . يحتاج java.lang.Threadالتحديث الذي من المفترض أن يُغير مفتاح سجل Map.Entry(k1, v)إلى آخر بشكل ذري إلى إجراء عملية قراءة ثم عملية قراءة ، بينما قد يفوت تكرار المدخل أو يراه في مكانين. تُعيد عمليات الاسترجاع القيمة لمفتاح معين والتي تعكس آخر تحديث مكتمل سابق لهذا المفتاح. وبالتالي، توجد علاقة "يحدث قبل".Map.Entry(k2, v)remove(k1)put(k2, v)

لا توجد طريقة java.util.concurrent.ConcurrentMap<K, V>لقفل الجدول بأكمله. لا يوجد احتمال لحدوث ذلك java.util.ConcurrentModificationExceptionكما هو الحال مع التعديل المتزامن غير المقصود java.util.Map<K, V>للجداول غير المتزامنة. size()قد تستغرق هذه الطريقة وقتًا طويلاً، على عكس java.util.Map<K, V>الجداول غير المتزامنة المقابلة والمجموعات الأخرى التي تتضمن عادةً حقل حجم للوصول السريع، لأنها قد تحتاج إلى مسح الجدول بأكمله java.util.Map<K, V>بطريقة ما. عند حدوث تعديلات متزامنة، تعكس النتائج حالة الجدول java.util.Map<K, V>في وقت ما، ولكن ليس بالضرورة حالة واحدة متسقة، وبالتالي ، size()يُفضل استخدامها فقط للمراقبة.isEmpty()containsValue(java.lang.Object)

هناك بعض العمليات التي يوفرها النظام java.util.concurrent.ConcurrentMap<K, V>والتي لا توجد في النظام الأساسي java.util.Map<K, V>(الذي يرث منه) لضمان ذرية التعديلات. replace(K, v1, v2)سيتحقق النظام من وجود العنصر المحدد v1في العنصر java.util.Map.Entry<K, V>المحدد K، وإذا وُجد، فسيتم v1استبداله به v2بشكل ذري. سيقوم النظام الجديد replace(k, v)بتنفيذ عملية الاستبدال put(k, v)فقط إذا kكان العنصر موجودًا بالفعل في العنصر الأساسي java.util.Map<K, V>. كما putIfAbsent(k, v)سيقوم النظام الجديد بتنفيذ عملية الاستبدال put(k, v)فقط إذا kلم يكن العنصر موجودًا بالفعل في العنصر الأساسي java.util.Map<K, V>، remove(k, v)وسيزيل العنصر java.util.Map.Entry<K, V>المحدد vفقط إذا vكان العنصر موجودًا. قد تكون هذه الذرية مهمة لبعض حالات الاستخدام متعددة الخيوط، ولكنها لا ترتبط بقيد الاتساق الضعيف.

بالنسبة لـ java.util.concurrent.ConcurrentMap<K, V>s، فإن ما يلي ذري.

m.putIfAbsent(k, v)هو ذري ولكنه مكافئ لما يلي:

إذا كان ( k == null || v == null ) { ارمِ استثناء NullPointerException (); }إذا لم يكن المفتاح ` k` موجودًا في المصفوفة ` m` ، فسيتم إرجاع القيمة ` v` من ` m` . وإلا ، فسيتم إرجاع القيمة ` k` من ` m` .

m.replace(k, v) عملية ذرية ولكنها مكافئة لما يلي:

إذا كان ( k == null || v == null ) { ارمِ استثناء NullPointerException (); }إذا كان ( m.containsKey ( k ) ) { return m.put ( k , v ) ; } else { return null ; }​

m.replace(k, v1, v2) عملية ذرية ولكنها مكافئة لما يلي:

إذا كان ( k == null || v1 == null || v2 == null ) { ارمِ استثناء NullPointerException (); }إذا كان ( m.containsKey ( k ) && Objects.equals ( m.get ( k ) , v1 ) ) { m.put ( k , v2 ) ; return true ; } else return false ; }​​​​

m.remove(k, v) عملية ذرية ولكنها مكافئة لما يلي:

// إذا كانت الخريطة لا تدعم المفاتيح أو القيم الفارغة (على ما يبدو بشكل مستقل) إذا ( k == null || v == null ) { throw new NullPointerException (); }إذا كان ( m.containsKey ( k ) && Objects.equals ( m.get ( k ) , v ) ) { m.remove ( k ) ; return true ; } else return false ; }​​​​

نظرًا لأنّ java.util.Map<K, V>`and` java.util.concurrent.ConcurrentMap<K, V>عبارة عن واجهات، فلا يمكن إضافة طرق جديدة إليها دون التأثير على التنفيذات. مع ذلك، أضافت Java 1.8 إمكانية استخدام تطبيقات افتراضية للواجهات، وأضافت إلى هذه Mapالتطبيقات الافتراضية بعض الطرق الجديدة getOrDefault(Object, V)` forEach(BiConsumer)and` replaceAll(BiFunction)و`and` computeIfAbsent(K, Function)و` computeIfPresent(K, BiFunction)and` و` compute(K,BiFunction)and` و`and` . لا تضمن merge(K, V, BiFunction)التطبيقات الافتراضية في `and` الذرية، ولكن في التطبيقات الافتراضية المُعدّلة، تُستخدم تقنيات لا تعتمد على الأقفال لتحقيق الذرية، وستكون التطبيقات الموجودة ذرية تلقائيًا. قد تكون تقنيات عدم استخدام الأقفال أبطأ من التعديلات في الفئات الملموسة، لذا يمكن للفئات الملموسة اختيار تنفيذها بشكل ذري أو لا، وتوثيق خصائص التزامن.java.util.Map<K, V>java.util.concurrent.ConcurrentMap<K, V>java.util.concurrent.ConcurrentMap<K, V>

من الممكن استخدام تقنيات غير مقفلة مع java.util.concurrent.ConcurrentMap<K, V>s لأنها تتضمن طرقًا ذات عدد توافق عالٍ بما فيه الكفاية، أي ما لا نهاية ، مما يعني أنه يمكن تنسيق أي عدد من java.lang.Threads. يمكن تنفيذ هذا المثال باستخدام Java 8، merge()ولكنه يوضح النمط العام غير المقفل، وهو نمط أكثر عمومية. لا يرتبط هذا المثال بالتفاصيل الداخلية لـ s، java.util.concurrent.ConcurrentMap<K, V>بل باستخدام كود العميل لـ s java.util.concurrent.ConcurrentMap<K, V>. على سبيل المثال، إذا أردنا ضرب قيمة في الخريطة بثابت بشكل Nذري:

استيراد java.util.concurrent.ConcurrentMap ؛ثابت نهائي طويل N = 10 ؛void atomicMultiply ( ConcurrentMap < Long , Long > map , long key ) { while ( true ) { Long oldValue = map . get ( key ); // بافتراض أن oldValue ليس فارغًا. هذه هي عملية "الحمولة"، ولا ينبغي أن يكون لها آثار جانبية بسبب إعادة الحساب المحتملة في حالة التعارض Long newValue = oldValue * N ; if ( map . replace ( key , oldValue , newValue )) { break ; } } }

يُعدّ هذا putIfAbsent(k, v)مفيدًا أيضًا عندما يُسمح بغياب قيمة المفتاح. يمكن تطبيق هذا المثال باستخدام Java 8، compute()ولكنه يُظهر نمطًا عامًا أكثر شمولًا للآلية غير المُقفلة. replace(k, v1, v2)لا تقبل هذه الآلية المعاملات الفارغة، لذا قد يكون من الضروري أحيانًا استخدام مزيج منها. بعبارة أخرى، إذا v1كانت قيمة المفتاح فارغة، putIfAbsent(k, v2)فسيتم استدعاء الدالة، وإلا replace(k, v1, v2)فسيتم استدعاء الدالة الأخرى.

استيراد java.util.concurrent.ConcurrentMap ؛void atomicMultiplyNullable ( ConcurrentMap < Long , Long > map , long key ) { while ( true ) { long oldValue = map . get ( key ); // هذه هي عملية "الحمولة"، ويجب ألا يكون لها آثار جانبية بسبب إعادة الحساب المحتملة في حالة التعارض long newValue = oldValue == null ? INITIAL_VALUE : oldValue * N ; if ( replaceNullable ( map , key , oldValue , newValue )) { break ; } } }دالة ثابتة منطقية تُسمى replaceNullable تأخذ خريطة متزامنة من نوع ConcurrentMap < Long , Long > ، ومفتاحًا طويلًا ، وقيمة طويلة v1 ، وقيمة طويلة v2 ، وتُرجع : إذا كانت v1 تساوي null ، تُرجع map.putIfAbsent ( key , v2 ) تساوي null ، وإلا تُرجع map.replace ( key , v1 , v2 ) .

تم تصميم وتطوير إطار عمل مجموعات جافا بشكل أساسي بواسطة جوشوا بلوخ ، وتم تقديمه في JDK 1.2 . ^{[ 8 ]} جاءت فئات التزامن الأصلية من حزمة المجموعات الخاصة بدوغ ليا [ ^{9 ] .}

• إطار عمل مجموعات جافا
• حاوية (بنية بيانات)
• التزامن في جافا
• قفل بدون قفل

• جوتز، برايان؛ بيرلز، تيم؛ بلوخ، جوشوا؛ بوبير، جوزيف؛ هولمز، ديفيد؛ ليا، دوغ (2006). التزامن في جافا عمليًا . أديسون ويسلي. ISBN 0-321-34960-1. OL 25208908M . 
• ليا، دوغ (1999). البرمجة المتزامنة في جافا: مبادئ التصميم والأنماط . أديسون ويسلي. ISBN 0-201-31009-0. OL 55044M . 

• دروس المجموعات
• البرنامج التعليمي لمجموعة Java 6 - بقلم جاكوب جينكوف، كادافي كامفولوسا
• ترويض النمر: إطار عمل المجموعات
• إطار عمل المجموعات (وثائق Oracle Java SE 8)
• كتاب "دروس جافا - المجموعات" من تأليف جوش بلوخ
• ما هي مجموعة جافا التي يجب أن أستخدمها؟ — مخطط انسيابي مفيد لتبسيط اختيار المجموعات
• «أيّ مجموعة جافا يجب استخدامها؟» - بقلم جينيف جورج