Автоматическое перераспределение коллекций Java при достижении размера

Question

Я не уверен, что использую правильные термины, но мне любопытно, как определяется, насколько увеличится размер Коллекции в Java, когда она заполнится?Я пытался искать, но я не могу придумать ничего полезного.

Итак, если у меня есть что-то вроде

<code>
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

Согласно javadoc ,

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

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

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

Источник 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 5

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

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

Означает, что размер увеличен вдвое по сравнению со старым размером, минимум 12.

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

Answer 6

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

Answer 7

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

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

Answer 8

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