что такое ArrayList

задняя часть

Введение

ArrayList — это более часто используемая структура данных в структуре коллекций Java. Унаследован от AbstractList и реализует интерфейс List. Нижний уровень реализует динамические изменения емкости на основе массивов. Допускается существование нуля. Он также реализует интерфейсы RandomAccess, Cloneable и Serializable, поэтому ArrayList поддерживает быстрый доступ, копирование и сериализацию.

Переменные-члены

Нижний слой ArrayList основан на массиве для реализации динамического изменения размера емкости.

/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;  // 实际元素个数
transient Object[] elementData;

ПРИМЕЧАНИЕ. Вышеуказанный размер относится к количеству фактически элемента ElementedDATA, поскольку установленные ElementData.length Mather представляет собой максимальное количество элементов может быть приспособлено.

Начальный размер емкости по умолчанию равен 10;

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

Эта переменная определена в AbstractList. Записывает количество операций в списке. Основное использование в итераторе, чтобы предотвратить изменение коллекции во время итерации.

protected transient int modCount = 0;

Следующие две переменные используются в конструкторе

/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

В чем разница между двумя пустыми массивами? Мы отличаем это от EMPTY_ELEMENTDATA, чтобы знать, насколько увеличиться при добавлении первого элемента. чтобы подтвердить, как расширить.

Конструктор

  • Не убогий конструктор
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ПРИМЕЧАНИЕ. Комментарий состоит в том, чтобы построить коллекцию пустого списка, которая создает мощность 10, но конструктор назначает только пустой массив на ElementData, на самом деле емкость расширяется до 10, когда первый элемент добавления увеличивается.

  • Создает ArrayList с начальной емкостью initialCapacity.
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);
	}
}

Это видно из приведенного выше исходного кода: При использовании конструктора без аргументов назначьте DEFAULTCAPACITY_EMPTY_ELEMENTDATA для elementData. Когда initialCapacity равно нулю, EMPTY_ELEMENTDATA присваивается elementData. Когда initialCapacity больше нуля, инициализируйте массив объектов размера initialCapacity и присвойте его elementData.

  • Конструктор для создания ArrayList с указанной коллекцией
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;
	}
}

Преобразуйте коллекцию в массив и назначьте ее для elementData, а количество элементов в elementData назначьте для размера. Если размер не равен нулю, оцените, является ли тип класса elementData Object[], если нет, выполните преобразование. Если размер равен нулю, присвойте EMPTY_ELEMENTDATA элементу elementData, что эквивалентно новому ArrayList(0).

Анализ основного метода работы

  • добавить операцию
public boolean add(E e) {
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}

private void ensureCapacityInternal(int minCapacity) {
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

Можно видеть, что каждый раз, когда элемент добавляется в набор, емкость следующего набора будет подтверждаться первой. Затем увеличьте размер на 1. В функции sureCapacityInternal оценивается, что если elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, максимальное значение DEFAULT_CAPACITY и minCapacity равно 10. В этом разница между EMPTY_ELEMENTDATA и DEFAULTCAPACITY_EMPTY_ELEMENTDATA. В то же время, это также подтверждает вышеприведенное утверждение: при использовании конструктора без страданий начальная емкость равна 10, когда элемент добавляется в первый раз. В sureExplicitCapacity modCount автоматически увеличивается на 1, записывается количество операций, а затем, если minCapacity больше длины elementData, коллекция расширяется. По-видимому, elementData имеет нулевую длину при первом добавлении элемента. Тогда давайте взглянем на функцию роста.

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,5 раза. Однако он может быть неприменим после расширения: он может быть слишком маленьким или слишком большим. Так что будут следующие два, если суждения. Если в 1,5 раза мало, присвоить размер нужной нам емкости newCapacity, если в 1,5 раза слишком много или нужная нам емкость слишком велика, то берем напрямуюnewCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZEрасширять. Затем скопируйте данные исходного массива в новый массив размером newCapacity и назначьте новый массив элементу 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++;
}

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;
}

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;
}

Можно увидеть больше, чем исходный код, добавить (int index, e элемент), Addall (Collection Extends E> C), Addall (Int Index, Collection Extendes E> C) работают, это проверить коллекцию Емкость для обеспечения не границ массива. Затем System.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;
}
	
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
}

Когда мы вызываем remove(int index), мы сначала проверяем, действителен ли индекс, а затем определяем, находится ли удаляемый элемент в последней позиции массива. Если индекс не последний, снова вызовите метод System.arraycopy(), чтобы скопировать массив. Проще говоря, все элементы будут перемещены вперед на одну позицию от индекса + 1. Затем очистите последнюю позицию массива, размер - 1. Если индекс является последним элементом, то просто очистите последнюю позицию массива, размер - 1. Когда мы вызываем remove(Object o), мы разделим o на то, пуст он или нет. Затем просмотрите массив, чтобы найти первый индекс нижнего индекса, соответствующий o, а затем вызовите метод fastRemove, чтобы удалить элемент с индексом нижнего индекса. На самом деле, обратите внимание, что метод fastRemove(int index) и метод remove(int index) в основном одинаковы.

  • получить операцию
public E get(int index) {
	rangeCheck(index);
	return elementData(index);
}

Поскольку нижний слой ArrayList реализован на основе массивов, получить элементы довольно просто, напрямую вызывая произвольный доступ к массиву.

итератор итератор

Любой, кто использовал коллекции, знает, что при использовании for для обхода коллекции операция удаления не может быть выполнена для коллекции, поскольку операция удаления изменит размер коллекции. В результате легко получить неточные результаты или даже выйти за пределы индексов массива, а в более серьезных случаях будет выдано исключение ConcurrentModificationException.

例子.png

Обход Foreach эквивалентен итератору. Для того, чтобы выяснить причину для исключения, мы также должны пройти исходный код.

public Iterator<E> iterator() {
	return new Itr();
}

Оказалось, что это прямой возвращаемый объект 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;

	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();
		}
	}

	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
}

Как видно из исходного кода, ArrayList определяет внутренний класс Itr, реализующий интерфейс Iterator. Внутри Itr есть три переменных-члена. курсор: представляет индекс следующего элемента, к которому нужно получить доступ. lastRet: представляет индекс последнего доступного элемента. ожидаемыйModCount: представляет ожидаемое значение количества модификаций в ArrayList, и начальное значение — modCount.

Давайте рассмотрим три основные функции Itr.

Реализация hasNext относительно проста: если индекс следующего элемента равен размеру множества, он доказывается до конца.

Следующий способ не сложный, но критический. Сначала определите, равны ли ожидаемые ModCount и modCount. Затем оцените курсор, чтобы увидеть, превышает ли он размер коллекции и длину массива. Затем назначьте курсор на lastRet и верните элемент с индексом lastRet. Наконец, курсор увеличивается на 1. В начале курсор = 0, lastRet = -1, каждый раз при вызове следующего метода курсор и lastRet будут увеличиваться на 1.

Метод удаления сначала определяет, меньше ли значение lastRet 0, а затем проверяет, равны ли ожидаемые значения ModCount и modCount. Далее идет ключ, напрямую вызывающий метод удаления ArrayList для удаления элемента с индексом lastRet. Затем присвойте lastRet курсору, присвойте lastRet значение -1 и переназначьте modCount ожидаемому ModCount.

图一

Давайте разберем работу Itr шаг за шагом. Как показано на рисунке 1, в начале курсор указывает на элемент с индексом 0, а lastRet указывает на элемент с индексом -1, который равен нулю. При каждом вызове next курсор и lastRet увеличиваются на 1 соответственно. Когда next возвращает «C», курсор и lastRet равны 3 и 2 соответственно [рис. 2].

图二

На данный момент вызовите удаление, обратите внимание, что ArrayList удаляет, а не удалить ITR. D E Два элемента будут двигаться вперед прямого, последнее пустое положение, а MODCOUNT будет увеличиваться одним. Как видно из метода удаления. [Рисунок III].

图三

В этот момент курсор = 3, размер = 4, конец массива не достигнут, поэтому цикл продолжается. Перейдите к следующему методу, потому что метод удаления на предыдущем шаге изменил modCount, так что ожидаемыеModCount и modCount не равны, что является причиной исключения ConcurrentModificationException. Из примера example.png также видно, что исключение исходит от метода checkForCommodification во внутреннем классе Itr в ArrayList.

Разрешение исключения:

solve.png

Просто вызовите iterator.remove() напрямую. Потому что в этом методе добавлена ​​операция expectModCount = modCount. Но у этого метода удаления есть и недостатки.

  1. Можно выполнять только операции удаления, добавления, очистки и т. д., которых нет в Itr.
  2. Next должен быть вызван до того, как будет вызвано удаление. Потому что remove проверяет lastRet в начале. И lastRet инициализируется с -1.
  3. После следующего можно вызвать только один раз удалить. Поскольку удаление lastRet будет повторно инициализировано до -1

Суммировать: ArrayList 底层基于数组实现容量大小动态可变。 扩容机制为首先扩容为原始容量的 1.5 倍。如果1.5倍太小的话，则将我们所需的容量大小赋值给 newCapacity，如果1.5倍太大或者我们需要的容量太大，那就直接拿newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZEрасширять. После расширения точность элементов обеспечивается копированием массива, поэтому операция расширения сводится к минимуму. Максимальная емкость хранилища ArrayList: Integer.MAX_VALUE. size — это количество элементов, хранящихся в коллекции. elementData.length — это длина массива, указывающая, сколько элементов может быть сохранено. Если вам нужно удалить во время обхода, вы должны использовать итератор. И перед удалением сначала нужно использовать next, а remove можно использовать только один раз после next.

Категории