Уравнение приращения емкости ArrayList

Question

В JDK 1.7 в ArrayList.java метод ensureCapacity увеличивает емкость массива с помощью следующего выражения: int newCapacity = oldCapacity + (oldCapacity >> 1), поэтому кажется, что новая емкость будет почти на 50% больше старой.

Однако во многих книгах говорится, что емкость удваивается ... поэтому книги не обновляются, или я плохо понимаю?

Answer 1

Вы понимаете, правильно, newCapacity на 50% больше, чем oldCapacity

В Java 6 newCapacity рассчитывается как

int newCapacity = (oldCapacity * 3)/2 + 1;

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

Answer 2

Из ArrayList Javadoc :

Подробности политики роста не указано, кроме того факта, что добавление элемента имеет константу Амортизированная стоимость времени.

Другими словами, книги могут быть точными для других реализаций, но ничего не гарантировано - и источник Java 7 по-прежнему совместим с документами, но показывает, что книги слишком специфичны.

Answer 3

ArrayLists в Java увеличивает емкость на 50%. Однако векторный класс в Java, который работает аналогично ArrayLists, но предлагает синхронизацию, удвоит емкость. Вероятно, именно из-за этого возникла путаница в ваших книгах.

Answer 4

В Java 6 newCapacity рассчитывается как => int newCapacity = (oldCapacity * 3) / 2 + 1;

В Java 7 newCapacity рассчитывается как => int newCapacity = oldCapacity + (oldCapacity >> 1)