Во сколько раз увеличивается List при превышении capacity?

Коэффициент расширения List при превышении capacity

• Контекст: динамические массивы, включая List в .NET, Java и других платформах
• Когда capacity оказывается недостаточной, List увеличивает размер своего внутреннего массива
• В большинстве реализаций размер буфера увеличивается в 2 раза (factor = 2)
• Удвоение помогает сократить число аллокаций и операций копирования элементов
• Само расширение требует значительных затрат времени: необходимо выделить память и перенести данные
• Благодаря этому вставка имеет амортизированную сложность O(1)
• Практический результат: элементы добавляются быстро, а количество операций realloc остается небольшим

Подробности:

В динамическом массиве, например List<T> в .NET или ArrayList в Java, добавление элемента запускает расширение, если внутренний буфер уже заполнен до текущего значения capacity.

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

Удвоение capacity представляет собой компромисс между стоимостью копирования и числом расширений. Если коэффициент меньше, переаллокации происходят слишком часто; если больше — увеличивается объем неиспользуемой выделенной памяти.

Хотя копирование при расширении само по себе является дорогой операцией, в среднем вставка сохраняет амортизированную сложность O(1).

Итак, в типичном случае коэффициент расширения равен 2: это позволяет поддерживать хороший баланс между производительностью и использованием памяти по мере увеличения списка.

Подробный ответ

Основной ответ

В стандартной реализации ArrayList в Java при достижении текущего значения capacity внутренний массив увеличивается примерно на 50%. Иными словами, к прежнему размеру добавляется его половина, поэтому новая capacity составляет приблизительно 1.5 от исходной.

Ключевые моменты

• В Java 8 и более поздних версиях при вызове метода ensureCapacity либо при автоматическом увеличении внутреннего массива используется формула: newCapacity = oldCapacity + (oldCapacity >> 1). Она соответствует расширению примерно в 1.5 раза.
• Такой коэффициент позволяет сократить частоту расширений и одновременно не расходовать память на слишком большой запас свободного места.
• В других языках и реализациях коллекций применяется иной коэффициент. Например, C# List<T> увеличивает capacity в 2 раза, тогда как ArrayList в Java — примерно в 1.5 раза.

Практический контекст

Такой механизм не дает слишком часто копировать большие объемы данных, что важно для производительности. Если количество элементов известно заранее, рекомендуется явно задать capacity: это помогает рациональнее использовать память и избежать лишних копирований при массовом добавлении.