首页 > 代码库 > ArrayList源码解析(二)自动扩容机制与add操作

ArrayList源码解析(二)自动扩容机制与add操作

  本篇主要分析ArrayList的自动扩容机制,add和remove的相关方法。

  作为一个list,add和remove操作自然是必须的。

  前面说过,ArrayList底层是使用Object数组实现的。数组的特性是大小固定,这个特性导致的后果之一就是,当ArrayList中成员个数超过capacity后,就需要重新分配一个大的数组,并将原来的成员拷贝到新的数组之中。

  add操作前都需要保证capacity足够,因此扩容机制和add放在一起讲解。

1.ArrayList的自动扩容机制

  ArrayList有两个概念,capacity和size。capacity就是底层Object数组的length,表示能容纳的最大成员数;size则表示已经存储的成员数,可以通过size()函数获取。

    /**     * Returns the number of elements in this list.     *     * @return the number of elements in this list     */    public int size() {        return size;    }

  有时我们需要保证ArrayList的capacity能满足一个最小值,比如ArrayList的当前capacity为10,且size也为10,这时需要插入一个成员,就要保证ArrayList的capacity至少为11。这时就需要ArrayList的扩容机制发挥作用。

  ArrayList的扩容相关方法如下:

  /**    
  * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * 如果需要,函数增加ArrayList的容量,以确保至少可以容纳minCapacity指定的成员数量。 * @param minCapacity the desired minimum capacity */ 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); } } private void ensureCapacityInternal(int minCapacity) { if (elementData =http://www.mamicode.com/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

  上面三个方法都比较简单,关键在于ensureExplicitCapacity()方法中调用的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) {        // overflow-conscious code        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1);        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 =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);    }

 

  当调用grow()方法时,已经确定要进行扩容了,所以grow()中不再进行是否进行扩容的判断。

  oldCapacity存储旧容量值,新的容量值newCapacity取(1+0.5)倍的oldCapacity大小,如下:

int newCapacity = oldCapacity + (oldCapacity >> 1);

  如果newCapacity仍然小于期望扩充的最小值minCapacity,newCapacity取minCapacity的大小;否则就取(1+0.5)倍的oldCapacity大小。

  如果计算得到的newCapacity比MAX_ARRAY_SIZE还大,就需要调用hugeCapacity()方法进行处理。

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

最后,将原来数组中的成员拷贝到新的数组中。

简言之,当minCapacity大于ArrayList的capacity时,就将数组的长度扩充到原来的1.5倍,如果这个值还是小于minCapacity,就取minCapacity作为新的capacity。

ArrayList的扩容机制提高了性能,如果每次只扩充一个,那么频繁的插入会导致频繁的拷贝,降低性能,而ArrayList的扩容机制避免了这种情况。

2.add操作

ArrayList操作都调用了上面的ensureCapacityInternal(),先保证ArrayList的capacity足够大(至少为size+1),所以可能发生了数组的复制,也可能没有发生。

所有的add相关的方法都修改了size的值,因此modCount值也会增加。

ArrayList共有四个add相关的方法,前两个用来添加单个成员,后两个用来将一个Collection的所有成员添加到ArrayList中:

1)在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;    }

这个方法比较容易理解,先保证capacity足够,然后在ArrayList的末尾添加成员,返回类型为boolean。

2)在指定位置插入一个成员

    /**     * Inserts the specified element at the specified position in this     * list. Shifts the element currently at that position (if any) and     * any subsequent elements to the right (adds one to their indices).     *     * @param index index at which the specified element is to be inserted     * @param element element to be inserted     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public void add(int index, E element) {        rangeCheckForAdd(index);        ensureCapacityInternal(size + 1);  // Increments modCount!!        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);        elementData[index] = element;        size++;    }

这个方法在index的位置插入成员element:

  先调用 rangeCheckForAdd 对index进行界限检查;

  然后调用 ensureCapacityInternal 方法保证capacity足够大;

  再将从index开始之后的所有成员后移一个位置;

  将element插入index位置;

  最后size加1。

3)将一个Collection的所有成员都添加到ArrayList的末尾

    /**     * Appends all of the elements in the specified collection to the end of     * this list, in the order that they are returned by the     * specified collection‘s Iterator.  The behavior of this operation is     * undefined if the specified collection is modified while the operation     * is in progress.  (This implies that the behavior of this call is     * undefined if the specified collection is this list, and this     * list is nonempty.)     *     * @param c collection containing elements to be added to this list     * @return <tt>true</tt> if this list changed as a result of the call     * @throws NullPointerException if the specified collection is null     */    public boolean addAll(Collection<? extends E> c) {        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;    }

这个方法只有一个参数,默认将Collection的所有成员都添加到ArrayList的末尾:

  先将Collection转换为数组a;

  确保ArrayList的capacity足够大(至少size+a.length);

  将数组a的所有成员拷贝到ArrayList的末尾;

     size增加Collection的成员个数, 并返回Collection成员个数。

 4)将一个Collection的所有成员插入到ArrayList的指定位置

    /**     * Inserts all of the elements in the specified collection into this     * list, starting at the specified position.  Shifts the element     * currently at that position (if any) and any subsequent elements to     * the right (increases their indices).  The new elements will appear     * in the list in the order that they are returned by the     * specified collection‘s iterator.     *     * @param index index at which to insert the first element from the     *              specified collection     * @param c collection containing elements to be added to this list     * @return <tt>true</tt> if this list changed as a result of the call     * @throws IndexOutOfBoundsException {@inheritDoc}     * @throws NullPointerException if the specified collection is null     */    public boolean addAll(int index, Collection<? extends E> c) {        rangeCheckForAdd(index);        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        int numMoved = size - index;        if (numMoved > 0)            System.arraycopy(elementData, index, elementData, index + numNew,                             numMoved);        System.arraycopy(a, 0, elementData, index, numNew);        size += numNew;        return numNew != 0;    }

这个方法需要注意的是,需要将index位置以及这之后的(size-index)个成员后移numNew位,空出numNew个位置,以便存放Collection中的numNew个成员。

 

ArrayList源码解析(二)自动扩容机制与add操作