《JDK源码阅读三》--ArrayList类

ArraList是基于动态数组实现的一种线性列表，这种基于动态数组的好处就是有索引,查询比较快，时间复杂度为O(1)；

但是对数据修改比较慢，因为需要移动数据，移动数据的过程需要消耗大量的时间。

1.默认初始容量是10

当添加第一个元素时,如果 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;那么默认初始大小设置为10

2.扩容大小为 1.5倍

关键代码: int newCapacity = oldCapacity + (oldCapacity >> 1);

在ArrayList中,有这么一段代码

/**
 * 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; // 要分配的最大数组大小

也就是说,ArrayList的最大容量只能是整数的最大长度减8,为什么要减8呢? 其实,代码中已经解释的很清楚了

简单点来说,就是因为ArrayList是一个数组对象,他需要一些空间来储存自己的一些类信息,,而且这些信息不能超过8个字节.

　　private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;　　
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
        if (newCapacity - minCapacity < 0) // 当扩容后,如果超过int的最大值那么newCapacity会是一个负数
            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;
    }

在hugeCapacity方法中当minCapacity大于MAX_ARRAY_SIZE时,会返回Integer.MAX_VALUE,不要多想,不是说最大容量可以是达到Integer.Max_VALUE,
而是会发生异常:请求的数组大小超过VM限制

3.  addAll(int index, Collection<? extends E> c)  在某位置把一个数组中的所有元素添加到源数组中

　　public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index); // 下标越界检查
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 扩容

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

这个方法的原理其实就是把目标数组指定下标处到目标数组的末尾之间的元素向后移动，然后把源数组覆盖到目标数组中

在该方法中进行判断，if (numMoved > 0)就是说，如果要插入的位置不在尾端，那么会将数组右移，然后再进行插入，否则，直接插入到末尾

 4. private boolean batchRemove(Collection<?> c, boolean complement)  

/**
 * 从此列表中删除指定集合中包含的所有元素
 */
public boolean removeAll(Collection<?> c) {
   Objects.requireNonNull(c);
return batchRemove(c, false); // 重点在这个方法
}

private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0; // r:遍历次数  w:保留的元素数量
        boolean modified = false; // 是否修改
        try {
　　　　　　　// 循环遍历整个数组,当执行删除操作时(complement==false),将数组中不包含的元素依次放入数组前段中,并且w+1
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {// 如果r != size说明 c.contains()时,抛出了异常,这个时候要保持与AbstractCollection的行为兼容性
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
　　　　　　　// 如果w != size说明数组进行了修改,即使try块抛出异常,也能正确处理异常抛出前的操作,因为w始终为要保存的前段部分,数组也不会因此乱序
　　　　　　　// 如果w == size说明数组未进行更改.
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w; // 修改次数
                size = w; 
                modified = true;
            }
        }
        return modified;
    }