1. Обзор ArrayList
ArrayListБазовая структура данныхдинамический массив, поэтому мы можем назвать это очередью массива. Зависимости ArrayList:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Как видно из зависимостей, ArrayList — это во-первых список, а во-вторых, у него есть родственные функции списка, поддерживающие быстрое (фиксированное время) позиционирование ресурсов. Можно выполнять операции копирования, поддерживается сериализация. Здесь нам нужно сосредоточиться на AbstractLit и RandomAccess. Этот класс предназначен для определения основных свойств списка, а также для определения общих действий в нашем списке. RandomAccess в основном обеспечивает функцию быстрого определения местонахождения ресурса.
2. Переменная-член ArrayList
/**
* Default initial capacity.数组默认大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
空队列
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
如果使用默认构造方法，则默认对象内容是该值
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
用于存储数据
*/
transient Object[] elementData;
// 当前队列有效数据长度
private int size;
// 数组最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
В исходном коде ArrayList в основном присутствуют указанные выше переменные-члены:
- elementData : динамический массив, который является основным массивом, в котором мы храним данные.
- DEFAULT_CAPACITY: длина массива по умолчанию, которая будет введена при вызове конструктора по умолчанию.
- size: запишите эффективную длину данных, метод size() возвращает это значение напрямую
- MAX_ARRAY_SIZE: максимальная длина массива, если расширение превышает это значение, установите длину в Integer.MAX_VALUE
Расширьте свое мышление:EMPTY_ELEMENTDATAиDEFAULTCAPACITY_EMPTY_ELEMENTDATAОба являются двумя пустыми объектами массива, в чем разница между ними? Мы проведем подробное сравнение, когда объясним метод построения в следующем разделе.
3. Метод строительства
ArrayListТри метода построения предусмотрены в:
- ArrayList()
- ArrayList(int initialCapacity)
- ArrayList (Коллекция c)
В зависимости от конструктора способ строительства будет разным. В нашей обычной разработке ArrayList (целая емкость) может вызываться внутри конструктора по умолчанию, но в ArrayList дляРазные конструкторы имеют разные внутренние реализации, в основном связанные с упомянутыми выше переменными-членами.
3.1 СписокСписков()
Это описано в комментариях к исходному коду следующим образом: Построить пустой список с начальной емкостью десять
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Как видно из исходного кода, он просто конвертируетelementDataуказал наDEFAULTCAPACITY_EMPTY_ELEMENTDATAадрес хранения иDEFAULTCAPACITY_EMPTY_ELEMENTDATAНа самом деле это пустой объект массива, так почему же он говорит создать список с размером по умолчанию 10?
Или давайте подумаем об этом с другой стороны, а что, если нам нужно добавить элементы в этот пустой массив?
public boolean add(E e) {
ensureCapacityInternal(size + 1); //确认内部容量
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
设置默认大小 为DEFAULT_CAPACITY
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确定实际容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果超出了容量，进行扩展
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Приведенный выше блок кода относительно длинный, вот краткое изложение:
1. add(E e): чтобы добавить элемент, сначала определите длину массива elementData, а затем установите значение
2. sureCapacityInternal (int minCapacity): определить, является ли элемент пустым, если да, установить длину массива по умолчанию
3. sureExplicitCapacity (int minCapacity): определите, превышает ли длина массива ожидаемого роста текущую емкость, и если да, вызовите функциюrow().
4. Grow (int minCapacity): расширить массив
回到刚才的问题：为什么说创建一个默认大小为10 的列表呢？或许你已经找到答案了～
3.2 ArrayList(int initialCapacity)
Инициализировать размер массива в ArrayList в соответствии с указанным размером, если значение по умолчанию больше 0, инициализировать в соответствии с параметром, если он равен 0, указать адрес памяти EMPTY_ELEMENTDATA (аналогично использованию конструктора по умолчанию выше) . Если меньше 0, генерируется исключение IllegalArgumentException.
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);
}
}
Расширение мышления: почему здесь используетсяEMPTY_ELEMENTDATAвместо использования конструктора по умолчаниюDEFAULTCAPACITY_EMPTY_ELEMENTDATA? Заинтересованная детская обувь может подумать сама, а знания после размышлений ваши~
3.3 ArrayList (коллекция c)
Преобразуйте данные, хранящиеся в Collection
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.4 Резюме
Как видно из приведенных выше трех методов построения, на самом деле то, что делает каждый конструктор, отличается, особенно прямая разница между конструктором по умолчанию и ArrayList(int initialCapacity), нам нужно сделать некоторые различия.
- ArrayList(): указывает наDEFAULTCAPACITY_EMPTY_ELEMENTDATA, когда список используется, он будет инициализирован, а размер массива по умолчанию будет установлен путем определения того, является ли он объектом DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
- ArrayList(int initialCapacity): когда initialCapacity > 0, установите длину. если initialCapacity = 0, указывает наEMPTY_ELEMENTDATAПри использовании длина массива по умолчанию не устанавливается.
Следовательно, существенное различие между DEFAULTCAPACITY_EMPTY_ELEMENTDATA и EMPTY_ELEMENTDATA заключается в том, будет ли установлена длина массива по умолчанию.
4. Добавить метод (Добавить)
ArrayList добавляет четыре метода добавления:
- add(E element)
- add(int i , E element)
- addAll(Collection<? extends E> c)
- addAll(int index, Collection<? extends E> c)
4.1 add(E element)
Сначала посмотрите на исходный код add(T t):
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 元素个数加一，并且确认数组长度是否足够
elementData[size++] = e; //在列表最后一个元素后添加数据。
return true;
}
В сочетании с конструктором по умолчанию или другими конструкторами, если массив по умолчанию пуст, массив будет инициализирован при вызове метода sureCapacityInternal(). Поэтому при вызове конструктора по умолчанию мы создаем пустой массив, но в комментариях он описан как массив длины 10.
4.2 добавить (int i , T t)
public void add(int index, E element) {
// 判断index 是否有效
rangeCheckForAdd(index);
// 计数+1，并确认当前数组长度是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //将index 后面的数据都往后移一位
elementData[index] = element; //设置目标数据
size++;
}
Этот метод на самом деле похож на добавление выше. Этот метод может вставлять элементы в соответствии с позицией элемента и указанной позицией. Конкретная логика выполнения выглядит следующим образом:
1) Убедитесь, что позиция, в которую вставляется число, меньше или равна текущей длине массива и не меньше 0, иначе выдается исключение
2) Убедитесь, что массив использовал длину (размер) плюс 1 достаточно для хранения следующих данных
3) Количество модификаций (modCount) автоматически увеличивается на 1. Если текущая длина массива (размер) плюс 1 больше, чем текущая длина массива, вызывается метод Grow для увеличения массива
4) Метод Grow изменит длину текущего массива в 1,5 раза по сравнению с исходной емкостью.
5) Убедившись, что емкости достаточно, используйте System.arraycopy для перемещения всех элементов после позиции (индекса), которую необходимо вставить, на одно место.
6) Сохраните новое содержимое данных в указанной позиции (индексе) массива.
4.3 addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
Метод addAll() завершает добавление всех данных коллекции путем преобразования данных в коллекции в Array[] и добавления их в массив elementData. В начале ничего особенного в целом, сборка здесь может вызывать исключение управления NullPointerException и на это нужно обратить внимание.
4.4 addAll(int index, Collection extends E> c)
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
По сравнению с описанным выше методом, здесь в основном есть еще два шага, чтобы определить, находится ли позиция добавления данных в конце, если она находится в середине, вам нужно сначала переместить данные назад на позицию длины коллекции.
5. Удалить метод (Удалить)
Существует пять способов удаления данных в ArrayList:
- удалить (интервал я)
- удалить (элемент E)
- removeRange (начало int, конец int)
- чистый()
- удалить все (коллекция c)
5.1. удалить (целое я):
Удаление данных не меняет длину массива, оно только удаляет перестановку данных.Если у цели нет других действительных ссылок, она будет переработана во время GC.
public E remove(int index) {
rangeCheck(index); // 判断索引是否有效
modCount++;
E oldValue = elementData(index); // 获取对应数据
int numMoved = size - index - 1; // 判断删除数据位置
if (numMoved > 0) //如果删除数据不是最后一位，则需要移动数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 让指针最后指向空，进行垃圾回收
return oldValue;
}
5.2, удалить (элемент E):
Таким образом, массив будет внутренне пройден методом AccessRandom.Когда совпадающие данные равны объекту, для его удаления будет вызвана функция fastRemove().
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
быстроудалить(): Операция fastRemove фактически согласуется с вышеупомянутым удалением на основе индексов.
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
5.3, removeRange (int fromIndex, int toIndex)
Этот метод в основном удаляет данные в диапазоне и может перезаписать всю часть данных через System.arraycopy.
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
5.4. очистить()
Непосредственно установите для всего массива значение null , которое здесь подробно описываться не будет.
5.5. removeAll (Коллекция c)
В основном по телефону:
private boolean batchRemove(Collection<?> c, boolean complement) {
//获取数组指针
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//根据 complement 进行判断删除或留下
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 进行数据整理
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
Также есть вызовы в continueAll (Collection c), основные функции — удалить элементы, содержащиеся в этой коллекции, и оставить элементы, содержащиеся в этой коллекции.
расширить мышление
Узнав метод удаления ArrayList, а затем объединив наши часто используемые методы удаления, мы подумаем, какие шаги вызовут проблемы.Обычно мы выбираем список переменных, и если он совпадает, удаляем его. Проходим следующими путями:
- foreach(): ConcurrentModificationException в основном происходит
- for(int i;**;i++): те же данные пропускаются, см.: https://blog.csdn.net/sun_flower77/article/details/78008491
- Обход итератора: в основном появляетсяConcurrentModificationExceptionСсылка: https://www.cnblogs.com/dolphin0520/p/3933551.html
Эффективный способ избежать исключения ConcurrentModificationException — использовать CopyOnWriteArrayList в пакете Concurrent, который будет подробно проанализирован позже.
6. в массив()
ArrayList предоставляет 2 функции toArray():
- Object[] toArray()
- T[] toArray(T[] contents)
Вызов toArray() вызовет исключение "java.lang.ClassCastException", но вызов toArray(T[] content) обычно возвращает T[].
toArray() генерирует исключение, потому что toArray() возвращает массив Object[] и преобразование Object[] в другие типы (например, преобразование Object[] в Integer[]) вызовет исключение «java. lang.ClassCastException», поскольку Java не поддерживает понижение.
исходный код toArray():
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
7. подсписок()
Если нам нужно получить определенную часть данных в коллекции для работы в процессе разработки, мы можем получить ее с помощью метода SubList(), который создаст внутренний класс SubList() для ArrayList.
SubList наследует AbstractList и реализует большинство действий AbstractList.
Следует отметить, что определенная часть данных в коллекции, возвращаемой SubList, будет связана с исходной коллекцией. То есть, когда мы работаем с Sublist, это все равно повлияет на исходную коллекцию. Давайте посмотрим на метод добавления в Sublist:
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
Видно, что операция сложения в подсписке на самом деле вызывает операцию сложения в родительском (то есть исходном наборе). Поэтому при использовании метода subList вы должны четко подумать, нужно ли вам изменять элементы вложенной коллекции, не затрагивая исходную коллекцию списка.
Суммировать
ArrayList в целом относительно прост, но ArrayList имеет следующие характеристики:
-
ArrayList реализует свои собственные методы сериализации и десериализации, поскольку он сам реализует методы private void writeObject(java.io.ObjectOutputStream s) и private void readObject(java.io.ObjectInputStream s).
-
ArrayList реализован на основе метода массива, без ограничения емкости (он будет расширяться)
-
Возможно, потребуется расширить вместимость при добавлении элементов (так что лучше заранее рассудить), а вместимость не будет уменьшаться при удалении элементов (если хотите уменьшить вместимость, trimToSize()), при удалении элементов, установите для удаленного элемента position значение null, и следующий gc. Пространство памяти, занимаемое этими элементами, будет восстановлено.
-
поток небезопасен
-
add(int index, E element): При добавлении элемента в указанную позицию в массиве необходимо скопировать позицию и все элементы за ней на один бит назад.
-
get(int index): при получении элемента в указанной позиции вы можете получить его непосредственно через индекс (O(1))
-
remove(Object o) должен пройти через массив
-
remove(int index) не нужно обходить массив, просто оцените, соответствует ли индекс условиям, эффективность выше, чем remove(Object o)
-
contains(E) должен пройти через массив
-
Обход с помощью итератора может вызвать исключение многопоточности
расширить мышление
- Расширенное мышление 1. Как интерфейс RandomAccess обеспечивает быстрое обнаружение ресурсов?
- Расширенное мышление 2. Какова роль EMPTY_ELEMENTDATA и DEFAULTCAPACITY_EMPTY_ELEMENTDATA?
- Расширение мышления 3. Яма метода удаления?
- Расширенное мышление 4: почему ArrayList не является потокобезопасным?
использованная литература
http://www.cnblogs.com/skywang12345/p/3308556.html https://blog.csdn.net/daye5465/article/details/77971530 https://blog.csdn.net/daye5465/article/details/77971530