Как динамически увеличивается емкость (capacity) ArrayList в Java?

ArrayList увеличивает свою внутреннюю емкость (размер базового массива) по мере необходимости. Стандартный коэффициент роста — 1.5.

Механизм увеличения:

1. При попытке добавить элемент, когда количество элементов (size) равно текущей емкости (capacity), срабатывает триггер на расширение.
2. Создается новый массив большего размера.
3. Новый размер вычисляется по формуле: newCapacity = oldCapacity + (oldCapacity >> 1).
   • oldCapacity >> 1 — это побитовый сдвиг вправо, эквивалентный целочисленному делению oldCapacity на 2.
   • Таким образом, newCapacity = oldCapacity * 1.5 (округление вниз).
4. Все элементы копируются из старого массива в новый.

Пример:

ArrayList<Integer> list = new ArrayList<>(10); // Исходный массив length = 10
for (int i = 0; i < 10; i++) list.add(i); // size=10, capacity=10
list.add(10); // Триггер! Вычисление: 10 + (10 >> 1) = 10 + 5 = 15
// Теперь capacity = 15, size = 11. Базовый массив length = 15.

Важные детали:

• Начальная емкость: По умолчанию равна 10. Ее можно задать через конструктор ArrayList(int initialCapacity) для оптимизации, если известен ожидаемый размер.
• Ручное управление: Метод ensureCapacity(int minCapacity) позволяет заранее увеличить внутренний массив до указанного размера, избегая многократных копирований при последовательном добавлении.

  ArrayList<String> list = new ArrayList<>();
  list.ensureCapacity(1000); // Сразу выделяется массив под 1000 элементов
  // Последующие 1000 вызовов add() не вызовут переаллокации.

• Уменьшение емкости: Метод trimToSize() уменьшает емкость до текущего размера списка, освобождая лишнюю память.