Java集合框架之ArrayList源码分析及如何扩展容量

1.介绍

ArrayList底层维护的是一个动态数组,每个ArrayList实例都有一个容量,并随着往ArrayList里面添加元素,其容量也自动增长。
下面通过ArrayList源码分析其原理。

以下代码取自JDK1.8

2.代码分析

注:请阅读代码注释结合代码来看

1.主要变量

transient Object[] elementData; // 真正存储数据的数组,整个ArrayList的元素数据都存在这个Object[]中.

    private int size;               // 实际ArrayList存储数据的元素大小(非容量).
Java集合框架之ArrayList源码分析及如何扩展容量


2.构造函数

//指定ArrayList的大小
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 指定数组大小(上面说了ArrayList是以elementData 存储元素数据的)
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 指定一个空数组,没有任何大小(相当于只是声明了数组变量)
            // private static final Object[] EMPTY_ELEMENTDATA = {};
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    public ArrayList() {
        // 指定一个空数组,没有任何大小(相当于只是声明了数组变量)
        // private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //传入一个集合
    public ArrayList(Collection<? extends E> c) {
        // 返回包含此 collection 中所有元素的数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                // 复制指定的数组,返回包含相同元素和长度的Object类型的数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 指定一个空数组,没有任何大小(相当于只是声明了数组变量)
            // private static final Object[] EMPTY_ELEMENTDATA = {};
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
Java集合框架之ArrayList源码分析及如何扩展容量

1) ArrayList()
    构造一个没有指定大小的空列表(相当于只是声明了数组变量)。

2) ArrayList(int initialCapacity)
    initialCapacity不为 0 时构造一个具有指定初始容量的空列表。
    如果initialCapacity指定为 0 ,那么还是同ArrayList()一样。

3) ArrayList(Collection c)
    (注:因此处代码放入会影响显示,只需知道是最后一个传入Collection的方法即可,见上面的代码块最后一个方法)
    构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

3.add方法

public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        //添加元素数据,为所存在的最大元素+1位置增加元素
        elementData[size++] = e;
        return true;
    }
Java集合框架之ArrayList源码分析及如何扩展容量

解说:上面代码块 add 方法调用ensureCapacityInternal(size + 1);    如下代码:

private void ensureCapacityInternal(int minCapacity) {
        // 如果数组是为空数组,那么设置当前数组默认容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //默认容量为:private static final int DEFAULT_CAPACITY = 10;
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
Java集合框架之ArrayList源码分析及如何扩展容量

解说:上面代码块 ensureCapacityInternal 方法拿到了默认值为10的默认数组空间
           然后调用ensureExplicitCapacity(minCapacity);    如下代码:

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //假如是刚刚创建List<String> list1 = new ArrayList<String>();
        // 当前容量10 - 所存元素大小0
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
Java集合框架之ArrayList源码分析及如何扩展容量

解说:上面代码块 ensureCapacityInternal 方法调用grow(minCapacity);    如下代码:

private void grow(int minCapacity) {
        // 老容量
        int oldCapacity = elementData.length;
        // 新容量,算法为老+(老/2),例如:10+(10/2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 设置为新容量,并重新赋值
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
Java集合框架之ArrayList源码分析及如何扩展容量

解说:上面代码块 grow方法为容量扩展方法

//当minCapacity > MAX_ARRAY_SIZE 取Integer最大值,否则取MAX_ARRAY_SIZE,也就是Integer最大值-8
    //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

总结:

1)
    创建ArrayList时是没有分配空间的,只是一个空数组,相当于一个声明的变量。
2)
    1.调用add方法时,如果没有指定初始容量,那么会给ArrayList初始容量10。
    2.在每次调用add方法都会判断是否需要扩充容量,
       用法是:用当前元素最大数量+1(size+1)> 容量(elementData.length)
       上述说明:如果当前元素已满,容量不足,那么调用扩充容量的方法grow(int minCapacity)


容量规则是:当前容量的1.5倍,直到Integer最大值-8,如果还需扩展则最大为Integer最大值


注:如有不合理之处请指点,莫让我误人子弟呀。

相关推荐