ArrayList源码分析

Java-Base

简述

ArrayList 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

1. 快速随机访问：实现RandmoAccess接口，提供随机访问功能，可以通过元素的序号快速获取元素对象;
2. 线程安全：非线程安全；
3. 序列化：实现Serializable这些接口接口，支持序列化。

继承关系如下：

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.ArrayList<E>
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

添加元素--add()

public boolean add(E e) {
    // 确定ArrayList的容量大小
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 添加e到ArrayList中
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    //minCapacity：最小容量 = size + 1（当执行add方法时）
    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;  
    //新容量 = 旧容量 + 旧容量二进制位数右移1位 （例：15 = 10 + 5），即，每次扩容都增加原始容量的二分一，减少执行Arrays.copyOf()
    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);
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    //验证参数是否Object[]数组，是：new Object[]；否：调用Arrays的native方法newArray()
    T[] copy = ((Object)newType == (Object)Object[].class)       
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //最后执行方法System.arraycopy()，调用native方法arraycopy()；参数24：源数组与目标数组的起始复制位，默认为0、0
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));           
    return copy;
}

Collections排序--Collections.sort()

Collections排序采用Timsort排序实现，参考：Timsort排序算法

使用方法：

List list = new ArrayList<Integer>();
...
Collections.sort(list, new Comparator<Integer>() {
    /**
     * 升序：Comparator.compare(右元素, 左元素) >= 0；
     * 降序：Comparator.compare(右元素, 左元素) < 0
     */
    public int compare(Integer o1, Integer o2) {
        if (o2 > o1) {
            return 1;
        } else {
            return -1;
        }
    }
});

Arrays排序--Arrays.sort()

去重

关于线程安全

java.util.ArrayList并非java API的线程安全类型，而java.util.Vector（矢量队列）则可以理解是ArrayList的线程安全版本。但以上两者都不是绝对的线程安全。参考：Vector源码分析