菜鸟看源码之ArrayList

首先扯点别的：现在刚吃完荔枝，也是很甜，8楼有人在弹钢琴，断断续续的，在修路，机械的声音很嘈杂。桌子上的水杯里放着两朵栀子花，香气弥漫，沁人心脾，生活还是挺美好的。

今天记录一下看ArrayList源码的过程。

先看一下ArrayList的继承结构 ArrayList的源码还是比较简单的。下面是ArrayList中几个成员变量

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //序列化id private static final long serialVersionUID = 8683452581122892189L; //默认的ArrayList的容量 private static final int DEFAULT_CAPACITY = 10; //一个空的Object数组 private static final Object[] EMPTY_ELEMENTDATA = {}; //一个空的Object数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList存放元素的数组 transient Object[] elementData; // non-private to simplify nested class access //ArrayList的size（包含的元素个数） private int size;

ArrayList还有一个继承自AbstrctList的一个成员变量

protected transient int modCount = 0;

modCount 用来指明当前的List结构化修改的次数。结构修改是指会更改List的size的修改，比如List的添加或者删除操作。或以其他方式的，使得正在进行的迭代可能会产生不正确的结果的修改。 在List的迭代过程中，如果modCount 被修改了，迭代器就会抛出一个 ConcurrentModificationException异常。

使用ArrayList的时候通常会使用ArrayList的无参构造函数来实例化一个ArrayList

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

就是一句简单的赋值操作，这时候elementData 就是一个空的Object数组。

实例化ArrayList的时候可以指定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); } }

如果initialCapacity大于0，就新建一个大小为initialCapacity的Object数组，然后elementData 指向这个数组。如果initialCapacity 等于0，就把EMPTY_ELEMENTDATA赋值给elementData ，这时候elementData 是一个空数组。

通过一个集合实例化一个ArrayList

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

如果Collection c的长度不等于0，就把c转化成数组然后拷贝到elementData中，否则就把EMPTY_ELEMENTDATA赋值给elementData ，这时候elementData 是一个空数组。

ArrayList的add(E e)方法，这个应该是最常用的方法了

public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }

添加元素的时候首先要确保添加元素的位置size，（size+1）不大于elementData的长度。若（size+1）大于了elementData的长度，就把elementData长度增加到原来长度的1.5倍。

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }

内部通过调用ensureExplicitCapacity方法实现

private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果超出了elementData的长度，就增加elementData的长度 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //elementData新的长度是elementData原来长度的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 拷贝elementData中的元素，并增长elementData的长度 elementData = Arrays.copyOf(elementData, newCapacity); }

elementData增加后的长度是elementData原来长度的1.5倍。

在确保要添加元素的位置在elementData的范围之内以后，就可以把元素添加到 elementData中同时 size要增加1。

elementData[size++] = e; return true;

add(int index, E element)方法

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //把index后面包括index位置上的元素都向后移动一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

首先检查index的范围在0到size之间

private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

检查是否需要增加elementData的长度，然后把index后面包括index位置上的元素都向后移动一个位置，然后把元素放入index位置上，并把size加一。

elementData[index] = element; size++;

ArrayList 的addAll 方法和add方法差不多

public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

get(int index)方法

rangeCheck(index); return elementData(index);

先检查是否越界，如果没越界，取出index位置上的元素返回

E elementData(int index) { return (E) elementData[index]; }

set(int index, E element)方法

public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }

先保证index没有越界，然后更新index位置上的元素，返回index位置上的旧的元素。

contains(Object o)方法

public boolean contains(Object o) { return indexOf(o) >= 0; }

内部通过indexOf方法实现

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

如果要查找的Object为null，就遍历elementData如果elementData中有元素为null，返回第一个为null的位置。如果Object不为null，就调用Object的equals方法来比较，返回第一个o.equals(elementData[i])的 位置。如果没找到就返回 -1。

remove(int index)方法

public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; //如果删除的元素不是最后一个元素，要把index后面的所有元素向前移动一个位置 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //最后一个元素置为null，size减一。 elementData[--size] = null; return oldValue; }

如果删除的元素不是最后一个元素，要把index后面的所有元素向前移动一个位置，然后最后一个元素置为null，size减1，返回删除的值。

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;

先找到第一个和要删除元素相等的元素的index，然后fastRemove(index)方法删除，删除成功返回true，否则返回false。

private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; //如果删除的不是最后一个元素，要把index后面的元素都向前移动一个位置。 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //size减1,把最后一个元素置为null elementData[--size] = null; }

clear()方法

public void clear() { modCount++; // 把所有的元素置为null for (int i = 0; i < size; i++) elementData[i] = null; //size置为0 size = 0; }

结尾：参考链接 【1】http://blog.csdn.net/fighterandknight/article/details/61240861 【2】http://www.jianshu.com/p/2cd7be850540