предисловие
В предыдущей статье мы упомянули ArrayList, можно сказать, что каждый человек изучает Java, использую самую квалифицированную коллекцию, но не знаю почему. О реализации ArrayList, являются одними из основных, которые также знают, что для достижения такого массива, безопасных потоков и т. Д., Но редко более бетон для понимания, например: длина инициализации, расширение и так далее.
В этой статье в основном объясняются некоторые распространенные методы ArrayList и отличия от Vector посредством некоторого анализа исходного кода.
ArrayList
определение
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList фактически является динамическим массивом, емкость которого может динамически увеличиваться, он наследует AbstractList и реализует интерфейсы List, RandomAccess, Cloneable и java.io.Serializable.
Интерфейс RandomAccess, реализованный List, указывает, что List предоставляет функцию произвольного доступа, то есть функцию получения объектов-элементов через индексы.
1. Интерфейс RandomAccess, обозначающий интерфейс, указывающий на то, что List предоставляет функцию произвольного доступа, то есть функцию получения объектов-элементов через индексы. Причина, по которой это интерфейс-маркер, заключается в том, что у класса уже есть определенная способность, и он помечен интерфейсом, что удобно другим классам для его идентификации (instanceof). 2. Реализация самого массива ArrayList имеет функцию случайного доступа к любому элементу через индексы. Итак, на что необходимо обратить внимание в деталях, так это на разницу между случайным доступом по индексу и последовательным доступом по индексу (LinkedList). Вот почему LinkedList лучше не использовать обход цикла, а использовать итератор для обхода. 3. Внедрение RandomAccess также означает, что некоторые алгоритмы могут быть оптимизированы с помощью суждения о типах.Например, существует метод перемешивания коллекций, и исходный код не будет вставлен.Проще говоря, если реализован интерфейс RandomAccess, он будет пройден индексами, иначе итераторы будут проходить. Реализация Cloneable, java.io.Serializable означает, что его можно клонировать и сериализовать.
инициализация
При использовании нам часто нужно обновить различные общие списки ArrayList, так как же выглядит процесс инициализации?
Следующая строка кода создает объект ArrayList.
List<Person> list = new ArrayList<>();
Давайте посмотрим на исходный код, как его инициализировать и найти метод построения
//无参构造方法
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
Когда я увидел эти коды, я тоже был озадачен, что такое elementData и EMPTY_ELEMENTDATA? Но очевидно, что EMPTY_ELEMENTDATA — это константа, давайте вернемся к источнику и посмотрим на атрибуты члена.
//如果是无参构造方法创建对象的话，ArrayList的初始化长度为10，这是一个静态常量
private static final int DEFAULT_CAPACITY = 10;
//在这里可以看到我们不解的EMPTY_ELEMENTDATA实际上是一个空的对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//保存ArrayList数据的对象数组缓冲区 空的ArrayList的elementData = EMPTY_ELEMENTDATA 这就是为什么说ArrayList底层是数组实现的了。elementData的初始容量为10，大小会根据ArrayList容量的增长而动态的增长。
private transient Object[] elementData;
//集合的长度
private int size;
После выполнения метода построения, как показано ниже
Можно сказать, что автор ArrayList действительно заботится об этом, даже кеш был обработан, и новые объекты, которые являются новыми несколько раз, будут выполнять одну и ту же ссылку.
Добавить метод Добавить
add(E e)
/**
* Appends the specified element to the end of this list.
*/
//增加元素到集合的最后
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//因为++运算符的特点 先使用后运算 这里实际上是
//elementData[size] = e
//size+1
elementData[size++] = e;
return true;
}
Независимо от sureCapacityInternal, этот метод должен добавить элемент в позицию size++ массива.
Вернемся к параметру sureCapacityInternal, который используется для расширения емкости, а точнее, для проверки расширения емкости. Давайте посмотрим на весь процесс расширения
//初始长度是10，size默认值0，假定添加的是第一个元素，那么minCapacity=1 这是最小容量 如果小于这个容量就会报错
//如果底层数组就是默认数组，那么选一个大的值，就是10
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//调用另一个方法ensureExplicitCapacity
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//记录修改的次数
modCount++;
// overflow-conscious code
//如果传过来的值大于初始长度 执行grow方法（参数为传过来的值）扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正的扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新的容量是在原有的容量基础上+50% 右移一位就是二分之一
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:
//这里是重点 调用工具类Arrays的copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
//Arrays
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
add(int index, E element)
добавить в указанное место
public void add(int index, E element) {
//判断索引是否越界，如果越界就会抛出下标越界异常
rangeCheckForAdd(index);
//扩容检查
ensureCapacityInternal(size + 1); // Increments modCount!!
//将指定下标空出 具体作法就是index及其后的所有元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//将要添加元素赋值到空出来的指定下标处
elementData[index] = element;
//长度加1
size++;
}
//判断是否出现下标是否越界
private void rangeCheckForAdd(int index) {
//如果下标超过了集合的尺寸 或者 小于0就是越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
remove(int index)
ArrayList поддерживает два способа удаления элементов.
- remove(int index) Удалить по нижнему индексу Обычно используется
- remove(Object o) remove by element удалит первый элемент, соответствующий параметру
Давайте посмотрим на реализацию ArrayList
/**
移除list中指定位置的元素
* Removes the element at the specified position in this list.
所有后续元素左移 下标减1
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*参数是要移除元素的下标
* @param index the index of the element to be removed
返回值是被移除的元素
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下标越界检查
rangeCheck(index);
//修改次数统计
modCount++;
//获取这个下标上的值
E oldValue = elementData(index);
//计算出需要移动的元素个数 （因为需要将后续元素左移一位 此处计算出来的是后续元素的位数）
int numMoved = size - index - 1;
//如果这个值大于0 说明后续有元素需要左移 是0说明被移除的对象就是最后一位元素
if (numMoved > 0)
//索引index只有的所有元素左移一位 覆盖掉index位置上的元素
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 将最后一个元素赋值为null 这样就可以被gc回收了
elementData[--size] = null; // clear to let GC do its work
//返回index位置上的元素
return oldValue;
}
//移除特定元素
public boolean remove(Object o) {
//如果元素是null 遍历数组移除第一个null
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//遍历找到第一个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
}
Сводка списка массивов
- Базовый массив реализован, и емкость, инициализированная с использованием метода построения по умолчанию, равна 10.
- Длина расширения основана на исходной длине плюс половина
- Реализован интерфейс RandomAccess, а нижний слой представляет собой массив, производительность чтения элементов чтения очень хорошая.
- Поток небезопасен, все методы не синхронизированы и не заблокированы, поэтому используйте их с осторожностью в многопоточности.
- Удобно добавлять последовательно
- Удалить и вставить нужно для копирования массива с плохой производительностью (можно использовать LinkindList)
Почему elementData ArrayList украшен переходным процессом?
Временное измененное свойство означает, что оно не будет сериализовано, то есть при сериализации ArrayList elementData не сериализуется.
Зачем ты это делаешь?
- elementData не всегда заполнен, он каждый раз сериализуется, что приводит к потере времени и места.
- Перепишите writeObject, чтобы убедиться, что хотя все элементы не сериализуются во время сериализации, некоторые элементы сериализуются.
Так что это не не сериализовано, но не все сериализовано.
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out array length
s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Разница между арайлистом и вектором
стандартный ответ
- ArrayList не является потокобезопасным, Vector — потокобезопасным
- При расширении ArrayList расширяется в 0,5 раза, а Vector расширяется в 1 раз.
Тогда вот проблема
Есть ли способ сделать ArrayList потокобезопасным?
Вспомогательный класс Collections имеет метод synchronizedList.
Вы можете превратить список в потокобезопасную коллекцию, но это не имеет особого смысла, потому что вы можете использовать Vector
Почему VECTOR кого?
Честно говоря, если не считать многопоточности, между ними нет большой разницы, но при многопоточности она отличается. Итак, как Vector обеспечивает потокобезопасность, давайте рассмотрим несколько ключевых методов.
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
С точки зрения реализации кода не так много логических отличий от ArrayList, но ключевые методы Vector используют синхронизированную модификацию.