关于后端:从源码层面理解ArrayList-扩容策略

43次阅读

共计 6573 个字符,预计需要花费 17 分钟才能阅读完成。

ArrayList 在咱们日常开发中用到的十分多,咱们晓得 ArrayList 外部是通过 Object 数组实现的,而数组的长度一经定义,就无奈更改了。

那么问题就来了,ArrayList 是如何实现扩容的呢?

咱们先来看看 ArrayList 类中有哪些成员变量。

ArrayList 的成员变量

/**
 * Default initial capacity.
 * 默认的初始容量 10。*/
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 共享的空数组实例,用于空实例。*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 *
 * 共享的空数组实例,用于默认大小的空实例。* 咱们辨别 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 和 EMPTY_ELEMENTDATA 
 * 为了晓得增加第一个元素时要扩容多少。*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 *
 * Object[] 用于理论存储 ArrayList 的元素。ArrayList 的容量是数组的长度。* 当增加第一个元素的时候,任何空的 ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)* 容量将被减少到 DEFAULT_CAPACITY。*/
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 * ArrayList 的大小(ArrayList 中蕴含的元素个数)* @serial
 */
private int size;
复制代码 
问题一:ArrayList 中的 size 和 capacity 怎么了解?

size 用于记录 ArrayList 实例中 elementData 数组中元素的个数,capacity 是 elementData 数组的长度(包含已应用的数组空间和未应用的数组空间)。如果被 ArrayList 看作一个喝水的杯子的话,capacity 就是杯子的容积,也就是代表了杯子能装多少水,size 就是杯子曾经装的水的体积。杯子可能装满了水也可能没装满。

要想应用一个类,首先要创立这个类的实例,那么接下来咱们看看 ArrayList 有哪些构造方法,这是咱们比较关心的。

ArrayList 的构造方法

1、无参构造方法

正文上说,结构一个初始容量为 10 的空列表。实际上,Java8 中应用了提早初始化,应用无参构造方法,并不会马上创立长度为 10 的数组,而是在调用 add 办法增加第一个元素的时候才对 elementData 数组进行初始化(前面会看到)。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
复制代码 

2、指定初始容量的构造方法

传入初始容量 initialCapacity,如果初始容量大于 0,那么间接创立一个指定大小的 Object 数组;如果初始容量等于 0,elementData 指向共享的空数组实例 EMPTY_ELEMENTDATA。如果初始容量小于 0,抛出 IllegalArgumentException 异样。

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}
复制代码 

3、指定初始汇合的构造方法

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();
    if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
复制代码 
问题二:ArrayList 源码中为何定义两个 Object 数组呢?EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 各有什么用途?

从以上源码中能够看出,这两个常量都是空 Object 数组的援用,都示意 ArrayList 实例的空状态,即 elementData 数组中没有元素。EMPTY_ELEMENTDATA 是应用指定初始容量的构造方法 ArrayList(int initialCapacity)(初始容量大小为 0)和 指定初始汇合的构造方法 ArrayList(Collection<? extends E> c)(初始汇合大小为 0)时应用。DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是应用无参构造方法时应用的。

构造方法也有了,接下来咱们看看如何向 ArrayList 容器中增加一个元素。

增加元素

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码 

add 办法向 ArrayList 中增加 1 个元素,为了确保 ArrayList 外部数组容量,add 办法外部首先调用 ensureCapacityInternal 办法,入参 minCapacity 为 ArrayList 蕴含的理论元素个数 size + 1。

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
复制代码 

ensureCapacityInternal 外部调用 calculateCapacity 办法来计算容量,如果 ArrayList 是通过无参构造方法进行创立的,那么满足上面 if 条件(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA),如果是增加第一个元素,则 minCapacity 为 1,则数组扩容到 DEFAULT_CAPACITY 大小为 10,这也对应了无参构造方法的正文 Constructs an empty list with an initial capacity of ten。

private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是空 ArrayList,则容量为 DEFAULT_CAPACITY 和 minCapacity 的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
复制代码 

笔者过后读到 Math.max(DEFAULT_CAPACITY, minCapacity); 这行代码的时候有点小小的困惑,既然 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 阐明以后的 ArrayList 是空的,那么间接返回 DEFAULT_CAPACITY 值不就行了么,为啥还要比拟呢。直到起初发现了 addAll(Collection<? extends E> c) 这个办法,addAll 办法能够一次向 ArrayList 中增加多个元素,新减少的元素个数可能大于 DEFAULT_CAPACITY,为了缩小扩容次数,应该取 DEFAULT_CAPACITY 和 minCapacity 的最大值。

minCapacity 等于 ArrayList 以后理论元素个数 size + 新增的元素个数,minCapacity 是扩容后 Object 数组的最小长度。

ensureExplicitCapacity 办法确保 ArrayList 有足够的容量寄存新的元素。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码 

容量不够的话,会调用 grow 办法 进行扩容操作。

扩容操作

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新容量扩充到原容量的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        // 如果新容量还是比所需的最小容量小,则让新容量等于所需的最小容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 如果新容量超过了 Integer.MAX_VALUE - 8,持续计算
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 所需的最小容量 minCapacity 靠近 size
    elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码 

扩容计算,int newCapacity = oldCapacity + (oldCapacity >> 1); oldCapacity 是 ArrayList 外部数组长度,oldCapacity >> 1 是位运算的右移操作,右移一位相当于除以 2,新的容量 newCapacity 为之前容量的 1.5 倍。

elementData = Arrays.copyOf(elementData, newCapacity); 对 elementData 数组进行扩容。

private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
复制代码 
问题三:ArrayList 扩容每次都是原容量的 1.5 倍吗?

从源码中能够看出,当应用无参构造方法创立一个 ArrayList 实例,调用 add 办法增加第一个元素的时候,calculateCapacity 办法返回的是默认初始容量 DEFAULT_CAPACITY 大小为 10;当应用指定初始容量创立 ArrayList 实例,调用 addAll 办法增加多个元素的时候,原容量的 1.5 倍也无奈寄存元素的时候,会创立一个更大(不会超过 Integer.MAX_VALUE)的数组来寄存元素。

问题四:ArrayList 的 add 操作如何优化?

扩容须要挪动数据,十分影响性能。那么优化的重点就是尽量避免 ArrayList 外部进行外部扩容。对于 add 操作,如果增加的元素个数已知,最好应用指定初始容量的构造方法创立 ArrayList 实例或者在增加元素之前执行 ensureCapacity 办法确保有足够的容量来寄存 add 操作的元素。

参考:《2020 最新 Java 根底精讲视频教程和学习路线!》

链接:https://juejin.cn/post/691246…

正文完
 0