Недостаточно места в ArrayList

#java #arraylist

Если при вставке новых элементов в ArrayList недостаточно места, то новая ёмкость
рассчитывается по формуле: (oldCapacity*3)/2+1
С какой целью разработчики так усложнили расчет ёмкости? Нельзя было сделать, чтобы
новая ёмкость добавлялась по одному? Спасибо.
    

Ответы

Ответ 1

Внутри ArrayList, как показывает его название, лежит обычный массив, так как Java
не может гарантировать, что после массива есть свободная память, она увеличивает емкость
ArrayList'а следующим образом: 


Создается массив с новой емкостью, под него выделяется соответствующее количество памяти,
Все элементы старого массива копируются в новый, 
Ссылки на старый массив удаляются и память, выделенная под него, может быть удалена
при следующей сборке мусора,


Как вы понимаете, это все достаточно медленные действия и если выполнять при каждом
добавлении элемента производительность будет плохой. С другой стороны, увеличивать
емкость слишком сильно приведет к перерасходу памяти. 

Поэтому экспериментально подобрали именно такую формулу. Так же эта формула удобна
из-за простоты целочисленного деления на 2. Если посмотреть текущую реализацию ArrayList,
то там формула:

int newCapacity = oldCapacity + (oldCapacity >> 1);


Что очень быстро, так как это просто побайтовый сдвиг и сложение.


Ответ 2

Коэффициент получили опытным путем. Если добавлять по одному то замедлится скорость
добавления новых элементов - так как на каждую вставку надо  будет новый массив делать
и копировать туда элементы. (Потому что после вашего массива в оперативной памяти могут
идти другие данные) Очень рекомендую сделать свою версию с добавлением только на 1
элемент и замерить скорость работы на больших массивах данных.