源码解读-ArrayList

ArrayList都很熟悉了

• List的接口大小可调整的实现类
• 除了实现List接口之外，此类还提供了一些方法来操作内部用于存储列表的数组的大小。
• 线程不安全
• 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们可以通过元素的序号快速获取元素对象；这就是快速随机访问。

---

1. ArrayList 内部的属性

//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//用户空实例的共享的空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小的空实例的共享空数组实例。如果使用默认构造函数创建，则默认对象就是它
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList元素的数组缓冲区。
transient Object[] elementData;
//当前数组长度
private int size;
//数组最大长度。
//为什么数组最大长度是int的最大值-8：有些虚拟机在数组中保留了一些头信息。尝试分配更大的数组可能会导致OutOfMemoryError内存溢出。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//此列表结构被修改的次数
protected transient int modCount = 0;

2.构造函数

• ArrayList(Collection<? extends E> c) 构造一个包含指定集合元素的列表。
• ArrayList() ：当没给出初始容量大小时，初始对象默认为DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
• ArrayList(int initialCapacity) 构造具有指定初始容量的空列表
  ArrayList() 就不用看了，直接看看另外两个构造函数
  ArrayList(int initialCapacity)

public ArrayList(int initialCapacity) {
   //如果指定容量大于0，直接创建
   if (initialCapacity > 0) {
       this.elementData = new Object[initialCapacity];
   //等于0，复制默认空数组
   } else if (initialCapacity == 0) {
       this.elementData = EMPTY_ELEMENTDATA; 
   //小于0，抛异常
   } else {
       throw new IllegalArgumentException("IllegalCapacity:"
                                                                      +initialCapacity);    
   }
}

ArrayList(Collection<? extends E> c)

public ArrayList(Collection<? extends E> c) {
    //将原来的c中保存的数据，转换成数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            //数组长度不为0，进行数组拷贝
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
 }

3.添加方法

• add(E e)：将指定的元素追加到此列表的末尾。
• add(int index, E element)：将指定元素插入此列表中的指定位置。
• addAll(Collection<? extends E> c)：按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。
• addAll(int index, Collection<? extends E> c)：从指定位置开始，将指定集合中的所有元素插入此列表。

先来看看add(E e)源码
add(E e)

public boolean add(E e) {
    //确认当前数组长度加1后，容量是否还够用，在这个方法中，会干几件事情：
    //1.判断当前数组对象是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果是，设置该数组容量为初始容量和size+1中的较大值。如果不是，直接去size+1.
    //2.判断size+1是否比数组当前容量大，如果是，进行扩容
    //3.modCount+1
    ensureCapacityInternal(size + 1);// Increments modCount!!
    //插入元素
    elementData[size++] = e;
    return true;
}

上面说到扩容，我们在这里先看看扩容的方法
grow(int minCapacity)

private void grow(int minCapacity) {
    // overflow-conscious code    
    int oldCapacity = elementData.length;
    //新容量为老容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //最终新容量取 刚才扩容后的容量与minCapacity（上层传下来的size+1）的较大值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
     //如果最终新容量大于数组允许的最大值（int最大值-8）,取int最大值？？？
    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);
    }

add(int index, E element)

public void add(int index, E element) {
    //检查index是否有效
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);// Increments modCount!! 
    //将数组index后的元素向后依次挪一个位置
    System.arraycopy(elementData, index,elementData, index + 1,
    size - index);
    //将元素插入index位置
    elementData[index] = element;    
    size++;
}

addAll(Collection<? extends E> c)

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

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

4.删除方法

• remove(int index)：删除此列表中指定位置的元素。idnex>size抛数组下标越界异常。
• remove(Object o) ：遍历数组，从此列表中删除指定元素的第一个匹配项，如果存在，则删除。如果列表中不包含该元素，则保持不变。如果包含该元素，返回true。
• removeRange(int fromIndex, int toIndex)，删除formIndex和toIndex区间内（包含fromIndex，不包含toIndex）的元素
• clear()：删除数组中所有元素
• removeAll(Collection<?> c)：删除集合中所有元素

remove(int index)

public E remove(int index) {
    //检查index是否有效，越界抛出异常
    rangeCheck(index);
    //数组操作计数+1
    modCount++;
    //取出目标元素
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    //判断需要删除的是不是队尾元素
    if (numMoved > 0)
        //如果不是，将index后的所以元素前移一个单位
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
     //如果是，直接置最后一个元素为null
     elementData[--size] = null; // clear to let GC do its work   
    //返回index的值
    return oldValue;
 }

remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            //如果o==null，循环判断是否有元素等于null，有则删除第一个等于null的元素，返回ture
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            } 
    } else { 
        //如果o!=null，循环判断是否有元素等于目标元素，有则删除第一个相等的，返回true
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; 
            } 
    } 
    return false;
}

前面这个源码中，我们看到，删除元素调用了fastRemove(int index)，接着我们看看这个方法的源码。关于这个操作计数modCount的作用，看完我前面写的这篇文章应该就能明白
fastRemove(int index)

private void fastRemove(int index) {
    //操作计数+1
    modCount++;
    int numMoved = size - index - 1;
    //判断删除的是不是最后一个元素，如果是，直接删，否走index后的元素向前移一个单位
    if (numMoved > 0) 
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

removeRange(int fromIndex, int toIndex)

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex; 
    //将toIndex及之后的元素前移
    System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved); 
    // clear to let GC do its work 
    int newSize = size - (toIndex-fromIndex);
    //删除newSize后的元素
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;  
    }   
    size = newSize;
}

clear()

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++) 
        //将所有元素置为null
        elementData[i] = null;
    size = 0;
}

removeAll(Collection<?> c)

public boolean removeAll(Collection<?> c) {
    //判断是否为null，为null抛出空指针
    Objects.requireNonNull(c); 
    return batchRemove(c, false);
}

removeAll主要调用了batchRemove来进行批量删除操作，我们就来看下这哥批量删除操作的源码

private boolean batchRemove(Collection<?> c, boolean complement) { 
    final Object[] elementData = this.elementData;
    int r = 0, w = 0; 
    boolean modified = false; 
    try { 
        for (; r < size; r++)
            //判断当前数组中是否包含集合c中元素，根据complement的值，删除元素或保留元素
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r]; 
    } finally { 
        // Preserve behavioral compatibility with AbstractCollection, 
        // even if c.contains() throws.  
        if (r != size) { 
            System.arraycopy(elementData, r,  elementData, w,size - r); 
            w += size - r;  
        }  
        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;
}