Добро пожаловать, чтобы обратить внимание на мою общедоступную учетную запись «Брат Тонг читает исходный код», проверить больше статей из серии исходного кода и поплавать в океане исходного кода с братом Тонгом.
Введение
ArrayList — это список, реализованный с помощью массива, который, по сравнению с массивом, имеет возможность динамически расширяться, поэтому его также можно назвать динамическим массивом.
система наследования
ArrayList реализует такие интерфейсы, как List, RandomAccess, Cloneable, java.io.Serializable и т. д.
ArrayList реализует список и обеспечивает основные операции, такие как добавление, удаление и обход.
ArrayList реализует RandomAccess, обеспечивающий возможности произвольного доступа.
ArrayList реализует Cloneable и может быть клонирован.
ArrayList реализует Serializable и может быть сериализован.
Анализ исходного кода
Атрибуты
/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组，如果传入的容量为0时使用
*/
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;
(1) DEFAULT_CAPACITY
Емкость по умолчанию равна 10, что является емкостью по умолчанию при создании с помощью new ArrayList().
(2) EMPTY_ELEMENTDATA
Пустой массив, такой пустой массив используется при создании через новый ArrayList(0).
(3) DEFAULTCAPACITY_EMPTY_ELEMENTDATA
Это тоже пустой массив, этот пустой массив используется при создании через new ArrayList() Отличие от EMPTY_ELEMENTDATA в том, что при добавлении первого элемента пустой массив будет инициализирован элементами DEFAULT_CAPACITY (10).
(4) данные элемента
Там, где элемент фактически хранится, используется переходный процесс, чтобы не сериализовать это поле.
Что касается отказа от использования частной модификации, следующий комментарий написан «для того, чтобы упростить доступ к вложенным классам», но арендодатель посчитал, что доступ к частным вложенным классам также возможен.
Частный означает, что это частное свойство класса, если оно доступно внутри класса, вложенные классы или внутренние классы также находятся внутри класса, поэтому вы также можете получить доступ к закрытым членам класса.
(5) размер
На самом деле он хранит количество элементов, а не длину массива elementData.
Конструктор ArrayList(int initialCapacity)
Передайте начальную емкость. Если она больше 0, инициализируйте elementData до соответствующего размера. Если она равна 0, используйте пустой массив EMPTY_ELEMENTDATA. Если она меньше 0, будет выдано исключение.
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 如果传入的初始容量大于0，就新建一个数组存储元素
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入的初始容量等于0，使用空数组EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果传入的初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
Конструктор ArrayList()
Если начальная емкость не передана, она инициализируется пустым массивом DEFAULTCAPACITY_EMPTY_ELEMENTDATA, который будет расширен до размера по умолчанию, равного 10, при добавлении первого элемента.
public ArrayList() {
// 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList(Collection extends E> c) конструктор
Передайте коллекцию и инициализируйте elementData. Здесь элементы входящей коллекции будут скопированы в массив elementData. Если количество элементов равно 0, он будет инициализирован пустым массивом EMPTY_ELEMENTDATA.
/**
* 把传入集合的元素初始化到ArrayList中
*/
public ArrayList(Collection<? extends E> c) {
// 集合转数组
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果c的空集合，则初始化为空数组EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
}
Почемуc.toArray();Возможно ли, что возвращаемый объект не имеет типа Object[]? См. код ниже:
public class ArrayTest {
public static void main(String[] args) {
Father[] fathers = new Son[]{};
// 打印结果为class [Lcom.coolcoding.code.Son;
System.out.println(fathers.getClass());
List<String> strList = new MyList();
// 打印结果为class [Ljava.lang.String;
System.out.println(strList.toArray().getClass());
}
}
class Father {}
class Son extends Father {}
class MyList extends ArrayList<String> {
/**
* 子类重写父类的方法，返回值可以不一样
* 但这里只能用数组类型，换成Object就不行
* 应该算是java本身的bug
*/
@Override
public String[] toArray() {
// 为了方便举例直接写死
return new String[]{"1", "2", "3"};
}
}
метод add(E e)
Добавление элементов в конец имеет среднюю временную сложность O (1).
public boolean add(E e) {
// 检查是否需要扩容
ensureCapacityInternal(size + 1);
// 把元素插入到最后一位
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新容量为旧容量的1.5倍
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);
}
(1) Проверьте, требуется ли расширение;
(2) Если elementData равен DEFAULTCAPACITY_EMPTY_ELEMENTDATA, размер инициализированной емкости равен DEFAULT_CAPACITY;
(3) Новая мощность в 1,5 раза превышает старую мощность (oldCapacity + (oldCapacity >> 1)).Если добавлена такая большая мощность и выясняется, что она меньше требуемой мощности, требуемая мощность имеет преимущественную силу;
(4) Создайте массив новой емкости и скопируйте старый массив в новый массив;
метод add(индекс int, элемент E)
Добавление элемента в указанную позицию имеет среднюю временную сложность O(n).
public void add(int index, E element) {
// 检查是否越界
rangeCheckForAdd(index);
// 检查是否需要扩容
ensureCapacityInternal(size + 1);
// 将inex及其之后的元素往后挪一位，则index位置处就空出来了
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将元素插入到index的位置
elementData[index] = element;
// 大小增1
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
(1) Проверить, не выходит ли индекс за пределы;
(2) Проверьте, требуется ли расширение;
(3) Переместить элементы, вставленные в позицию индекса, на один бит назад;
(4) Поместите вставленный элемент в позицию индекса вставки;
(5) Добавьте 1 к размеру;
метод addAll(Collection extends E> c)
Найдите объединение двух множеств.
/**
* 将集合c中所有元素添加到当前ArrayList中
*/
public boolean addAll(Collection<? extends E> c) {
// 将集合c转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 检查是否需要扩容
ensureCapacityInternal(size + numNew);
// 将c中元素全部拷贝到数组的最后
System.arraycopy(a, 0, elementData, size, numNew);
// 大小增加c的大小
size += numNew;
// 如果c不为空就返回true，否则返回false
return numNew != 0;
}
(1) Скопируйте элементы из c в массив a;
(2) Проверьте, требуется ли расширение;
(3) Скопируйте элементы массива a в конец elementData;
метод get(int index)
Получить элемент в указанной позиции индекса, временная сложность O (1).
public E get(int index) {
// 检查是否越界
rangeCheck(index);
// 返回数组index位置的元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
(1) Проверьте, не выходит ли индекс за пределы. Здесь только проверьте, не выходит ли он за верхнюю границу. Если он превышает верхнюю границу, выдается исключение IndexOutOfBoundsException, а если он превышает нижнюю границу, выдается исключение ArrayIndexOutOfBoundsException.
(2) Вернуть элемент в позицию индекса;
метод удаления (внутренний индекс)
Удалить элемент в указанной позиции индекса, временная сложность O (n).
public E remove(int index) {
// 检查是否越界
rangeCheck(index);
modCount++;
// 获取index位置的元素
E oldValue = elementData(index);
// 如果index不是最后一位，则将index之后的元素往前挪一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将最后一个元素删除，帮助GC
elementData[--size] = null; // clear to let GC do its work
// 返回旧值
return oldValue;
}
(1) Проверить, не выходит ли индекс за пределы;
(2) Получить элемент в указанной позиции индекса;
(3) Если удаляется не последняя цифра, остальные элементы сдвигаются вперед на единицу;
(4) Установите последнюю позицию в нулевое значение для облегчения повторного использования ГХ;
(5) Вернуть удаленный элемент.
Как видите, ArrayList не сжимается при удалении элементов.
метод удаления (объекта)
Удалить элемент с указанным значением элемента, временная сложность O(n).
public boolean remove(Object o) {
if (o == null) {
// 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
for (int index = 0; index < size; index++)
// 如果要删除的元素为null，则以null进行比较，使用==
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
for (int index = 0; index < size; index++)
// 如果要删除的元素不为null，则进行比较，使用equals()方法
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
// 少了一个越界的检查
modCount++;
// 如果index不是最后一位，则将index之后的元素往前挪一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将最后一个元素删除，帮助GC
elementData[--size] = null; // clear to let GC do its work
}
(1) Найти первый элемент, равный указанному значению элемента;
(2) Быстрое удаление;
По сравнению с remove(int index), fastRemove(int index) требует меньше операций для проверки выхода индекса за границы.Видно, что jdk максимально оптимизирует производительность.
Метод keepAll(Collection> c)
Найдите пересечение двух множеств.
public boolean retainAll(Collection<?> c) {
// 集合c不能为null
Objects.requireNonNull(c);
// 调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素
return batchRemove(c, true);
}
/**
* 批量删除元素
* complement为true表示删除c中不包含的元素
* complement为false表示删除c中包含的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
// 使用读写两个指针同时遍历数组
// 读指针每次自增1，写指针放入元素的时候才加1
// 这样不需要额外的空间，只需要在原有的数组上操作就可以了
int r = 0, w = 0;
boolean modified = false;
try {
// 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 正常来说r最后是等于size的，除非c.contains()抛出了异常
if (r != size) {
// 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// 将写指针之后的元素置为空，帮助GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
size = w;
modified = true;
}
}
// 有修改返回true
return modified;
}
(1) пройтись по массиву elementData;
(2) Если элемент находится в c, добавьте элемент в позицию w массива elementData и переместите позицию w на одну позицию назад;
(3) После обхода элементы перед w являются общими для обоих, а элементы после (включая) w не являются общими для обоих;
(4) Установить элемент после w (включительно) равным нулю, чтобы облегчить повторный цикл GC;
removeAll(Collection<?> c)
Найдите набор однонаправленных разностей двух наборов, сохраните в текущем наборе только те элементы, которых нет в c, и не сохраните элементы в c, которых нет в текущем наборе.
public boolean removeAll(Collection<?> c) {
// 集合c不能为空
Objects.requireNonNull(c);
// 同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素
return batchRemove(c, false);
}
Аналогичен методу continueAll(Collection> c), за исключением того, что здесь сохраняются элементы, которых нет в c.
Суммировать
(1) ArrayList использует массив для внутреннего хранения элементов. Когда длины массива недостаточно, он будет расширен. Каждый раз, когда добавляется половина пространства, ArrayList не будет уменьшаться;
(2) ArrayList поддерживает произвольный доступ, доступ к элементам по индексу осуществляется очень быстро, а временная сложность составляет O(1);
(3) ArrayList очень быстро добавляет элементы в хвост, а средняя временная сложность составляет O(1);
(4) ArrayList медленно добавляет элементы в середину, потому что средняя временная сложность перемещения элементов составляет O(n);
(5) ArrayList очень быстро удаляет элементы из хвоста, а временная сложность составляет O(1);
(6) ArrayList медленнее удаляет элементы из середины, потому что средняя временная сложность перемещения элементов составляет O(n);
(7) ArrayList поддерживает объединение, просто вызовите метод addAll(Collection extends E> c);
(8) ArrayList поддерживает пересечение, вызовите метод continueAll(Collection extends E> c);
(7) ArrayList поддерживает одностороннее различие, просто вызовите метод removeAll(Collection extends E> c);
пасхальные яйца
elementData имеет значение transient, так как же ArrayList сериализует элементы?
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 防止序列化期间有修改
int expectedModCount = modCount;
// 写出非transient非static属性（会写出size属性）
s.defaultWriteObject();
// 写出元素个数
s.writeInt(size);
// 依次写出元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 如果有修改，抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 声明为空数组
elementData = EMPTY_ELEMENTDATA;
// 读入非transient非static属性（会读取size属性）
s.defaultReadObject();
// 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
s.readInt();
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();
}
}
}
Глядя на метод writeObject(), вы можете видеть, что сначала вызывается метод s.defaultWriteObject(), затем в поток записывается размер, а затем элементы записываются в поток один за другим.
В общем, если реализован интерфейс Serializable, он может быть автоматически сериализован. writeObject() и readObject() используются для управления методом сериализации. Эти два метода должны быть объявлены как частные. В java.io.ObjectStreamClass# Метод getPrivateMethod() Метод writeObject() получается посредством отражения.
В методе writeObject() списка ArrayList сначала вызывается метод s.defaultWriteObject(), который предназначен для записи нестатического непереходного атрибута, который является атрибутом размера в ArrayList. Точно так же метод s.defaultReadObject() вызывается первым в методе readObject() для разрешения свойства размера.
elementData определяется как преимущество переходного процесса, который сериализует реальные элементы в соответствии с размером, а не сериализует элементы в соответствии с длиной массива, что уменьшает занимаемое пространство.
Добро пожаловать, чтобы обратить внимание на мою общедоступную учетную запись «Брат Тонг читает исходный код», проверить больше статей из серии исходного кода и поплавать в океане исходного кода с братом Тонгом.
