Зачем увеличивать массив

Ответ

Зачем увеличивать массив

Массивы в Java имеют фиксированный размер, определяемый при создании. Когда нужно добавить больше элементов, чем может вместить текущий массив, требуется перестроение (resizing) массива. Это основной механизм работы динамических структур данных как ArrayList.

Проблема: фиксированный размер массива

// Массив создаётся с фиксированным размером
int[] arr = new int[5];  // Может содержать ровно 5 элементов
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;

// Попытка добавить 6-й элемент вызывает ошибку
arr[5] = 60;  // ArrayIndexOutOfBoundsException!

Для разрешения этой проблемы требуется увеличение размера массива.

Как работает увеличение массива

Процесс состоит из четырёх шагов:

public class DynamicArray {
    private int[] arr;
    private int size = 0;  // Количество элементов, которые мы используем
    
    public DynamicArray() {
        arr = new int[10];  // Начальный размер
    }
    
    public void add(int value) {
        // Если достигли полной вместимости — увеличиваем
        if (size == arr.length) {
            resize();
        }
        arr[size] = value;
        size++;
    }
    
    private void resize() {
        // Шаг 1: Создаём новый массив большего размера
        int newCapacity = arr.length * 2;  // Увеличиваем в 2 раза
        int[] newArr = new int[newCapacity];
        
        // Шаг 2: Копируем все элементы из старого в новый массив
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        // ИЛИ используем System.arraycopy() для оптимизации:
        // System.arraycopy(arr, 0, newArr, 0, arr.length);
        
        // Шаг 3: Переназначиваем ссылку на новый массив
        arr = newArr;
        
        // Шаг 4: Старый массив помечается для сборки мусора
        // (происходит автоматически)
    }
}

Как работает ArrayList в Java

ArrayList внутри использует точно этот же механизм:

public class ArrayList<E> implements List<E> {
    private Object[] elementData;
    private int size = 0;
    
    public ArrayList() {
        elementData = new Object[10];  // Начальная вместимость
    }
    
    public boolean add(E e) {
        // Проверяем, нужно ли расширять
        ensureCapacity(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // В Java 8+: используется формула oldCapacity + (oldCapacity >> 1)
        // Это означает: oldCapacity * 1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Стратегии увеличения размера

1. Удвоение (doubling) — O(n) амортизированная сложность

new_capacity = old_capacity * 2;

Преимущества:

• Гарантирует быстрый рост
• Минимизирует количество переаллокаций

Недостатки:

• Может потратить больше памяти, чем нужно
• Пустое место может быть потрачено впустую

2. Увеличение на 50% (что использует Java 8+)

new_capacity = old_capacity + (old_capacity >> 1);  // *1.5

Лучше сбалансирует память и производительность.

3. Линейный рост — O(n²) сложность

new_capacity = old_capacity + 10;

Это плохая идея, потому что приводит к квадратичной сложности:

// Добавление 1000 элементов с линейным ростом
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // Множество копирований!
}
// Суммарно: 10 + 20 + 30 + ... + 1000 = O(n²) операций

Временная сложность операций

ArrayList<Integer> list = new ArrayList<>();

// add() с увеличением размера
// Амортизированная сложность: O(1)
for (int i = 0; i < 1000; i++) {
    list.add(i);
}

// get() — O(1)
int element = list.get(500);

// remove(index) — O(n)
list.remove(0);  // Нужно сдвинуть все элементы

// add(index, element) — O(n)
list.add(500, 999);  // Нужно сдвинуть элементы

Практический пример: собственная реализация

public class SimpleList<T> {
    private T[] arr;
    private int size = 0;
    private static final int INITIAL_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public SimpleList() {
        arr = new Object[INITIAL_CAPACITY];
    }
    
    public void add(T element) {
        if (size == arr.length) {
            growCapacity();
        }
        arr[size++] = element;
    }
    
    @SuppressWarnings("unchecked")
    private void growCapacity() {
        int newCapacity = arr.length * 2;
        T[] newArr = new Object[newCapacity];
        
        System.arraycopy(arr, 0, newArr, 0, size);
        arr = newArr;
        
        System.out.println("Расширили массив до " + newCapacity);
    }
    
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        return (T) arr[index];
    }
    
    public int size() {
        return size;
    }
}

// Использование
public class Main {
    public static void main(String[] args) {
        SimpleList<Integer> list = new SimpleList<>();
        
        for (int i = 0; i < 30; i++) {
            list.add(i);
        }
        
        System.out.println("Размер: " + list.size());
    }
}

Вывод

Увеличение массива — это критически важный механизм для работы динамических структур данных. Правильная стратегия роста (обычно удвоение) обеспечивает O(1) амортизированную сложность для добавления элементов, что делает ArrayList мощным и часто используемым инструментом в Java.