ArrayList源碼分析(jdk1.7)

ArrayList

ArrayList是數組實作的線性表，容量不夠時會進行擴容。

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

首先 它繼承了AbstractList類，實作了List，RandomAccess，Cloneable，java.io.Serializable接口.

ArrayList特點

1. 元素可以重複，可以為null。ArrayList實作了List接口。
2. 可以随機通路。實作了RandomAccess接口，這個接口是一個标志接口。
3. 可以進行對象克隆。實作了Cloneable接口。
4. 可以被序列化。實作了Serializable接口。

ArrayList核心源碼分析

1.屬性分析：

//序列化id
private static final long serialVersionUID = 8683452581122892189L;
//預設初始容量為10
private static final int DEFAULT_CAPACITY = 10;
//空數組對象，如果采用預設構造方式，初始化為空數組
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于儲存資料的數組
private transient Object[] elementData;
//目前容量
private int size; 
           

2.構造函數

/*
 *帶初始容量的構造函數
 */
public ArrayList(int initialCapacity) {
	super();
	//如果輸入初始容量小于0，抛出異常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    //建立一個大小為initialCapacity的數組
    this.elementData = new Object[initialCapacity];
}
/**
 *預設構造函數
  */
public ArrayList() {
	//實作了父類的構造方法
    super();
	//将數組初始化為空數組
    this.elementData = EMPTY_ELEMENTDATA;
}
/*
 *構造一個指定集合的元素的清單，按照它們由集合的疊代器傳回的順序
  */
public ArrayList(Collection<? extends E> c) {
	
    elementData = c.toArray(); 
    size = elementData.length;
    // c.tc.toArray 傳回的可能不是  Object[]
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
           

3.方法分析

1. 增加

/*
 *插入一個元素到線性表的末尾
 */
public boolean add(E e) {
	//調用ensureCapacityInternal()方法
	ensureCapacityInternal(size + 1); 
	//将元素e指派給elementData[size] 然後size++
	elementData[size++] = e;
	return true;
}
/*
 *指定位置index插入元素e
 */
public void add(int index, E element) {
	//調用rangeCheckForAdd()方法檢查範圍
	rangeCheckForAdd(index);
	//同樣調用這個方法
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	//将原數組index之後的值包括index都向後移動一個位置
	System.arraycopy(elementData, index, elementData, index + 1,
	                size - index);
	//将元素e插入index位置。
	elementData[index] = element;
	//容量size++
	size++;
}
/*
 *檢驗下标是否正确
 */
private void rangeCheckForAdd(int index) {
	//下标不正确抛出異常
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/*
 *判斷容量的大小
 */
private void ensureCapacityInternal(int minCapacity) {
	//判斷目前容量是否是預設的空容量
   if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
   //調用ensureExplicitCapability方法判斷插入後的容量和數組長度的大小
    ensureExplicitCapacity(minCapacity); 
}

/**
 *判斷插入後的容量和數組長度的大小
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果目前插入後的容量比數組長度大，調用grow方法進行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);  
}
/*
 *擴容
 */
private void grow(int minCapacity) {
	//儲存老的數組容量
    int oldCapacity = elementData.length;
    //新的數組容量 1.5倍擴容
    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) {
	//異常處理
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    //如果數組容量超過最大數組容量，傳回整型的最大值，否則傳回最大數組容量
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
           

1. 删除

/*
 *删除線性表的指定位置的一個元素
 */
public E remove(int index) {
	//範圍檢查
    rangeCheck(index);
    modCount++;
    //儲存删除的元素
    E oldValue = elementData(index);
	//要移動的第一個元素的下标
    int numMoved = size - index - 1;
    //如果删除的不是最後一個元素，那麼numMoved大于0，将index以後的元素全部向前移動一個位置
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //将最後一個位置置為null，GC自動回收
    elementData[--size] = null; // clear to let GC do its work
	//傳回删除的元素
    return oldValue;
}
/*
 *範圍檢測
 */
private void rangeCheck(int index) {
	//如果index比數組容量大，抛出異常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/*
 *删除所有和o相等的第一個元素
 */
public boolean remove(Object o) {
	//空指針檢驗
	if (o == null) {
	     for (int index = 0; index < size; index++)
	     //判斷數組中有沒有null
	          if (elementData[index] == null) {
	              fastRemove(index);
	              return true;
	          }
	} else {
	    for (int index = 0; index < size; index++)
	    //判斷是否相等
	        if (o.equals(elementData[index])) {
	        //調用fastRemove方法删除index位置元素
	            fastRemove(index);
	            return true;
	        }
	}
	//沒有這個元素，傳回false
	return false;
}
/*
 * 删除最後一個元素，與remove的後半部分完全相同
 */
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
}
           

1. 修改

public E set(int index, E element) {
	//範圍檢查，這個方法上面看過了
    rangeCheck(index);
	//oldValue儲存原來的元素
    E oldValue = elementData(index);
    //将index下标處的值修改為element
    elementData[index] = element;
    //傳回舊元素
    return oldValue;
}
           

1. 查找

public E get(int index) {
    rangeCheck(index);
	//傳回index下标處的元素
    return elementData(index);
}