Во сколько раз расширится массив, если заполнить его наполовину

Расширение массива при заполнении наполовину

Ответ зависит от того, о каком контейнере идёт речь.

ArrayList в Java

ArrayList использует амортизированное расширение с коэффициентом 1.5:

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

// При добавлении 11-го элемента:
// capacity увеличивается на 50%: 10 * 1.5 = 15

// Формула в OpenJDK:
newCapacity = oldCapacity + (oldCapacity >> 1);
// >> 1 это то же самое, что разделить на 2

Процесс:

Банан заполнен на 50% (5 элементов из 10):
[1][2][3][4][5][ ][ ][ ][ ][ ]  capacity = 10

При добавлении 6-го элемента:
[1][2][3][4][5][6][ ][ ][ ][ ][ ][ ][ ][ ][ ]  capacity = 15
Расширился в 1.5 раза

HashMap в Java

HashMap удваивает размер:

HashMap<String, Integer> map = new HashMap<>();  // capacity = 16

// При достижении loadFactor * capacity элементов:
// loadFactor по умолчанию = 0.75

// Когда size > 16 * 0.75 = 12 элементов:
// capacity удваивается: 16 -> 32

newCapacity = oldCapacity << 1;  // << 1 это умножение на 2

Процесс:

Заполнено на 50% (8 элементов из 16):
size = 8, capacity = 16, loadFactor = 0.75
Порог расширения = 16 * 0.75 = 12

Ещё не достигнут порог, расширение НЕ происходит!

При добавлении 13-го элемента (65% заполнения):
size > порог (13 > 12) -> расширяем
capacity: 16 -> 32 (удвоилось в 2 раза)

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

// ArrayList
ArrayList<Integer> list = new ArrayList<>();  // cap = 10
for (int i = 0; i < 5; i++) {
    list.add(i);  // 50% заполнено
}
// cap всё ещё 10

list.add(5);  // При 6-м элементе: 10 * 1.5 = 15
list.add(6);  // 7-й элемент, все ещё 15

// HashMap
HashMap<Integer, Integer> map = new HashMap<>();  // cap = 16
for (int i = 0; i < 8; i++) {
    map.put(i, i);  // 50% заполнено (8 из 16)
}
// cap всё ещё 16 (порог = 12, не достигнут)

for (int i = 8; i < 13; i++) {
    map.put(i, i);  // При 13-м элементе cap -> 32
}

Сравнение

Амортизированная сложность

Расширение дорогое O(n), но происходит редко:

// Добавить n элементов в ArrayList:
// Время = O(n) + стоимость копирований
// Если расширяем в 1.5 раза: O(n) в сумме
// Если расширяем в 2 раза: O(n) в сумме
// Амортизированная сложность одного add: O(1)

Вывод: При заполнении ровно наполовину (50%) массив НЕ расширяется ни в ArrayList, ни в HashMap. Расширение происходит в разные моменты: ArrayList расширяет в 1.5 раза при переполнении, HashMap - в 2 раза при 75% заполнения.