Если при вставке новых элементов в ArrayList
недостаточно места, то новая ёмкость рассчитывается по формуле: (oldCapacity*3)/2+1
С какой целью разработчики так усложнили расчет ёмкости? Нельзя было сделать, чтобы новая ёмкость добавлялась по одному? Спасибо.
2 ответа
Внутри ArrayList, как показывает его название, лежит обычный массив, так как Java не может гарантировать, что после массива есть свободная память, она увеличивает емкость ArrayList'а следующим образом:
- Создается массив с новой емкостью, под него выделяется соответствующее количество памяти,
- Все элементы старого массива копируются в новый,
- Ссылки на старый массив удаляются и память, выделенная под него, может быть удалена при следующей сборке мусора,
Как вы понимаете, это все достаточно медленные действия и если выполнять при каждом добавлении элемента производительность будет плохой. С другой стороны, увеличивать емкость слишком сильно приведет к перерасходу памяти.
Поэтому экспериментально подобрали именно такую формулу. Так же эта формула удобна из-за простоты целочисленного деления на 2. Если посмотреть текущую реализацию ArrayList, то там формула:
int newCapacity = oldCapacity + (oldCapacity >> 1);
Что очень быстро, так как это просто побайтовый сдвиг и сложение.
-
Понял, огромное спасибо за ответ. Интересно, а как JVM себя поведет, когда рассчитанный коэффициент получится с десятичной точкой? Сможет ли машина выделить 5.5 ячеек памяти или она округлит коэффициент до целого значения? 19 ноя 2017 в 13:37
-
Естественно округлит коэффициент до целого значения, на самом деле посмотрел реализацию в IDEA, там формула int newCapacity = oldCapacity + (oldCapacity >> 1); то есть десятичной точки там не будет никак. 19 ноя 2017 в 14:16
-
Эту формулу и битовый сдвиг стоит понимать как увеличение памяти в полтора раза, т.е. newCapacity=oldCapacity+(oldCapacity/2) 20 ноя 2017 в 18:14
-
Так формула аналогична той что приводили вы. (oldCapacity*3)/2+1 это тоже увеличение примерно в полтора раза. Вроде бы где-то до этого oldCapacity дополнительно увеличивалось на 1 (хотя не на 100% уверен), так что где-то тоже и выходит oldCapacity * 1,5 + 1 . Вообще, все исходники JDK открыты, а IDEA можно их отлично посмотреть, если интересно. 20 ноя 2017 в 18:18
Коэффициент получили опытным путем. Если добавлять по одному то замедлится скорость добавления новых элементов - так как на каждую вставку надо будет новый массив делать и копировать туда элементы. (Потому что после вашего массива в оперативной памяти могут идти другие данные) Очень рекомендую сделать свою версию с добавлением только на 1 элемент и замерить скорость работы на больших массивах данных.