Расскажите о сжатии ArrayList, которого вы не знаете

Java

предисловие

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

PS: сокращение относится к уменьшению размера массива объектов elementData в ArrayList.

ArrayListБудет ли он уменьшаться автоматически?

теперь, когдаArrayListАвтоматическое расширение обычно происходит вadd()а такжеaddAll()метод, то когдаArrayListперечислитьremove()Будет ли он автоматически уменьшаться при использовании метода?

ArrayList#remove()Анализ исходного кода

remove()Есть два метода

  1. Входной параметр является индексом массива и возвращает удаленный элемент.
  2. Входной параметр является элементом массива и возвращает индекс массива.

PS: Исходный код JDK, изучаемый в этой статье, — это Oracle JDK 1.8.

Вот анализ исходного кода первого метода

    public E remove(int index) {
        // 校验传入的下标是否大于或等于当前ArrayList的长度size
        // 如果超过直接抛出IndexOutOfBoundsException
        rangeCheck(index);
        
        // 修改次数自增
        // modCount是用于快速失败机制的，这里不展开
        modCount++;
        // 获取需要删除的元素的值
        E oldValue = elementData(index);
        
        // 计算数组从需要删除的元素后需要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 使用System.arraycopy()来进行数组元素左移
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 多余的元素标记为null便于gc回收，同时size自减
        elementData[--size] = null;
        // 返回被删除的元素值
        return oldValue;
    }

PS: System#arraycopy() не влияет на длину исходного и целевого массивов.

ArrayList#remove()Диаграмма исходного кода

Если вам трудно понять исходный код, вы можете обратиться к следующемуArrayListизremove()Схема ключевого процесса метода

ArrayList的remove方法关键过程图解

Как видно из вышеизложенногоArrayListв исполненииremove()метод, встроенныйObjectМассив на самом деле не уменьшает свою длину, он просто сдвигает некоторые элементы массива влево и устанавливает последний элемент вnullв то же времяsizeСамоуменьшение для реализации операции удаления. А входной параметр является элементом массива и возвращает индекс массиваremove(),removeAll()а такжеremoveRange()Это аналогичный подход.

ArrayList#clear()Анализ исходного кода

Кромеremove()за пределами,ArrayListесть еще одинclear()Метод используется для очистки массива. Итак, как это работает? Это на самом деле так просто, что я не могу в это поверить

public void clear() {
        // 修改次数自增
        modCount++;

        // 遍历数组并置为null便于gc回收
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        // 直接给size赋值为0
        size = 0;
    }

В заключение

Из анализа исходного кода в двух предыдущих разделах мы можем узнать, что на самом делеArrayListМеханизм автоматического масштабирования отсутствует. На самом деле такая конструкция понятна, ведь зачастую невозможно судить о том, требуется ли операция масштабирования. Поскольку автоматического сжатия нет, можно ли уменьшить ArrayList?

ArrayListМожно ли его уменьшить?

конечнонемного,То естьtrimToSize()метод. Этот метод будетArrayListВстроенный массив сжимается до текущегоsize, исходник тоже очень простой, достаточно датьelementDataсоответствующийsizeмассив длин. Исходный код выглядит следующим образом

    public void trimToSize() {
        // 修改次数自增
        modCount++;
        // 判断当前是否需要缩容
        if (size < elementData.length) {
            // 如果size为0，直接给elementData赋值内置的空数组
            // 不为0则创建一个size长度的新数组
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

Суммировать

  1. ArrayListизremoveПросто переместите некоторые элементы массива влево и установите последний элемент вnullв то же времяsizeСамоуменьшение для реализации операции удаления. на самом деле не правильноelementDataсокращать.
  2. можно использоватьtrimToSize()пара методовelementDataсокращать.
Категории