集合源碼學(xué)習(xí)之路---ArrayList

neroneroffy 發(fā)布于2019-08-15 12:30 / 914人閱讀

摘要：雖然迭代器不常用，但是里面的一些知識點，設(shè)計模式我們還是要學(xué)習(xí)以下的。需要注意的是，在使用迭代器期間，若使用非迭代器對容器進(jìn)行數(shù)據(jù)結(jié)構(gòu)上的改變，將會通過報錯。

ArrayList簡單介紹

ArrayList底層數(shù)據(jù)結(jié)構(gòu)使用的是數(shù)組，也就是線性表的順序存儲結(jié)構(gòu)，是一段連續(xù)的存儲單元。具有存取快，增刪慢的特點。ArrayList不是線程安全的

類定義

從類定義上看，arrayList是支持泛型的,繼承自AbstractList,實現(xiàn)了List接口。同時實現(xiàn)了Serializable接口，因為它支持序列化，支持序列化傳輸。實現(xiàn)了Cloneable接口，可以被克隆。實現(xiàn)了RandomAccess接口，可以被快速訪問，實際上就是通過下標(biāo)進(jìn)行訪問,RandomAccess只是一個標(biāo)記，無任何定義。

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

類屬性

private static final long serialVersionUID = 8683452581122892189L;

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

serialVersionUID：是實現(xiàn)了Serializable可自動生成的。簡單來說，Java的序列化機(jī)制是通過在運行時判斷類的serialVersionUID來驗證版本一致性的。在進(jìn)行反序列化時，JVM會把傳來的字節(jié)流中的serialVersionUID與本地相應(yīng)實體（類）的serialVersionUID進(jìn)行比較，如果相同就認(rèn)為是一致的，可以進(jìn)行反序列化，否則就會出現(xiàn)序列化版本不一致的異常。

EMPTY_ELEMENTDATA & DEFAULTCAPACITY_EMPTY_ELEMENTDATA :其實兩個都是一個空數(shù)組，只不過再明確長度為0時，會用EMPTY_ELEMENTDATA，無參構(gòu)造調(diào)用會用DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

DEFAULT_CAPACITY:當(dāng)沒有指定容量，第一次添加元素,arraylist的初始容量.

elementData:arraylist的buffer，arrayList的容量就是elementData的容量。當(dāng)arraylist為空時，elementData就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，當(dāng)添加第一個元素的時候，會自動擴(kuò)容DEFAULT_CAPACITY(10)長度.注意到，它被transient修飾，也就是不參與序列化，只存在調(diào)用者的內(nèi)存當(dāng)中。

size:arraylist含有元素的個數(shù)。

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

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

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(Collection 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;
        }
    }

arraylist一共定義了三個構(gòu)造函數(shù)。

構(gòu)造一個指定大小的elementData

初始化一個默認(rèn)數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA

將一個集合Collection初始化為arrayList

核心方法

/**
trim就是去除兩段空格的意思，這個方法是用來給elementdata瘦身用，將占據(jù)的多余的空間給釋放掉
*/
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

/**
確保容器容量，若為空,minCapacity去當(dāng)前值和默認(rèn)容量的最大值，然后判斷是否進(jìn)行擴(kuò)容
*/
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

/**
minCapacity大于數(shù)組長度，則調(diào)用grow函數(shù)進(jìn)行擴(kuò)容
*/
private void ensureExplicitCapacity(int minCapacity) {
        /**
        modCount:是父類AbstractList的變量。集合中所有用到modCount的都是線程不安全的。在做對線性表結(jié)構(gòu)修改的操作會對modCount進(jìn)行+1，當(dāng)我們調(diào)用iterator，會檢測modCount是不是我們期望的，如果在調(diào)用期間modCount又發(fā)生了變化，iterator將拋出異常.
        */
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

/**
獲取到數(shù)組長度，對其進(jìn)行擴(kuò)容，增加將近一半的容量，使用Arrays.copyOF進(jìn)行擴(kuò)容
*/
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);
    }

//返回容器元素個數(shù)
public int size() {
        return size;
    }

//判斷是否為空
public boolean isEmpty() {
        return size == 0;
    }

/**
兩個方法都是判斷索引正否越界
*/
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

/**
* 此方法用戶往線性表最后一位插入元素，若容器容量足夠，則時間復(fù)雜度是O（1），若需要擴(kuò)容，則時間復(fù)雜度是O（n）
*/
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
/**
* 此方法用于向指定位置插入元素，時間復(fù)雜度為O(n)
*    1.判斷角標(biāo)是否越界  2.保證數(shù)組容量足夠，不夠通過新建數(shù)組擴(kuò)容 3.從數(shù)組指定索引復(fù)制直到最后一位，全*部加一
*/
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++;
    }

//刪除制定索引元素，需算出位移量，將index之后的其他元素提前一位，其復(fù)雜度為o(n)
public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        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

        return oldValue;
    }
    //遍及elementData，若值相同，則調(diào)用fastRemove移除
    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;
    }
    //此方法和remove大致相同，只是少了判斷索引越界的問題，因為在被調(diào)用前已經(jīng)通過遍歷方式驗證了
    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
    }

迭代器

什么是迭代器呢？其實就是用來遍歷容器內(nèi)部分或全部元素的對象，每個迭代器代表容器中確定的地址，我們把具有類似行為的都叫迭代器。雖然迭代器不常用，但是里面的一些知識點，設(shè)計模式我們還是要學(xué)習(xí)以下的。arraylist迭代器分為Iterator和ListIterator。Iterator接口只定義了遍歷和刪除的職責(zé)，ListIterator繼承于Iterator,新增了add和set方法，方便我們在迭代的時候增加刪除元素。需要注意的是，在使用迭代器期間，若使用非迭代器對容器進(jìn)行數(shù)據(jù)結(jié)構(gòu)上的改變，將會通過checkForComodification()報錯。

ListIterator的實現(xiàn)如下:

private class ListItr extends Itr implements ListIterator {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

總結(jié)

arraylist源碼方法實在是過多，無法一一向大家解釋，不過相信大家理解上面的，再去研究剩下的內(nèi)容應(yīng)該沒有多大問題。通過學(xué)習(xí)源碼，我們可以更清楚的知道arraylist在操作時，底層結(jié)構(gòu)發(fā)生了哪些變化，為什么arraylist適合存取，不適合增刪.