Введение
Класс коллекции Java предоставляет набор хорошо разработанных интерфейсов и классов, поддерживающих операции над группой объектов.В JAVA существует четыре типа широко используемых интерфейсов коллекций, а именно:
- Коллекция: представляет набор объектов, каждый объект является его дочерним элементом.
- Набор: коллекция, не содержащая повторяющихся элементов.
- Список: существует последовательная коллекция, которая может содержать повторяющиеся элементы.
- Карта: объект, который может сопоставлять ключи со значениями, а ключи не могут повторяться.
Отношение классов коллекции JAVA может быть представлено диаграммой следующим образом:
- сплошная границаЯвляется ли класс реализации, такой как: ArrayList, LinkedList, HashMap и т. д.
- Ломаная границаЯвляется абстрактным классом, например: AbstractCollection, AbstractList, AbstractMap и т. д.
- Пунктирная границаИнтерфейс, такой как: Коллекция, Итератор, Список и т.д.
- с цветомКоробка — это класс инструментов, например: Коллекции, Массивы.
Из диаграммы классов мы знаем, что все коллекции наследуют интерфейс Iterator, то есть все коллекции имеют итераторы, которые можно зацикливать через итераторы.На самом деле многие функции коллекций реализованы с использованием итераторов.
2. Общие методы ArrayList
| имя метода | Функции |
|---|---|
| size() | Возвращает количество элементов в текущей коллекции |
| isEmpty() | Проверить, пуста ли текущая коллекция |
| contains(Object o) | Определить, содержит ли текущая коллекция объект |
| indexOf(Object o) | Получить позицию индекса объекта в коллекции |
| lastIndexOf(Object o) | Получить последнюю позицию индекса в коллекции |
| get(int index) | Получить объект коллекции в указанном месте |
| set(int index, E element) | Переопределить объект в расположении в коллекции |
| add(E e) | Добавить объект в коллекцию |
| add(int index, E element) | Добавить объект в указанное место в коллекции |
| remove(int index) | удалить элемент в индексной позиции |
| remove(Object o) | удалить элемент |
Наиболее распространенные методы, которые мы обычно используем ArrayList, — это добавление, запрос и удаление. Далее мы проанализируем, как ArrayList добавляется, запрашивается и удаляется на уровне исходного кода.
Исходное свойство ArrayList
//默认容量长度
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;
Конструктор ArrayList
//指定容量构造方法
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);
}
}
//默认无参数构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//指定集合构造方法
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//官方的一个bug，c.toArray()可能不是一个object数组，所以需要通过Arrays.copyOf创建1个Object[]数组，这样数组中就可以存放任意对象了
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
Благодаря приведенному выше методу построения ArrayList мы знаем, что ArrayList может создать список заданной длины, или вы можете указать коллекцию для создания списка, а созданный по умолчанию список представляет собой пустой массив длиной 10.
add() метод ArrayList
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 确认能否装得下size+1的对象
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是默认长度，就比较默认长度和size+1,取最大值
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) {
//取数组的长度
int oldCapacity = elementData.length;
//计算新长度，新长度=旧长度+旧长度/2
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);
}
Приведенная выше логика исходного кода включает добавление и расширение ArrayList.Согласно приведенному выше исходному коду, мы знаем, что фактическая емкость исходного ArrayList по умолчанию не будет расширена до 10, пока не будет вызван метод add().Здесь память выделенный новым ArrayList() является пустым массивом, и нет прямого нового объекта [10], этот дизайн очень умный, может сэкономить много места.
Метод ArrayList add(int index, E element)
public void add(int index, E element) {
//判断是否越界
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 重新复制数组，把index+1位置往后的对象全部后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//覆盖index位置的对象
elementData[index] = element;
size++;
}
Добавьте метод объекта ArrayList с назначенной позицией, объект необходимо указать позже после всех позиций сдвига, поэтому именно здесь относительный список ссылок ArrayList добавляет много времени.
Метод GET (INT INDEX) ArrayList
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Метод get(int index) в ArrayList относительно прост: всего два шага: во-первых, проверить, не выходит ли он за границы, во-вторых, вернуть данные в позиции индекса массива.
Метод удаления (int index) ArrayList
public E remove(int index) {
rangeCheck(index);
//父类的属性，用来记录list修改的次数，后续迭代器中会用到
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//把index位置后面的元素左移
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Метод remove(int index) в ArrayList в основном делится на 3 шага.Первый шаг – определить, выходит ли нижний индекс за границы.Второй шаг – записать количество модификаций и переместить элемент после позиции индекса в позицию налево. Третий шаг — присвоить последней позиции значение null. , для быстрой сборки мусора.
Проблемы, на которые необходимо обратить внимание при использовании метода удаления ArrayList в цикле
- для петли
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
integers.add(3);
integers.add(4);
integers.add(5);
for (int i = 0; i < integers.size(); i++) {
integers.remove(i);
}
System.out.println(integers.size());
Здесь сначала объявите коллекцию ArrayList длиной 5, затем добавьте пять элементов и, наконец, удалите ее с помощью обхода цикла Теоретический результат выводит 0, но выходной результат равен 2. Почему? Из предыдущего анализа исходного кода удаления мы знаем, что каждый раз, когда ArrayList удаляется, все следующие элементы будут сдвигаться влево.В качестве примера возьмем эти 5 элементов, первый обычно удаляется без проблем.После удаление, только [2,3, 4,5], в это время удалить(1), осталось [2,4,5], а затем удалить(2), осталось [2,4], и есть нет элементов в следующем удалении, поэтому окончательный размер равен 2.
- Цикл Foreach
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
integers.add(3);
integers.add(4);
integers.add(5);
for (Integer integer : integers) {
integers.remove(integer);
}
System.out.println(integers.size());
Этот код просто изменяет цикл for на цикл foreach в приведенном выше коде Теоретический результат здесь также состоит в том, чтобы вывести 0, но в конце сообщается об ошибке, и сообщается сообщение об ошибке:
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
Здесь мы обнаруживаем, что это метод итератора ArrayList.ArrayList$Itr указывает на наличие проблемы с проверкой для коммодификации во внутреннем классе Itr ArrayList. Я проверяю исходный код,
//这是Itr内部的属性，初始化等于ArrayList中的modCount
int expectedModCount = modCount;
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Видя это, мы должны быть ясны, мы вызываем метод удаления ArrayList, значение modCount изменяется, но значение ожидаемогоModCount в итераторе не изменяется, поэтому генерируется исключение. В это время кто-то должен сказать, что вы лжец, и написанный мной foreach не сообщит об ошибке! Ну да! Бывает ситуация, когда об ошибке не будет сообщено, то есть когда в списке всего два элемента, например такой:
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
for (Integer integer : integers) {
integers.remove(integer);
}
System.out.println(integers.size());
}
В это время результат вывода равен 1, и об ошибке не сообщается. Почему? Мы знаем, что foreach является усовершенствованием цикла for. Он реализован внутри с помощью итераторов. Просмотр кода, который только что сообщил об ошибке, также подтвердил нашу догадку. Поэтому итератор удален. Процесс выглядит следующим образом. Сначала судите iterator.hasNext (), iterate Если есть какой-либо следующий элемент, пройдите его, обход вызовет iterator.next(), исходный код выглядит следующим образом:
public boolean hasNext() {
return cursor != size;
}
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];
}
Мы просмотрели исходный код и обнаружили, что описанный выше процесс можно выполнить только с помощью вызова next().checkForComodification()Когда мы удаляем первый элемент, вводим суждение о цикле, HASNext на этот раз ложно, в этом нет необходимости, поэтому он не будет выполнен.checkForComodification(), поэтому он может вывести 1.
3. Резюме
- ArrayList может указать емкость для создания экземпляра или указать инициализацию содержимого коллекции, длина инициализации по умолчанию равна 10 (реальное пространство будет предоставлено после выполнения метода добавления),
- Добавление и удаление указанной позиции ArrayList изменит позицию элемента после позиции.
- ArrayList должен обращать внимание на ошибки и индексы при удалении в цикле, для его удаления рекомендуется использовать итератор.
Рекомендуемое чтение
"ReentrantLock блокировки Java (1)》
"ReentrantLock из Java Lock (2)》
"ReentrantReadWriteLock блокировки Java》
"Введение в программирование JAVA NIO (1)》