مجموعات Java تلقائي تلقائي عند الوصول إلى الحجم

Question

لست متأكدًا مما إذا كنت أستخدم المصطلحات الصحيحة ، لكنني أشعر بالفضول كيف يتم تحديد مقدار زيادة حجم المجموعة في Java عندما تصبح ممتلئة؟ لقد حاولت البحث ولكني لا أخرج حقًا أي شيء مفيد.

لذا ، إذا كان لدي شيء مثل

List l = new ArrayList(1);
l.add("1");
l.add("2");

كيف تحدد مقدار زيادة حجم القائمة؟ هل هي دائما قيمة محددة ، وإذا كان الأمر كذلك ، فما هي هذه القيمة؟ سأكون مهتمًا أيضًا بهذه المعلومات الخاصة بـ Bitset إذا كان يختلف.

شكرا واسمحوا لي أن أعرف إذا كان ينبغي علي توضيح أي.

Answer 1

يدعو ensureCapacity:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

لذلك كما ترون newCapacity هل (oldCapacity * 3) / 2 + 1

Answer 2

يحمل مصدر ArrayList بعض القرائن:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}


/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

هذا الخط: int newCapacity = (oldCapacity * 3)/2 + 1; يوضح المبلغ الذي يتغير به ArrayList.

Answer 3

يحتوي ArrayList على مجموعة من الكائنات التي تنمو إذا كان الحجم للتأكد من أن العنصر يمكن أن ينمو في الصفيف.

داخل ArrayList.ensureCapacity() .

يزيد من قدرة مثيل ArrayList ، إذا لزم الأمر ، للتأكد من أنه يمكن أن يحتفظ بما لا يقل عن عدد العناصر المحددة بواسطة وسيطة السعة الدنيا.

ال add(E e) المكالمات ensureCapacity()

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

Answer 4

بحسب ال جافادوك,

لم يتم تحديد تفاصيل سياسة النمو بما يتجاوز حقيقة أن إضافة عنصر له تكلفة زمنية مستمرة.

لذا ، على الرغم من أنه من الجيد أن ينشر الناس رمز مصدر JDK ، إلا أنه قد يكون مختلفًا في الإصدارات المختلفة ؛ لا يوجد عامل نمو مضمون.

Answer 5

عادة ما يتم مضاعفة السعة (أو مضروبها ثابت). هذا يضمن أن الوقت المستغرق لإدراج عنصر جديد هو تقريبا على) (مستقلة عن حجم ن).

Answer 6

يعتمد ذلك على تطبيق JDK الذي تستخدمه. لقد وجدت بعد الخوارزمية (يستخدم في Apache Harmony):

int increment = size / 2;
if (required > increment) {
    increment = required;
}
if (increment < 12) {
    increment = 12;
}

يعني أن الحجم يزداد بمقدار نصف الحجم القديم ، 12 الحد الأدنى.

ولكن كما قلت ، هذا هو التنفيذ محدد ، بحيث يمكن لجميع JVM التعامل مع هذا بطريقتها الخاصة.

Answer 7

تزداد سعة ArrayList حسب الحاجة. عندما تقوم بتعيين السعة عليها ، فأنت تقوم بتعيين السعة الأولية - فأنت تقدم تخمينًا للمُنشئ بحيث يمكن أن يكون للمجموعة جيدًا مبدئي بحجم. ArrayList! = صفيف.

Answer 8

لن ينتهي ArrayList في Java أبدًا ، سينمو حجمه عندما يكون ممتلئًا ويحتاج إلى إضافة المزيد من البيانات فيه.

إذا كنت تريد أن تسأل عن التنفيذ المنخفض المستوى ، والتي أفترض أن قائمة ArrayList يمكنها استخدام صفيف لاحتواء البيانات. بعد ذلك ، أعتقد أنه عندما تكون الصفيف الذي يحمله ArrayList ممتلئًا ، تقوم ArrayList بإنشاء صفيف جديد بحجم مزدوج ونسخ جميع العناصر من الصفيف القديم إلى الصفيف الجديد. ولكن هذا هو افتراضي وتحتاج إلى قراءة Doc Java