Как определить понятие емкости в ArrayLists?

1. Класс называется ArrayList, потому что он основан на массиве. Емкость — это размер массива, для которого требуется блок непрерывной памяти кучи. Однако обратите внимание, что сам массив содержит только ссылки на элементы, которые являются отдельными объектами в куче.
2. Увеличение емкости требует выделения нового массива большего размера и копирования всех ссылок из старого массива в новый, после чего старый становится пригодным для сборки мусора.
3. Вы упомянули основной случай, когда производительность может быть проблемой. На практике я никогда не видел, чтобы это действительно становилось проблемой, поскольку объекты-элементы обычно занимают гораздо больше памяти (и, возможно, процессорного времени), чем список.

ArrayList реализован так:

class ArrayList {
  private Object[] elements;
}

емкость - это размер этого массива.

Теперь, если ваша емкость равна 10, и вы добавляете 11-й элемент, ArrayList сделает следующее:

Object[] newElements = new Object[capacity * 1.5];
System.arraycopy(this.elements, newElements);
this.elements = newElements;

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

С другой стороны, если вы укажете емкость 1 000 000 и добавите в ArrayList только 3 элемента, это тоже будет плохо.

Правило большого пальца: если вы знаете емкость, укажите ее. Если вы не уверены, но знаете верхнюю границу, укажите это. Если вы просто не уверены, используйте значения по умолчанию.

Емкость - это то, что вы описали, - непрерывная память, выделенная ArrayList для хранения значений. ArrayList сохраняет все значения в массиве и автоматически изменяет размер массива для вас. Это влечет за собой накладные расходы на управление памятью при изменении размера.

Если я правильно помню, Java увеличивает размер резервного массива ArrayList с размера N до размера 2N + 2, когда вы пытаетесь добавить еще один элемент, чем может вместить емкость. Я не знаю, до какого размера он увеличивается, когда вы используете метод insert (или аналогичный) для вставки в определенную позицию за пределами емкости, и даже позволяет ли он это.

Вот пример, который поможет вам подумать о том, как это работает. Представьте каждое пространство между | как ячейку в резервном массиве:

| | |

размер = 0 (не содержит элементов), емкость = 2 (может содержать 2 элемента).

|1| |

размер = 1 (содержит 1 элемент), емкость = 2 (может содержать 2 элемента).

|1|2|

размер = 2, емкость = 2. Добавление еще одного элемента:

|1|2|3| | | |

размер увеличен на 1, вместимость увеличена до 6 (2 * 2 + 2). Это может быть дорого с большими массивами, так как выделение большой непрерывной области памяти может потребовать немного работы (в отличие от LinkedList, который выделяет много маленьких частей памяти), потому что JVM необходимо искать подходящее место и, возможно, потребуется запросить у ОС дополнительную память. Также дорого стоит копировать большое количество значений из одного места в другое, что будет сделано после того, как такая область будет найдена.

Мое эмпирическое правило таково: если вы знаете, какая емкость вам потребуется, используйте ArrayList, потому что будет только одно выделение, а доступ будет очень быстрым. Если вы не знаете требуемую емкость, используйте LinkedList, потому что добавление нового значения всегда требует одинакового объема работы и не требует копирования.

1) Какие есть хорошие способы определить, что представляет емкость с точки зрения памяти?

... (непрерывная?) память, выделенная для ArrayList?

Да, ArrayList поддерживается массивом, который представляет внутренний размер массива.

... объем памяти, занимаемой ArrayLists в (куче?)?

Да, чем больше емкость массива, тем больше места занимает массив.

2) Тогда, если вышесказанное верно, изменение емкости требует некоторых накладных расходов на управление памятью?

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

3) У кого-нибудь есть пример, где № 2 был или мог быть проблемой производительности? Помимо, возможно, большого количества больших списков массивов, емкость которых постоянно корректируется?

Да, если вы создаете ArrayList с начальной емкостью 1 (например), и ваш список выходит за эти пределы. Если вы заранее знаете количество элементов для хранения, вам лучше запросить начальную емкость этого размера.

Однако я думаю, что это должно быть последним в вашем списке приоритетов, в то время как копирование массива может происходить очень часто, оно оптимизировано с ранних стадий Java и не должно вызывать беспокойства. Думаю, лучше было бы выбрать правильный алгоритм. Помните: Преждевременная оптимизация — корень всех зол

См. также: Когда использовать LinkedList вместо ArrayList