ArrayList源碼解析

khlbat 發(fā)布于2019-08-19 11:13 / 2318人閱讀

摘要：說(shuō)明是對(duì)中數(shù)組的擴(kuò)展，其底層還是使用數(shù)據(jù)實(shí)現(xiàn)，支持自動(dòng)擴(kuò)容，不是線程安全的類。其繼承，實(shí)現(xiàn)了各個(gè)接口，其中為支持隨機(jī)讀寫(xiě)的標(biāo)記接口，在后續(xù)類的講解中會(huì)用到。加上主要是為了不能直接序列化，而是必須使用自帶的和方法，主要是為了節(jié)省空間。

1.說(shuō)明

ArrayList是對(duì)java中數(shù)組的擴(kuò)展，其底層還是使用數(shù)據(jù)實(shí)現(xiàn)，支持自動(dòng)擴(kuò)容，不是線程安全的類。其繼承AbstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable,Serializable各個(gè)接口，其中RandomAccess為支持隨機(jī)讀寫(xiě)的標(biāo)記接口，在后續(xù)Collections類的講解中會(huì)用到。

2.優(yōu)缺點(diǎn)

ArrayList是一個(gè)支持自動(dòng)擴(kuò)容的線性表，所以其與普通線性表的特點(diǎn)一樣，如下：

順序存儲(chǔ)，所以按照下標(biāo)讀取元素的時(shí)間復(fù)雜度為O(1)

在刪除元素時(shí)其后面的所有元素都得前移，新增元素時(shí)后面的所有元素都得后移

在存儲(chǔ)時(shí)就需要開(kāi)辟一塊固定的存儲(chǔ)空間

3.重要變量

//默認(rèn)的容量，當(dāng)構(gòu)造函數(shù)沒(méi)有傳入此參數(shù)時(shí)，會(huì)在加入第一個(gè)元素時(shí)將數(shù)組擴(kuò)容為此值
private static final int DEFAULT_CAPACITY = 10;
    
//當(dāng)數(shù)組中元素為空時(shí)，會(huì)將數(shù)組初始化為此數(shù)組，代表空數(shù)組，這個(gè)空數(shù)組是在傳入
初始容量并且初始容量為0的情況下令數(shù)組等于這個(gè)
private static final Object[] EMPTY_ELEMENTDATA = {};

//與上一個(gè)變量的區(qū)別在于其是在于這個(gè)空數(shù)組是在使用無(wú)參構(gòu)造函數(shù)時(shí)創(chuàng)建
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//這個(gè)數(shù)組用于ArrayList存儲(chǔ)元素,ArrayList的容量就是數(shù)組的長(zhǎng)度。加上transient主要是為了
不能直接序列化，而是必須使用自帶的writeObject和readObject方法，主要是為了節(jié)省空間。不私有
化主要是為了以后擴(kuò)展，防止以后嵌套等操作
transient Object[] elementData; // non-private to simplify nested class access

//ArrayList的實(shí)際大小，即元素所占個(gè)數(shù)
private int size;

4.構(gòu)造方法

//傳入初始參數(shù)的構(gòu)造方法
public ArrayList(int initialCapacity) {
        //如果初始容量大于0，那么直接按照初始容量初始化數(shù)組，
          如果初始容量等于0，等于EMPTY_ELEMENTDATA，上文
          的常量，不過(guò)不會(huì)在添加第一個(gè)元素的時(shí)候令容量等于DEFAULT_CAPACITY
          如果初始容量小于0，直接拋出異常
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}

//無(wú)參構(gòu)造函數(shù)，直接令存儲(chǔ)數(shù)組等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
  在添加第一個(gè)元素的時(shí)候令容量等于DEFAULT_CAPACITY
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//通過(guò)一個(gè)集合類來(lái)構(gòu)造一個(gè)ArrayList
public ArrayList(Collection c) {
    //獲取集合類的底層數(shù)組
    elementData = c.toArray();
    //判斷集合類的元素個(gè)數(shù)是否為0
    if ((size = elementData.length) != 0) {
        //ps:c.toArray()可能返回的數(shù)組類型不為Object[]類型，
          通過(guò)ArrayList的toArray一定是Object[]類型，但是Arrays.asList（）
          里轉(zhuǎn)化成其內(nèi)部自身的ArrayList，其內(nèi)部的ArrayList的toArray方法會(huì)
          返回E[]這種泛型的對(duì)象，導(dǎo)致出現(xiàn)問(wèn)題
        //如果集合類的toArray方法返回的不為Object[]類型，使用Arrays.copyOf
          將其遷移到一個(gè)新的Object[]數(shù)組中
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果元素個(gè)數(shù)為0，那么直接將元素?cái)?shù)組置為EMPTY_ELEMENTDATA空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

5.基本方法

//增加一個(gè)新元素
public void add(int index, E element) {
        //檢驗(yàn)index是否超出范圍
        rangeCheckForAdd(index);
        //檢驗(yàn)當(dāng)前容量是否足夠，如果不夠，進(jìn)行擴(kuò)容
        ensureCapacityInternal(size + 1);  
        //將index之后的元素都后移一個(gè)
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //將新增的元素填入
        elementData[index] = element;
        //添加數(shù)組元素個(gè)數(shù)
        size++;
}

//檢驗(yàn)index是否超出范圍
private void rangeCheckForAdd(int index) {
        //判斷index是否大于當(dāng)前長(zhǎng)度或者小于0，如果不在數(shù)組范圍，
          那么直接跑出數(shù)組超出范圍異常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//確保內(nèi)部元素的容量足夠
private void ensureCapacityInternal(int minCapacity) {
        //對(duì)數(shù)組進(jìn)行擴(kuò)容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

//用于判斷數(shù)組是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此處用==號(hào)進(jìn)行比較，是因?yàn)?  只用于判斷是構(gòu)造函數(shù)時(shí)未傳初始容量，延遲到第一次添加新元素時(shí)進(jìn)行默認(rèn)初始容量的設(shè)置，然后
  返回比較默認(rèn)容量與需要的最小容量的最大值，這里返回最大值是因?yàn)橛锌赡芤淮翁砑佣鄠€(gè)元素，  AddAll也會(huì)復(fù)用這個(gè)函數(shù)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

//對(duì)數(shù)組進(jìn)行擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
        //修改次數(shù)+1
        modCount++;

        // 如果需要的容量數(shù)大于當(dāng)前容量，進(jìn)行擴(kuò)容，否則，不在繼續(xù)，
          并且防止溢出，如果溢出，不進(jìn)行下列操作，直接會(huì)在后續(xù)數(shù)組
          賦值中直接拋出越界異常，因?yàn)檫@個(gè)時(shí)候代表size已經(jīng)很大了
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
 //對(duì)數(shù)組進(jìn)行擴(kuò)容
 private void grow(int minCapacity) {

        int oldCapacity = elementData.length;
        //令新的容量等于原容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新的容量小于當(dāng)前需要的的最小容量，那么新容量等于當(dāng)前需要的的最小容量
          防止newCapacity溢出或者增加1.5倍還是小于minCapacity的情況
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新的容量比MAX_ARRAY_SIZE還大，MAX_ARRAY_SIZE為
          Integer.MAX_VALUE - 8，那么對(duì)當(dāng)前需要的最小容量進(jìn)行擴(kuò)容
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //為數(shù)組開(kāi)辟更大的空間
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //根據(jù)需要的容量進(jìn)行擴(kuò)容
    private static int hugeCapacity(int minCapacity) {
        //如果minCapacity此時(shí)小于0，代表已經(jīng)溢出，其實(shí)此時(shí)已經(jīng)不大可能，因?yàn)樵?          ensureExplicitCapacity已經(jīng)有一層判斷了
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        //如果minCapacity小于MAX_ARRAY_SIZE，那么直接等于MAX_ARRAY_SIZE，
          否則直接等于Integer的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

下面，來(lái)看看Api中的add，addAll等方法，其他類似方法不在贅述，get和set也不贅述，比較簡(jiǎn)單

//與add方法不同的是，他是在這個(gè)索引處新增了一個(gè)集合的元素
public boolean addAll(int index, Collection c) {
        //檢驗(yàn)index是否合法
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //size + numNew代表需要的最小容量
        ensureCapacityInternal(size + numNew);  

        //numMoved代表需要向后移動(dòng)的元素個(gè)數(shù)
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //將集合c中的所有元素移動(dòng)到elementData的index之后
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        //如果集合c的長(zhǎng)度不為0，返回true，否則返回false
        return numNew != 0;
    }
    //將elementData中的空元素去除，節(jié)省空間(去除不了中間的等于null這樣類型的元素)
    public void trimToSize() {
        modCount++;
        //如果當(dāng)前元素個(gè)數(shù)小于elementData的容量，當(dāng)size == 0時(shí)
          將elementData賦值為EMPTY_ELEMENTDATA，否則，將elementData
          容量減小到size大小
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
    
    //根據(jù)對(duì)應(yīng)元素計(jì)算出元素位置（遍歷為從前到后）
    public int indexOf(Object o) {
        //如果傳入元素為null，找到等于null的元素，否則，使用
          equals遍歷
        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;
    }
    
    //移除當(dāng)前元素
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        //獲取當(dāng)前index在數(shù)組對(duì)應(yīng)元素
        E oldValue = elementData(index);

        //獲取需要移動(dòng)的元素個(gè)數(shù)，即index之后的元素都需要向前移動(dòng)，不包括index
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //將最后一個(gè)元素置為空，其中的元素有g(shù)c自動(dòng)回收
        elementData[--size] = null; 
        //返回被刪除的元素值
        return oldValue;
    }
    
    //對(duì)對(duì)應(yīng)元素進(jìn)行移除，先遍歷查找，在進(jìn)行移除，值得一提的是，
      此處的remove方法，使用的是fastRemove，與remove方法具體
      少了rangeCheck方法和獲取oldValue，從而減少時(shí)間復(fù)雜度
    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;
    }