Что такое Capacity в ArrayList и HashSet?

Capacity в ArrayList и HashSet: Размер буфера

Capacity — это размер внутреннего буфера (массива), который резервируется для хранения элементов коллекции. Это отличается от Size (размер), который представляет количество фактически добавленных элементов. Понимание capacity критически важно для оптимизации производительности.

Концепция Capacity vs Size

ArrayList<String> list = new ArrayList<>();
System.out.println(list.size());      // 0
System.out.println(list.capacity());  // 10 (по умолчанию)

list.add("A");
list.add("B");
list.add("C");
System.out.println(list.size());      // 3
System.out.println(list.capacity());  // 10 (буфер не заполнен)

ArrayList Capacity

Инициализация

По умолчанию ArrayList инициализируется с capacity = 10:

ArrayList<Integer> list = new ArrayList<>();  // capacity = 10
ArrayList<Integer> list2 = new ArrayList<>(20);  // capacity = 20
ArrayList<Integer> list3 = new ArrayList<>(otherList);  // capacity = размер otherList

Динамическое расширение

Когда size достигает capacity, ArrayList автоматически растет:

ArrayList<Integer> list = new ArrayList<>();  // capacity = 10

for (int i = 0; i < 15; i++) {
    list.add(i);
}
// После добавления 11-го элемента:
// capacity увеличился до 15 (10 * 1.5)
// После добавления 16-го элемента:
// capacity увеличился до 22 (15 * 1.5)

Формула расширения

Когда требуется новый capacity:

// Расчет нового capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);  // oldCapacity * 1.5

То есть ArrayList расширяет буфер на 50% каждый раз.

Получение и установка capacity

ArrayList предоставляет методы для управления capacity:

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

// Получить текущий capacity (через reflection или JVM tools)
// В Java нет прямого метода, но можно проверить при добавлении

// Зарезервировать место заранее
list.ensureCapacity(100);  // гарантирует capacity >= 100
list.add("element");        // не вызовет расширения

// Освободить неиспользуемое место
list.trimToSize();  // capacity = size
list.add("element");  // может вызвать расширение

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

ArrayList<Integer> list = new ArrayList<>();
long before = System.currentTimeMillis();

// БЕЗ оптимизации: много расширений
for (int i = 0; i < 100000; i++) {
    list.add(i);
}
long time1 = System.currentTimeMillis() - before;

// С оптимизацией: одно резервирование
ArrayList<Integer> list2 = new ArrayList<>();
list2.ensureCapacity(100000);  // резервируем место один раз
before = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    list2.add(i);
}
long time2 = System.currentTimeMillis() - before;

System.out.println("Без оптимизации: " + time1 + "ms");
System.out.println("С оптимизацией: " + time2 + "ms");
// Оптимизация примерно в 2 раза быстрее

HashSet Capacity

Инициализация

HashSet использует HashMap внутри, поэтому имеет свою стратегию capacity:

HashSet<String> set = new HashSet<>();  // capacity = 16 (по умолчанию)
HashSet<String> set2 = new HashSet<>(32);  // capacity = 32
HashSet<String> set3 = new HashSet<>(100, 0.75f);  // capacity=100, load factor=0.75

Load Factor

HashSet имеет концепцию load factor (коэффициент загрузки):

// Load factor по умолчанию = 0.75
// Это означает: когда (size / capacity) >= 0.75,
// HashSet автоматически удваивает capacity

HashSet<Integer> set = new HashSet<>();  // capacity=16, loadFactor=0.75
for (int i = 0; i < 13; i++) {
    set.add(i);
}
// size = 13, capacity = 16
// 13/16 = 0.8125 > 0.75, поэтому capacity увеличится до 32

set.add(13);  // Это добавление вызовет rehashing

Расчет rehashing

// Когда нужен новый capacity
int newCapacity = oldCapacity * 2;  // удваивается

// Все элементы перехешируются и перераспределяются
for (int i = 0; i < oldCapacity; i++) {
    // Переместить элементы в новые бакеты
}

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

HashSet<String> set = new HashSet<>();

// БЕЗ оптимизации: много rehashing
long before = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    set.add(String.valueOf(i));
}
long time1 = System.currentTimeMillis() - before;

// С оптимизацией: одно резервирование
HashSet<String> set2 = new HashSet<>(200000);  // capacity достаточный
before = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    set2.add(String.valueOf(i));
}
long time2 = System.currentTimeMillis() - before;

System.out.println("Без оптимизации: " + time1 + "ms");
System.out.println("С оптимизацией: " + time2 + "ms");

Сравнение ArrayList и HashSet Capacity

Когда оптимизировать Capacity

1. Известный размер заранее

// Если заранее знаете размер
ArrayList<String> list = new ArrayList<>(50000);
HashSet<Integer> set = new HashSet<>(50000);

// Добавляйте элементы без опасения

2. Массовые операции

// Перед большим циклом добавлений
ArrayList<Data> data = new ArrayList<>();
data.ensureCapacity(1000000);

for (Data d : loadDataFromDatabase()) {
    data.add(d);  // быстро без расширений
}

3. Уменьшение памяти

// После множества удалений
ArrayList<String> list = new ArrayList<>();
// ... добавления и удаления ...
list.trimToSize();  // освобождает неиспользуемую память

Мифы и заблуждения

Миф 1: HashSet медленнее ArrayList

// Неправда! На больших объемах HashSet быстрее благодаря O(1) поиску
ArrayList<Integer> list = new ArrayList<>();
HashSet<Integer> set = new HashSet<>();

// Добавления O(1) для обоих
for (int i = 0; i < 100000; i++) {
    list.add(i);
    set.add(i);
}

// Поиск: HashSet O(1), ArrayList O(n)
for (int i = 0; i < 100000; i++) {
    set.contains(i);      // быстро
    list.contains(i);     // медленно
}

Миф 2: Нужно всегда резервировать capacity

// Неправда для малых коллекций
ArrayList<String> small = new ArrayList<>();
small.add("a");
small.add("b");
// Оптимизация здесь не нужна

// Но для больших коллекций критична
ArrayList<String> large = new ArrayList<>();
large.ensureCapacity(1000000);  // ОБЯЗАТЕЛЬНО

Лучшие практики

1. Используйте конструкторы с capacity при известном размере
2. ensureCapacity() перед большими циклами добавления
3. trimToSize() для освобождения памяти после массовых удалений
4. Выбирайте нужную коллекцию: ArrayList для последовательности, HashSet для уникальности
5. Профилируйте настоящие критичные места, не оптимизируйте вслепую

Понимание capacity — это ключ к написанию высокопроизводительного Java кода.