Анализ исходного кода коллекции Java ArrayList (см. исходный код с проблемами)

Java задняя часть программист исходный код
Анализ исходного кода коллекции Java ArrayList (см. исходный код с проблемами)

учиться сегодняArrayListИсходный код исходного кода отличается от блогов, написанных другими людьми, многие комментарии в исходном коде переведены, а затем непосредственно вставлены в статью. Редактор намерен изменить стиль написания.Возможно, просмотр исходного кода с проблемами может быть более полезным.В этой статье будут обсуждаться следующие вопросы.

1. Проблемы возникают

  • 1. ПочемуArrayListКонтейнер, в котором хранятся элементы коллекции, объявляется какtransient Object[] elementData;?

  • 2. Так какArrayListЕго можно автоматически расширять, так как же реализован его механизм расширения?

  • 3. ЗвонокArrayListизiterator()Итератор что вернул?

  • 4. ПринятьArrayListКогда итератор пересекает коллекцию, почему он выбрасывает при выполнении связанных операций модификации в коллекции?ConcurrentModificationException, как мы можем избежать этого?

  • 5. Когда коллекция расширяется или клонируется, копирование коллекции неизбежно, а затемArrayListКак реализовано копирование массива?

  • 6.ArrayListМеханизм сериализации в

Сяобянь правоArrayListПосле грубого просмотра исходного кода резюмирую вышеперечисленные проблемы.С этими проблемами давайте откроем исходники и решим их вместе!

2. Ответы на вопросы

1. ПочемуArrayListКонтейнер, в котором хранятся элементы коллекции, объявляется какtransient Object[] elementData;?

ArrayListЭто контейнер для сбора. Так как это контейнер, то должно быть некоторые вещи. Поскольку вам нужно хранить некоторые вещи, вы должны иметь место для хранения! Это как сказать, что вам нужно установить тонну воды, вы должны иметь бассейн, чтобы дать вам! Или вы хотите установить десятки воды Millilita, всегда получайте эту бутылку или сумку! Разница в том, что вода, которую нам нужна, не совпадает с водой, размер контейнера нам нужен!

теперь, когдаArrayListДженерики уже поддерживаются, так почемуArrayListПочему определение контейнера исходного кода должно быть определено следующим образомObject[]Что насчет типа?

transient Object[] elementData;

На самом деле, используете ли выtransient E[] elementData;способ объявить или использоватьtransient Object[] elementData;Утверждения разрешены, разница состоит в том, что первая требует от нас в создании экземпляраelementDataНужно сделать преобразование типов, и это преобразование типов требует от наших программистов, чтобы гарантировать, что это преобразование не вызовет никаких ошибок. Чтобы предупредить программистов о возможных исключениях преобразования типов, компилятор выдаетType safety: Unchecked cast from String[] to E[]Предупреждение, я не знаю, будет ли это очень запутанно, следующий код говорит вам:

public class MyList<E> {
    // 声明数组，类型为E[]
    E[] DATAS;
    // 初始化数组，必须做一次类型转换
    public MyList(int initialCapacity) {
    	DATAS = (E[]) new Object[initialCapacity];
    }
    public E getDATAS(int index) {
    	return DATAS[index];
    }
    public void setDATAS(E[] dATAS) {
    	DATAS = dATAS;
    }
}

Приведенный выше код находится в1где мы объявилиE[]Массив, точный тип зависит от того, что вы передаетеEфактический тип, но имейте в виду, что когда выDATASПри выполнении инициализации вы не можете инициализировать так:

E[] DATAS = new E[10]; // 这句代码将报错

Это,Общие массивы не могут быть реифицированы, то есть не может пройтиnew 泛型[size];Другими словами, сама JVM не поддерживает дженерики, а только компилирует стирание типов, так как же это решить? Есть два способа:

  • 1. Выполните преобразование, как указано выше, но это не рекомендуется.

    Как показано в коде выше, мы можем инициализировать какObject[]введите, а затем преобразуйте вE[], но предпосылкой является то, что вы должны убедиться, что в этом преобразовании не будет ошибок, обычно мы не рекомендуем писать таким образом!

  • 2. Прямо объявить какObject[]

    Этот способ такжеArrayListОпределение исходного кода, тогда давайте посмотримArrayListКак это инициализируется:

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 此处直接new Object[]，不会出现任何错误
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

Но есть одно замечание, но ты звонишьArrayListизtoArrayКогда метод преобразует коллекцию в массив объектов, могут возникнуть неожиданные результаты.Подробности см. в другом сообщении блога редактора.

[На самом деле у ArrayList есть близнецы, но разница довольно большая! ]

Суммировать:В общем, надо знать, что универсальные массивы нельзя бетонировать, и как их решать! Вам может быть интересно, почему я неtransientЭтот редактор введен в следующую сериализацию и десериализацию.

2. Так какArrayListЕго можно автоматически расширять, так как же реализован его механизм расширения?

Иногда мы должны убедиться, что при добавлении воды исходный контейнер также может быть заполнен новой водой без перелива, то естьArrayListавтоматический механизм расширения. Мы можем представить, что если размер списка равен 10, он может содержать только 10 элементов при нормальных обстоятельствах, нам любопытно вызвать после этогоadd()метод делает что-то волшебное под капотом, так что давайте посмотримadd()Как реализован метод:

// 增加一个元素
public boolean add(E e) {
    // 确保内部容量大小，size指的是当前列表的实际元素个数
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

Из приведенного выше метода видно, что сначала определяют, достаточна ли внутренняя емкостьsize + 1Элементы, если возможно, напрямуюelementData[size++] = e;, иначе его нужно расширить, так как расширить?ensureCapacityInternal()метод посмотрите, здесь очень важный момент, пожалуйста, помните следующие параметры:

  • minCapacityВсегда представляет фактическое общее количество элементов после увеличения
  • newCapacityВсегда означает, что список может удовлетворить объем хранилищаminCapacityРазмер списка элементов, которые необходимо расширить
// 校验内部容量大小
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 这个方法只有首次调用时会用到，不然默认返回 minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 这里如果成立，表示该ArrayList是刚刚初始化，还没有add进任何元素
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// 扩容判断
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断是否需要扩容，elementData.length表示列表的空间总大小，不是列表的实际元素个数，size才是列表的实际元素个数
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Вышеизложенное будет судить о том, инициализирована ли коллекция, то есть нет ли вызова.add()Метод, если установлен, будет набор по умолчанию расширение на 10,DEFAULT_CAPACITYравно 10, в зависимости от того, что больше. последний методgrow()Условие - элемент контейнера больше 10 и нет свободного места, то есть его нужно расширить, давайте посмотримgrow()метод:

private void grow(int minCapacity) {
    // 获取旧的列表大小
    int oldCapacity = elementData.length;
    // 扩容之后的新的容器大小，默认增加一半 ..............................1
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容一半之后还不足，则新的容器大小等于minCapacity.............................2
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    // 如果新的容器大小比MAX_ARRAY_SIZE还大，
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    // 数组拷贝操作
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 最大不能超过Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
    	throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

выше1где>>Представляет сдвиг вправо, что эквивалентно делению на 2 и уменьшению его пополам.2Может позвонитьaddAll()метод установлен.

Ниже мы перечислим несколько случаев:

ID Описание ситуации вызвать добавить()? Вызвать addAll(size)? + size size Результаты
1 Список только что инициализирован да нет Инициализировать список длиной 10, то есть контейнер расширяется до 10 единиц
2 Фактическое количество элементов в списке равно 10, и фактический размер также равен 10. В это время вызывается операция добавления да нет К расширению судна 15, количество элементов контейнеров 11, то есть, есть четыре работоспособности
3 Фактическое количество элементов 10, 10 списка 10 - это также длина списка, затем Addall addall нет да + 5 Контейнер расширился до 15, и места не осталось
4 Фактическое количество элементов в списке равно 5, а длина списка равна 10. В это время вызывается операция addAll(). нет да + 10 Контейнер расширился до 15, и места не осталось

Суммировать:

Механизм расширения следующий:

  • 1. Сначала установите размер списка по умолчаниюnewCapacityУвеличьте исходную половину, то есть, если исходный размер равен 10, новый размер равен 15;
  • 2. Если новый размерnewCapacityвсе еще не удовлетворенaddОбщее количество входящих элементовminCapacity, затем измените размер списка на иminCapacityтого же размера, то есть если увеличить вдвоеnewCapacity15, ноaddОбщее количество входящих элементовminCapacityравно 20, то 15, очевидно, не может хранить 20 элементов, тогдаnewCapacityРазмер увеличен до 20, что достаточно для хранения 20 элементов;
  • 3. Если размер развернутого списка больше2147483639, то есть больше, чемInteger.MAX_VALUE - 8, в это время требуется дополнительная обработка, поскольку фактический общий размер элемента может быть больше, чемInteger.MAX_VALUEдаже больше, когда фактический общий размер элементаminCapacityзначение больше, чемInteger.MAX_VALUE, что больше, чем2147483647когда, в это времяminCapacityЗначение станет отрицательным, поскольку int имеет знак, и становится отрицательным, когда превышает максимальное значение.

Редактор считает, что третий пункт выше также отражает своего рода мудрость, то есть, когда что-то может пойти не так, мы должны решить это заранее, вместо того, чтобы ждать, когда это будет устранено, когда произойдет ошибка. Это цель нашей эксплуатации и технического обслуживания для мониторинга.

3. ЗвонокArrayListизiterator()Как выглядит возвращаемый итератор?

Мы все знаем, что все наборыCollectionКласс реализации интерфейса, и посколькуCollectionнаследоватьIterableинтерфейс, поэтому все коллекции повторяемы. Мы часто используем итераторы коллекций для обхода элементов коллекции, как в следующем коде:

ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
// 获取集合的迭代器对象
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String item = iter.next();
    System.err.println(item);
}

Мы можем назвать коллекциюiterator()метод для получения объекта итератора коллекции, затем вArrayListсередина,iterator()Как реализуется метод?

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

Супер просто, оказалось, что это новый называетсяItrобъект, то этоItrЧто это? Открываем исходный код и находимItrкласс на самом делеArrayListВнутренний класс , определенный следующим образом:

 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;......................... 1
    Itr() {}
    public boolean hasNext() {...}// 具体实现被我删除了
    public E next() {...}
    public void remove() {...}
    public void forEachRemaining(Consumer<? super E> consumer) {...}
    final void checkForComodification() {...}
}

Этот итератор реализуетIteratorИнтерфейс и реализует связанные методы, предоставляя нам возможность перемещаться по коллекции. Суммировать:ArrayListИтератор по умолчанию использует свою внутреннюю реализацию класса, и для реализации пользовательского итератора нужно только реализоватьIteratorинтерфейс и реализовать связанные методы. реализоватьIterableИнтерфейс указывает, что реализующий класс имеет что-то вродеfor-each loopВозможность итеративного обхода.

4. ПринятьArrayListКогда итератор пересекает коллекцию, почему он выбрасывает при выполнении связанных операций модификации в коллекции?ConcurrentModificationException, как мы можем избежать этого?

В подразделе 3 выше мы рассмотрелиArrayListИсходный код итератора, мы все знаем, что если во время итерации будет выполнен внутренний вызов не итератораremoveилиclearметод выдастConcurrentModificationExceptionНеобычно, почему? Давайте посмотрим вместе. Прежде всего, здесь разработаны две очень важные переменные, одна из которыхexpectedModCount, другойmodCount,expectedModCountОпределяется во внутреннем итераторе коллекции, как и исходный код в третьем разделе выше.1показано здесь,modCountсуществуетAbstractListопределено в. как третий бар1Там, где они видны, они равны по умолчанию, т.е.expectedModCount = modCount, выдает исключение, только если не хочет ждать. Вы действительно хотите создать исключение, если не хотите ждать? Заглянем внутрь итератораnextметод:

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];
}
// 具体检查
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Видно, что сообщается об ошибке, когда они не хотят ждать между двумя.Вопрос в том, когда они не захотят ждать? Не торопитесь, давайте посмотримArrayListизremoveметод:

public E remove(int index) {
    rangeCheck(index);
    // 这里会修改modCount的值
    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;
}

Видно, что при вызовеremove()Когда метод действительно модифицированmodCountЗначение, приводящее к ошибке. Тогда как мы можем сделать, чтобы не хотелось добавлять или удалять ошибку в итерации данных? Ответ заключается в использовании внутреннего итератораremove()метод.

Суммировать:

Когда итератор выполняет итерацию по коллекции, он не может изменить итерируемую коллекцию, потому чтоmodCountиexpectedModCountДва значения переменных не хотят ждать!

5. Когда коллекция расширяется или клонируется, копирование коллекции неизбежно, а затемArrayListКак реализовано копирование массива?

существуетArrayListКопия коллекции делается по телефонуArraysизcopyOfМетод реализуется следующим образом:

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());.................2
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    // 在创建新数组对象之前会先对传入的数据类型进行判定
    @SuppressWarnings("unchecked")
    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;
}

Наконец позвонилSystemизarraycopyметод.

6.ArrayListМеханизм сериализации в

В первом разделе мы знаемArrayListСохраненные данные определяются как:

transient Object[] elementData;

Нам показалось бы очень странным, что это ядро ​​коллекции, хранящей элементы, но объявленное какtransient, Означает ли это, что он не будет сериализован? Это не научно! На самом деле данные, хранящиеся в коллекции, все равно будут сериализованы, давайте посмотрим подробнее.ArrayListсерединаwriteObjectметод:

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 size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
    
    // 这个地方做一个序列化操作
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

Из приведенного выше кода мы видим, чтоArrayListНа самом деле даelementDataсериализуется, но причина этого в том, чтоelementDataВ нем может быть много нулевых элементов, чтобы не сериализовать нулевые элементы, так настроитьwriteObjectиreadObjectметод.

Спасибо за чтение, приветствуются комментарии, обсуждаем вместе ~

Категории