ArrayList原理解析

發(fā)布時(shí)間：2017年07月21日作者： IT網(wǎng)絡(luò)文摘 (該文來(lái)自筆記，點(diǎn)擊查看原文)

ArrayList就是動(dòng)態(tài)數(shù)組，用MSDN中的說(shuō)法，就是Array的復(fù)雜版本，它提供了動(dòng)態(tài)的增加和減少元素，實(shí)現(xiàn)了ICollection和IList接口，靈活的設(shè)置數(shù)組的大小等好處

有圖有碼

圖為手工畫的，有點(diǎn)丑見諒 _！

初始化集合ArrayList list = new ArrayList();
因?yàn)槭褂脽o(wú)參構(gòu)造時(shí)候集合容器為空，所以無(wú)任何空位。
第一次添加元素 add("a") 第一次添加元素時(shí)候，檢測(cè)容器為空，根據(jù)默認(rèn)容量10進(jìn)行初始化容器。然后將元素放置到第一個(gè)空位中。初始化容器：
增加一個(gè)元素：
第十一次添加元素 add("k") 第十一次添加元素，發(fā)現(xiàn)元素超出容量，所以進(jìn)行一次擴(kuò)容，擴(kuò)容后的大小為原容量加原容量的二分之一，即為15；然后將元素放置到第是一個(gè)空位中。
增加容量：
增加一個(gè)元素：
移除期中一個(gè)元素 remove(3) 移除第三個(gè)元素，將數(shù)組從第四個(gè)元素到最后一個(gè)元素放置到第三個(gè)元素開始到最后，然后將數(shù)組的最后一位元素設(shè)為null。

源碼分析

構(gòu)造方法

//無(wú)參構(gòu)造方法，初始化elementData為{}private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//元素?cái)?shù)組transient Object[] elementData;//集合大小private int size;//默認(rèn)容量private static final int DEFAULT_CAPACITY = 10;public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//指定容量大小的構(gòu)造方法 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);
        }
    }

//帶有初始化數(shù)據(jù)的構(gòu)造 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();        if ((size = elementData.length) != 0) {            // c.toArray might (incorrectly) not return Object[] (see 6260652)            // 因?yàn)閏.toArray返回的不一定為Object[]            // 如Object[] objs = new String[]{""};            // objs[0]=new Object();//java.lang.ArrayStoreException: java.lang.Object            //經(jīng)測(cè)試 在1.8被修復(fù)了^_^            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {            // replace with empty array.            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

方法及源碼

//增加一個(gè)元素public boolean add(E e) {        //確保有空余的容量，否則則增加容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;        return true;
    }

//指定位置插入一個(gè)元素public void add(int index, E element) {        //檢測(cè)下標(biāo)是否越界，否則 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!        //拷貝數(shù)組，為新元素騰出一個(gè)空位
        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);
        elementData[index] = element;        size++;
    }

//確保有空余的容量，否則則增加容量private void ensureCapacityInternal(int minCapacity) {//如果集合為空，則取默認(rèn)和當(dāng)前size+1較大的值        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }//判斷當(dāng)前容量是否夠用private void ensureExplicitCapacity(int minCapacity) {
        modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)          
            //增加容量
            grow(minCapacity);
    }//增加容量private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        //新容量=原來(lái)大小+原來(lái)大小/2，也就是說(shuō)擴(kuò)容原來(lái)大小的一半。        //備注： x>>1=x/2        int newCapacity = oldCapacity + (oldCapacity >> 1);        //如果新容量還不夠用，設(shè)容量為所需容量        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;        //如過(guò)所需容量大于最大容量Integer.MAX_VALUE - 8,則設(shè)置超大容量        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);
    }//設(shè)置超大容量，capacity=Integer.MAX_VALUE=2147483647    
private static int hugeCapacity(int minCapacity) {        if (minCapacity < 0) // overflow            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

remove

//首先根據(jù)對(duì)象循環(huán)對(duì)比，找出第一個(gè)相等的對(duì)象的下標(biāo)//然后通過(guò)fastRemove方法進(jìn)行快速移除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;
    }

//根據(jù)下標(biāo)進(jìn)行移除，返回被移除的元素public E remove(int index) {        //檢查下標(biāo)是否越界
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);        //計(jì)算出要拷貝的對(duì)象個(gè)數(shù)        int numMoved = size - index - 1;         //移除的原理就是將指定下標(biāo)的后面元素全部向前移動(dòng)一步，將末端元素設(shè)為null        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work        return oldValue;
    }

//快速移除方法private void fastRemove(int index) {
        modCount++;        int numMoved = size - index - 1;        //移除的原理就是將指定下標(biāo)的后面元素全部向前移動(dòng)一步，將末端元素設(shè)為null        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

public E get(int index) {        //檢測(cè)下標(biāo)是否越界
        rangeCheck(index);        return elementData(index);
    }

//修改某個(gè)下標(biāo)的元素public E set(int index, E element) {        //檢測(cè)下標(biāo)是否越界
        rangeCheck(index);        //獲取老的元素
        E oldValue = elementData(index);        //賦值新的元素
        elementData[index] = element;        return oldValue;
    }

clear

//清楚集合，循環(huán)元素，將每個(gè)元素設(shè)置為nullpublic void clear() {
        modCount++;        // clear to let GC do its work        for (int i = 0; i < size; i++)
            elementData[i] = null;        size = 0;
    }

總結(jié)

通過(guò)源碼分析，ArrayList集合就是通過(guò)System.arraycopy方法將普通數(shù)組Object[]包裝為一個(gè)動(dòng)態(tài)數(shù)組，實(shí)現(xiàn)數(shù)組的增刪改查。

優(yōu)點(diǎn)
1、修改元素和通過(guò)下標(biāo)查詢?cè)匦矢?br/>2、集合是有順序的
缺點(diǎn)
1、刪除元素效率低，因?yàn)橐ㄟ^(guò)拷貝數(shù)組來(lái)實(shí)現(xiàn)
2、大量新增效率低，因?yàn)榇罅啃略龅臅r(shí)候要不斷進(jìn)行擴(kuò)容和數(shù)組的拷貝
3、清除集合效率低，因?yàn)榍宄δ苁峭ㄟ^(guò)循環(huán)數(shù)組進(jìn)行清除的
4、移除元素后，容量有大量剩余，需要手動(dòng)調(diào)用trimToSize進(jìn)行清理

其他

1、使用時(shí)候如果知道預(yù)期容量，建議設(shè)定容量，避免不斷擴(kuò)容影響效率。
2、建議改進(jìn)清除操作，避免使用循環(huán)進(jìn)行清除。

參考

百度百科 http://baike.baidu.com/link?url=Ff4TnTpO2FNkD2y4Z0VuM_caPtYUkV74O4f-rFnXB_kvu-KA8FlttknMy481CwO2XcN1nfhZHqk7UAnBKVMOgki5rB3WlfLvxZHuJktz8gu
由ArrayList構(gòu)造函數(shù)源碼引出的問(wèn)題 http://www.cnblogs.com/zhizhizhiyuan/p/3662371.html

http://www.cnblogs.com/mvilplss/p/7112725.html

分類導(dǎo)航