Какой размер начального массива у ArrayList?

Какой размер начального массива у ArrayList?

Это классический вопрос, который хорошо показывает понимание внутреннего устройства коллекций Java. ArrayList — это один из наиболее часто используемых классов в Java, и знание его реализации критично для оптимизации производительности.

Размер начального массива

Ответ: 10 элементов по умолчанию

Когда вы создаёте ArrayList без указания начального размера, его внутренний массив имеет размер 10:

ArrayList<String> list = new ArrayList<>();
// Внутренний массив имеет размер 10, но содержит 0 элементов

Почему именно 10?

Это число выбрано как баланс между:

• Экономией памяти — 10 элементов достаточно для большинства случаев
• Частотой переаллокаций — не слишком мало, чтобы часто переживимать
• Практичностью — число 10 было подобрано эмпирически разработчиками Sun Microsystems

Исходный код Java

Если посмотреть на исходный код ArrayList в Java, вы найдёте:

public class ArrayList<E> extends AbstractList<E> {
    // Размер по умолчанию
    private static final int DEFAULT_CAPACITY = 10;
    
    // Внутренний массив
    transient Object[] elementData;
    
    // Размер списка
    private int size;
    
    // Конструктор без параметров
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // Конструктор с начальным размером
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}

Как работает расширение

Когда массив переполняется, ArrayList автоматически расширяется:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    // Увеличиваем на 50% (oldCapacity >> 1 это деление на 2)
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Процесс роста ArrayList

Представьте, что мы добавляем элементы в новый ArrayList:

ArrayList<Integer> list = new ArrayList<>();
// Внутренняя ёмкость: 10, размер: 0

for (int i = 0; i < 20; i++) {
    list.add(i);
}

// После add(0-9): ёмкость 10, размер 10
// После add(10): ёмкость расширена до 15, размер 11 (10 + 50% = 15)
// После add(11-14): ёмкость 15, размер 15
// После add(15): ёмкость расширена до 22, размер 16 (15 + 50% = 22.5 → 22)
// После add(16-19): ёмкость 22, размер 20

Как видите, при каждом расширении ёмкость увеличивается на 50% от текущего размера.

Оптимизация: указание начального размера

Если вы знаете примерный размер, лучше указать его при создании ArrayList:

// Плохо: множество переаллокаций
ArrayList<User> users = new ArrayList<>();
for (User user : getUsersFromDatabase()) {  // 10000 пользователей
    users.add(user);
}

// Хорошо: один раз создаём с нужным размером
ArrayList<User> users = new ArrayList<>(10000);
for (User user : getUsersFromDatabase()) {
    users.add(user);
}

Практический пример

public class ArrayListCapacityDemo {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        
        // Получаем размер через рефлексию (обычно это не рекомендуется)
        java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        
        System.out.println("Начальная ёмкость: " + ((Object[]) field.get(list)).length);
        // Вывод: Начальная ёмкость: 0 (до первого add)
        
        list.add(1);
        System.out.println("После 1-го add: " + ((Object[]) field.get(list)).length);
        // Вывод: После 1-го add: 10
        
        // Добавляем до 11 элементов
        for (int i = 2; i <= 11; i++) {
            list.add(i);
        }
        System.out.println("После 11 элементов: " + ((Object[]) field.get(list)).length);
        // Вывод: После 11 элементов: 15 (10 * 1.5)
        
        // Добавляем до 16 элементов
        for (int i = 12; i <= 16; i++) {
            list.add(i);
        }
        System.out.println("После 16 элементов: " + ((Object[]) field.get(list)).length);
        // Вывод: После 16 элементов: 22 (15 * 1.5 = 22.5 → 22)
    }
}

Влияние на производительность

// Измеряем влияние начального размера
public class PerformanceTest {
    public static void main(String[] args) {
        int size = 100_000;
        
        // Без оптимизации
        long start = System.nanoTime();
        ArrayList<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list1.add(i);
        }
        long time1 = System.nanoTime() - start;
        
        // С оптимизацией
        start = System.nanoTime();
        ArrayList<Integer> list2 = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list2.add(i);
        }
        long time2 = System.nanoTime() - start;
        
        System.out.println("Без размера: " + (time1 / 1_000_000) + "ms");
        System.out.println("С размером: " + (time2 / 1_000_000) + "ms");
        // На больших объёмах может быть 20-30% разница
    }
}

Дополнительные интересные факты

1. LinkedList не имеет начального размера — это список узлов, они создаются по требованию

2. CopyOnWriteArrayList — используется другая стратегия для потокобезопасности

3. Collections.synchronizedList() — обёртка вокруг ArrayList для синхронизации

4. trimToSize() — метод для экономии памяти, уменьшает ёмкость до текущего размера

ArrayList<String> list = new ArrayList<>(1000);
list.add("one");
list.add("two");
// Внутренняя ёмкость: 1000, размер: 2

list.trimToSize();
// Теперь внутренняя ёмкость: 2, размер: 2

Заключение

Начальный размер ArrayList — это 10 элементов. Когда нужно добавить больше, он расширяется на 50%. Если вы знаете, сколько элементов будет в списке, всегда указывайте начальный размер — это экономит время на переаллокации памяти и улучшает производительность приложения.