ArrayList源码解析

一航jason

2019-06-28

1.说明

ArrayList是对java中数组的扩展，其底层还是使用数据实现，支持自动扩容，不是线程安全的类。其继承AbstractList，实现了List, RandomAccess, Cloneable,Serializable各个接口，其中RandomAccess为支持随机读写的标记接口，在后续Collections类的讲解中会用到。

2.优缺点

ArrayList是一个支持自动扩容的线性表，所以其与普通线性表的特点一样，如下：

顺序存储，所以按照下标读取元素的时间复杂度为O(1)
在删除元素时其后面的所有元素都得前移，新增元素时后面的所有元素都得后移
在存储时就需要开辟一块固定的存储空间

3.重要变量

//默认的容量，当构造函数没有传入此参数时，会在加入第一个元素时将数组扩容为此值
private static final int DEFAULT_CAPACITY = 10;
    
//当数组中元素为空时，会将数组初始化为此数组，代表空数组，这个空数组是在传入
初始容量并且初始容量为0的情况下令数组等于这个
private static final Object[] EMPTY_ELEMENTDATA = {};

//与上一个变量的区别在于其是在于这个空数组是在使用无参构造函数时创建
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//这个数组用于ArrayList存储元素,ArrayList的容量就是数组的长度。加上transient主要是为了
不能直接序列化，而是必须使用自带的writeObject和readObject方法，主要是为了节省空间。不私有
化主要是为了以后扩展，防止以后嵌套等操作
transient Object[] elementData; // non-private to simplify nested class access

//ArrayList的实际大小，即元素所占个数
private int size;

4.构造方法

//传入初始参数的构造方法
public ArrayList(int initialCapacity) {
        //如果初始容量大于0，那么直接按照初始容量初始化数组，
          如果初始容量等于0，等于EMPTY_ELEMENTDATA，上文
          的常量，不过不会在添加第一个元素的时候令容量等于DEFAULT_CAPACITY
          如果初始容量小于0，直接抛出异常
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}

//无参构造函数，直接令存储数组等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
  在添加第一个元素的时候令容量等于DEFAULT_CAPACITY
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//通过一个集合类来构造一个ArrayList
public ArrayList(Collection<? extends E> c) {
    //获取集合类的底层数组
    elementData = c.toArray();
    //判断集合类的元素个数是否为0
    if ((size = elementData.length) != 0) {
        //ps:c.toArray()可能返回的数组类型不为Object[]类型，
          通过ArrayList的toArray一定是Object[]类型，但是Arrays.asList（）
          里转化成其内部自身的ArrayList，其内部的ArrayList的toArray方法会
          返回E[]这种泛型的对象，导致出现问题
        //如果集合类的toArray方法返回的不为Object[]类型，使用Arrays.copyOf
          将其迁移到一个新的Object[]数组中
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果元素个数为0，那么直接将元素数组置为EMPTY_ELEMENTDATA空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

5.基本方法

//增加一个新元素
public void add(int index, E element) {
        //检验index是否超出范围
        rangeCheckForAdd(index);
        //检验当前容量是否足够，如果不够，进行扩容
        ensureCapacityInternal(size + 1);  
        //将index之后的元素都后移一个
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //将新增的元素填入
        elementData[index] = element;
        //添加数组元素个数
        size++;
}

//检验index是否超出范围
private void rangeCheckForAdd(int index) {
        //判断index是否大于当前长度或者小于0，如果不在数组范围，
          那么直接跑出数组超出范围异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//确保内部元素的容量足够
private void ensureCapacityInternal(int minCapacity) {
        //对数组进行扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

//用于判断数组是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此处用==号进行比较，是因为
  只用于判断是构造函数时未传初始容量，延迟到第一次添加新元素时进行默认初始容量的设置，然后
  返回比较默认容量与需要的最小容量的最大值，这里返回最大值是因为有可能一次添加多个元素，  AddAll也会复用这个函数
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

//对数组进行扩容
private void ensureExplicitCapacity(int minCapacity) {
        //修改次数+1
        modCount++;

        // 如果需要的容量数大于当前容量，进行扩容，否则，不在继续，
          并且防止溢出，如果溢出，不进行下列操作，直接会在后续数组
          赋值中直接抛出越界异常，因为这个时候代表size已经很大了
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
 //对数组进行扩容
 private void grow(int minCapacity) {

        int oldCapacity = elementData.length;
        //令新的容量等于原容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新的容量小于当前需要的的最小容量，那么新容量等于当前需要的的最小容量
          防止newCapacity溢出或者增加1.5倍还是小于minCapacity的情况
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新的容量比MAX_ARRAY_SIZE还大，MAX_ARRAY_SIZE为
          Integer.MAX_VALUE - 8，那么对当前需要的最小容量进行扩容
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //为数组开辟更大的空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //根据需要的容量进行扩容
    private static int hugeCapacity(int minCapacity) {
        //如果minCapacity此时小于0，代表已经溢出，其实此时已经不大可能，因为在
          ensureExplicitCapacity已经有一层判断了
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        //如果minCapacity小于MAX_ARRAY_SIZE，那么直接等于MAX_ARRAY_SIZE，
          否则直接等于Integer的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

下面，来看看Api中的add，addAll等方法，其他类似方法不在赘述，get和set也不赘述，比较简单

//与add方法不同的是，他是在这个索引处新增了一个集合的元素
public boolean addAll(int index, Collection<? extends E> c) {
        //检验index是否合法
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //size + numNew代表需要的最小容量
        ensureCapacityInternal(size + numNew);  

        //numMoved代表需要向后移动的元素个数
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //将集合c中的所有元素移动到elementData的index之后
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        //如果集合c的长度不为0，返回true，否则返回false
        return numNew != 0;
    }
    //将elementData中的空元素去除，节省空间(去除不了中间的等于null这样类型的元素)
    public void trimToSize() {
        modCount++;
        //如果当前元素个数小于elementData的容量，当size == 0时
          将elementData赋值为EMPTY_ELEMENTDATA，否则，将elementData
          容量减小到size大小
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
    
    //根据对应元素计算出元素位置（遍历为从前到后）
    public int indexOf(Object o) {
        //如果传入元素为null，找到等于null的元素，否则，使用
          equals遍历
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    
    //移除当前元素
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        //获取当前index在数组对应元素
        E oldValue = elementData(index);

        //获取需要移动的元素个数，即index之后的元素都需要向前移动，不包括index
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后一个元素置为空，其中的元素有gc自动回收
        elementData[--size] = null; 
        //返回被删除的元素值
        return oldValue;
    }
    
    //对对应元素进行移除，先遍历查找，在进行移除，值得一提的是，
      此处的remove方法，使用的是fastRemove，与remove方法具体
      少了rangeCheck方法和获取oldValue，从而减少时间复杂度
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

arraylist 源码 object 数组