Java Collections автоматическое перераспределение, когда размер достигнут

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; показывает сумму, с помощью которого переходит арилист.

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

Согласно javadoc.,

Детали политики роста не указаны за пределы того факта, что добавление элемента имеет постоянную амортизированную стоимость времени.

Поэтому, хотя приятно, что люди публикуют исходный код JDK, он может отличаться в разных версиях; Там нет гарантированного фактора роста.

Answer 5

Обычно емкость удваивается (или умножена на постоянную). Это гарантирует, что время, необходимое для вставки нового элемента, примерно На) (независимо от размера N.).

Answer 6

Это зависит от реализации JDK, которую вы используете. Я нашел следующий алгоритм (используется в Apache Garmony):

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

Означает, что размер увеличивается на половину старого размера, 12 минимума.

Но, как я уже сказал, это особое внимание реализации, поэтому все JVM могут справиться с этим своим путем.

Answer 7

Емкость арарилиста увеличивается по мере необходимости. Когда вы устанавливаете емкость на нее, вы устанавливаете начальную емкость - вы предоставляете предположение для конструктора, чтобы собрание может иметь хорошее исходный размер. ArrayList! = Array.

Answer 8

ArrayList в Java никогда не получится, его размер будет расти, когда он будет полон и должен добавить больше данных в него.

Если вы хотите спросить о реализации низкого уровня, которую я предполагаю, что ArrayList может использовать массив для содержения данных. Затем, я думаю, что, когда массив, который удерживает ArrayList, ArrayList создает новый массив с двойным размером и скопируйте все элементы из старого массива в новый массив. Но это мое предположение, и вам нужно прочитать Java Doc