Вопрос по java – Почему емкость по умолчанию ArrayList 10?

35

Я видел документацию по Java для ArrayList и обнаружил, что начальная емкость ArrayList равна 10.

 /**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
this(10);
}

Я думаю, что было бы разумно, если бы это была степень 2, но почему 10?

Я также проверил начальную емкость HashMap, и это 16, что имеет смысл.

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

Есть ли какая-то конкретная причина за номером 10?

@AbhisekBose: да, ты пишешь. Моя ошибка. Это не размер. Я изменил вопрос. :) Priyank Doshi
После обновления Java 1.7.0_40 начальная емкость ArrayList равна 0 (указывает на пустой массив) Ankit Sharma
10 - это начальная емкость списка массивов, а не размер. Начальный размер всегда равен 0. BOSS
Я думаю, что это восходит к доминирующей форме жизни в CS, которая, кажется, имеет два манипулятора с 5 цифрами на каждом. Те, которые использовались для подсчета в первые дни вычислений. Поэтому они предпочитают степени 10 для всех видов вещей. Jens Schauder
& GT; & GT; & GT;it may make sence if it would be any number of power of 2 Зачем? Op De Cirkel

Ваш Ответ

7   ответов
0

Если в коде нет комментариев, мы никогда не узнаем наверняка. Тем не менее, я полагаю, что в какой-то момент инженер Sun собрал статистику использования ArrayList для большого числа реальных приложений и определил ... опытным путем ... что 10 дал примерно лучшие результаты в среднем. (Вот как они настраивают такие вещи, как оптимизатор, дизайн байт-кода и т. Д.)

И, как отметили другие, нет вычислительного преимущества (или недостатка) в использовании размера, который является степенью двойки для размераArrayList.

13

Для Списка нет никакого преимущества в том, чтобы емкость была степенью двойки. На самом деле, нет никакого реального преимущества в какой-либо конкретной стартовой мощности. Он должен быть достаточно большим, чтобы избежать нескольких шагов изменения размера для обычного случая маленьких списков, и достаточно маленьким, чтобы не тратить память на неиспользуемую емкость в этом же случае. Вероятно, 10 был выбран просто потому, что он соответствует нужному диапазону, чтобы соответствовать этим требованиям, и потому, что он «круглый».

@Priyank Doshi: Вы, возможно, думаете об этом ...
@PriyankDoshi: ответ почти наверняка состоит в том, что он не имеет достаточного значения, чтобы его стоило суетиться. 10 более или менее достаточно мала, так что это не имеет большого значения, если оно переоценено, но достаточно велико, чтобы большеArrayLists будет изменен относительно быстро; беспокоиться о таких деталях, как точная емкость, просто излишне.
Для какой-либо конкретной емкости может не быть реального преимущества, даже если ее мощность равна 2. Но тогда, если разработчики Sun выполнили достаточно анализа большого количества сценариев, чтобы узнать какое-либо число, они должны, по крайней мере, поделиться им, возможно, не в документе Java, но любой официальный блог. Чтобы у каждого в сообществе оперсорсеров была идея, а другие программисты могли выразить свое мнение, чтобы сделать этот начальный номер емкости более релевантным фактическим сценариям использования разработки. Priyank Doshi
Обычно число, которое является степенью 2, является предпочтительным выбором в алгоритмах компьютерного программирования, когда вы имеете дело с распределением памяти и всем этим. Так я и думал. Priyank Doshi
@Priyank Doshi: идеальный начальный объем будет отличаться между приложениями, поэтому среднее значение по большому количеству сценариев на самом деле не будет очень полезным - точное значение крайне маловероятно для большинства приложений, но для тех, где оно имеет значение, Вы хотите использовать лучшее значение для этого конкретного приложения, а не какое-то среднее значение.
10

Vectorиз JDK 1.0 исходная емкость по умолчанию равнялась 10, поэтому, вероятно, имело смысл оставаться последовательным, когда они представилиArrayList в 1.2.

Нет. Это было бы несовместимым изменением. Javadoc, который является спецификацией, говорит, что емкость по умолчанию равна 10, поэтому они не могут просто изменить ее.
@PriyankDoshi Я имею в виду, что они, вероятно, хотели, чтобы ArrayList оставался совместимым с Vector, поскольку они тесно связаны. Не ссылаясь на другие реализации коллекции.
40

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

1 будет слишком мало. Даже с несколькими элементами у нас будет несколько операций изменения размера.

100 будет потеря пространства.

Итак, 10 - это компромисс. Почему 10, а не 12 или 8? Первый намек на то, что были проанализированы типичные варианты использования, и это наилучшее соответствие между потерей производительности и потерей места. Однако, я думаю, видя исходный код Солнца, он не был так глубоко проанализирован, и это произвольный «не слишком маленький, не слишком большой». число.

0

ArrayList is just an Array which can grow automatically..

Yes..the default size is 10

и я думаю, что за этим начальным значением / значением по умолчанию не особо задумывается. Значение по умолчанию 10 кажется не слишком большим, а также не слишком маленьким (возможно, это может быть причиной). Что если вы превысите начальную емкость массива по умолчанию? Следующая емкость для массива рассчитывается как

New capacity=(current capacity*3)/2+1
So next size would be (10*3)/2+1= 16
And next (16*3)/2+1= 25
And So on...
1

10, вероятно, является более или менее произвольным числом для числа элементов по умолчанию.

Я не думаю, что разработчики Sun достаточно безумны, чтобы использовать любое случайное число в качестве числа по умолчанию, не задумываясь. Должно быть, они думали о каком-то полезном и эффективном сценарии. Priyank Doshi
5

Совершенно произвольный выбор.

И нет никакой причины, почему power-2 имеет больше смысла здесь. Это имеет смысл в HashMap из-за того, как работает хеширование. На самом деле этоhas to be степень двойки (согласно комментарию в источнике).

Обратите внимание, что java.util.Vector (который является старшим братом ArrayList) также имеет 10.

да, это также имеет. И может быть причина также в емкости ArrayList. Но тогда возникает вопрос: почему начальная емкость вектора равна 10? Priyank Doshi

Похожие вопросы