ArrayList源码解析

ArrayList简介

ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
  ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

ArrayList源码分析 (JDK 1.6)

首先我们先分析一个List接口的实现类之一，也是最常用的ArrayList的源码。

ArrayList底层使用一个数组完成数据的添加，查询，删除，修改。这个数组就是下面提到的elementData。

这里分析的代码是基于jdk1.6的（加入了比较详细的注释）。限于篇幅有几个小方法没有列出,80%的代码都列出了。

// MyArryList=ArrayList

public class MyArrayList<T> extends AbstractList<T> implements List<T>, RandomAccess, Cloneable, Serializable {    
  private static final long serialVersionUID = -6268233918174116440L;    
  // ArrayList基于该数组实现，用该数组保存数据    
  private transient Object[] elementData;   
   // ArrayList中实际数据的数量    
  private int size;

// ArrayList带容量大小的构造函数
public MyArrayList(int initialCapacity) {    
  if (initialCapacity < 0)        
    throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  elementData = new Object[initialCapacity];
}

// ArrayList无参构造函数。默认容量是10。
public MyArrayList() {    
  this(10);
}

// 创建一个包含collection的ArrayList
public MyArrayList(Collection<? extends T> c) {  
  elementData = c.toArray();    
  size = elementData.length;    
  // c.toArray方法可能不会返回一个Object[]结果，需要做一层判断。这个一个Java的bug，可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652查看    
  if (elementData.getClass() != Object[].class)        
    elementData = Arrays.copyOf(elementData, size, Object[].class);
}

@Override
public void trimToSize() {    
  modCount++;    
  int oldSize = elementData.length;    
  if (size < oldSize) 
  // 真实的size小于数组的大小        
    elementData = Arrays.copyOf(elementData, size);
}

@Override
public void ensureCapacity(int minCapacity) {
    modCount++;    
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        //新的容量=“(原始容量x3)/2 + 1” 
       int newCapacity = oldCapacity * 3 / 2 + 1; 
       //如果还不够，则直接将minCapacity设置为当前容量
       if (minCapacity > newCapacity)
          newCapacity = minCapacity;
          elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

// 直接添加元素e
@Override
public boolean add(T e) {
    // 确定ArrayList的容量大小
    ensureCapacity(size + 1);  // Increments modCount!!
    // 添加e到ArrayList中
    elementData[size++] = e;
    return true;
}

// 将element添加到ArrayList的指定位置
@Override
public void add(int index, T element) {
    rangeCheckForAdd(index);
    ensureCapacity(size + 1);
    // System.arraycopy最终实现是native方法
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

// 从index位置开始，将集合c全部添加到ArrayList
public boolean addAll(int index, Collection<? extends T> c) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacity(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;
}

// 删除ArrayList指定位置index的元素
@Override
public T remove(int index) {
    rangeCheck(index);
    modCount++;
    T oldVal = (T) elementData[index];
    int numMoved = size - index - 1;
    // 删除ArrayList中最后一个元素,是不会执行这个if的
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;     // Let gc do its work
    return oldVal;
}

// 删除ArrayList的指定元素
@Override
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                remove(index);  //JDK 1.6版本实际上用了fastRemove(int index). 这个和remove(int index)区别就是没有了rangeCheck步骤                
                return true;
    }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                remove(index);  //JDK 1.6版本实际上用了fastRemove(int index). 这个和remove(int index)区别就是没有了rangeCheck步骤
                return true;
            }
    }
    return false;
}

@Override
public void clear() {
    modCount++;
    for (int i = 0; i < elementData.length; i++)
        elementData[i] = null;
    size = 0;
}

@Override
public T get(int index) {
    rangeCheck(index);
    return (T) elementData[index];
}

@Override
public T set(int index, T element) {
    rangeCheck(index);
    T oldData = (T) elementData[index];
    elementData[index] = element;
    return oldData;
}

@Override
protected Object clone() throws CloneNotSupportedException {
    try {
        MyArrayList<T> cloned = (MyArrayList<T>) super.clone();
        cloned.elementData = Arrays.copyOf(elementData, size);
        cloned.modCount = 0;
        return cloned;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}

@Override
public int size() {
    return size;
}

// ArrayList是否包含Object(o)
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

//返回ArrayList是否为空
public boolean isEmpty() {
    return size == 0;
}

// 正向查找，返回元素的索引值
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;
}

// 返回ArrayList的Object数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 返回ArrayList元素组成的数组
public <T> T[] toArray(T[] a) {
    // 若数组a的大小 < ArrayList的元素个数；
    // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 若数组a的大小 >= ArrayList的元素个数；
    // 则将ArrayList的全部元素都拷贝到数组a中。
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}

// 迭代器实现
public Iterator<T> iterator() {
    return new Itr();
}

private class Itr implements Iterator<T> {
    int cursor;       // index of next element to return 下一个将要返回的元素的下表
    int lastRet = -1; // index of last element returned; -1 if no such 上一个返回的元素的下表, -1表示没有
    int expectedModCount = modCount;    // fast-fail机制

    // 是否还有元素
    @Override
    public boolean hasNext() {
        // 由于cursor是将要返回元素的索引，也就是下一个元素的索引，和size比较是否相等，也就是判断是否已经next到最后一个元素
        return cursor != size();
    }

    // 下一个元素
    @Override
    public T next() {
        checkForComodification();
        // i=下一个元素索引
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = MyArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        lastRet = i;
        return (T) elementData[lastRet];
    }

    // 将迭代器返回的元素删除
    @Override
    public void remove() {
        if (lastRet == -1)
            throw new IllegalStateException();
        checkForComodification();
        try {
            MyArrayList.this.remove(lastRet);
            cursor = lastRet;            // 重置为-1,不能连续两次调用remove()
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

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

ArrayList注意点

• 当数据量很大的时候, ArrayList内部操作元素的时候会移动位置，很耗性能

• ArrayList虽然可以自动扩展长度，但是数据量一大，扩展的也多，会造成很多空间的浪费

• ArrayList允许加入null元素

• ArrayList支持3种遍历方式
  (01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
  value = (Integer)iter.next();
}

(02) 第二种，随机访问，通过索引值去遍历。由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
  value = (Integer)list.get(i);
}

(03) 第三种，for循环遍历。如下：

Integer value = null;
for (Integer i:list) {
  value = i;
}

遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！！！