ArrayList内部實作原理

• 初始化
• • 添加元素add
  • 擴容
  • 移除元素Remove

初始化

無參構造初始化

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
           

說明當new ArrayList<>()時隻是給内部屬性賦了員工Object類型的空數組

有參構造初始化 當是數值類型時

private static final Object[] EMPTY_ELEMENTDATA = {};
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);
        }
    }
           

會先判斷傳入的值是否大于0，大于0就把執行個體化一個大小為參數值得數組，等于就指派為空數組，否則抛出異常

有參構造初始化 當是數值類型時

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

先把集合轉換為數組，然後判斷數組的值大小是否大于0，大于0後，判斷傳入的類型是否為Object.class,這裡的判斷toArray方法傳回的不一定是Object類型，因為數組也有自己.class類型如

String [] m  = new String[0];//這裡的class是Ljava.lang.String
Object [] n  = new Object[0];//這裡的class是Ljava.lang.Object
           

兩者完全不一樣，還因為子類重寫父類toArray方法的時候，不修改傳回值類型的前提下，子類傳回了什麼類型，具體得到的是子類的傳回值類型，而不會上轉成父類的傳回值類型,是以當類型不是Ljava.lang.Object需要調用方法重新轉換為Ljava.lang.Object的類型

添加元素add

直接添加元素

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 初始化容量
        elementData[size++] = e;//指派并記錄size
        return true;
    }
     private void ensureCapacityInternal(int minCapacity) {
        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);
    }
           

ensureCapacityInternal是容量的初始化，方法中判斷資料如果為空數組，設定容量為預設10或者比10更小的值，然後ensureExplicitCapacity方法判斷需不需擴容，當擴容的最小容量大于目前實際的容量大小 這裡用減法是因為： a<b 和 a-b<0 計算機中不同，因為數字用的是有限位的補碼，也正是是以才會有考慮溢出的代碼

添加到指定下表位置的元素

public void add(int index, E element) {
        rangeCheckForAdd(index);//檢查添加元素的下标範圍
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//元素後移一位
        elementData[index] = element;//指派
        size++;
    }
           

rangeCheckForAdd方法判斷下傳入的下标是否小于0或大于容量的size，判斷下标值是否符合範圍内；然後進行容量的初始化，system.arraycopy就是移動元素後移一位，然後index下标的值就為空，然後把添加的值進行指派

擴容

grow方法

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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
           

先擷取實際容量大小，然後進行1.5倍擴容，新擴容後的容量小于最小容量，新容量就為最小容量minCapacity，如果新容量比限制最大的容量MAX_ARRAY_SIZE （Integer.MAX_VALUE - 8）大，就比較最小容量是不是比限制最大的容量大，大于取最大容量，小于取最小容量， ArraysopyOf(elementData, newCapacity)進行重新指派

移除元素Remove

移除指定值

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

移除指定值會先周遊數組，然後找到指定值的下标，然後調用fastRemove(index)進行移除

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
    }
           

modCount記錄目前對象的次數，numMoved 是計算移除資料後需要移動的元素個數，移動的個數大于0，說明指定的删除的元素不是最好一個元素，就需要移動後面的元素往前移動一位，這裡就存在一個問題，周遊元素删除元素時，删除元素，後面元素會移動，造成下一個元素無法周遊到，造成資料錯誤，所有用for循環删除元素不可取的

elementData[–size] = null;是清除引用，為了讓GC能夠回收對象。

一開始不明白為什麼需要modCount記錄目前對象的修改的次數

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

這個方法說明為什麼要記錄修改次數，當集合周遊時，防止其他線程對數組進行操作，如果修改次數不一緻，說明集合已經被其他線程修改，然後抛出異常ConcurrentModificationException。

以上純屬個人見解，有什麼問題可以指出來