ArrayList底层实现源码分析(JDK1.8)

1. 类信息

java

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

2. 基本属性

java

//定义序列化ID，主要是为了表示不同的版本的兼容性
private static final long serialVersionUID = 8683452581122892189L;

//默认的数组存储容量(ArrayList底层是数组结构)
private static final int DEFAULT_CAPACITY = 10;

//当指定数组的容量为0时使用这个常量赋值
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认空参构造函数时使用这个常量赋值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//真正存放数据的对象数组，transient标识不被序列化
transient Object[] elementData;

//数组中的真实元素个数，该值小于或等于elementData.length
private int size;

//最大数组长度：0x7fffffff - 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//构造器一：创建具有初始化长度的list
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);
    }
}

//构造器二：默认空参构造器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//构造器三：创建具有初始化值的集合，可传入的集合类型父类是Collection即可，此处是多态的一个应用
public ArrayList(Collection<? extends E> c) {
    //将传入的集合转化为数组
    elementData = c.toArray();
    //判断elementData数组长度
    if ((size = elementData.length) != 0) {
        // elementData转化的数组如果不是Object的子类，就对当前数组进行复制，重新赋值给elementData
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {//如果数组长度为0，复制为EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

3. add(E e) 方法

ArrayList集合创建时，默认初始化长度为0，通过add( )方法在添加元素时对数组长度进行动态赋值。添加第一个元素时，长度为10。当添加的元素个数超过10时，会进行首次扩容，容量为原数组长度的1.5倍。

java

   //此方法是添加元素的方法，另外还有一个重载方法
   public boolean add(E e) {
       //调用ensureCapacityInternal方法，初始化数组长度（默认为10）
       ensureCapacityInternal(size + 1); 
       //为数组复制
       elementData[size++] = e;
       return true;
   }
//初始化数组长度，默认值为10
   private void ensureCapacityInternal(int minCapacity) {
       //判断如果数组长度为0，对长度进行初始化
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           //从默认数组长度（10）和添加的元素个数（添加第一个元素时size=0,minCapacity=size+1）中取出最大值
           //作为数组初始化长度
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       //再次确定数组容量
       ensureExplicitCapacity(minCapacity);
   }
   //再次确定数组容量
   private void ensureExplicitCapacity(int minCapacity) {
       //对数组元素个数进行统计
       modCount++;
       //如果数组长度超过10，就对数组长度进行扩容
       //那第一次扩容举例：minCapacity值为11，DEFAULT_CAPACITY值为10
       if (minCapacity - elementData.length > 0)
           //对数组进行扩容，默认为老数组的1.5倍
           grow(minCapacity);
   }
   //对数组进行扩容，默认为老数组的1.5倍
   private void grow(int minCapacity) {
       //老数组容量：minCapacity
       int oldCapacity = elementData.length;
       //新数组容量：是老数组长度的1.5倍
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       //对新数组容量进行合法检测
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       //MAX_ARRAY_SIZE：0x7fffffff - 8
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           //如果超过最大数组长度，再次进行扩容
           newCapacity = hugeCapacity(minCapacity);
       //对原数组进行复制
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) 
           throw new OutOfMemoryError();
       //三元运算符，如果超过最大数组长度返回Integer最大值：0x7fffffff
       return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
   }

4. add (int idnex,E element)

从源码中可以看出，与add(E e)方法大致一致，主要的差异是增加了一行代码：System.arraycopy(elementData, index, elementData, index + 1, size - index)，从index位置开始以及之后的数据，整体拷贝到index+1开始的位置，然后再把新加入的数据放在index这个位置，而之前的数据不需要移动。

java

//在指定位置添加元素
public void add(int index, E element) {
    //判断index是否在范围内
    rangeCheckForAdd(index);
    //与add(E e)方法一致，对数组长度进行初始化
    ensureCapacityInternal(size + 1);
    //对原数组从index位置进行拷贝，复制到index+1的位置，elementData[index]此时为空
    //System.arraycopy是一个native方法，意味着这个方法是C/C++语言实现的，我们无法再以普通的方式去查看这些方法了
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    //为该下标赋值
    elementData[index] = element;
    size++;
}
//判断index是否在范围内的具体实现
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

arraycopy(elementData, index, elementData, index + 1, size - index)函数中各个参数对应的意义：（原数组，原数组的开始位置，目标数组，目标数组的开始位置，拷贝的个数）

5. remove(int index)

java

   //移除指定index下的元素
   public E remove(int index) {
       //index是否合法检测
       rangeCheck(index);
       modCount++;
       //指定index下的元素
       E oldValue = elementData(index);
       //移除后数组长度
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index, numMoved);
       //为最后一个元素赋值为null
       elementData[--size] = null;
       return oldValue;
   }

   //返回指定index下的元素
E elementData(int index) {
       return (E) elementData[index];
   }
   //根据元素（对象）移除该元素
   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;
   }

   //类似于remove()方法
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index, numMoved);
       elementData[--size] = null; 
   }

remove方法与add正好是一个相反的操作，移除一个元素，会影响到一批数字的位置移动，所以也是比较耗性能。核心代码都是调用了java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法

6. get(int index)

java

//根据指定下标获取元素值
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

7. set(int index, E element)

java

//修改指定index下的元素值
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

8. clear()

java

//清空所有元素
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

9. contains(Object o)

java

//查询是否包含某个元素
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
//具体的实现方法，如果不包含返回-1
public int indexOf(Object o) {
    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;
}

10. 总结

基于数组实现的List在随机访问和遍历的效率比较高，但是往指定位置加入元素或者删除指定位置的元素效率比较低。