ArrayList集合扩容

ArrayList集合扩容 ArrayList

List集合代表一个元素有序、可重复的集合，集合中的每个元素都有其对应的索引顺序，可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引，比如第一次添加的元素索引为0，第二次添加的元素索引为1…。

List作为Collection接口的子接口，可以调用Collection接口里的全部方法。由于List集合是有序集合，因此List集合增加了一些根据索引来 *** 作集合的方法。

ArrayList实例化

ArrayList提供了3个构造器，一个无参构造器，两个有参构造器

1.指定列表容量大小的构造器

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];   //如果传进来的容量大于0，elementData数组就会初始化一个容量为initialCapacity的Obj数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;       //如果传进来的参数等于0，就会让elementData数组为空共享数组
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);                   //如果传入的参数小于零，就会抛出异常
    }
}

2.无参构造一个初始容量为10的空列表

  
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3.将Collection的实现类作为参数实例化ArrayList对象，该构造器会将参数对象中存储的元素拷贝到实例化的ArrayList对象中。

   
                        //参数必须是Collection接口的实现类或子接口，并且类型参数必须是E或者其子类
    public ArrayList(Collection c) {
        elementData = c.toArray();  //把传入进来的参数数组化，然后赋给elementData
        if ((size = elementData.length) != 0) {     //如果elementData不为空
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class) 
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {           //如果elementData的类型和参数一致，就直接赋给elementData，如果不一致就调用Arrays.copyOf()复制给elementData数组
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList扩容

当向列表中添加元素时可能会发生扩容，先来分析一下添加元素的 *** 作
ensureCapacityInternal()；函数用来判断是否需要扩容

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;//将元素e添加到数组的索引处，然后size++
    return true;//添加成功返回true
}

ensureCapacityInternal(size + 1)：

1.minCapacity=size+1，表示最小容量为当前元素个数+1
2.这里的if判断的是空参数构造器实例化的列表，上面提到的第二类空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA在添加元素时的默认容量是10。
3.**minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)**比较初始默认容量和minCapacity=size+1(也就是当前列表容量和初始默认大小比较)，把大的赋值给minCapacity。
4.获得新的minCapacity后，开始执行ensureExplicitCapacity(minCapacity);函数

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

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

    ensureExplicitCapacity(minCapacity);
}

ensureExplicitCapacity(int minCapacity)：

注意这里的大小关系（假如是无参构造器实例化的ArrayList）
①假如还没达到扩容的需求(默认初始容量>size+1),那么最后的minCapacity为较大值，即minCapacity=默认初始容量
那么minCapacity-elementData.length是等于0的，因为elementData这个数组最先是个长度为0的空数组，在添加第一个元素的时候已经从空数组扩展的为长度为DEFAULT_CAPACITY(默认初始容量)的数组了

②假如达到了扩容需求(size+1>=默认初始容量)，那么最后的minCapacity为较大值，即minCapacity=size+1
那么minCapcity-elementData.length是大于0的

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

    // overflow-conscious code
    //判断是否需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow(int minCapacity)函数

  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//记录原来的数组容量大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组扩容成原来的1.5倍
        if (newCapacity - minCapacity < 0)//如果扩容后还是比minCapacity小
            newCapacity = minCapacity;//就让minCapcity作为新的数组大小
        if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新数组的大小超过了定义的最大值
            newCapacity = hugeCapacity(minCapacity);//执行hugeCapacity函数
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//将原来的数组内容copy到新扩容的数组里面
    }