Как реализованы ArrayLists в Java?

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

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

Или существуют ли оптимизации для тестирования членства и разреженных массивов?

Ответы

Ответ 1

Это массив объекта. Из источника:

http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/tip/src/share/classes/java/util/ArrayList.java

private transient Object[] elementData;

Ответ 2

Да, основной объект [] управляется, как вы впервые предполагали, включая рост массива путем удвоения. Нет оптимизации для тестирования членства; просто поиск по элементам списка один за другим.

Стоит посмотреть исходный код, связанный с TofuBeer... вы можете многому научиться, изучив формальность, оптимизацию и "защитное кодирование" инженеров Sun/Oracle.

Ответ 3

An ArrayList расширяет AbstractList и реализует четыре интерфейса: List<E>, RandomAccess, Cloneable, java.io.Serializable.

И он хранит элементы в массиве Object[] как: private transient Object[] elementData;

Если вы скажете: ArrayList arr=new ArrayList();, то по умолчанию он создает ArrayList размера 10.

Существует метод private void grow(int minCapacity), который изменяет размер ArrayList