Почему разные коллекции Java имеют различную емкость по умолчанию?

11

Глядя на разных конструкторов коллекций, возникает вопрос. Почему ArrayList () создает пустой список с начальной емкостью десять, а ArrayDeque () создает пустой массив массивов с начальной емкостью, достаточной для хранения 16 элементов.

java collections Старый Бадман Грей
источник
У меня не было нового, у которого был предел мощности. Я просто добавляю новые элементы с помощью add (). Это всегда работает.
Тулин Кордова
1
Я думаю, что он говорит о начальном размере массива в реализации ArrayList. Как следует из его названия, ArrayList - это просто старый массив под обложками, и он автоматически создает большие массивы, когда вы пытаетесь добавить больше элементов, чем содержит его текущий размер массива.
dsw88
1
Я думаю, что StringBuilder - еще один, у которого есть емкость по умолчанию, это было 10 или 16?
Инго
@ Инго Интересно. Я даже не знал о вещах вне коллекций, перепутанных с емкостью, но я полагаю, что это имеет смысл. В то время не было метки для емкости, поэтому я не особо интересовался другими видами использования.
Старый Бадман Грей

Ответы:

17

Краткий ответ

Поскольку емкость ArrayDeque должна быть степенью двойки, а 16 - это наименьшая степень двойки, равная по меньшей мере 10.

ArrayDeque должен использовать множество% операций везде, чтобы обернуть вокруг линейного массива, который притворяется круглым.

a % bможет быть выражено, как a & (b - 1) будто b это степень двух. Побитовое И значительно быстрее, поэтому емкость ArrayDeque ограничена степенью двойки. Все операции% выполняются с битовой маскировкой вместо фактического% в реализации.

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

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

Esailija
источник
3

Не исключайте возможности того, что нет конкретной причины.

Возможно, эти две коллекции были написаны разными командами. Оба выбрали небольшое число в качестве емкости по умолчанию, но первая команда думала десятично и выбирала 10, а вторая команда думала двоично и выбирала 16.

рем
источник
1

Ответ @ Esailija хорош для этого конкретного случая.

В более общем смысле, это компромисс, который зависит от многих факторов. Я приведу несколько примеров:

  • Как обычно используется структура данных ? Структуры данных, которые используются в качестве буферов данных, обычно предпочитают гораздо более высокую емкость, чем структуры данных, используемые, например, для небольших кортежей.
  • Какой размер данных по умолчанию помещается в строку кэша на целевой платформе ЦП? Это может иметь большое значение для производительности, если значение по умолчанию помещается в строку кэша. Выбор 10 по умолчанию в Java вполне может быть обусловлен тем, что массив из 10 32-битных слов плюс издержки массива / объекта помещаются в 64-байтовую строку кэша.
  • Сколько вы цените пространство против эффективности времени выполнения ? Если вам нужна лучшая производительность во время выполнения, обычно лучше заранее выделить больше места, чтобы впоследствии избежать дополнительных перераспределений.

В результате этих компромиссов вполне понятно, что разные реализации коллекций могут иметь различную оптимальную емкость по умолчанию.

mikera
источник