ArrayList的原理

ArrayList是我們經常使用的集合類。底層是通過數組實作的！

先看一下實作原理圖

由圖可知，ArrauyList是按順序存儲資料的。

類結構

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

成員變量

    size：集合中存儲資料的數目。

    elementData：這個就是集合底層使用的數組了。

構造方法

1
	public ArrayList(int initialCapacity) {
        super();
        /*容量肯定不能小于0*/
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

	2
	public ArrayList() {
        this(10);
    }

	3	
	public ArrayList(Collection<? extends E> c) {
        /*轉成數組*/
        elementData = c.toArray();
        /*看看數組的長度*/
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        /*c.toArray()可能不會傳回Object[]，如果類型不對，需要轉化。*/
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }	
           

ArrayList的add()方法：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
	private void ensureCapacityInternal(int minCapacity) {
        modCount++;//更改次數+1
        // overflow-conscious code
        /*目前需要的容量 - 底層數組的容量 > 0 說明底層數組長度不夠用啦，要擴容 */
        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;
        /*如果擴容後的容量大于限制的最大容量，調用方法判斷minCapacity是否大于ArrayList允許配置設定的最大容量*/
        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);
    }
	
	/*需要的容量是否大于MAX_ARRAY_SIZE,是的話直接将需要的容量設定為Inteer的最大容量，不是就直接設定為MAX_ARRAY_SIZE*/
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
           

add()方法主要關注擴容問題!

如果此時集合的容量已經是最大容量且存滿了資料，即Integer的MAX_VALUE，通過擴容時發現MAX_VALUE不會再擴大。在add()方法中，給elementData[size++] = e;就會發現size=MAX_VALUE，size+1>MAX_VALUE,底層數組中并沒有MAX_VALUE+1這個index，是以會報數組越界，是以ArrayList集合的容量是有上限的！

ArrayList的get()方法

public E get(int index) {
        /*檢查index是否大于ArrayList存儲資料數量*/
        rangeCheck(index);
        /*直接去數組對應小标找到這個值，直接傳回*/
        return elementData(index);
    }
           

    邏輯相當簡單，隻要判斷index是否超出集合此時集合擁有值的數量。超出就報異常。

ArrayList的remove()方法

remove(int index)

public E remove(int index) {
        //檢查index是否合法
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);
        /*需要移動元素的數目*/
        int numMoved = size - index - 1;
        if (numMoved > 0)
            /*在該方法裡實作資料的移動*/
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        /*将無用結點設定為null*/
        elementData[--size] = null; // Let gc do its work
        /*傳回删除的值*/
        return oldValue;
    }
           

remove(Object o)

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 void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            /*将删除資料後的資料往前移動*/
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }
           

這裡要注意的是，若存此時集合存在多個object.equals(true),那麼隻會講比對的第一次對象移除。

所有的移除資料後的資料都要往前移動一個。如圖