ArrayList — это часто используемая структура данных в структуре коллекций Java.Фактически, нижний уровень — это реализация операции над массивом, но этот массив может реализовать динамические изменения емкости и размера.Это особое место. Также ArrayList не является потокобезопасным.
Фреймворк
Из рисунка видно, что класс ArrayList наследует класс AbstractList и реализует интерфейсы List, RandomAccess, Serialzable и Cloneable.
实现RandomAccess接口：可以通过下标序号快速访问
实现了Cloneable，能被克隆
实现了Serializable，支持序列化
Переменные-члены
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
...
}
- Емкость по умолчанию DEFAULT_CAPACITY равна 10.
- EMPTY_ELEMENTDATA пустая коллекция
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA Пустой набор по умолчанию (немного отличается от EMPTY_ELEMENTDATA, используется в разных конструкторах), первый элемент будет расширен до емкости по умолчанию 10 при добавлении.
- Где elementData действительно хранит данные
- size Количество элементов в массиве
Конструктор
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
Укажите длину инициализации.Разумеется, длина емкости инициализации не может быть меньше 0. Если она равна 0, назначается пустой набор EMPTY_ELEMENTDATA.
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Это наиболее распространенный конструктор по умолчанию, который использует размер начальной емкости по умолчанию, равный 10, и назначает пустой массив DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
Создайте ArraList, используя существующую коллекцию, и скопируйте значения из коллекции в ArrayList. Сначала преобразуйте коллекцию в массив, а затем определите, является ли преобразованный тип массива типом Object[], если да, скопируйте значение массива в список, иначе или емкость равна 0, присвойте пустой массив
Общие операции
Добавить действие
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//扩容之后再添加元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
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;
//新容量大于数组能申请的最大值 MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
size представляет количество элементов в ArrayList. Перед добавлением элементов убедитесь, что массив имеет достаточную емкость. Когда места, требуемого текущим массивом, недостаточно, его необходимо расширить и убедиться, что новая емкость не может быть меньше, чем текущая требуемая емкость, а затем вызвать Arrays.copyOf(), чтобы создать новый массив и скопировать данные в новый массив и поместите ссылку Assign на elementData
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Добавьте элемент в указанную позицию индекса массива. Во-первых, он проверит, выходит ли индекс за пределы массива; затем, поскольку вы хотите добавить элементы, вы должны убедиться, что в массиве достаточно места; конечно, чтобы вставить элементы в позицию индекса, вы должны переместить все элементы после индекса на один бит назад, чтобы освободить позицию индекса Установите элемент для добавления.
При добавлении элементов происходит копирование и перемещение массива, причем используются два метода.
Arrays.copyOf(elementData, newCapacity);
System.arraycopy(elementData, index, elementData, index + 1,size - index);
Первый метод заключается в создании нового объекта того же размера, конечно, нижний слой также использует метод System.arraycopy.
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
Второй метод — скопировать массив в указанный массив, при необходимости скопировав длину массива. Используйте метод arraycopy, чтобы скопировать себя и переместить объект, в котором должен быть размещен массив, на задний план.
По сути, это результат базового клона.
удалить операцию
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; // clear to let GC do its work
return oldValue;
}
Удаляет элемент в указанной позиции. Первый — проверить валидность индекса, затем получить старый элемент на этой позиции, вычислить длину, которую нужно переместить, и, если нужно переместить, вызвать Систему.Позиция нулевая, что удобно для GC для работы и, наконец, возвращает удаленный элемент.
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;
}
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
}
Удаляет указанный элемент, при этом удаляется первый элемент, найденный в массиве. Метод fastRemove удален, здесь нет проверки диапазона индекса
получить операцию
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Получить элемент в указанной позиции индекса. Эта реализация очень проста: сначала проверяется диапазон индекса, а затем напрямую возвращается элемент в позиции индекса в массиве.
Изменить операцию
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Изменить элемент в указанной позиции и вернуть старое значение
итератор
Каждый, кто использует коллекции, знает, что коллекция не может быть удалена, когда цикл for проходит по коллекции, потому что удаление приведет к изменению размера коллекции, что приведет к выходу нижнего индекса массива за границы при обходе массива, и ConcurrentModificationException будет выброшено в серьезных случаях.
Использование итератора для итерации по удалению работает нормально
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Из кода видно, что метод итератора возвращает объект Itr().
Объект Itr имеет три переменных-члена:
cursor：代表下一个要访问的数组下标
lastRet：代表上一个要访问的数组下标
expectedModCount：代表ArrayList修改次数的期望值，初始为modeCount
Он выполняет три основные функции:
hasNext：实现简单，判断下一个要访问的数组下标等于数组大小，表示遍历到最后了
next：首先判断 expectedModCount 和 modCount 是否相等。每调用一次 next 方法， cursor 和 lastRet 都会自增 1。
remove ：首先会判断 lastRet 的值是否小于 0，然后在检查 expectedModCount 和 modCount 是否相等。然后直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素。然后将 lastRet 赋值给 cursor ，将 lastRet 重新赋值为 -1，并将 modCount 重新赋值给 expectedModCount。
Недостатки метода удаления:
调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1
Суммировать
ArrayList — это динамический массив, который может быть автоматически расширен.
Размер емкости по умолчанию для ArrayList равен 10.
Расширение в 1,5 раза превышает первоначальную емкость. Если в 1,5 раза недостаточно, напрямую увеличьте емкость до необходимой нам емкости. Если в 1,5 раза или требуемая емкость слишком велика, непосредственно увеличьте емкость до Integer.MAX_VALUE или MAX_ARRAY_SIZE
После расширения точность элементов обеспечивается копированием массива, а механизм расширения сведен к минимуму.
Скопируйте и разверните с помощью методов Arrays.copyOf и System.arraycopy.
Эффективность поиска ArrayList высока, операции вставки и удаления относительно неэффективны.
size — фактическое количество элементов, хранящихся в коллекции.
elementData.length — длина массива, указывающая, сколько элементов массив может хранить
Если вам нужно удалить во время обхода, вы должны использовать итератор. И перед удалением сначала нужно использовать next, а remove можно использовать только один раз после next.