ArraryList源码解读

先由一道题引发思考：

ArrayList list = new ArrayList(20);中的list扩充几次（）

A 0 B 1 C 2 D 3

答案：A

直接翻看 jdk1.8 源码ArrayList，初始化共有三种方式；

 /**

  * 默认初始化容量

  */

private static final int DEFAULT_CAPACITY = 10;

 /**

  * 共享空数组实例，用于空实例。调用构造函数容量为0时，会赋予数据的数组

  */

private static final Object[] EMPTY_ELEMENTDATA = {};

 /**

  * 共享空数组实例用于默认大小的空实例。使用默认构造函数时，会赋予数据的数组

  */

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

 /**

  * 存储ArrayList元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。在第一次

  * 加入元素时，任何空实例（elementData ==

  * DEFAULTCAPACITY_EMPTY_ELEMENTDATA）会扩充成默认大小

  */

transient Object[] elementData;

 /**

  * ArrayList的大小

  */

private int size;

第一种：有参构造方法，通过指定大小来初始化内部的数组，无需动态扩容。因此前面问题答案是不需要扩容。

    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);

        }

    }

第二种：无参的构造方法，以默认的大小来初始化内部的数组，需动态扩容。

public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

第三种：Collection对象来构造，并将该集合的元素添加到ArrayList。

    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;

        }

    }

无参构造方法的实现：

ArraryList使用 add() 添加元素的过程，调用链 add()->ensureCapacityInternal()->ensureExplicitCapacity()->grow()

    public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

    }

    private void ensureCapacityInternal(int minCapacity) {

        if (elementData == 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);

    }

    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 = Arrays.copyOf(elementData, newCapacity);

    }

    private static int hugeCapacity(int minCapacity) {

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?

            Integer.MAX_VALUE :

            MAX_ARRAY_SIZE;

    }

当第一次添加元素，空实例会被赋予默认容量10，此时并未扩容，直到添加第11个元素，进入grow()方法扩容，新的容量= 旧容量 + 旧容量/2 ，第一次扩容后容量为15，以此类推第二次扩容后容量

为15+15/2 = 22

当使用的是addAll()添加集合时，

    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;

    }

当list 使用addAll() 添加集合时，第一次扩容后容量为15，但是还是小于需要最小容量20，因此将需要的最小容量赋值给新容量，扩容后新容量为20；参考源码，grow() 方法中 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 有趣的是 modCount 为 6 ，因为此时的list只做了6次操作。

Collection对象来构造的实现：

使用集合来创建ArraryList对象，elementData的容量即为集合的大小。此时的modCount 为0；参照源码集合对象构造方法实现，即可明白。

总结：

有参构造方法，通过指定大小来初始化内部的数组，无需扩容，容量即为指定大小；

集合对象的构造方法，容量即为集合大小；

无参的构造方法，扩容后的新容量为旧容量的1.5倍，如果所需最小容量仍大于新容量，则将所需的最小容量赋值给新容量。如果扩容后的新容量超过限制的容量，则用所需的最小容量与限制的容量进行判断，所需的最小容量大于限制的容量则指定为Integer的最大值2^31-1，否则指定为限制容量大小（2^31-1）-8。然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。

本文参考文章：http://www.cnblogs.com/ggmfengyangdi/p/5738491.html

关于ArraryList 面试参考文章：

http://www.importnew.com/9928.html

https://blog.csdn.net/qq_38859786/article/details/80265851

巴特西

ArraryList源码解读

最新文章

热门文章