ArrayList: как размер увеличивается?

Ответ 1

Создается новый массив и копируется содержимое старого. Это все, что вы знаете на уровне API. Цитата из документы (мой акцент):

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

В терминах того, как это происходит на самом деле с конкретной реализацией ArrayList (например, Sun), в их случае вы можете увидеть детали gory в источнике. Но, конечно, полагаться на детали конкретной реализации, как правило, не является хорошей идеей...

Ответ 2

Sun JDK6:

Я считаю, что он вырос до 15 элементов. Не кодируя это, но глядя на grow() кода в jdk.

int newCapacity then = 10 + (10 → 1) = 15.

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Из Javadoc, он говорит, что это от Java 2 и дальше, так что это безопасная ставка в Sun JDK.

EDIT: для тех, кто не понял, какая связь между множителем 1.5 и int newCapacity = oldCapacity + (oldCapacity >> 1);

>> - оператор сдвига справа, который уменьшает число до его половины. Таким образом, int newCapacity = oldCapacity + (oldCapacity >> 1);
= > int newCapacity = oldCapacity + 0.5*oldCapacity;
= > int newCapacity = 1.5*oldCapacity ;

Ответ 3

Это будет зависеть от реализации, но от исходного кода Sun Java 6:

int newCapacity = (oldCapacity * 3)/2 + 1;

Это в методе ensureCapacity. Другие реализации JDK могут различаться.

Ответ 4

Когда мы пытаемся добавить объект к arraylist,

Java проверяет, чтобы обеспечить достаточную емкость существующего массива для хранения нового объекта. Если нет, создается новый массив большего размера, старый массив копируется в новый массив с помощью Arrays.copyOf, а новый массив присваивается существующему массиву.

Посмотрите на код ниже (взятый из кода Java ArrayList на GrepCode.com).

Edit:

public ArrayList() Создает пустой список с начальной емкостью в десять.

public ArrayList (int initialCapacity), мы можем указать начальную емкость.

public ArrayList (Collection c) Создает список, содержащий элементы указанной коллекции, в том порядке, в котором они возвращаются итератором коллекции.

Теперь, когда мы используем конструктор ArrayList(), мы получаем ArrayList с Size = 10 При добавлении 11-го элемента в список создается новый Arraylist внутри метода securityCapacity().

Используя следующую формулу:

  int newCapacity= (oldCapacity * 3)/2 +1;

Ответ 5

когда ArrayList объявляется и инициализируется по умолчанию конструктор, пространство памяти для 10 элементов. теперь, когда я добавляю 11-й элемент, что происходит,

ArrayList создает новый объект со следующим размером

i.e OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16

Ответ 6

До JDK 6 емкость увеличивается с формулой newCapacity = (oldCapacity * 3/2) + 1.

В JDK 7 и выше формула меняется на newCapacity = oldCapacity + (oldCapacity >> 1).

Таким образом, если начальная емкость равна 10, то новая емкость будет 16 in JDK6 и 15 in above JDK6

Ответ 7

Как правило, память для контейнеров типа ArrayList увеличивается за счет его удвоения. Таким образом, если вначале у вас было место для 10 предметов, и вы добавили 10, одиннадцатый элемент будет добавлен в новый (внутренний) массив из 20 элементов. Причиной этого является то, что добавочная стоимость добавления элементов уменьшается от O (n ^ 2), если массив был увеличен с шагом фиксированного размера до хорошего O (n) при удвоении размера каждый раз, когда внутренний массив заполнен.

Ответ 8

Контекст java 8

Я даю свой ответ здесь в контексте реализации Oracle java 8, так как после прочтения всех ответов я обнаружил, что ответ в контексте java 6 дал gmgmiller, а другой ответ был дан в контексте java 7. Но как java 8 реализует увеличение размера, не было дано.

В java 8 поведение увеличения размера совпадает с java 6, см. метод grow ArrayList:

   private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

key code - это строка:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Таким образом, фактор роста также равен 1.5, так же как java 6.

Ответ 9

Давайте посмотрим на этот код (jdk1.8)

@Test
    public void testArraySize() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("last");
    }

1) Поместите точку останова на строку, когда вставлено "последнее"

2) Перейти к методу добавления ArrayList Вы увидите

ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;

3) Перейдите к методу обеспечить CapacityInternal, который вызывает этот метод ensureExplicitCapacity

4)

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
            return true;

В нашем примере minCapacity равен 11 11-10 > 0, поэтому вам нужен метод grow

5)

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Давайте опишем каждый шаг:

1) oldCapacity = 10, потому что мы не указали этот параметр при инициализации ArrayList, поэтому он будет использовать емкость по умолчанию (10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Здесь newCapacity равен oldCapacity плюс oldCapacity со смещением вправо на единицу (oldCapacity is 10 это двоичное представление 00001010, сдвигающееся на один бит вправо, мы получим 00000101, которое равно 5 в десятичной системе, поэтому newCapacity равно 10 + 5 = 15)

3)

if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;

Например, ваша емкость инициализации равна 1, когда вы добавляете второй элемент в arrayList newCapacity будет равен 1(oldCapacity) + 0 (moved to right by one bit) = 1 В этом случае newCapacity меньше minCapacity и elementData (объект массива внутри arrayList) не может содержать новый элемент, поэтому newCapacity равен minCapacity

4)

if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

Проверьте, достигает ли размер массива MAX_ARRAY_SIZE (который равен Integer.MAX - 8) Почему максимальный размер массива ArrayList равен Integer.MAX_VALUE - 8?

5) Наконец, он копирует старые значения в newArray длиной 15

Ответ 10

Когда ArrayList объявляется и инициализируется с использованием конструктора по умолчанию, создается пространство памяти для 10 элементов.

НЕТ. Когда ArrayList инициализируется, выделение памяти выполняется для пустого массива. Распределение памяти для емкости по умолчанию (10) выполняется только после добавления первого элемента в ArrayList.

 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

P.S. Не хватает репутации, чтобы прокомментировать вопрос, поэтому я ставил это как ответ, поскольку никто ранее не указывал это неправильное предположение.

Ответ 11

Исходя из исходного кода JDK, я нашел код ниже

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Ответ 12

Что происходит с новым массивом, созданным с пробелами n * 2, тогда все элементы в старом массиве копируются и новый элемент вставляется в первое свободное пространство. В общем, это приводит к тому, что O (N) добавляет время для ArrayList.

Если вы используете Eclipse, установите Jad и Jadclipse, чтобы декомпилировать JAR, хранящиеся в библиотеке. Я сделал это, чтобы прочитать исходный код.

Ответ 13

ArrayList увеличивает размер коэффициента загрузки в следующих случаях:

• Начальная емкость: 10
• Коэффициент загрузки: 1 (т.е. когда список заполнен)
• Скорость роста: current_size + current_size/2

Context: JDK 7

При добавлении элемента в ArrayList следующие вызовы public ensureCapacityInternal и другие частные вызовы методов происходят внутри, чтобы увеличить размер. Это то, что динамически увеличивает размер ArrayList. при просмотре кода вы можете понять логику, присваивая соглашения об именах, поэтому я не добавляю явное описание

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

Ответ 14

Размер ArrayList всегда увеличивается с n+n/2+1.

Ответ 15

Значение по умолчанию для ArrayList равно 10. Как только емкость достигнет максимальной емкости, размер массива ArrayList будет равен 16, как только емкость достигнет максимальной емкости 16, размер ArrayList составит 25 и будет увеличиваться в зависимости от размера данных.....

Как? Вот ответ и формула

New capacity = (Current Capacity * 3/2) + 1

Итак, если значение по умолчанию равно 10, то

Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16

Ответ 16

static int getCapacity(ArrayList<?> list) throws Exception {
            Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(list)).length;
    }

используйте вышеуказанный метод, чтобы проверить размер при изменении массива.

Ответ 17

В JDK 1.6: Новая емкость = (Текущая емкость * 3/2) + 1;

В JDK 1,7:

int j = i + (i >> 1); это так же, как Новая емкость = (Текущая емкость * 1/2) + Текущая емкость;

пример: размер будет увеличиваться как: 10--> 15 → 22--> 33

Ответ 18

Размер по умолчанию для arraylist равен 10. Когда мы добавляем 11-й... arraylist увеличивает размер (n * 2). Значения, хранящиеся в старых arraylist, копируются в новый arraylist, размер которого равен 20.