4

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

2 ответа 2

8

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

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

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

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

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

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

4
  • Понял, огромное спасибо за ответ. Интересно, а как 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
4

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.