java集合之ArrayList源码解析

ArrayList 继承结构

ArrayLisy.png

ArrayList的本质是一个数组

这是ArrayList的属性，包括默认长度，空数组，elementData（存储数据的数组）和size（集合中元素个数）

   private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

ArrayList的构造函数

无参够着函数，就是初始化为一个默认空数组，不分配内存空间，实现懒加载，需要的时候再分配内存

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

有参构造函数，出入初始化大小，检查初始参数
大于0：分配对应内存空间
等于0：赋值给默认空数组
小于0：抛出初始化参数异常

 public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

重要方法分析：add(E e) , get(int index), set(int index , T data), remove(int index)

add(E e): 添加一个数据
ensureCapacityInternal(size + 1): 确认容量
minCapacity -> size+1
calculateCapacity(elementData, minCapacity)：计算容量，如果插入后size大于当前数组的容量则扩容，如果size小于，直接返回，执行赋值操作，同时size+1
grow(minCapacity)：扩容方法

 private void grow(int minCapacity) {
        // 获取原来数组的容量
        int oldCapacity = elementData.length;
       // 扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
       // 主要用于第一次插入时扩容，默认为10，所以第一次不是扩1.5倍，而是创建长度为10的数组
        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);
    }

get(int index)

public E get(int index) {
        // 数组下标越界检查
        rangeCheck(index);
        return elementData(index);
    }

set(int index, T data)

public E set(int index, E element) {
        // 数组下标越界检查
        rangeCheck(index);
        E oldValue = elementData(index);
        // 赋值
        elementData[index] = element;
       // 返回旧值
        return oldValue;
    }

remove(int index)

public E remove(int index) {
        // 数组下标越界检查
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        // 计算需要移动的数量，如果是最末尾贼不要移动
        int numMoved = size - index - 1;
       // 如果在非末尾
        if (numMoved > 0)
          //  将当前索引所在的后面的所有值，向前移动一位（拷贝index+1到最后的所有数据到index开始的位置）
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一位设置为空，同时size-1
        elementData[--size] = null; // clear to let GC do its work
       // 返回旧值
        return oldValue;
    }

源码中modCount++的作用

用于在多线程环境下，保证数据安全的FailFast机制。主要是在集合迭代过程中，防止集合变化导致错误。原理是集合开始迭代是会把modCount赋值给迭代器一个属性，迭代过程中不断检查值当前modCount与原始值是否相等，不等则抛出ConcurrentModificationException异常

总结

ArrayList的实现是数组，底层结构是连续内存空间的线性表，在随机读写上性能好，通过计算获取下标位置
在随机插入和删除时，需要移动插入位置后面的所有元素，性能较差
在插入时可能需要动态扩容，第一次扩容到10，后面每次扩容1.5倍