ArrayList源码分析（JDK1.8）

不积跬步，无以至千里；不积小流，无以成江海。从基础做起，一点点积累，加油！

来，首先看一下Java集合类的父子关系（图片转自：http://biancheng.dnbcw.info/1000wen/359774.html）：

ArrayList的定义

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

• 从ArrayList<\E>可以看出它是支持泛型的，它继承自AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable接口。

Collection接口的方法：

List：
定义

public interface List<E> extends Collection<E>

List接口方法：

AbstractList提供了List接口的默认实现（个别方法为抽象方法(get方法)）。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

//ArrayList中使用的modCount就是AbstractList中声明的
protected transient int modCount = 0;

AbstractList中对于List集合的判断equals（）方法

public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
        }
return !(e1.hasNext() || e2.hasNext());
    }

这个方法我觉得写得特别好，放在这里留着。。。

• AbstractList继承了AbstractCollection类，实现了List集合的除了get方法之外的所有方法：
  
• RandomAccess是一个标记接口，接口内没有定义任何内容。
• 实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝。
• 通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。

ArrayList的数据域

    transient Object[] elementData; // non-private to simplify nested class access
/**
 * The size of the ArrayList (the number of elements it contains).
 */
private int size;

transient 关键字

• Java的Serializable提供了一种序列化对象实例的机制。当序列化对象时，可能有一个特殊的对象数据成员，我们不想用Serializable机制来保存它。为了在一个特定对象的一个域上关闭Serializable，可以在这个域前加上关键字transient。
• transient是Java语言的关键字，用来表示一个域不是该对象序列化的一部分。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。

看个列子：

public class Person implements Serializable{

private static final long serialVersionUID = -3319659493471806232L;
private String name;
private transient String pass;

public Person(String name, String pass) {
this.name = name;
this.pass = pass;
    }

@Override
public String toString() {
return "Person [name=" + name + ", pass=" + pass + "]";
    }
}

public class TestTransient {
public static void main(String[] args) {
        Person person = new Person("Tome", "1234");
        System.out.println(person);
try {
// 序列化，被设置为transient的属性没有被序列化
            ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
"person.out"));
            o.writeObject(person);
            o.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
try {
// 重新读取内容
            ObjectInputStream in = new ObjectInputStream(new FileInputStream(
"person.out"));
            Person readPerson = (Person) in.readObject();
// 读取后psw的内容为null
            System.out.println(readPerson.toString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
/**运行结果
*Person [name=Tome, pass=1234]
*Person [name=Tome, pass=null]
*/

被标记为transient的属性在对象被序列化的时候不会被保存。

构造方法分析

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};

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

public MyArrayList(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(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;
    }
}

三个构造方法：

• 无参构造方法
  
  • 使用无参构造方法创建的是一个length为0的内部数组，当第一次插入数据时，会对其扩容，扩容为默认的大小10
• 带有初始容量的构造方法
  
  • 创建一个默认容量的数组
• 带有初始集合的构造方法

add(E e)方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 检查是否需要扩容
    elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
//如果创建ArrayList时用的是无参构造器，则第一次插入时会进行一次扩容并且扩到默认数组大小10
//然而如果是使用带有容量参数的构造器且initialCapacity=0时，则不会进行这一步，直接扩展数组容量为minCapacity
//这就导致一个结果，扩容之后带参数的构造器的数组length为1，而默认的为10
//所以，带容量参数的初始化时注意自己需要的大小
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}

容量的拓展将导致数组元素的复制，多次拓展容量将执行多次整个数组内容的复制。若提前能大致判断list的长度，调用ensureCapacity调整容量，将有效的提高运行速度。

可以理解提前分配好空间可以提高运行速度，但是测试发现提高的并不是很大，而且若list原本数据量就不会很大效果将更不明显。

add(int index, E element)

    public void add(int index, E element) {
        rangeCheckForAdd(index);//检查index是否越界

        ensureCapacityInternal(size + 1);  // 确保容量
        System.arraycopy(elementData, index, elementData, index + 1,//将index以后的元素后移一个
                         size - index);
        elementData[index] = element;
        size++;
    }
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)//元素可以添加在最后尾端
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//本地的C/C++库方法，直接操纵内存，速度更快
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
int length);

indexOf(Object o)

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

remove(int index)

public E remove(int index) {
    rangeCheck(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; // 将对象的引用置为null，让垃圾回收器可以回收

return oldValue;
}
//删除等其他操作和插入不同，插入可以将元素插在最后面，而删除等操作是在原有的元素上做修改，所以范围检查不一样
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

clear()

public void clear() {
    modCount++;

// 清空让垃圾回收器清理
for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clone()

返回此 ArrayList 实例的浅表副本。（不复制这些元素本身。）

 public Object clone() {
try {
 ArrayList<?> v = (ArrayList<?>) super.clone();
 v.elementData = Arrays.copyOf(elementData, size);
 v.modCount = 0;
return v;
 } catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
 }
 }

调用父类的clone方法返回一个对象的副本，将返回对象的elementData数组的内容赋值为原对象elementData数组的内容，将副本的modCount设置为0。

removeRange(int fromIndex, int toIndex)

    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

执行过程是将elementData从toIndex位置开始的元素向前移动到fromIndex，然后将toIndex位置之后的元素全部置空顺便修改size。

        ArrayList<Person> arrayList = new ArrayList<Person>();
        arrayList.add(new Person(2));
        arrayList.add(new Person(3));
        arrayList.add(new Person(4));
        arrayList.add(new Person(5));
        arrayList.add(new Person(6));
        arrayList.subList(2, 4).clear();

上面这段代码的运行结果与removeRange（2, 4）一样，原因是：

arrayList.subList(2, 4)创建一个AbstractList的子类SubList的实例，调用clear方法时由于子类SubList没有重写，所以直接调用AbstractList的clear方法，然而，在AbstractList的clear方法中，调用的是removeRange方法，该方法在SubList中重写了；所以，调用的是子类的removeRange，在SubList中有一个指向外部类的指针parent，在removeRange方法中通过parent调用了外部类的removeRange方法。所以经过辗转调用，最终调用的还是外部类的removeRange方法

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
    }
//SubList类中没有重写AbstractList的clear方法
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;//指向外部类
private final int parentOffset;
private final int offset;
int size;

        SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
        }
        ...
protected void removeRange(int fromIndex, int toIndex) {
            checkForComodification();
            parent.removeRange(parentOffset + fromIndex,parentOffset + toIndex);
//调用外部类的removeRange()，所以最终修改的就是外部类数组的元素，即相当于调用了外部类的removeRange方法
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
        }
    }
//AbstractList类中申明的clear()方法
public void clear() {
        removeRange(0, size());//由于SubList重写了removeRange方法，所以调用SubList的removeRange方法，
    }

每一次对数组做添加元素，删除元素等改变数组大小或者容量的操作时都会引起对modCount的加1， 究竟这个值有什么作用呢？

//返回一个遍历的指针
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的元素的下标
int lastRet = -1; // 最后一个元素的下标
int expectedModCount = modCount;  //这个的作用就是当用itr来遍历集合时，不允许往里面添加或者删除元素

public boolean hasNext() {//hasNext方法不会检查expectedModCount 的值，不会引发ConcurrentModificationException异常
return cursor != size;
    }

    @SuppressWarnings("unchecked")
public E next() {//next方法在最开始的时候就会使用checkForComodification进行检查
//所以如果在调用next之前对集合进行了改变则会抛出异常
        checkForComodification();//检查是否改变
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
        Object[] elementData = MyArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
        cursor = i + 1;
return (E) elementData[lastRet = i];
    }
//remove方法首先会调用checkForComodification进行检查
//同时，在MyArrayList.this.remove(lastRet)时会改变modCount，expectedModCount = modCount
//又让情况变为正常，所以删除之后这两个的值又会想等，在之后调用next的方法时不会炮竹异常
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
        checkForComodification();

try {
            MyArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
        }
    }

    @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
final int size = MyArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
        }
final Object[] elementData = MyArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
        }
while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
// update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
    }
}

ArrayList的三种遍历

• 使用下标（在遍历的时候可以对集合进行添加删除）

        MyArrayList<Integer> array = new MyArrayList<Integer>();
array.add(1);
array.add(2);
array.add(1, 3);
array.display();

for(int i = 0; i < array.size(); i++){
            System.out.println(array.get(i));
array.remove(new Integer(3));
if (i == 1) {
array.add(1);
            }
        }

• 使用iterator

        Iterator<Integer> it = array.iterator();
while(it.hasNext()){
//array.add(4); 会导致modCount发生变化,从而导致next方法的checkModCount抛出异常
int value = it.next();
//array.remove(new Integer(value));同样会导致modCount发生变化
            it.remove();//但是可以这样，因为Iterator的remove方法删除元素之后对modCount又进行了复原
            System.out.println(value);
        }

• 使用forEach循环（其实本质就是利用的Iterator循环）先是it.hasNext()，然后在将value = it.next()，所以执行这段代码时，会先打印第一个值，在进行第二轮循环的value = it.next()时抛出异常

        for(Integer value : array){
//array.add(4);//发生错误
//array.remove(value);
            System.out.println(value);
        }

本文参考：http://www.cnblogs.com/hzmark/archive/2012/12/20/ArrayList.html
今天看了大牛的代码很开心，明天再接再厉，加油。感受大牛的风采~~