JDK8的ArrayList源码学习笔记

itliusir

发布于 2018-05-21 17:04:18

6520

发布于 2018-05-21 17:04:18

文章被收录于专栏：刘君君

摘要:ArrayList基本上是我们在java编程中用得最多的集合类了，是一个动态的数组，在我们用ArrayList的时候发现其非常方面，功能也很强大，但是其这强大的功能是底层是怎么实现的呢？

正文:

首先，ArrayList的继承和实现了的类和接口：

ArrayList实现的接口

可以看出，ArrayList不仅实现了Cloneable、Serializable接口，还实现了RandomAccess接口、List接口。

RandomAccess是一个标记接口，用于标明实现该接口的List支持快速随机访问，主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。因为这个接口是没有任何实现的，实现了这个接口的类，就表明这个类支持快速访问，就相当于实现了Serializable就等于支持序列化和反序列化，这是个标准。

接下来看ArrayList的构造方法：

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;
   }

   public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {
           // c.toArray might (incorrectly) not return Object[] (see 6260652)
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           // replace with empty array.
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

ArrayList提供了三个构造方法，第一个是由调用者传入指定List的大小来创建elementData数组。第二个是默认的构造方法，默认数组容量是10。第三个是根据传入的一个集合，将集合转化成数组，然后赋给elementData。面试题里经常出现ArrayList list = new ArrayList(20)一共扩容了几次，虽然ArrayList默认容量是10，但是它有一个是指定list大小的构造方法，会在new ArrayList(20)时候自动生成一个20容量的集合，所以是不会发生扩容也即是0次。

成员变量分析

//默认容量
   private static final int DEFAULT_CAPACITY = 10;
   //空数组
   private static final Object[] EMPTY_ELEMENTDATA = {};
//空数组，新增元素时候用
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数组
   transient Object[] elementData; 
//数组大小
   private int size;
//数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

核心方法分析

1. trim to size 压缩空间

public void trimToSize() {
       modCount++;
	//一个精简的三元表达式
       if (size < elementData.length) {
           elementData = (size == 0)
             ? EMPTY_ELEMENTDATA
             : Arrays.copyOf(elementData, size);
       }
   }

2. grow 扩容

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       //新空间分配直接扩大50%
       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);
   }

private static int hugeCapacity(int minCapacity) {
       /**
	 * hugeCapacity的判断小于0则为溢出，由于在jvm内部是以反
	 * 码存储的数据，首位为符号位，当容量扩增后，若溢出，首位  * 则变为1，此时变为负数，则可以快速判断出是否溢出。
	 */
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }

3. fail-fast机制

/**
  * 子类使用这个字段是可选的，若子类希望提供fail-fast(快速失败) iterators或者list iterators 可以在方法里使用该方法.
  */
protected transient int modCount = 0;

这个变量用于快速判断该实例是否有变化，若在进行迭代的时候有变更，那么就抛出一个并发修改异常(ConcurrentModificationException)。 fail-fast是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。

4. add 新增一个元素

指定位置插入：

public void add(int index, E element) {
       //下标检查，是否越界了
       rangeCheckForAdd(index);
       //扩增容量，同时改变modcount
       ensureCapacityInternal(size + 1);
       //index后面的元素后移
       System.arraycopy(elementData, index, elementData, index + 1, size - index);
       //指定位置放置元素
       elementData[index] = element;
       //元素数量大小自增
       size++;
   }

向后插入：

public boolean add(E e) {
       //扩大容量,修改modcount
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //注意
       //数组是从0开始的存元素的，而数组个数是从1开始计数的
       //这个地方是往第size个位置上存元素
       //再将元素个数加1
       elementData[size++] = e;
       return true;
   }

由此可见，向后插入没有使用数组复制，因此效率会高于指定位置插入。

5. remove 移除一个元素

由上面的插入方法可以看到List底层的数组处理使用到了System.arraycopy()方法,下面综合删除和数组复制方法讲下删除原理，下面是删除代码：


	public class TestArrayList {
	    static Object[] elementData = null;
	    public static void main(String[] args) {
	        List<String> list = new ArrayList<String>();
	        list.add("A");
	        list.add("B");
	        list.add("C");
	        list.add("D");
	        list.add("E");
	        int size = list.size();
	        elementData = list.toArray();
	        /**
	         * removeMyList(要删除元素的位置,size);
	         * */
	        removeMyList(2,size);
	        for(Object ele:elementData){
	            System.out.println(ele);
	        }
    }

	    private static void removeMyList(int index,int size) {
	        /**
	         * arraycopy(Object src,int srcPos,
	         *           Object dest,int destPos,
	         *           int length);
	         * src:源数组； srcPos:源数组要复制的起始位置；
	         * dest:目的数组；  destPos:目的数组放置的起始位置；
	         * length:复制的长度。
	         * 
	         * 若自己到自己复制实现过程是先生成一个长度为length的临时数组,
	         * 将elementData数组中srcPos到srcPos+length-1之间的数据拷贝到临时数组中，
	         * 再执行System.arraycopy(临时数组,index+1,elementData,index,size-index-1).
	         * index:要删除元素的位置
	         * list删除元素时候是srcPos=index+1,destPos=index,length=size-index-1
	         * 意思是将要删除的元素和之后元素复制到自己元素和之后的位置将自己覆盖
	         * */
	        System.arraycopy(elementData, index+1, elementData, index, size-index-1);
	        elementData[--size] = null; //相当于往前移了一位将最后一位重复的置null
	    }
}

其删除操作如下图所示：