Что означает capacity в ArrayList и HashSet в Java?

Capacity (вместимость) — это размер внутреннего массива, выделенного для хранения элементов. Отличается от size (фактическое количество элементов).

ArrayList

// Создание с указанием начальной capacity
ArrayList<String> list = new ArrayList<>(50); // capacity = 50, size = 0

// Методы для работы с capacity
list.ensureCapacity(100); // Гарантирует capacity не менее 100
list.trimToSize();        // Уменьшает capacity до текущего size

Механизм расширения:

1. Начальная capacity по умолчанию = 10
2. При добавлении элемента, если size == capacity, происходит расширение:

   // Внутренняя логика ArrayList
   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1); // Увеличение в 1.5 раза
       if (newCapacity < minCapacity) {
           newCapacity = minCapacity;
       }
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

HashSet

HashSet использует внутри HashMap, поэтому capacity относится к размеру массива бакетов.

// capacity = 16, loadFactor = 0.75 по умолчанию
HashSet<String> set1 = new HashSet<>();

// Явное указание начальной capacity
HashSet<String> set2 = new HashSet<>(32); // capacity = 32

// capacity и loadFactor
HashSet<String> set3 = new HashSet<>(64, 0.5f); // capacity=64, loadFactor=0.5

Порог расширения (threshold):

threshold = capacity * loadFactor
// По умолчанию: 16 * 0.75 = 12
// При добавлении 13-го элемента HashMap/HashSet увеличит capacity

Процесс rehashing при расширении:

1. Создаётся новый массив в 2 раза больше
2. Все элементы перераспределяются по новым бакетам
3. index = hash(key) & (newCapacity - 1)

Практические рекомендации:

// 1. Избегайте частых расширений при известном размере
List<String> largeList = new ArrayList<>(expectedSize);

// 2. Для HashSet выбирайте capacity с запасом
// Если ожидается ~1000 элементов:
Set<String> optimalSet = new HashSet<>(1333); // 1000 / 0.75 ≈ 1333

// 3. Сравнение capacity vs size
ArrayList<Integer> list = new ArrayList<>(100);
list.add(1); list.add(2); list.add(3);
System.out.println(list.size());     // 3 (элементы)
// capacity остаётся 100, но это внутренняя деталь реализации

Критические моменты:

• Увеличение capacity — операция O(n) (копирование массива)
• Слишком большая начальная capacity — пустая трата памяти
• Для HashSet/HashMap capacity всегда степень двойки (для битовой маски)