تحلل هذه المقالة رمز المصدر لـ ArrayList. اسمحوا لي أن أتحدث عن المصفوفات قبل تحليلها. قد تكون المصفوفات واحدة من أولى هياكل البيانات التي تلامس معها. أنها تقسم مساحة عنوان مستمرة في الذاكرة لتخزين العناصر. نظرًا لأنها تعمل بشكل مباشر ، فإن أداء المصفوفات أفضل من فئات التجميع ، وهو ميزة كبيرة لاستخدام المصفوفات. لكننا نعلم أن الصفيف له عيب مميت ، أي ، يجب تحديد حجم الصفيف أثناء التهيئة ، ولا يمكن تغيير حجم الصفيف في العمليات اللاحقة. في المواقف الفعلية ، نواجه المزيد من الأشياء التي لا نعرف عدد العناصر التي سيتم تخزينها في البداية ، ولكن بدلاً من ذلك نأمل أن تتمكن الحاوية من توسيع قدرتها تلقائيًا حتى تتمكن من تخزين المزيد من العناصر. يمكن أن تلبي ArrayList مثل هذه الاحتياجات بشكل جيد للغاية ، ويمكنه تلقائيًا توسيع حجم الحجم للتكيف مع الزيادة المستمرة لعناصر التخزين. يتم تنفيذ طبقتها الأساسية بناءً على المصفوفات ، لذلك تحتوي على بعض ميزات المصفوفات ، مثل العثور على التعديلات سريعة ويكون الإدراج والحذف بطيئين. في هذه المقالة ، سوف نتعمق في رمز المصدر لنرى كيف يتضمن المصفوفات. إلقاء نظرة أولى على متغيرات الأعضاء والمقدمين الرئيسيين الثلاثة.
// سعة التهيئة الافتراضية الخاصة الثابتة الثابتة int default_capacity = 10 ؛ // كائن فارغ كائن خاص ثابت الثابت [] فارغ _elementData = {} ؛ // كائن كائن كائن عابر خاص [] elementData ؛ // عدد عناصر التجميع الخاصة بحجم int ؛ if (initialCapacity <0) {refl new alficalArgumentException ("القدرة غير القانونية:"+ initialCappacity) ؛ } // قم بإنشاء صفيف نوع كائن جديد من السعة المحددة this.elementData = كائن جديد [initialCapacity] ؛} // bonstructor بدون معلمات ArrayList () {super () ؛ // تمرير مثيل صفيف فارغ إلى elementData this.elementData = فارغ_eelementData ؛} // طريقة المنشأة للانتقال إلى مجموعة ArrayList العامة الخارجية (مجموعة <؟ تمديد e> c) {// عقد العنصر المرجعي للمصفوفة الداخلية التي تم تمريرها إلى elementData = c.toarray () ؛ // تحديث عدد عناصر حجم المجموعة = elementData.Length ؛ . }}يمكنك أن ترى أن بنية التخزين الداخلية لـ ArrayList هي مجموعة من نوع الكائن ، بحيث يمكنها تخزين عناصر من أي نوع. عند إنشاء قائمة ArrayList ، إذا تم تمرير الحجم الأولي ، فسيقوم بإنشاء مجموعة كائن جديدة من السعة المحددة. إذا لم يتم تعيين الحجم الأولي ، فلن يخصص مساحة الذاكرة ولكن استخدام صفيف كائن فارغ ، ثم تخصيص الذاكرة عندما يتم وضع العنصر فعليًا. دعنا نلقي نظرة على أساليبها لإضافة وحذف وتعديل والبحث.
// زيادة (إضافة) إضافة منطقية عامة (e e) {// تحقق مما إذا كان هناك حاجة إلى توسيع المصفوفة قبل الإضافة ، يكون الحد الأدنى لطول الصفيف حجمًا + 1 insureCapacityIntern (الحجم + 1) ؛ // إضافة عنصر إلى نهاية elementData الصفيف [size ++] = e ؛ Return True ؛} // زيادة (إدراج) void public add (int index ، e element) {// insert range range check rangecheckforadd (index) ؛ // تحقق مما إذا كان هناك حاجة إلى توسيع السعة insureCapacityInternal (الحجم + 1) ؛ // حرك العنصر وراء نظام موضع الإدراج. arraycopy (elementData ، index ، elementData ، index + 1 ، size - index) ؛ // تعيين قيمة جديدة elementData [index] = element ؛ Size ++ ؛} // حذف الإزالة العامة (int index) {// index لا يمكن أن يكون أكبر من حجم RangeCheck (index) ؛ modcount ++ ؛ e oldvalue = elementData (index) ؛ int numMoved = size - index - 1 ؛ if (numMoved> 0) {// انقل العنصر خلف الفهرس إلى الأمام بواسطة نظام واحد. } // elementData الفارغ المرجعي [-الحجم] = null ؛ Return OldValue ؛} // تغيير مجموعة E العامة (int index ، e element) {// index لا يمكن أن يكون أكبر من حجم RangeCheck (index) ؛ e oldvalue = elementData (index) ؛ // استبدال بعنصر جديد elementData [index] = element ؛ Return OldValue ؛} // تحقق من public e get (int index) {// index لا يمكن أن يكون أكبر من حجم RangeCheck (index) ؛ // إرجاع عنصر إرجاع عنصر الموضع المحدد (الفهرس) ؛} في كل مرة يتم فيها إضافة عنصر إلى المجموعة ، سيتحقق أولاً ما إذا كانت السعة كافية ، وإلا سيتم توسيع السعة. ستتم مناقشة تفاصيل توسيع السعة أدناه. دعونا أولاً نلقي نظرة على النقاط المحددة للانتباه إلى الإضافة وحذف وتعديل وفحص.
إضافة (إضافة): فقط أضف هذا العنصر إلى النهاية. عملية سريعة.
أضف (إدراج): العملية أبطأ لأن العنصر وراء موضع الإدراج يجب نقله وإشراك نسخ الصفيف.
حذف: نظرًا لأن العناصر التي تقف وراء موضع الحذف تحتاج إلى نقل إلى الأمام ، سيتم أيضًا تصميم نسخة الصفيف ، وبالتالي فإن العملية بطيئة.
التغيير: قم بتعديل العناصر مباشرة في الموقع المحدد ، دون إشراك حركة العناصر أو نسخ الصفيف ، والعملية سريعة.
تحقق: إرجاع عنصر الصفيف بشكل مباشر من المُخطط المحدد ، والعملية سريعة.
من الكود المصدري ، يمكن ملاحظة أنه نظرًا لأن البحث والتعديل يتم وضعه مباشرة إلى مركز الصفيف ، فإنه لا ينطوي على حركة العناصر ونسخ المصفوفة ، لذلك فهو أسرع. ومع ذلك ، نظرًا لأن العناصر يجب نقلها ، فإنها تتضمن نسخ صفيف ، وبالتالي فإن العملية أبطأ. بالإضافة إلى ذلك ، قد تؤدي كل عملية إضافة أيضًا إلى توسيع Array ، مما سيؤثر أيضًا على الأداء. دعونا نلقي نظرة على كيفية توسيع ArrayList بشكل ديناميكي قدرتها.
private void insureCapacityInternal (int mincapacity) {// إذا كانت الصفيف لا تزال فارغة في هذا الوقت إذا كان (elementData == فارغ_elementdata) {// قارن مع السعة الافتراضية ، خذ القيمة الكبيرة minicapacity = math.max (default_capacity ، mincapacity) ؛ } // إذا تم تهيئة الصفيف ، فأداء هذه الخطوة ، مما يضمن SuperCplicitCapacity (mincapacity) ؛} private void superexplicitcapacity (int mincapacity) {modcount ++ ؛ // إذا كان الحد الأدنى للسعة أكبر من طول الصفيف ، فقم بتضخيم المصفوفة إذا (MinCapacity - elementData.length> 0) {Grow (mincapacity) ؛ }} // الحد الأقصى للسعة للمجموعة الثابتة الثابتة int max_array_size = integer.max_value - 8 ؛ // زيادة طول الصفيف الفراغ الخاص (int mincapacity) {// احصل على السعة الأصلية للمصفيف intcapacity = elementData.length ؛ // سعة الصفيف الجديد ، أضف نصفًا على الأساس الأصلي int newCapacity = OldCapacity + (OldCapacity >> 1) ؛ // تحقق مما إذا كانت السعة الجديدة أقل من الحد الأدنى للسعة إذا (NewCapacity - minicapacity <0) {newCapacity = minCapacity ؛ } // تحقق مما إذا كانت السعة الجديدة تتجاوز سعة الصفيف القصوى إذا (newCapacity - max_array_size> 0) {newCapacity = hugecapacity (minicapacity) ؛ }. قبل إضافة عناصر ، سيتم استدعاء insureCapacityInternal لفحص سعة التجميع. داخل هذه الطريقة ، سوف تحقق ما إذا كانت المجموعة الداخلية للمجموعة الحالية لا تزال مجموعة فارغة. إذا كان الأمر كذلك ، فقم بإنشاء مجموعة كائن جديدة مع الحجم الافتراضي 10. إذا لم يكن الأمر كذلك ، فإنه يثبت أنه تم تهيئة المجموعة الحالية. ثم اتصل على طريقة SureExplicitCapacity للتحقق مما إذا كانت سعة الصفيف الحالي تلبي الحد الأدنى من السعة المطلوبة. إذا لم يكن راضيا ، اتصل بطريقة النمو للتوسع. في طريقة النمو ، يمكنك أن ترى أن كل توسع هو زيادة نصف طول الصفيف الأصلي. التوسع هو في الواقع إنشاء صفيف جديد بسعة أكبر ، ونسخ جميع عناصر الصفيف الأصلي إلى الصفيف الجديد ، ثم تجاهل الصفيف الأصلي واستخدام الصفيف الجديد. حتى الآن ، قمنا بتحليل الأساليب الأكثر استخدامًا في ArrayList ، وبعض النقاط الرئيسية التي تستحق الإشارة إليها:
1. يعتمد التنفيذ الأساسي لـ ArrayList على المصفوفات ، وبالتالي فإن البحث والتعديل للمرضات المحددة أسرع ، لكن عمليات الحذف والإدراج أبطأ.
2. عند إنشاء قائمة ArrayList ، حاول تحديد السعة قدر الإمكان لتقليل عمليات نسخة الصفيف الناجمة عن التوسع. إذا كنت لا تعرف الحجم ، فيمكنك تعيين السعة الافتراضية إلى 10.
3. قبل إضافة عناصر ، تحقق مما إذا كان توسيع السعة مطلوبًا. كل توسيع السعة هو نصف السعة الأصلية.
4. في كل مرة يتم فيها تشغيل عملية التراجع ، سيتم إجراء فحص أمان. إذا كانت الصفيف خارج الحدود ، فسيتم طرح استثناء على الفور.
5. لا يتم مزامنة جميع طرق قائمة ArrayList ، لذلك فهي ليست آمنة.
6. يعتمد التحليل أعلاه على JDK1.7 ، وسيكون للإصدارات الأخرى بعض الاختلافات ، لذلك لا يمكن تعميمها.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.