Анализ исходного кода ArrayList (механизм расширения jdk8)

Java

Обзор ArrayList

(1)ArrayListЭто класс коллекций переменной длины, реализованный на основе массивов фиксированной длины.

(2)ArrayListДопускаются нулевые значения и повторяющиеся элементы, и когда количество элементов, добавленных в ArrayList, больше, чем емкость базового массива, он пройдетРасширениеМеханизм регенерирует больший массив.

(3) Из-заArrayListНижний слой реализован на основе массивов, поэтому он может гарантироватьO(1)Операция случайного поиска завершается на уровне сложности.

(4)ArrayListЭто не потокобезопасный класс.В параллельной среде, если несколько потоков работают с ArrayList одновременно, будут возникать непредсказуемые исключения или ошибки.

Свойства члена ArrayList

Прежде чем представить различные методы ArrayList, давайте взглянем на основные члены свойств. вDEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA的区别是：当我们向数组中添加第一个元素时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会知道数组该扩充多少.

//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;

//默认的空的数组，这个主要是在构造方法初始化一个空数组的时候使用
private static final Object[] EMPTY_ELEMENTDATA = {};

//使用默认size大小的空数组实例，和EMPTY_ELEMENTDATA区分开来，
//这样可以知道当第一个元素添加的时候进行扩容至多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。
//一个空的实例elementData为上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候
//会进行扩容，扩容大小就是上面的默认容量DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access

//arrayList的大小
private int size;

статический модифицированныйEMPTY_ELEMENTDATAиDEFAULTCAPACITY_EMPTY_ELEMENTDATA

Конструктор ArrayList

(1) Конструктор с инициализированной емкостью

  • Если параметр больше 0, elementData инициализируется массивом размера initialCapacity.
  • Если параметр меньше 0, elementData инициализируется пустым массивом.
  • Если параметр меньше 0, выбрасывается исключение
//参数为初始化容量
public ArrayList(int initialCapacity) {
    //判断容量的合法性
    if (initialCapacity > 0) {
        //elementData才是实际存放元素的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果传递的长度为0，就是直接使用自己已经定义的成员变量(一个空数组)
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

(2) Безпараметрическая конструкция

  • Инициализировать elementData пустым массивом DEFAULTCAPACITY_EMPTY_ELEMENTDATA в конструкторе
  • При вызове метода add для добавления первого элемента будет выполнено расширение.
  • Расширить до размера DEFAULT_CAPACITY=10
//无参构造，使用默认的size为10的空数组，在构造方法中没有对数组长度进行设置，会在后续调用add方法的时候进行扩容
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

(3) Конструктор, параметр которого имеет тип Collection

//将一个参数为Collection的集合转变为ArrayList（实际上就是将集合中的元素换为了数组的形式）。如果
//传入的集合为null会抛出空指针异常（调用c.toArray()方法的时候）
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        //c.toArray()可能不会正确地返回一个 Object[]数组，那么使用Arrays.copyOf()方法
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果集合转换为数组之后数组长度为0，就直接使用自己的空成员变量初始化elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Вышеупомянутые методы построения относительно просты для понимания.Обратите внимание на то, что делают первые два метода построения.Цель состоит в том, чтобыИнициализировать базовый массив elementData(this.elementData=XXX). Разница в том, что无参构造方法会将 elementData 初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组. и有参的构造方法则会将 elementData 初始化为参数值大小（>= 0）的数组. В общем, мы можем использовать конструктор по умолчанию. Если вы знаете, сколько элементов будет вставлено в ArrayList, вы можете использовать параметризованный конструктор.

Как упоминалось выше, когда используется конструкция без параметров, расширение будет выполняться при вызове метода добавления, поэтому давайте рассмотрим метод добавления и детали расширения.

Метод добавления ArrayList

Общий процесс метода добавления

//将指定元素添加到list的末尾
public boolean add(E e) {
    //因为要添加元素，所以添加之后可能导致容量不够，所以需要在添加之前进行判断（扩容）
    ensureCapacityInternal(size + 1);  // Increments modCount!!（待会会介绍到fast-fail）
    elementData[size++] = e;
    return true;
}

Мы видим, что в методе add размер размера будет оцениваться перед добавлением элементов, поэтому давайте взглянем на детали метода sureCapacityInternal.

sureCapacityInternal метод анализа

private void ensureCapacityInternal(int minCapacity) {
    //这里就是判断elementData数组是不是为空数组
    //（使用的无参构造的时候，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA）
    //如果是，那么比较size+1(第一次调用add的时候size+1=1)和DEFAULT_CAPACITY，
    //那么显然容量为10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

** При добавлении первого элемента minCapacity равно (size+1=0+1=)1, после сравнения метода Math.max() minCapacity равно 10. ** Затем вызовите sureExplicitCapacity, чтобы обновить значение modCount и определить, требуется ли расширение.

Анализ метода sureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //这里就是add方法中注释的Increments modCount
    //溢出
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//这里就是执行扩容的方法
}

Давайте рассмотрим основной метод расширения.

анализ метода выращивания

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // oldCapacity为旧数组的容量
    int oldCapacity = elementData.length;
    // newCapacity为新数组的容量（oldCap+oldCap/2:即更新为旧容量的1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 检查新容量的大小是否小于最小需要容量，如果小于那旧将最小容量最为数组的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果新容量大于MAX_ARRAY_SIZE，使用hugeCapacity比较二者
    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);
}

метод огромных емкостей

Вот краткий обзор метода hugeCapacity.

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //对minCapacity和MAX_ARRAY_SIZE进行比较
    //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

Добавить сводку процесса выполнения метода

Давайте на картинке кратко разберем процесс выполнения после первого вызова метода add при использовании безпараметрической конструкции.

Это процесс вызова метода добавления в первый раз.Когда емкость значения расширения равна 10,

  • Продолжайте добавлять второй элемент (сначала обратите внимание, что параметр, передаваемый методу sureCapacityInternal, равен size+1=1+1=2)

  • В методе sureCapacityInternal elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA не хранится, поэтому выполните метод sureExplicitCapacity напрямую.

  • В методе sureExplicitCapacity minCapacity — это только что переданное значение 2, поэтому второе суждение if (2-10=-8) не будет выполнено, то есть если newCapacity не больше MAX_ARRAY_SIZE, он не войдет.growметод. Емкость массива равна 10, метод add возвращает true, а размер увеличивается до 1.

  • Предположим, добавлено 3, 4...10 элементов (процесс аналогичен, но метод расширения роста выполняться не будет)

  • Когда добавляется 11-й элемент, вводится метод роста, и значение newCapacity вычисляется равным 15, что больше, чем minCapacity (10+1=11), и первым, если оценка недействительна. Новая емкость не превышает максимальный размер массива и не войдет в метод hugeCapacity. Емкость массива увеличивается до 15, метод add возвращает true, а размер увеличивается до 11.

метод add(индекс int, элемент E)

//在元素序列 index 位置处插入
public void add(int index, E element) {
    rangeCheckForAdd(index); //校验传递的index参数是不是合法
    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index 及其之后的所有元素都向后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. 将新元素插入至 index 处
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) //这里判断的index>size（保证数组的连续性），index小于0
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

метод add(int index, E element) (указанная позиция в последовательности элементов (假设该位置合理) вставка) процесс наверное следующий

  1. Проверить, достаточно ли места в массиве (реализация здесь и выше)
  2. Сдвинуть индекс и все элементы после индекса на один бит назад
  3. Вставьте новый элемент в index.

Чтобы вставить новый элемент в указанную позицию последовательности, необходимо сдвинуть позицию и элементы после нее на один бит назад, чтобы освободить место для нового элемента. Временная сложность этой операцииO(N), перемещение элементов часто может вызвать проблемы с эффективностью, особенно когда количество элементов в коллекции велико. В повседневной разработке мы должны стараться избегать вызова второго метода вставки в больших коллекциях, если это не требуется.

удалить метод ArrayList

ArrayList поддерживает два способа удаления элементов.

1. удалить (индекс int) удалить по нижнему индексу

public E remove(int index) {
    rangeCheck(index); //校验下标是否合法（如果index>size，旧抛出IndexOutOfBoundsException异常）
    modCount++;//修改list结构，就需要更新这个值
    E oldValue = elementData(index); //直接在数组中查找这个值

    int numMoved = size - index - 1;//这里计算所需要移动的数目
    //如果这个值大于0 说明后续有元素需要左移(size=index+1)
    //如果是0说明被移除的对象就是最后一位元素(不需要移动别的元素)
    if (numMoved > 0)
        //索引index只有的所有元素左移一位  覆盖掉index位置上的元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //移动之后，原数组中size位置null
    elementData[--size] = null; // clear to let GC do its work
    //返回旧值
    return oldValue;
}
//src:源数组   
//srcPos:从源数组的srcPos位置处开始移动
//dest:目标数组
//desPos:源数组的srcPos位置处开始移动的元素，这些元素从目标数组的desPos处开始填充
//length:移动源数组的长度
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

Процесс удаления показан на следующем рисунке

2. remove(Object o) удаляет в соответствии с элементом, он удалит первый элемент, соответствующий параметру

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
}

Другие методы ArrayList

метод Ennerecapacity

Лучше использовать метод sureCapacity перед добавлением большого количества элементов, чтобы уменьшить количество инкрементных перераспределений.

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

ArrayListСводка

(1)ArrayListЭто класс-коллекция переменной длины.Реализован на основе массива фиксированной длины.Емкость, инициализируемая с помощью метода построения по умолчанию, равна 10 (после 1.7 у всех отложенная инициализация, то есть при вызове метода add для при первом добавлении элементов емкость elementData инициализируется как 10).

(2)ArrayListДопускаются нулевые значения и повторяющиеся элементы, и когда количество элементов, добавленных в ArrayList, больше, чем емкость базового массива, он пройдетРасширениеМеханизм регенерирует больший массив.ArrayListДлина расширения в 1,5 раза больше исходной длины.

(3) Из-заArrayListНижний слой реализован на основе массивов, поэтому он может гарантироватьO(1)Операция случайного поиска завершается на уровне сложности.

(4)ArrayListЭто не потокобезопасный класс.В параллельной среде, если несколько потоков работают с ArrayList одновременно, будут возникать непредсказуемые исключения или ошибки.

(5) Удобно добавлять последовательно

(6) Удаление и вставка должны копировать массив, который имеет низкую производительность (можно использовать LinkindList)

(7) Integer.MAX_VALUE - 8: в основном с учетом различных JVM, некоторые JVM добавят некоторые заголовки данных. Когда расширенная емкость больше, чем MAX_ARRAY_SIZE, мы сравним минимальную требуемую емкость с MAX_ARRAY_SIZE. Если она большая, она может занять только Integer.MAX_VALUE, иначе Integer.MAX_VALUE -8. Это доступно только с jdk1.7

быстродействующий механизм

Объяснение отказоустойчивости:

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

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

//这里的代码是一个对两个整数做除法的方法，在fast_fail_method方法中，我们对被除数做了个简单的检查，如果其值为0，那么就直接抛出一个异常，并明确提示异常原因。这其实就是fail-fast理念的实际应用。
public int fast_fail_method(int arg1,int arg2){
    if(arg2 == 0){
        throw new RuntimeException("can't be zero");
    }
    return arg1/arg2;
}

Этот механизм используется во многих местах в классе коллекций Java для проектирования. При неправильном использовании код, запускающий проектирование отказоустойчивого механизма, вызовет непредвиденные ситуации. Обычно мы говорим об отказоустойчивом механизме в Java,Значение по умолчанию относится к механизму обнаружения ошибок для коллекций Java.. Когда несколько потоков выполняют структурные изменения в частичной коллекции, этот механизм может быть запущен, и тогда будет выдано исключение параллельной модификации**ConcurrentModificationException** Конечно, если вы не находитесь в многопоточной среде, если вы используете метод добавления/удаления во время обхода foreach, это исключение также может быть выдано. Ссылаться набыстродействующий механизм, вот краткое содержание

​之所以会抛出ConcurrentModificationException异常，是因为我们的代码中使用了增强for循环，而在增强for循环中，集合遍历是通过iterator进行的，但是元素的add/remove却是直接使用的集合类自己的方法。这就导致iterator在遍历的时候，会发现有一个元素在自己不知不觉的情况下就被删除/添加了，就会抛出一个异常，用来提示可能发生了并发修改！所以，在使用Java的集合类的时候，如果发生ConcurrentModificationException，优先考虑fail-fast有关的情况，实际上这可能并没有真的发生并发，只是Iterator使用了fail-fast的保护机制，只要他发现有某一次修改是未经过自己进行的，那么就会抛出异常。

Категории