數(shù)組(Array)

數(shù)組指的就是一組相關(guān)類型的變量集合苛谷，并且這些變量可以按照統(tǒng)一的方式進(jìn)行操作辅鲸，數(shù)組數(shù)據(jù)引用數(shù)據(jù)類型，在堆中進(jìn)行內(nèi)存分配腹殿，在內(nèi)存中是連續(xù)存在独悴，大小固定的。

ArrayList

ArrayList可以算是數(shù)組的加強(qiáng)版赫蛇，其繼承AbstractList接口绵患，實(shí)現(xiàn)了List，RandomAccess悟耘，Cloneable接口落蝙，可序列化。在存儲(chǔ)方面 數(shù)組可以包含基本類型和對(duì)象類型，比如：int[],Object[]筏勒，ArrayList只能包含對(duì)象類型移迫；在空間方面，數(shù)組的空間大小是固定的管行，空間不夠時(shí)不能再次申請(qǐng)厨埋，所以需要事前確定合適的空間大小。ArrayList的空間是動(dòng)態(tài)增長(zhǎng)的捐顷，如果空間不足荡陷，它會(huì)創(chuàng)建一個(gè)1.5倍大的新數(shù)組，然后把所有元素復(fù)制到新數(shù)組迅涮，而且每次添加新的元素時(shí)會(huì)檢測(cè)內(nèi)部數(shù)組的空間是否足夠废赞。

源碼解析

變量

    //默認(rèn)初始容量    
    private static final int DEFAULT_CAPACITY = 10;
    //空數(shù)組   
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //空數(shù)組與EMPTY_ELEMENTDATA 區(qū)別在于添加第一個(gè)元素時(shí)，擴(kuò)充多少
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //實(shí)例數(shù)組對(duì)象
    transient Object[] elementData; // non-private to simplify nested class access

    //數(shù)組大小
    private int size;

構(gòu)造函數(shù)

ArrayList的構(gòu)造方法有三種：

//自定義初始容量
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        //初始化容量大小   
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //容量初始值不能 < 0 小于零會(huì)拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//常用無(wú)參構(gòu)造函數(shù)叮姑，默認(rèn)數(shù)組大小為 10
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//創(chuàng)建一個(gè)包含collection的ArrayList
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)
        //構(gòu)造大小為size的Object[]數(shù)組賦值給elementData
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替換空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

常用函數(shù)(方法)

add函數(shù)

ArrayList調(diào)用add()方法添加函數(shù)唉地，源碼為

//在數(shù)組尾部添加元素 
public boolean add(E e) {
    //長(zhǎng)度+1，也就是修改次數(shù)+1 確保內(nèi)部容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
    //數(shù)組下標(biāo)+1 并賦值
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
    //若數(shù)組元素為空传透，取最小容量耘沼，與默認(rèn)容量的最大值做為最小容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //明確ArrayList的最小容量
        ensureExplicitCapacity(minCapacity);
    }
//用于內(nèi)部?jī)?yōu)化確保空間資源不被浪費(fèi)
private void ensureExplicitCapacity(int minCapacity) {
    //修改統(tǒng)計(jì)數(shù)+1朱盐，主要用來(lái)實(shí)現(xiàn)fail-fast機(jī)制
        modCount++;

        // 防止溢出群嗤，保證最小容量 > 數(shù)組緩沖區(qū)當(dāng)前長(zhǎng)度
        if (minCapacity - elementData.length > 0)
        //增加容量
            grow(minCapacity);
    }

 //增加容量以確保它至少可以容納最小容量參數(shù)指定的元素?cái)?shù)量。
 private void grow(int minCapacity) {
        // 元素長(zhǎng)度為舊容量大小
        int oldCapacity = elementData.length;
    // 新容量= 舊容量 + 舊容量右移一位（舊容量/2）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判斷新容量與最小容量大小 
        if (newCapacity - minCapacity < 0)
        //最小容量>新容量 托享，則新容量為最小容量
            newCapacity = minCapacity;
    //若新容量 > 最大容量 骚烧，對(duì)新容量重新計(jì)算
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //重新計(jì)算新容量
            newCapacity = hugeCapacity(minCapacity);
        // 擴(kuò)容并賦值數(shù)組元素
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
    //若最小容量 < 0 則拋出異常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
    //最小容量大于 最大數(shù)組長(zhǎng)度，則返回int最大值作為容量大小
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

查看復(fù)制數(shù)組方法

Arrays.copyOf(elementData, newCapacity)

//Arrays.java類中的方法
public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    
//復(fù)制指定的數(shù)組闰围，截?cái)嗷蚴褂胣ull填充（如果需要）赃绊，以便副本具有指定的長(zhǎng)度。
// 對(duì)于在原始數(shù)組和副本中均有效的所有索引羡榴，兩個(gè)數(shù)組將包含相同的值
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //從指定的源數(shù)組開(kāi)始復(fù)制數(shù)組碧查，從指定的位置開(kāi)始到目標(biāo)數(shù)組的指定位置
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

//內(nèi)部調(diào)用System.arraycopy方法
@FastNative
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

在對(duì)應(yīng)下標(biāo)出添加數(shù)據(jù)元素
public void add(int index, E element) {
    //超出數(shù)據(jù)長(zhǎng)度或 小于0 ，則拋出數(shù)組越界異常
        if (index > size || index < 0) 
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ///增加容量以確保它至少可以容納最小容量參數(shù)指定的元素?cái)?shù)量校仑，修改次數(shù)+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
    //數(shù)組拷貝賦值
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//添加數(shù)組集合
public boolean addAll(Collection<? extends E> c) {
    //轉(zhuǎn)化數(shù)據(jù)
        Object[] a = c.toArray();
        int numNew = a.length;
    //修改次數(shù)+1
        ensureCapacityInternal(size + numNew);  // Increments modCount
    //數(shù)組拷貝賦值
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

通過(guò)分析add方法可以發(fā)現(xiàn)ArrayList內(nèi)部是調(diào)用System.arraycopy方法復(fù)制數(shù)組忠售。

set函數(shù)

//對(duì)應(yīng)下標(biāo)設(shè)置對(duì)應(yīng)的數(shù)組元素，原來(lái)的元素被替換掉并返回替換的數(shù)組元素
public E set(int index, E element) {
    //下標(biāo) >數(shù)組長(zhǎng)度迄沫， 則拋出數(shù)組越界異常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //查找索引對(duì)應(yīng)數(shù)組元素
        E oldValue = (E) elementData[index];
    //數(shù)組元素重新賦值
        elementData[index] = element;
        return oldValue;
    }

get函數(shù)

public E get(int index) {
    //下標(biāo) >數(shù)組長(zhǎng)度稻扬， 則拋出數(shù)組越界異常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //根據(jù)下標(biāo)直接返回對(duì)應(yīng)數(shù)組元素，查找速度快
        return (E) elementData[index];
    }

remove函數(shù)

//移除數(shù)組下標(biāo)對(duì)應(yīng)的數(shù)組元素,返回刪除的數(shù)組元素  
public E remove(int index) {  
     //下標(biāo) >數(shù)組長(zhǎng)度羊瘩， 則拋出數(shù)組越界異常  
     if (index >= size)  
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
     //修改次數(shù)統(tǒng)計(jì) +1  
     modCount++;  
     //通過(guò)索引下標(biāo)查找對(duì)應(yīng)數(shù)組元素  
     E oldValue = (E) elementData[index];  
     //數(shù)組移動(dòng)個(gè)數(shù)  
     int numMoved = size - index - 1;  
     if (numMoved > 0)  
         //后續(xù)數(shù)組元素整體往前移動(dòng)   
         System.arraycopy(elementData, index+1, elementData, index,  
         numMoved);  
     //數(shù)組最后一位元素置空泰佳，且長(zhǎng)度-1  
     elementData[--size] = null; // clear to let GC do its work  
     //返回移除對(duì)應(yīng)數(shù)組元素  
     return oldValue;  
 }  

//刪除對(duì)應(yīng)元素盼砍，如果刪除成功返回true  
public boolean remove(Object o) {  
    if (o == null) { //判斷是否為空  
         for (int index = 0; index < size; index++)  
             if (elementData[index] == null) { //若數(shù)組下標(biāo)對(duì)應(yīng)元素為空則移除null元素  
                fastRemove(index);  
                return true;  
        }  
     } else {//不為空  
         for (int index = 0; index < size; index++)  
             //判斷要?jiǎng)h除的對(duì)象在數(shù)組是否存在，存在則刪除  
             if (o.equals(elementData[index])) {   
                 fastRemove(index);  
                 return true;  
             }  
     }  
     return false;  
 }  
  
  
 //私有方法快速刪除數(shù)組元素逝她，該方法與remove(int 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  
 }  
  

indexof函數(shù)

//查找數(shù)組元素對(duì)應(yīng)下標(biāo) 浇坐，數(shù)組元素  
public int indexOf(Object o) {
        if (o == null) {  //判斷是否為空
            for (int i = 0; i < size; i++)//遍歷
        //數(shù)組元素為null返回對(duì)應(yīng)下標(biāo)
                if (elementData[i]==null) 
                    return i;
        } else {
            for (int i = 0; i < size; i++)
        //遍歷存在對(duì)象o 則返回對(duì)應(yīng)下標(biāo)
                if (o.equals(elementData[i]))
                    return i;
        }
    //數(shù)組中不存在，則返回-1
        return -1;
    }

subList方法

//從ArrayList中截取子列表集合
public List<E> subList(int fromIndex, int toIndex) {
    //子列表集合范圍檢測(cè)
        subListRangeCheck(fromIndex, toIndex, size);
    //返回值為一個(gè)SubList對(duì)象
        return new SubList(this, 0, fromIndex, toIndex);
    }

SubList為ArrayList的一個(gè)內(nèi)部類

 private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
        //該參數(shù)為父類ArrayList 把自身傳了進(jìn)來(lái)   
            this.parent = parent;
        //開(kāi)始截取的位置索引         
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
        //截取后得到的ArrayList長(zhǎng)度
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }


       public void add(int index, E e) {
        //檢測(cè)索引是否越界黔宛，越界則拋出異常  
            rangeCheckForAdd(index);
        //檢測(cè)數(shù)組列表是否被修改
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        private void checkForComodification() {
        //判斷ArrayList的修改次數(shù)與子類的修改次數(shù)是否相等近刘，否則拋出并發(fā)修改異常   
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
          }

    .....
}

舉個(gè)例子：

    ArrayList<String> list = new ArrayList<>();
        list.add("f1");
        list.add("f2");
        list.add("f3");
        
        List<String> subList =list.subList(0,2);
        subList.add("s1");
        subList.remove(1);
        System.out.println("list = " + list);
        System.out.println("subList = " + subList);

輸出為：
list = [f1, s1, f3]
subList = [f1, s1]

從輸出結(jié)果可以看出，截取后的subList是可以增刪查找的臀晃，而list是跟隨subList改變而改變的觉渴。原因是，在初始化SubList的時(shí)候直接把ArrayList 自身傳了進(jìn)去徽惋，在subList進(jìn)行增刪查找時(shí)相當(dāng)于是對(duì)ArrayList自身操作疆拘。

那在subList 執(zhí)行增刪方法后還可以操作list增刪嗎？答案：是可以的寂曹，不過(guò)是有一個(gè)前提是 不能再對(duì)subList進(jìn)行任何操作，包括輸出subList對(duì)象回右。
緊接上面的例子

        subList.add("s2");
        list.add("f4");
        System.out.println("list = " + list);
        list.remove("s1");
        System.out.println("list = " + list);

輸出結(jié)果為：
list = [f1, s1, f3]
subList = [f1, s1]
list = [f1, s1, s2, f3, f4]
list = [f1, s2, f3, f4]

如果對(duì)list進(jìn)行操作后又對(duì)subList操作將會(huì)拋出ConcurrentModificationException,原因是ArrayList進(jìn)行增刪時(shí)修改了modCount 隆圆，而 SubList的modCount并沒(méi)有被修改，檢測(cè)的時(shí)候二者不相等所以拋出異常翔烁。

總結(jié)

• 數(shù)組與ArrayList之間的區(qū)別
• 本文主要分析了ArrayList的常用add渺氧，remove等方法的源碼，以及子類SubList的使用方法蹬屹。

相關(guān)文章閱讀
Java集合系列之HashMap源碼分析

Android 源碼解析系列分析

自定義View繪制過(guò)程源碼分析
ViewGroup繪制過(guò)程源碼分析
ThreadLocal 源碼分析
Handler消息機(jī)制源碼分析
Android 事件分發(fā)機(jī)制源碼分析
Activity啟動(dòng)過(guò)程源碼分析
Activity中View創(chuàng)建到添加在Window窗口上到顯示的過(guò)程源碼分析