С каким фактором расширяется List при превышении capacity?

Question

При превышении Capacity внутренний массив List<T> в .NET заменяется на новый, размер которого рассчитывается как удвоение текущей емкости. Например, если Capacity был 4, то после добавления 5-го элемента он станет 8. Это стратегия позволяет операциям Add выполняться в среднем за константное время (амортизированная O(1)).

YeaHub · Accepted Answer

Механизм роста List — это оптимизация, предназначенная для минимизации количества дорогостоящих операций копирования массива.Детали процесса расширения:Изначальное состояние:При создании пустого списка начальная Capacity обычно равна 0.При создании списка с элементами или заданной емкостью, Capacity устанавливается соответственно.Момент расширения:Когда вызывается Add и текущее количество элементов (Count) равно Capacity, срабатывает триггер расширения.Алгоритм роста:Новая Capacity рассчитывается как CurrentCapacity * 2 (удвоение).Если текущая емкость равна 0, то новая емкость устанавливается в стандартное начальное значение (в современных версиях .NET это 4, но это деталь реализации).Выделяется новый массив увеличенного размера.Все элементы из старого массива копируются в новый.Старый массив отправляется в сборщик мусора.Пример:List numbers = new List(); // Capacity = 0, Count = 0 numbers.Add(1); // Capacity становится 4, Count = 1 numbers.Add(2); // Count = 2 numbers.Add(3); // Count = 3 numbers.Add(4); // Count = 4 (Capacity == Count) numbers.Add(5); // Срабатывает расширение. Новая Capacity = 4 * 2 = 8.Почему именно удвоение?Эта стратегия обеспечивает хороший баланс. Слишком маленький шаг роста (например, +10 элементов) приводит к частым копированиям. Слишком большой шаг (например, x10) приводит к избыточному расходу памяти. Удвоение — это компромисс, при котором амортизированная стоимость операции Add остается O(1).Вывод:Стратегия роста списка — это важная деталь, влияющая на производительность. Знание этого механизма помогает понять, почему задание начальной Capacity (если она известна) через конструктор List(int capacity) может устранить многократные копирования и повысить эффективность.