Механизм расширения ArrayList

Java

начальная мощность

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

// 默认容量是10
private static final int DEFAULT_CAPACITY = 10;
// 如果容量为0的时候，就返回这个数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 使用默认容量10时，返回这个数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素存放的数组
transient Object[] elementData;
// 元素的个数
private int size;

// 记录被修改的次数
protected transient int modCount = 0;
// 数组的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

ArrayListСуществует три метода построения, и возможности разных методов построения различны.Подробнее вы можете проверить исходный код JDK.

  • Если начальная емкость не передается, используйте емкость по умолчанию и установитеelementDataзаDEFAULTCAPACITY_EMPTY_ELEMENTDATA
  • Если исходная емкость передана, будет оценено входящее значение.Если оно больше 0, будет создан новый массив объектов.Если оно равно 0, оно будет установлено напрямую.elementDataзаEMPTY_ELEMENTDATA.
  • Если коллекция передана, она будет называтьсяtoArray()метод превращает его в массив и присваиваетelementData. Он также определит, равна ли его длина 0. Если она равна 0, установитеelementDataзаEMPTY_ELEMENTDATA.

Что именно означает расширение?

можно увидеть,ArrayListВ нем два понятия, одноcapacity, что означает «емкость», которая по сути является массивомelementDataдлина. иsizeОн представляет собой «количество сохраненных элементов».

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

Как ArrayList достигает расширения?

Нижний уровень — это в основном эти три частных метода:

// 扩容一个
private Object[] grow() {
	return grow(size + 1);
}

// 保证扩容到期望容量minCapacity及以上
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

// 根据期望容量minCapacity计算实际需要扩容的容量
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 得到旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 设置新容量为旧容量的1.5倍
    if (newCapacity - minCapacity <= 0) { // 如果新容量仍然小于期望容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 如果是使用的默认容量
            return Math.max(DEFAULT_CAPACITY, minCapacity); // 取默认容量和期望容量较大值返回
        if (minCapacity < 0) // overflow // 检查期望容量是否越界（int 的范围）
            throw new OutOfMemoryError();
        return minCapacity; // 返回期望容量
    }
    // 如果新容量大于期望容量，判断一下新容量是否越界
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

Видно, что нижний слой на самом деле называетсяArrays.copyOfметод расширения емкости массива. Здесь мы в основном рассматриваем реализацию последнего метода newCapacity(int minCapacity).

По умолчанию новая емкость будет в 1,5 раза больше исходной емкости, и здесь используются битовые операции для повышения эффективности.. Как правило, если емкость больше ожидаемой емкости после расширения в 1,5 раза, возвращается значение, в 1,5 раза превышающее старую емкость. А если она меньше ожидаемой емкости, то вернуть ожидаемую емкость. Емкость по умолчанию, равная 10, здесь специально обрабатывается.

Использование этого значения в 1,5 раза вместо прямого использования ожидаемой емкости позволяет предотвратить влияние частого расширения емкости на производительность.. Только представьте, что если каждую операцию добавления нужно развернуть один раз, производительность будет очень низкой.

Вышеупомянутый метод роста на самом деле в основном используется для достижения автоматического расширения. Пользователи также могут расшириться вручную, вызвав следующие методы:

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

Зачем вам вручную расширять? Представьте себе, что пользователь уже знает, что будет размещено большое количество элементов, например, в настоящее время имеется 20 элементов, а должно быть размещено 2000. В настоящее время использование автоматического расширения многократно расширит возможности. Ручное расширение может быть расширено до 2000 за один раз, что может повысить производительность.

Уменьшается ли ArrayList?

ArrayListНет усадки. Будь тоremoveметод ещеclearметоды, ни один из которых не изменит существующий массивelementDataдлина. Но они оба устанавливают элемент в соответствующей позиции наnull, чтобы сборщик мусора мог перерабатывать неиспользуемые элементы и экономить память.

Категории