1. تحليل رمز مصدر ArrayList (JDK7)
يحافظ ArrayList على صفيف كائن ديناميكي داخليًا. الإضافة الديناميكية وحذف ArrayList هي الإضافة الديناميكية وحذف هذا الزوج من المجموعات.
1. ArrayList بناء وتهيئة
ArrayList مثيل متغير // ArrayList السعة الافتراضية الخاصة الثابتة الثابتة int default_capacity = 10 ؛ // صفيف الكائن الفارغ الافتراضي ، المستخدمة لتحديد الكائن النهائي arrayListPrivate الفارغ [] element_elementdata = {} ؛مُنشئ ArrayList:
لا يوجد مُنشئ للمعلمات: أي ، بناء كائن فارغ []
ArrayList () {super () ؛ this.elementData = فارغة _elementdata ؛} حدد بنية حجم السعة:
ArrayList Public (int initialCapacity) {super () ؛ إذا (initialCappacity <0) رمي غير alficalaRgumentException ("القدرة غير القانونية:"+ initialCappacity) ؛ this.elementData = كائن جديد [initialCapacity] ؛} حدد بنية المجموعة التي تنفذ واجهة التجميع:
ArrayList Public (Collection <؟ Extends e> c) {elementData = C.Toarray () ؛ الحجم = elementData.Length ؛ .وهذا ما يفسر أيضًا دور التجميع ، والسبب في تصميم Java-Collection-Framwork واجهة التجميع بدلاً من استخدام القائمة والمجموعة والواجهات الأخرى مباشرة.
2. آلية تخصيص القدرات في ArrayList
سعة الحد الأقصى لـ ArrayList: سعة ArrayList هي الحد الأعلى ، والنظريات تسمح بتخصيص integer.max_value - 8 سعة الحجم. ومع ذلك ، فإن مقدار ما يمكن تخصيصه يعتمد على إعدادات المكدس ، ويجب تعيين معلمات VM
int static int int max_array_size = integer.max_value - 8 ؛
قم بتوسيع مستوى الصوت عند استدعاء طريقة إضافة
إضافة منطقية عامة (e e) {insureCapacityInternal (size + 1) ؛ // زيادة modcount !! elementData [size ++] = e ؛ العودة صحيح. }تحدد طريقة EnsureCapacityInternal (INT) بالفعل الحد الأدنى من حجم التوسع.
private void insureCapacityInternal (int mincapacity) {if (elementData == فارغ_elementData) {minCapacity = math.max (default_capacity ، mincapacity) ؛ } ضمان capticacity (mincapacity) ؛ } private void superexplicitcapacity (int mincapacity) {modcount ++ ؛ // رمز وعي فائض إذا (mincapacity - elementData.Length> 0) تنمو (mincapacity) ؛ } حول modcount: يتم تعريف modcount في قائمة ملخصية مجردة. تشرح تعليقات التعليمات البرمجية المصدر استخدامه بشكل أساسي: عند استخدام ITERATOR لتجاوزه ، يتم استخدامه للتحقق مما إذا كانت العناصر في القائمة لها تغييرات هيكلية (تم تغيير عدد عدد عناصر القائمة). يتم استخدامه بشكل أساسي في بيئة متعددة الخيوط لمنع مؤشر ترابط واحد من التكرار وخيط آخر يعدل بنية هذه القائمة.
طريقة النمو هي طريقة توسع حقيقية
Private void Grow (int mincapacity) {// overflow-concious code int oldcapacity = elementData.Length ؛ int newCapacity = OldCapacity + (OldCapacity >> 1) ؛ if (newCapacity - minicapacity <0) newCapacity = mincapacity ؛ if (newCapacity - max_array_size> 0) newCapacity = hugecapacity (mincapacity) ؛ // عادة ما تكون Mincapacity قريبة من الحجم ، لذلك هذا هو الفوز: elementData = Arrays.copyof (ElementData ، NewCapacity) ؛ }هناك أيضًا طريقة عابض لمقدار السعة التي يتم توسيعها
private static int hugeCapacity (int mincapacity) {if (mincapacity <0) // verflow rems outofmemoryerror () ؛ العودة (mincapacity> max_array_size)؟ integer.max_value: max_array_size ؛ } تلخيص:
يرافق كل توسع نسخة من الصفيف ، لذا فإن إعطاء السعة المناسبة في وقت واحد سيحسن الأداء قليلاً.
الشكل التالي هو عملية التوسع بأكملها التي تلخصها:
3.Raylist ITerator
هناك نوعان من التكرار الرئيسيين لـ ArrayList و ListItr ، ولكن تمت إضافة arraylistspliterator أيضًا في JDK1.8. دعنا نتعلم تحليل الكود المصدري لـ ITR و ListItr على التوالي.
(1) ITR: لا يمكن العودة إلا للخلف
الطبقة الخاصة ITR تنفذ iterator <e> {int arsor ؛ // فهرس العنصر التالي لإرجاع int lastret = -1 ؛ // فهرس العنصر الأخير عاد ؛ -1 إذا لم يكن هناك // متوقعة هو نسخة من modcount int equiredModCount = modCount ؛ boolean public hasnext () {return Cursor! = size ؛ } suppressWarnings ("Unchecked") public e next () {checkForComodification () ؛ // سجل الموضع الحالي int i = المؤشر ؛ إذا (i> = size) رمي nosuchelementException () ؛ Object [] elementData = ArrayList.Tis.ElementData ؛ if (i> = elementData.Length) رمي New ConvalrentModificationException () ؛ // موضع المؤشر العنصر التالي = i + 1 ؛ إرجاع (e) elementData [lastret = i] ؛ } // استخدم طريقة إزالة الفراغ العام refled () {if (lastret <0) رمي جديد alficalstateException () ؛ checkForComodification () ؛ جرب {// لاحظ كيف تستدعي الفئة الداخلية ArrayList. this.remove (lastret) ؛ // بعد الإزالة ، تحتاج إلى إعادة ضبط موضع كل مؤشر مؤشر = lastret ؛ lastret = -1 ؛ المتوقع expectModCount = modCount ؛ } catch (indexoutofBoundSexception ex) {رمي New ConcurrentModificationException () ؛ }} النهائي checkForComodification () {if (modCount! = متوقعة) رمي convalentModificationexception () ؛ }} من الكود المصدري ، يمكن ملاحظة أن ITR Iderator هو تكرار إلى الأمام ، والذي يوفر طريقة التالية للحصول على عناصر في قائمة ArrayList.
checkforcomodification هي آلية الكشف عن الأخطاء الفاشلة في عمل Java-Collection-Framwork. قد تؤدي التشغيل على نفس المجموعة في بيئة متعددة الخيوط إلى أن تؤدي إلى آلية فاشلة وتلقي استثناءً من ذلك.
يحدد ITR iterator نسخة من سجل السجل المتوقع. عندما تنفذ ArrayList عمليات لتغيير الهيكل ، مثل الطرق الإضافية وإزالة وتطهيرها ، ستتغير قيمة ModCount.
من خلال رمز مصدر ITR ، يمكن ملاحظة أن استدعاء التالي وإزالة الأساليب سيؤدي إلى فحص الفشل. في هذا الوقت ، في حالة حدوث استثناء عندما تقوم مؤشرات الترابط الأخرى بإجراء عمليات تغير بنية المجموعة أثناء عبور المجموعة.
(2) LISTITR: يدعم اجتياز الأمام والخلف. دعنا نلقي نظرة على رمز المصدر لـ Listitr:
يمتد ListIrt الخاص بتوسيع ITR ITR ListIrator <e> {listitr (int index) {super () ؛ المؤشر = فهرس ؛ } boolean public hasprevious () {return cursor! = 0 ؛ } public int nextIndex () {return cursor ؛ } public int previousIndex () {return cursor - 1 ؛ } suppressWarnings ("unchected") public e previp () {checkforcomodification () ؛ // موضع العنصر السابق من arraylist int i = المؤشر - 1 ؛ إذا (i <0) رمي nosuchelementException () ؛ Object [] elementData = ArrayList.Tis.ElementData ؛ if (i> = elementData.Length) رمي New ConvalrentModificationException () ؛ المؤشر = أنا ؛ إرجاع (e) elementData [lastret = i] ؛ } // تتم إضافة طريقة SET إلى مجموعة الفراغ العامة ITerator (e e) {if (lastret <0) رمي جديد alficalstateException () ؛ checkForComodification () ؛ Try {ArrayList.This.set (lastret ، e) ؛ } catch (indexoutofBoundSexception ex) {رمي New ConcurrentModificationException () ؛ }} // يضيف هذا ايتراتور إضافة طريقة إضافة الفراغ العام add (e e) {checkforcomodification () ؛ حاول {int i = المؤشر ؛ ArrayList.This.add (i ، e) ؛ // ملاحظة المؤشر المؤشر المؤشر = i + 1 ؛ lastret = -1 ؛ المتوقع expectModCount = modCount ؛ } catch (indexoutofBoundSexception ex) {رمي New ConcurrentModificationException () ؛ }}}إن تنفيذ ListItr هو نفسه في الأساس مثل ITR ، مع إضافة طرق يمكن اجتيازها مسبقًا ، وكذلك الأساليب إضافة وتعيين.
(3) استخدم CopyOnWriteArrayList في java.util.concurrent لحل مشكلة الفشل السريع
CopyOnWriteArrayList هو آمن مؤشر الترابط. للحصول على التفاصيل ، دعونا نلقي نظرة على رمز مصدر طريقة إضافة طريقة:
إضافة منطقية عامة (e e) {final reentrantlock lock = this.lock ؛ lock.lock () ؛ حاول {Object [] elements = getArray () ؛ int len = elements.length ؛ Object [] newElements = arrays.copyof (عناصر ، len + 1) ؛ newelements [len] = e ؛ Setarray (NewElements) ؛ العودة صحيح. } أخيرًا {lock.unlock () ؛ }} CopyOnWriteArrayList هي قائمة ArrayList تم نسخها على الكتابة. عند بدء تشغيل بيانات الكتابة ، فإن المصفوفات.
هذه التكلفة هي فقدان الذاكرة وتحقيق مشاكل في الأداء. عند كتابة CopyOnWriteArrayList ، يتم إنشاء كائن نسخ في الذاكرة ، ولا يزال الكائن الأصلي موجودًا.
لا يمكن لـ CopyOnWriteArrayList ضمان اتساق البيانات في الوقت الفعلي ، ويمكنه فقط ضمان اتساق النتائج. مناسبة للسيناريوهات مثل ذاكرة التخزين المؤقت عند قراءة المزيد والكتابة أكثر والكتابة أقل في المواقف المتزامنة.
(4) طرق أخرى مدونة مصدر ArrayList:
طريقة خاصة batchremove (مجموعة <؟> C ، مكملة منطقية) ، أي عملية إزالة الدُفعات
تم ذكر BATCHREMOVE الخاص (Collection <؟> C ، مكمل منطقي) {// سبب استخدام النهائي أدناه الكائن النهائي [] elementData = this.elementData ؛ int r = 0 ، w = 0 ؛ تعديل منطقي = خطأ ؛ حاول {// tranquility من خلال العناصر في القائمة والتحقق من (؛ r <size ؛ r ++) if (c.contains (elementData [r]) == complement) elementData [w ++] = elementData [r] ؛ } أخيرًا {// إذا حدث استثناء في المحاولة ، تأكد من تناسق البيانات وأداء عملية النسخ التالية إذا (r! = size) {system.arrayCopy (elementData ، r ، elementData ، w ، size - r) ؛ W += Size - R ؛ }. modcount += size - w ؛ الحجم = ث ؛ تعديل = صحيح ؛ }} الإرجاع المعدلة ؛ } يشير المتغير المعدل بواسطة النهائي إلى نفس المرجع للحفاظ على اتساق البيانات لاحقًا.
في هذه الطريقة ، عندما تريد الاحتفاظ بالعناصر في المجموعة C ، تكون القيمة المكملة صحيحة ؛ عندما تريد إزالة العناصر في C ، تكون القيمة المكملة خاطئة. هذا يصبح أساليب الاحتفاظ والإزالة على التوالي.
مبادلة: مبادلة الموقفين في قائمة ArrayList
2. تحليل رمز مصدر LinkedList (JDK7)
LinkedList هي قائمة مرتبطة. مقارنة بجدول الطلب ، لا تحتاج القائمة المرتبطة إلى استخدام وحدات الذاكرة المستمرة لتخزين البيانات. يقلل من مشكلة نقل العناصر الناجمة عن تعديل بنية الحاوية ، والوصول المتسلسل فعال نسبيًا.
1. تعريف العقدة
LinkedList في JDK هي قائمة مرتبطة ثنائية الاتجاه ، وتخزن كل عقدة معلومات حول العقدة السابقة والعقدة التالية على التوالي. تعريفه كما يلي:
عقدة الفئة الثابتة الخاصة <e> {e item ؛ العقدة <e> التالية ؛ العقدة <e> prev ؛ العقدة <e> (العقدة <e> prev ، e element ، node <e> next) {this.item = element ؛ this.next = التالي ؛ this.prev = prev ؛ }}2. إنشاء وتهيئة LinkedList
العضو: يتم الحفاظ على 3 متغيرات الأعضاء في LinkedList لتسجيل عدد العقد في القائمة المرتبطة ، سلف وخليفة العقد
حجم int عابرة = 0 ؛ عقدة عابرة <e> أولاً ؛ عقدة عابرة <e> last ؛
المُنشئ: المُنشئ الافتراضي هو بناء قائمة ربط فارغة
Public LinkedList () {}أو بناء بناءً على حاويات أخرى ، وبعد ذلك سنكتب مُنشئًا لتشكيل قائمة ارتباط مرتبة.
LinkedList (مجموعة <؟ تمديد E> C) {this () ؛ addall (c) ؛}هنا إضافي قليلا. للاختلاف بين المعدل العام؟ Super T وتوسيع T ، راجع هذا المقال حول الفرق بين Super T ويمتد T في الأدوية الجيلية.
3. التشغيل الهيكلي لـ LinkedList
طريقة إدخال الرأس: أي ، أدخل عنصرًا في رأس القائمة المرتبطة
private void linkfirst (e e) {final node <e> f = first ؛ العقدة النهائية <e> newNode = new node <> (null ، e ، f) ؛ أولا = newNode ؛ // احكم على ما إذا كانت قائمة مرتبطة فارغة إذا (f == null) last = newNode ؛ آخر f.prev = newNode ؛ حجم ++ ؛ modcount ++ ؛ } طريقة إدخال الذيل: أي ، أدخل عنصرًا في نهاية القائمة المرتبطة
void linklast (e e) {final node <e> l = last ؛ العقدة النهائية <e> newNode = new node <> (l ، e ، null) ؛ الأخير = newNode ؛ إذا (l == null) أولاً = newNode ؛ آخر l.next = newNode ؛ حجم ++ ؛ modcount ++ ؛ } قبل الإدراج في العقدة الحالية: ابحث عن محرك الأقراص الأمامي للعقدة الحالية
linkbefore void (e e ، node <e> succ) {// حدد ما إذا كانت العقدة ليست فارغة بالطبع العقدة النهائية <e> pred = succ.prev ؛ العقدة النهائية <e> newNode = new node <> (pred ، e ، succ) ؛ succ.prev = newNode ؛ // تحديد ما إذا كانت العقدة الحالية هي العقدة الأولى إذا (pred == null) أولاً = newNode ؛ آخر pred.next = newNode ؛ حجم ++ ؛ modcount ++ ؛ } طريقة حذف الرأس: حذف العقدة الأولى من القائمة المرتبطة
Private E UnlinkFirst (Node <e> f) {// assert f == first && f! = null ؛ e element e النهائي = f.item ؛ العقدة النهائية <e> next = f.next ؛ F.Item = null ؛ f.next = null ؛ // مساعدة GC أولاً = التالي ؛ إذا (التالي == null) last = null ؛ آخر next.prev = null ؛ مقاس--؛ modcount ++ ؛ عنصر العودة ؛ } طريقة حذف الذيل: حذف العقدة الأخيرة من القائمة المرتبطة
Private E UnlinkLast (Node <e> l) {// تأكد من l == last and l! = null final e element = l.Item ؛ العقدة النهائية <e> prev = l.prev ؛ L.Item = null ؛ L.Prev = null ؛ // مساعدة GC Last = Prev ؛ إذا (prev == null) أولاً = فارغ ؛ آخر prev.next = null ؛ مقاس--؛ modcount ++ ؛ عنصر العودة ؛ }4. الحفاظ على الاتساق بين واجهة القائمة و deque
تتيح واجهة القائمة استخدام المشتركين لتنفيذ وصول عشوائي إلى الحاويات ، ومن السهل تنفيذ وصول عشوائي إلى صفائف مثل هذا. بالنسبة للقوائم المرتبطة ، يستخدم JDK أيضًا عددًا من العقد في القوائم المرتبطة لإعطاء تنفيذ الوصول العشوائي
العقدة <e> node (int index) {// تأكد من صحة الفهرس if (index <(size> 1)) {node <e> x = first ؛ لـ (int i = 0 ؛ i <index ؛ i ++) x = x.next ؛ إرجاع x ؛ } آخر {node <e> x = last ؛ لـ (int i = size-1 ؛ i> index ؛ i--) x = x.prev ؛ إرجاع x ؛ }} الفهرس هو عدد النصف الأول ، والبحث من البداية. ينتمي الفهرس إلى عدد النصف الثاني ، ويبحث من النهاية. الاستفادة الكاملة من خصائص القوائم المرتبطة ثنائية الاتجاه.
لذلك ، إضافة (int index ، t t) ، get (int) ، set (int) والطرق الأخرى يمكن تنفيذها بسهولة.
تنفذ LinkedList الواجهة deque ، أي LinkedList تنفذ طريقة حاويات قائمة الانتظار المزدوجة. فيما يلي بعض ملخص API.
5. LinkedList Traversal
نظرًا لأن LinkedList عبارة عن قائمة مرتبطة في اتجاهين ، يمكنك عبورها بشكل طبيعي ذهابًا وإيابًا. مثل ArrayList ، تعاني LinkedList أيضًا من مشاكل فاشلة عندما يتعلق الأمر بتشغيل حاوية متعدد الخيوط.
تم شرح مسألة الفشل في المقالة السابقة ، لذلك لن أتحدث عنها هنا.
فيما يتعلق بالتكرار ، لدى LinkedList قائمة تكرار ثنائية الاتجاه قائمة ، ومتكرر عكسي DescendingIterator. كلها بسيطة جدا. لم يتم تحليل رمز المصدر
إذا اجتازت العناصر ، فإن تكلفة الوصول العشوائي مرتفعة نسبيًا.
3. LinkedList ، ArrayList ، ملخص المتجه
1. LinkedList و ArrayList
يقوم ArrayList بتنفيذ بنية بيانات تعتمد على المصفوفات الديناميكية ، ويستند LinkedList على بنية بيانات تعتمد على قائمة مرتبطة.
للوصول العشوائي إلى Get and Set ، يشعر ArrayList أفضل من LinkedList لأن LinkedList يحرك المؤشر.
للإضافة والإزالة الجديدة والحذف ، يتمتع LiningList بميزة أفضل لأن ArrayList يحتاج إلى نقل البيانات. هذا يعتمد على الوضع الفعلي. إذا تم إدخال أو حذف جزء واحد فقط من البيانات ، فإن سرعة ArrayList أفضل من سرعة LinkedList. ومع ذلك ، إذا تم إدخال البيانات بشكل عشوائي على دفعات ، فإن سرعة LinkedList أفضل بكثير من سرعة ArrayList. لأنه في كل مرة تقوم فيها ArrayList بإدراج البيانات ، من الضروري نقل نقطة الإدراج وجميع البيانات بعد ذلك.
2. ArrayList و Vector
المتجه متزامن الخيط ، لذلك هو أيضًا آمن من مؤشرات الترابط ، في حين أن ArrayList هو مؤشر الترابط ، وهو أمر غير آمن. إذا لم يتم أخذ عوامل سلامة الخيط في الاعتبار ، فإن ArrayList يكون أكثر كفاءة بشكل عام.
إذا كان عدد العناصر الموجودة في المجموعة أكبر من طول مجموعة المجموعة الحالية ، فإن معدل نمو المتجه هو 100 ٪ من طول الصفيف الحالي ، ومعدل نمو قائمة ARRAYLIS هو 50 ٪ من طول الصفيف الحالي. إذا كان استخدام البيانات بكميات كبيرة نسبيًا من البيانات في المجموعة ، فإن استخدام المتجه له مزايا معينة.
إذا كنت تبحث عن بيانات في موقع محدد ، فإن الوقت المستخدم من قبل Vector و ArrayList يكون هو نفسه ، سواء 0 (1) ، ويمكنك استخدام المتجه و ArrayList في هذا الوقت. إذا كان الوقت الذي يقضيه نقل البيانات في موقع محدد هو 0 (ni) n ، وهو الطول الإجمالي ، فيجب عليك التفكير في استخدام LinkList ، لأنه يتطلب 0 (1) نقل البيانات في موقع محدد ، والوقت الذي يقضيه الاستعلام عن البيانات في موقع محدد هو 0 (i).
ArrayList و Vector استخدام المصفوفات لتخزين البيانات. عدد العناصر في هذه الصفيف أكبر من البيانات المخزنة الفعلية لإضافة وإدراج عناصر. كلاهما يسمح عناصر فهرس الرقم التسلسلي المباشر. ومع ذلك ، يجب تصميم إدراج البيانات لنقل عناصر الصفيف وعمليات الذاكرة الأخرى ، لذلك فإن بيانات الفهرس سريعة وبطيئة لإدراج البيانات. يستخدم Vector طريقة متزامنة (مؤشر ترابط آمن) ، لذلك يكون الأداء أسوأ من ArrayList. يستخدم LinkedList قائمة مرتبطة ثنائية الاتجاه لتخزين البيانات. يتطلب فهرسة البيانات وفقًا للرقم التسلسلي اجتيازًا للأمام أو للخلف ، ولكن عند إدخال البيانات ، يتم تسجيل العناصر الأمامية والخلفية لهذا العنصر فقط ، لذلك فإن إدخال عدة درجات أسرع!