ArrayList源码剖析

本文主要探究ArrayList内部构成原理

1.首先确认ArrayList的底层存储结构，找到源码，锁定以下三个可能的字段，基本可以确定底层用的数组存储。

根据字段名和注释，猜测存储在elementDate元素上。

    /**
     * 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

2.我们都知道数初始化的时候要指定大小，并且添加元素超过数组长度时就会报错，而我们在用ArryList时，并没有出现这个问题，先看一下构造方法，一个无参构造方法，初始创建一个大小为0的数组，一个有参构造方法，创建一个指定初始大小的数组。这时候能确定数据存储在elementData属性上。迎来了一个问题就是初始化成空的数组如何存储数据

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3.list添加元素会调用add方法，看一下add方法如何添加元素，解决心中疑惑

看一下ensureCapacityInternal方法，主要玄机都在这里（这3行代码，只有这个方法看不懂）

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e; //添加元素到数组中
        return true;
    }

看字面意思ensureExplicitCapacity为扩容，calculateCapacity为计算大小

    private static final int DEFAULT_CAPACITY = 10;//默认大小为10
    // minCapacity为当前元素数+1
    // elementData为存储数据字段
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 计算数组应该为多大
    // 如果初始为空，则设置大小为10，否则为当前元素数+1
    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) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); //如果计算出来的结果>数组长度，则扩容
    }

主要扩容逻辑都在grow方法里了，大概意思是创建一个1.5倍的数组，并复制原数组数据。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//相当于扩展1.5倍（向下取整）
        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);//创建并复制数据到新的数组
    }

数组复制为调用本地方法进行复制

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

Arrays.copyOf是引用复制还是值复制，做个测试，根据测试结果可知，为引用复制，并不是把元素都复制一份。

	public static void main(String[] args) {
		ArraysTest test = new ArraysTest();
		TestBean bean1=test.new TestBean(1);
		TestBean bean2=test.new TestBean(2);
		TestBean[] original = new TestBean[]{bean1,bean2};
		TestBean[] target = Arrays.copyOf(original, 3);
		System.out.println("old original="+original[0]+","+original[1]);
		System.out.println("old target  ="+target[0]+","+target[1]);
		bean1.a=3;
		System.out.println("new original="+original[0]+","+original[1]);
		System.out.println("new target  ="+target[0]+","+target[1]);
	}
	public class TestBean{
		public int a;
		public TestBean(int a) {
			this.a=a;
		}
		public String toString() {
			return a+"";
		}
	}

执行结果如下：

old original=1,2
old target  =1,2
new original=3,2
new target  =3,2

4.移除元素有两种方法，按索引删除和按元素删除，先看按索引删除

将index+1到size（元素个数）之间的元素复制到以index开始的数组后边

    public E remove(int index) {
        rangeCheck(index);  //index范围检查

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

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

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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; // clear to let GC do its work
    }

删除元素小结：按元素删除元素会先遍历数组，最坏的情况比按索引多了O(n)的时间复杂度，能用索引还是用索引快一点。

5.咱们看add和remove方法时发现有以下代码，这个无论数组是增是减始终++，modCount起到的是一个版本号的作用。

        modCount++;

在用增强for循环查找数据时增加或删除元素会抛出异常

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

我们测试验证一下，用foreach遍历时，会抛出异常

	public static void foreachTest() {
		ArrayList<TestBean> list = new ArrayList<>();
		ArraysTest test = new ArraysTest();
		for(int i=0;i<7;i++) {
			list.add(test.new TestBean(i));
		}
		for (TestBean bean:list) {
			System.out.println("foreach:"+bean);
			if (bean.a==4)
				list.remove(bean);
		}
	}

结果

foreach:0
foreach:1
foreach:2
foreach:3
foreach:4
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.study.anytest.ArraysTest.foreachTest(ArraysTest.java:23)
	at com.study.anytest.ArraysTest.main(ArraysTest.java:9)

用普通for循环遍历就不会出现异常

	public static void foreachTest() {
		ArrayList<TestBean> list = new ArrayList<>();
		ArraysTest test = new ArraysTest();
		for(int i=0;i<7;i++) {
			list.add(test.new TestBean(i));
		}
		for (int i = 0; i < list.size(); i++) {
			System.out.println("for    :"+list.get(i));
			if (list.get(i).a==4)
				list.remove(i);
		}
	}

结果：

for    :0
for    :1
for    :2
for    :3
for    :4
for    :6