ArrayList: как увеличивается размер?
У меня есть основной вопрос по Java ArrayList,
когда ArrayList объявляется и инициализируется с помощью конструктора по умолчанию, создается пространство памяти для 10 элементов. Теперь, когда я добавляю 11-й элемент, что происходит? Будет ли создано новое пространство памяти с емкостью 20 (или более) элементов (для этого необходимо скопировать элементы из первой ячейки памяти в новую ячейку) ИЛИ что-нибудь еще?
Я проверил здесь. Но я не нашел ответа.
Пожалуйста, поделитесь знаниями. Благодарю.
23 ответа
Создается новый массив, а содержимое старого копируется. Это все, что вы знаете на уровне API. Цитирую из документов (мой акцент):
каждый
ArrayListЭкземпляр имеет емкость. Емкость - это размер массива, используемого для хранения элементов в списке. Это всегда как минимум размер списка. Когда элементы добавляются в ArrayList, его емкость увеличивается автоматически. Детали политики роста не указаны за исключением того факта, что добавление элемента имеет постоянные амортизированные временные затраты.
С точки зрения того, как это на самом деле происходит с конкретной реализацией ArrayList (например, Sun), в их случае вы можете увидеть кровавые подробности в источнике. Но, конечно, полагаться на детали конкретной реализации обычно не очень хорошая идея...
Sun's JDK6:
Я считаю, что он растет до 15 элементов. Не кодирую, а смотрю на код grow() в 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.
РЕДАКТИРОВАТЬ: для тех, кто не понял, какова связь между множителем 1.5 а также int newCapacity = oldCapacity + (oldCapacity >> 1);
>> является оператором смещения вправо, который уменьшает число до половины. Таким образом,int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;
Это будет зависеть от реализации, но от исходного кода Sun Java 6:
int newCapacity = (oldCapacity * 3)/2 + 1;
Это в ensureCapacity метод. Другие реализации JDK могут отличаться.
До JDK 6 емкость растет с формулой newCapacity = (oldCapacity * 3/2) + 1,
В JDK 7 и выше формула меняется на newCapacity = oldCapacity + (oldCapacity >> 1),
Так что, если начальная емкость 10 тогда новая емкость будет 16 in JDK6 а также 15 in above JDK6
Когда мы пытаемся добавить объект в массив,
Java проверяет, достаточно ли в существующем массиве емкости для хранения нового объекта. Если нет, то создается новый массив большего размера, старый массив копируется в новый массив с помощью Arrays.copyOf, и новый массив присваивается существующему массиву.
Посмотрите на приведенный ниже код (взят из Java ArrayList Code на GrepCode.com).
Редактировать:
public ArrayList() Создает пустой список с начальной емкостью десять.
public ArrayList (int initialCapacity) мы можем указать начальную емкость.
public ArrayList (Collection c) Создает список, содержащий элементы указанной коллекции, в том порядке, в котором они возвращаются итератором коллекции.
Теперь, когда мы используем конструктор ArrayList(), мы получаем ArrayList с размером =10. При добавлении 11-го элемента в списке новый метод Arraylist создается внутри метода sureCapacity().
Используя следующую формулу:
int newCapacity= (oldCapacity * 3)/2 +1;
Давайте посмотрим на этот код (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 был init, поэтому он будет использовать емкость по умолчанию (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
Когда ArrayList объявлен и инициализирован с использованием конструктора по умолчанию, будет создано пространство памяти для 10 элементов. Теперь, когда я добавляю 11-й элемент, происходит
ArrayList создать новый объект со следующим размером
т.е. OldCapacity*3/2+1 = 10*3/2+1 =16
Как правило, память для контейнеров типа ArrayList увеличивается путем удвоения ее. Таким образом, если у вас изначально было место для 10 элементов и вы добавили 10, одиннадцатый элемент будет добавлен в новый (внутренний) массив из 20 элементов. Причиной этого является то, что дополнительные затраты на добавление элементов уменьшаются с O(n^2), если массив был увеличен с приращением фиксированного размера, до хорошего O(n) при удвоении размера каждый раз, когда внутренний массив заполнен.
Когда ArrayList объявлен и инициализирован с использованием конструктора по умолчанию, создается пространство памяти для 10 элементов.
NO. Когда 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;
PS У меня недостаточно репутации, чтобы комментировать вопрос, поэтому я ставлю это в качестве ответа, поскольку никто ранее не указывал на это неверное предположение.
Контекст java 8
Я даю свой ответ здесь в контексте реализации Oracle java 8, так как после прочтения всех ответов я обнаружил, что gmgmiller дал ответ в контексте java 6, а другой ответ был дан в контексте 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);
}
код ключа этой строки:
int newCapacity = oldCapacity + (oldCapacity >> 1);
Очевидно, что фактор роста также 1,5, так же, как Java 6.
static int getCapacity(ArrayList<?> list) throws Exception {
Field dataField = ArrayList.class.getDeclaredField("elementData");
dataField.setAccessible(true);
return ((Object[]) dataField.get(list)).length;
}
используйте вышеуказанный метод, чтобы проверить размер при изменении массива.
Емкость Arraylist по умолчанию - 10.
[1,2,3,4,5 ..... 10]
если вы хотите увеличить размер Arraylist в java, вы можете применить это
формула
int newcapacity, текущая емкость;
newcapacity =((текущая емкость *3/2)+1)
Арралист будет [1,2,3,4,5 ..... 10,11], а количество арралистов - 16.
Из исходного кода JDK я нашел ниже код
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 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);
}
После заполнения ArrayList в Java увеличивается на 50% от своей исходной емкости.
Происходит следующее: создается новый массив с n*2 пробелами, затем копируются все элементы старого массива, и новый элемент вставляется в первое свободное пространство. В общем, это приводит к тому, что O(N) добавляет время для ArrayList.
Если вы используете Eclipse, установите Jad и Jadclipse для декомпиляции JAR-файлов, хранящихся в библиотеке. Я сделал это, чтобы прочитать исходный код.
Это последняя версия JDK (июнь 2022 г.), JDK 18, и вы можете скачать ее на https://jdk.java.net/18/ или посмотреть исходный код на Githubhttps://github.com/openjdk/ . jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java
Когда вы добавляете элемент в свой ArrayList, Java гарантирует, что он может содержать по крайней мере элементы, которые были в нем, и новый элемент. Java предпочитает увеличивать емкость до 1,5 * текущей емкости в соответствии с этим выражением.
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);.
oldCapacity >> 1означает 0,5 * oldCapacity, поэтому newLength будет 1,5 * oldCapacity, если он положительный и не переполняется.
Вот фрагменты кода:
src/java.base/доля/классы/java/util/ArrayList.java
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
src/java.base/share/classes/jdk/internal/util/ArraysSupport.java
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
return hugeLength(oldLength, minGrowth);
}
}
В Jdk 1.6: Новая емкость = (Текущая емкость * 3/2) + 1;
В JDK 1.7:
int j = i + (i >> 1); это то же самое, что Новая емкость = (Текущая емкость * 1/2) + Текущая емкость;
пример: размер увеличится как:10 ->15->22->33
Емкость 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
(старый размер * 3)/2 + 1
Если вы используете конструктор по умолчанию, тогда начальный размер ArrayList будет 10 иначе вы можете передать начальный размер массива при создании объекта ArrayList.
Пример: в случае конструктора по умолчанию
List<String> list = new ArrayList<>();
list.size()
Пример: в случае параметризованного конструктора
List<String> list = new ArrayList<>(5);
list.size()
ArrayList - это класс интерфейса коллекции.Java - это язык с открытым исходным кодом, мы можем изменить его реализацию. здесь предопределенная реализация java:new capacity = (currentCapacity*3)/2 + 1; или в JAVASE8newcapacity = oldCapacity+(oldcapacity>>1);
Размер массива по умолчанию равен 10. Когда мы добавляем 11-й....arraylist увеличивает размер (n*2). Значения, хранящиеся в старом массиве, копируются в новый массив, размер которого равен 20.