首页   >   代码编程

ArrayList初始大小、上限、扩容机制图文详解

在使用arraylist的时候,从来没有手动给它指定过大小,每次使用都是直接new arraylist(),但是那么它的默认大小是多少呢?超出这个默认大小之后,它又是如何扩容的呢扩容的前提条件是什么呢上限又是多少呢

想弄清楚这个问题,最简单有效的方式就是看源码,今天就来给大家看一下它的扩容机制。

本文中以jdk1.8.0_121为例,以截取代码片段的方式来逐一给大家分析:

默认容量

有一个DEFAULT_CAPACITY变量,大小为10

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

再来看一下它的三个构造方法:

无参构造方法

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

传入容量的构造方法

/**
 * 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);
    }
}

传入集合的构造方法

/**
 * 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;
    }
}

三个构造方法中,都没有看到使用DEFAULT_CAPACITY变量的地方,没关系,我们先记住这个变量,继续往下面看。

自动扩容

往list中插入元素时,使用的是add方法,我们就从这里入手

/**
 * 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;
}

在插入之前,它调用了ensureCapacityInternal方法,字面上就是确认容量的意思,参数是size+1,我们再来看一下这个size是个什么东西

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

从注释上来看,这个就是list的size,此时,才初始化这个list,并没有元素,所以这个size==0,那么ensureCapacityInternal方法传的参数就是1(元素个数 + 1)

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

终于用到了DEFAULT_CAPACITY变量,但却是包裹在一个if中,我们来看一下if条件中的两个变量

/**
 * 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.
 */
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.
 */
transient Object[] elementData; // non-private to simplify nested class access

上面那个是默认的空数组,下面那个数组就是list存放元素的地方,在上面add方法的代码块中,可以看到插入元素的实现就是:elementData[size++] = e,也就是说将数组下标+1,然后再来存储元素。

这样一来就好理解这个if了,如果首次进来,null == null,肯定是成立的,所以此时就会用到DEFAULT_CAPACITY了,从来和传入的1作比对,取最大值作为list的minCapacity(最小容量 == 默认容量)。

现在可以搞明白默认容量这个问题了,总结如下:

如果我们指定的默认容量超过了DEFAULT_CAPACITY,那么默认容量就是我们指定的大小;

如果我们制定的默认容量不超过DEFAULT_CAPACITY,那么默认容量就是DEFAULT_CAPACITY的大小;

为了找到扩容的地方,我们继续追踪ensureCapacityInternal方法中的ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

经过上面的分析,这个if肯定是true,因为elementData此时还是一个空数组,那它的length一定为0,所以进入到grow方法继续查看,我会在代码中加入一些注释帮助大家理解

/**
 * 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) {
    // 将当前的list大小取出来
    int oldCapacity = elementData.length;
    // 新的容量大小为:旧的容量 + 旧的容量的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的容量小于minCapacity,就使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新的容量是否超过了上限
    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);
}

上限

正常扩容的容量是:旧容量 + 旧容量的1/2,然后对上限做了校验,我们看一下MAX_ARRAY_SIZE变量和hugeCapacity()方法

/**
 * 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;

int的最大值减去8,那为什么需要减去8呢?

将注释翻译了一下,大概意思是因为还需要存放jdk自身的一些头文件信息,所以也需要占用一部分空间。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

此方法用来处理最大上限的问题,如果说传入的值超过了最大上限,直接使用int的最大值,否则使用最大上限。

其实这个方法比较有趣,也让我感到了一点儿困惑,不知道是否我看漏了代码,我觉着这个里面的判断并没有什么卵用,尤其是return的那个三目,既然我调用方都已经是超过了上限才会调用,那么这岂不是恒为true?而且既然设置了Integer.MAX_VALUE这么一个变量,可是到了最后,还是会有超出这个变量的处理,也就是说,这个其实并非是最大的值?

哎,不管他了,反正我们知道最大上限是Integer.MAX_VALUE即可。。。

扩容时机

这个问题其实在上面已经给大家贴出代码了,不过需要几个方法一起来看,我给大家串起来看一下

public boolean add(E e) {
	// 1.第一个地方
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

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

    // 2.第二个地方
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 3.第三个地方
    elementData = Arrays.copyOf(elementData, newCapacity);
}

第一个地方:size + 1,也就是元素个数 + 1;

第二个地方:传进来的容量超过了list的size,就需要触发扩容;

第三个地方:计算好新的容量之后,利用Arrays.copyOf拷贝一个大小为newCapacity的数组;

假设我们此时new了一个list,那么此时的容量是10,那么,我们此时依次来插入元素,当前9个元素插入的时候,在第二个地方的if是过不了的,就算是第9个元素,9 + 1 = 10,而10 > 10是不成立的,也就是说,当插入第10个元素的时候,10 + 1 > 10才会成立,才会触发扩容。

几个问题,总结如下:

list默认大小为10,如果手动设置了初始化大小,list的默认大小就是自己设置的那个值;

list大小为n,插入第n个元素时才会触发扩容;

扩容上限为int的最大值;

QQ群: 686430774  /  718410762

站长Q: 1347384268

如果文章有帮到你,可以考虑请博主喝杯咖啡!

分享到:

欢迎分享本文,转载请注明出处!

作者:不忘初心

发布时间:2019-03-17

永久地址:https://www.jiweichengzhu.com/article/90a3c00dce0e4c95801d21234614dace

评论