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

Question

У меня есть основной вопрос по Java ArrayList.

Когда ArrayList объявляется и инициализируется с использованием конструктора по умолчанию, создается пространство памяти для 10 элементов. Теперь, когда я добавляю 11-й элемент, что происходит? Будет ли создано новое пространство памяти с емкостью 20 (или более) элементов (для этого необходимо скопировать элементы из первой ячейки памяти в новую ячейку) ИЛИ что-нибудь еще?

Я проверил здесь . Но я не нашел ответа.

Пожалуйста, поделитесь знаниями. Спасибо.

Answer 1

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

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

Контекст: 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);
}

Answer 2

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

В JDK 1,7:

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

ex: размер увеличится как: 10 -> 15 -> 22 -> 33

Answer 3

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

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

Answer 4

Емкость 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

Answer 5

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

Answer 6

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

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

Answer 7

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