Когда ArrayList изменяет свой размер, сколько элементов он добавляет?

Question

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

И копирует ли старый массив в новый или как-то связывает их вместе?

Answer 1

Взгляните на исходный код :

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

Точный коэффициент зависит от реализации, GNU использует коэффициент 2. Он неочень важно, это просто обмен памяти на скорость.

Копирует все элементы в новый массив.

Answer 2

Создает новый массив double , кратный размеру, и копирует элементы поверх. (Я не уверен, указан ли фактический множитель в соответствии со стандартом Java.)

Теперь естественный вопрос: почему? Почему бы просто не добавить, скажем, пять элементов каждый раз?

Это делается быстрее: вы добавляете n элементов бесплатно, а для элемента n + 1 вы должны скопировать предыдущие элементы n в массив размером 2n . Таким образом, стоимость копирования этих n элементов распределяется («амортизируется») по самим себе (поскольку вы ранее добавляли их бесплатно), и в среднем стоимость добавления каждого элемента составляла n / n , или около 1 операции на элемент.

(См. эту ссылку для дальнейшего обсуждения этой темы.)

Answer 3

Строго говоря, точное поведение при изменении размера не указано в спецификации / JavaDoc :

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

Это подразумевает, что внутренний массив не может быть изменен путем добавления постоянного числа, но что некоторое умножение должно быть вовлечено. Как указал maartinus, Sun JDK и OpenJDK умножают размер на 1,5 (примерно).