ArrayList源码解析

ArrayList是一个底层基于数组的List接口实现,类似于Java的数据模型Array,但跟Array不一样的是它对于存储数量理论上是没有上限的(长度最大值是Integer.MAX_VALUE - 8),线程不安全,跟其相应的线程安全实现类是Vector,两者源码几乎一样,只不过在数据操作的时候Vector使用了synchronized机制来实现线程安全.
在阅读ArrayLIst的源码的时候,将它当成一个Array去理解解读的话会事半功倍,因为ArrayList相当于是用java代码实现的Array

番外篇手写ArrayList https://github.com/wkx359518081/collection

源码版本 openjdk 1.8.0_212

字段

   /**
     * 默认初始化底层存储数组大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * ArrayList 延迟初始化的底层数组,构造方法不指定底层数组初始化大小或初始化大小为0时,先将底层数组赋值等于它
     * 后面需要写操作的时候再进行初始化底层数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 用于存储数据的底层数组,绝大部分读写操作都与之相关
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 存储数据数量, 相当于array.length
     */
    private int size;
    
    /**
    * ArrayList 写操作次数,主要Java fastfail机制相关
    *
    */
    protected transient int modCount = 0;

读写操作

  /**
     * 获取ArrayList下某个下标的值
     * 相当于 array[index]
     */
    public E get(int index) {
        // 核对是否数组越界
        rangeCheck(index);

        return elementData(index);
    }

   /**
   *   设置ArrayList下某个下标的值为element
   *   相当于array[index] = element
   */
    public E set(int index, E element) {
       // 核对index是否大于ArrayList的size,如果大于会抛出一个IndexOutOfBoundsException
       // 如果array[array.length] = element 也会抛出IndexOutOfBoundsException,前面也说了ArrayList相当于Java代码实现的Array
        rangeCheck(index);
        // 将新的值放在该下标下并返回老的值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

   /**
   *  往数组的末梢添加一个值,
   *  在将ArrayList.size当成array.length的话相当于array[array.length] = e
   *  但跟array不一样的是ArrayList会自动扩展它的底层数组ArrayList.elementData的长度大小,
   *  避免ArrayList.elementData[size + 1] = e的时候抛出IndexOutOfBoundsException
   */
    public boolean add(E e) {
        // 检查ArrayList.elementData的大小是否大于size+1,如果小于需要进行对ArrayList.elementData长度扩展,具体实现看下面的动态扩展环节
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
   
   /**
   *  跟前面的set(int index, E element)方法差不多,都会改变ArrayList下某个下标的值,
   *  不一样的是该方法在修改index下标的值之前会移动将index到size-1下标的值进行右移
   */
   public void add(int index, E element) {
        // 核对index是否大于ArrayList.的size,如果大于抛出IndexOutOfBoundsException
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将index到size-1下标的值进行右移
        /**   
         *     System.arraycopy(arr, 2, arr, 3, arr.length - 1) 之前
         *      | A | B | C | D | E | F | G | H |
         *     System.arraycopy(arr, 2, arr, 3, arr.length - 1) 之后
         *       | A | B | null | C | D | E | F | G | H |
         *     如果在面试的时候,面试官问你移动数组元素最快的方法是什么,答案就是System.arraycopy方法因为它的底层是用调用汇编的
         */
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

   /**
     * 将ArrayLIst实例内存储的所有数据清空
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
           // 方便jvm垃圾回收,去除掉没用数据的引用,参考jvm垃圾回收的可达性算法
            elementData[i] = null;

        size = 0;
    }

动态扩展

/**
* 计算扩展的时候容量ArrayList.elementData数组的最小长度,
* 如果ArrayList.elementData没有初始化的话(值为{}),长度就是ArrayList.DEFAULT_CAPACITY
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {  
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

/**
* 确保ArrayLIst.elementData的数组长度是否大于等于minCapacity如果不等于进行数组长度扩展
*/
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

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

        // 判断是否需要数组长度扩展
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
/**
* 实际扩展ArrayLIst.elementDatad的代码实现,每一次扩展都是老的长度的1.5倍
*/
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 计算新的数组长度,每一次扩展都是老的长度的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 判断计算出来的新的长度是否大于最大的长度,
       //  如果大于的话但没有溢出Integer的存储范围的话等于Integer.MAX_VALUE
      // 溢出抛出异常,表示达到了存储上限
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 进行数组扩展数据迁移
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList源码解析

番外篇 手写ArrayList https://github.com/wkx359518081/collection

源码版本 openjdk 1.8.0_212

字段

读写操作

动态扩展

番外篇手写ArrayList https://github.com/wkx359518081/collection