Коллекции: как увеличить размер?

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

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

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

Солнце JDK6:

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

int newCapacity тогда = 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 ;

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

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

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

Edit:

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

public ArrayList (int initialCapacity) мы можем определить начальную емкость.

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

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

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

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

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

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

т. е. OldCapacity*3/2+1 = 10*3/2+1 =16

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

контекст java 8

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

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

   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);
    }

код ключа это строка:

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

так ясно, фактор роста также 1.5, то же самое, что и java 6.

когда 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. Не хватает репутации, чтобы комментировать вопрос, поэтому я оставлю это в качестве ответа, так как никто не указывал на это неверное предположение ранее.

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

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

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

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

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

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

емкость по умолчанию 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

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

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

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

В Jdk 1.7:

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

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

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);
}

давайте посмотрим на этот код (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) Перейдите к методу add ArrayList Вы увидите

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

3) перейдите к методу ensureCapacityInternal этот вызов метода ensureExplicitCapacity

4)

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

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

в нашем примере minCapacity равен 11 вам нужно 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, потому что мы не ставили этот param, когда 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 (который является целым числом.Максимум - 8) почему максимальный размер массива ArrayList является целым числом.MAX_VALUE-8?

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

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