предисловие
Как наиболее часто используемый класс в структуре коллекций Java, ArrayList в целом лучше всего подходит для хранения данных коллекций. Чтобы лучше понять и использовать ArrayList, в этой статье мы подробно рассмотрим ArrayList со следующих аспектов:
- Почему бы не использовать массив, используйте ArrayList
- Анализ исходного кода функции ArrayList
- ArrayList после Java 8
- Правильная поза использования ArrayList
Почему бы не использовать массив, используйте ArrayList.
В языке Java, поскольку обычные массивы ограничены по длине, длина массива должна быть ограничена во время инициализации, и он не может быть динамически расширен в соответствии с количеством элементов, а массивы Java имеют ограниченные методы для вызова разработчиками. взять элементы, получить длину массива и добавить элементы.Некоторые простые операции. В фоновом режиме в Java 1.2 была представлена мощная и богатая структура Collection, в которой ArrayList используется как реализация списка динамически расширяемых массивов, чтобы заменить использование Array в повседневной разработке.ArrayList реализует все методы работы со списками, что удобно для разработчикам управлять коллекциями списков. Здесь мы сначала перечислим основные функции ArrayList, которые будут объяснены в следующих разделах:
-
заказанные элементы хранения
-
Разрешено повторение элемента, разрешено хранение
nullценность -
Поддержка динамического расширения
-
Не потокобезопасный
Чтобы лучше понять ArrayList, давайте сначала посмотрим на диаграмму классов UML из ArrayList:
Как видно из рисунка выше, ArrayList наследует AbstractList и напрямую реализует интерфейсы флагов типа Cloneable, Serializable и RandomAccess.
- AbstractList, как абстрактная реализация списка, поручает добавление, удаление, изменение и проверку элементов конкретным подклассам для реализации и предоставляет реализацию по умолчанию для итеративного обхода элементов.
- Реализация интерфейса Cloneable, указывающая, что ArrayList поддерживает вызов объектов
cloneметод, который реализует копию ArrayList. - Реализация сериализуемого интерфейса, показывающая, что ArrayList также поддерживает операции сериализации и десериализации с фиксированным
serialVersionUIDстоимость имущества. - Реализован интерфейс RandomAccess, указывающий, что к элементам в ArrayList можно получить произвольный доступ эффективно и результативно, а элементы можно получить в виде индексных номеров. Списки, реализующие интерфейс RandomAccess, можно просматривать напрямую с помощью обычных
forМетод цикла и эффективность выполнения выше для метода итератора.
Анализ исходного кода ArrayList
Войдя в исходный код ArrayList, вы можете быстро увидеть две важные переменные-члены ArrayList из структуры класса:elementDataиsize.
-
elementDataЭто массив объектов, а сохраненные элементы — это именно те элементы, которые должны храниться в ArrayList извне, то есть объект ArrayList поддерживает этот массив объектов Object[], а добавление, удаление, изменение и обход предоставляются извне. относятся к этому массиву. Элементы ArrayList хранятся в объектах массива в порядкеelementDataсередина. -
sizeПоле представляет количество элементов, добавленных в настоящее время в ArrayList. Следует отметить, что оно должно быть меньше или равно объекту массива.elementDataдлина. однажды, когдаsizeиelementDataArrayList имеет ту же длину и по-прежнему добавляет элементы в список, ArrayList выполнит операцию расширения, используя более длинный объект массива для хранения предыдущего элемента.
Поскольку нижний слой поддерживает массив объектов, элементы, добавленные в коллекцию ArrayList, естественным образом повторяются, что позволяетnull, и их позиции в индексах различаются.
Как расширить
Поняв, почему ArrayList хранит элементы по порядку и элементы могут повторяться, давайте посмотрим, как базовое расширение реализовано в виде динамического списка массивов.
В первую очередь определить, где время на расширение, как описано вышеsizeполе упоминается, когдаsizeиelementDataЕсли длина одинакова, добавление другого элемента в коллекцию в этот момент приведет к недостаточной емкости и ее необходимо расширить, то есть операция расширения ArrayList происходит в методе добавления и происходит только при выполнении определенных условий. .
Теперь давайте посмотрим на структуру кода класса ArrayList, мы видим, что есть четыре метода добавления элементов, разделенных на две категории: добавление одного элемента и добавление всех элементов в другую коллекцию.
Начнем с простого метода анализа, см.add(E):booleanРеализация метода:
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Из приведенного выше вы можете видеть, что третья строка кода просто добавляет один элемент и позволяетsizeУвеличьте на 1, тогда реализация расширения будетensureCapacityInternalметод, передаваемые здесь параметрыsize+1 должен оценить количество добавленных элементов до фактического добавления элементов, то есть будет ли минимальная емкость, необходимая для коллекции, превышать длину исходного массива. посмотри на это сноваensureCapacityInternalреализация метода
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
}
Внутри него по-прежнему есть два вызова методов, сначала посмотрите на более простыеcalculateCapacityметод:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
когдаelementDataиDEFAULTCAPACITY_EMPTY_ELEMENTDATAРавно, то есть когда массив пуст, возвращает значение минимальной емкости по умолчанию, которое может добавлять элементыDEFAULT_CAPACITYсоответствует 10, иначе согласно входящемуsize+1 — минимальное значение вместимости, продолжайте видеть после выполненияensureExplicitCapacityметод:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Из кода видно, что расширение реализовано вgrowметод, и только если длина массива меньше требуемой минимальной емкости: когда элемент хранения массива заполнен, он не может хранить больше элементов, которые будут добавлены.
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Перейти дальшеgrowРеализация метода, вы можете видеть, что 8-я строка использует метод класса инструментаjava.util.Arrays#copyOf(T[], int), Скопируйте исходный массив и сохраните все внутренние элементы до длиныnewCapacityв новый массив , и назначьте ссылку на соответствующий новый массив дляelementData. На данный момент объект, указанный внутри ArrayList, является новым массивом с обновленной длиной, и эффект реализации показан ниже:
Теперь обратим внимание на новую емкость массиваnewCapacityНасколько регулируется. во-первыхnewCapacityпройти черезoldCapacity + (oldCapacity >> 1)Рассчитано с использованием битовых операций для преобразования исходного значения емкостиoldCapacityСдвинув один бит вправо, получить половину его значения (округлить в меньшую сторону), а затем добавить исходное значение емкости, тогда это исходное значение емкостиoldCapacity1,5 раза.
>>Правый битовый оператор, который сдвигает левый операнд вправо, что эквивалентно делению на 2 и округлению в меньшую сторону, например, выражение(7 >> 1) == 3Результат верный.
при расчетеnewCapacityКогда он все еще меньше входящего значения минимальной емкости, это означает, что текущее количество массивов пусто, и используется значение по умолчанию.DEFAULT_CAPACITYВыделите массив как значение емкости.
Следует отметить, что существует также суждение о максимальном количестве массивов.MAX_ARRAY_SIZEСоответствующий код в файле определяется следующим образом:
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Существует максимальное ограничение на количество элементов, хранящихся в ArrayList.Если ограничение будет превышено, JVM выдастOutOfMemoryErrorаномальный.
сюдаjava.util.ArrayList#add(E)Анализируется логика расширения метода. Точно так же мы можем видеть, что при реализации других методов добавления элементовensureCapacityInternalПри вызове метода емкость будет подтверждена перед фактической операцией базового массива, и будет выполнено динамическое расширение, если емкость недостаточна.
Сериализация и десериализация
transient Object[] elementData;
Видно в исходном коде ArrayListelementDataс ключевыми словамиtransient, в то время как обычноtransientЕсли ключевое слово изменяет поле, это означает, что поле не будет сериализовано, но ArrayList реализует интерфейс сериализации и предоставляет метод сериализации.writeObjectметодом десериализацииreadObjectреализация, как это делается?
Давайте сначала посмотрим на код для сериализации ArrayList:
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Строка 4 сначала преобразует не-staticмодифицированный, неtransientВ поток выписывается декорированное поле, в строке 6 в качестве емкости будет записано количество элементов.
Следующим шагом является запись всех содержащихся в нем элементов в поток через цикл.На этом шаге видно, что ArrayList не сериализует пространство памяти без хранения данных в реализованном сам по себе методе сериализации, экономя место и время .
Точно так же при десериализации он получается из данных потока, прочитанных вsizeатрибут, затем расширьте массив и, наконец, сохраните все данные элемента, считанные в потоке данных, в удерживаемый массив объектов.
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
s.defaultReadObject();
s.readInt(); // ignored
if (size > 0) {
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
О копировании
Для копирования элементов списка ArrayList предоставляет пользовательскую реализацию клона следующим образом:
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
Из приведенного выше кода видно, что выполнениеcopyOfОперация представляет собой неглубокую операцию копирования, элементы исходного объекта ArrayList не будут скопированы и сохранены в новом объекте ArrayList, а затем возвращены в соответствующие поля.elementDataКаждое место в массиве хранит ссылку на один и тот же элемент.Как только один список изменяет элемент в массиве, другой список также будет затронут.
ArrayList после JDK 1.8
Проанализировав характеристики ArrayList с точки зрения исходного кода, давайте взглянем на новые изменения в классе ArrayList после JDK 1.8.
Добавлен метод removeIf
removeIfЭто метод интерфейса, недавно добавленный в интерфейс Collection.Поскольку родительский класс реализует этот интерфейс, ArrayList также имеет этот метод.removeIfМетод используется для удаления элемента из массива с заданным условием.
public boolean removeIf(Predicate<? super E> filter){...}
Передайте параметр функционального интерфейса, представляющий условиеPredicate, то есть лямбда-выражение выполняет условное сопоставление, если условиеtrue, затем удалите элемент из массива, как показано в следующем примере кода:
List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
numbers.removeIf(i -> i % 2 == 0);
System.out.println(numbers); // [1, 3, 5, 7, 9]
Добавлен метод разделения
Этот метод также исходит из интерфейса Collection, и ArrayList переопределяет этот метод. Этот метод возвращает экземпляр ListSpliterator, который используется для повторения и разделения элементов, хранящихся в контейнере.
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
В реализации ArrayList этот метод возвращает внутренний объект статического класса ArrayListSpliterator, с помощью которого можно управлять элементами коллекции.
Существует три основных метода работы:
-
tryAdvanceИтерация по одному элементу, что-то вродеiterator.next() -
forEachRemainingперебирать оставшиеся элементы -
trySplitРазделение элемента на две части выполняется параллельно, но следует отметить, что Spliterator не является потокобезопасным.
Хотя эти три метода обычно не используются, все же необходимо понять, вы можете просто посмотреть, как используются методы.
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6));
Spliterator<Integer> numbers = numbers.spliterator();
numbers.tryAdvance( e -> System.out.println( e ) ); // 1
numbers.forEachRemaining( e -> System.out.println( e ) ); // 2 3 4 5 6
Spliterator<Integer> numbers2 = numbers.trySplit();
numbers.forEachRemaining( e -> System.out.println( 3 ) ); //4 5 6
numbers2.forEachRemaining( e -> System.out.println( 3 ) ); //1 2 3
Должен использовать позу
Изучив исходный код ArrayList и новый API, мы, наконец, научились эффективно использовать ArrayList в обычной разработке.
Эффективная инициализация
ArrayList реализует три конструктора, которые будут выделены пустому объекту массива при создании по умолчанию.EMPTY_ELEMENTDATA; Второй — передать данные типа коллекции для инициализации; третий позволяет передать в инициализирующем значении длину коллекции, то есть длину массива. Так как длины массива не хватает, каждый раз это будет приводить к расширению, повторно подавать заявку на большее пространство памяти и копировать его. И давайте инициализируем ArrayList, чтобы указать начальный размер массива, что может уменьшить количество расширений массива и повысить производительность.
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
обход элемента
До JDK 1.8 ArrayList поддерживал только три метода обхода: обход итератора, нормальный обходforцикл,for-eachУлучшение: после введения Stream API в JDK1.8 ArrayList, принадлежащий коллекции Collection, может использоватьstream.foreach()Метод получает элементы один за другим:
ArrayList<String> names = new ArrayList<String>(Arrays.asList( "alex", "brian", "charles"));
names.forEach(name -> System.out.println(name)); // alex brian charles
Преобразовать массив
ArrayList предоставляет два метода преобразования списков в массивы.
public Object[] toArray();
public <T> T[] toArray(T[] a);
- Первый метод напрямую возвращает массив типа Object
- Во втором методе тип возвращаемого массива является типом переданного указанного массива. И если длина списка соответствует входящему массиву, то после копирования элементов в массив в нем возвращается массив. В противном случае новый массив будет перераспределен в зависимости от типа переданного массива и размера списка, а копирование будет выполнено перед возвратом.
Из вышеприведенного описания видно, что больше подходит второй способ, который позволяет сохранить исходный тип:
ArrayList<String> list = new ArrayList<>(4);
list.add("A");
list.add("B");
list.add("C");
list.add("D");
String[] array = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(array)); // [A, B, C, D]
справиться с многопоточностью
Здесь следует отметить, что сам ArrayList не является потокобезопасным.Если вам нужно использовать потокобезопасный список, обычно этоjava.util.Collections#synchronizedList(java.util.List<T>)Или используйте вместо этого класс Vector. Другой способ — использовать параллельный класс-контейнер CopyOnWriteArrayList в многопоточности.Внизу он реализует операции, которые необходимо синхронизировать, такие как обновление и добавление, путем создания копии исходного массива.Это не только потоко- безопасно, но также снижает синхронизацию потоков.
Обработка добавления и удаления головных узлов
ArrayList реализован в виде массива и использует непрерывное пространство памяти, когда элементы добавляются или удаляются в начале массива, данные после головы необходимо копировать и переупорядочивать, что неэффективно. Для сценариев с большим количеством однотипных операций по соображениям производительности вместо этого следует использовать LinkedList. Поскольку LinkedList реализован на основе связанного списка, когда позиция элемента, с которым нужно работать, находится в первой половине списка, он будет проходить с самого начала, и элемент будет вставлен или удален в соответствующей позиции после его удаления. нашел сразу.
Эпилог
Здесь мы изучаем и подводим итоги реализации и общего использования ArrayList.Как базовая коллекция контейнеров, чем больше мы понимаем, тем проще будет наше повседневное использование. Поскольку выше упоминается еще одна коллекция списков, LinkedList, она реализована иначе, чем ArrayList, и имеет другие сценарии использования. Она появится в виде коллекции, анализируемой в следующей статье. Заинтересованные друзья могут обратить внимание на мой публичный аккаунт WeChat и ожидать к обновлениям.