Java容器類研究4：ArrayList

xfee 發(fā)布于2019-08-15 12:08 / 2347人閱讀

摘要：顯然，開發(fā)人員認(rèn)為通過下標(biāo)遍歷的數(shù)組結(jié)構(gòu)更加高效。在進(jìn)行分裂時(shí)，原始保留中部至末尾的元素，新的保留原起始位置到中部的元素。同樣，也會(huì)進(jìn)行重新賦值，使得在使用前與保持一致。在遍歷時(shí)，會(huì)調(diào)用方法，將動(dòng)作施加于元素之上。

java.util.ArrayList

ArrayList繼承自AbstractList，AbstractList為隨機(jī)訪問數(shù)據(jù)的結(jié)構(gòu)，如數(shù)組提供了基本實(shí)現(xiàn)，并且提供了Iterator。首先看AbstractList實(shí)現(xiàn)了什么方法。

AbstractList AbstractList里可以存儲(chǔ)null嗎

null可以作為一項(xiàng)存儲(chǔ)在ArrayList中。ListIterator是遍歷訪問AbstractList中元素較好的方式，需要注意獲取元素序號(hào)的方法是previousIndex，而不是nextIndex，因?yàn)橹坝衝ext方法的調(diào)用。還有，這里判斷兩個(gè)元素是否相等采用的是equals方法，而不是==。

 public int indexOf(Object o) {
        ListIterator it = listIterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

ListIterator可以逆序訪問元素

從后向前遍歷AbstractList，過程恰恰相反。

 public int lastIndexOf(Object o) {
        ListIterator it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }

Iterator遍歷元素時(shí)，被其它線程修改了怎么辦

如果在使用Iterator時(shí)，有其他線程嘗試去修改List的大小，會(huì)被發(fā)現(xiàn)且立即拋出異常。

可以看class Itr implements Iterator中，有屬性int expectedModCount = modCount;記錄著期望的數(shù)組大小，如果不一致，會(huì)拋出ConcurrentModificationException。

Iterator在AbstractList中如何實(shí)現(xiàn)的

有兩個(gè)游標(biāo)分別記錄當(dāng)前指向的位置和上一次指向的位置。

       /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

如何處理遍歷過程中，刪除list中的元素導(dǎo)致的序號(hào)偏移

Iterator可以正確的刪除AbstractList中的元素，并且保證訪問的順序的正確性。

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

刪除的元素是上一個(gè)next調(diào)用后的元素，并且連續(xù)調(diào)用兩次remove會(huì)拋出異常，因?yàn)樵刂荒軇h除一次，上次指向的元素已經(jīng)沒有了。

ListIterator可以添加元素

在class ListItr extends Itr implements ListIterator中實(shí)現(xiàn)了向list添加元素的方法。添加的位置是上一次next返回的元素之后，下一個(gè)next之前。

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

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

ArrayList ArrayList用什么來(lái)存儲(chǔ)元素

就是用了一個(gè)簡(jiǎn)單的數(shù)組。。。

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

如何節(jié)約ArrayList占用的空間

使用trimToSize函數(shù)，將原始數(shù)組copy到適合大小的數(shù)組中。

/**
     * Trims the capacity of this ArrayList instance to be the
     * list"s current size.  An application can use this operation to minimize
     * the storage of an ArrayList instance.
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

用Iterator遍歷ArrayList真的高效嗎

不可否認(rèn)，Iterator為遍歷一個(gè)集合提供了統(tǒng)一的接口，用戶可以忽略集合內(nèi)部的具體實(shí)現(xiàn)，但是過多的封裝會(huì)導(dǎo)致效率的降低。顯然，Java開發(fā)人員認(rèn)為通過下標(biāo)遍歷ArrayList的數(shù)組結(jié)構(gòu)更加高效。所以重寫了indexOf和lastIndexOf。

    public int indexOf(Object o) {
        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;
    }

ArrayList的clone是淺copy

ArrayList只是新建了數(shù)組，copy了元素的引用，元素本身沒有進(jìn)行copy。clone方法為什么不new一個(gè)ArrayList對(duì)象，而是調(diào)用了Object類的clone？因?yàn)镺bject的clone函數(shù)是native的，更高效。

/**
     * Returns a shallow copy of this ArrayList instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this ArrayList instance
     */
    public Object clone() {
        try {
            //使用Object的clone獲得一個(gè)對(duì)象
            ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn"t happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

ArrayList存儲(chǔ)空間的擴(kuò)展策略

如果list初始沒有元素，使用一個(gè)靜態(tài)的空數(shù)組。元素增加時(shí)，空間擴(kuò)展為默認(rèn)的10。在后續(xù)的擴(kuò)展過程中，容量會(huì)每次增加原始大小的1/2。

ArrayList實(shí)現(xiàn)了自己的iterator

雖然AbstractList實(shí)現(xiàn)了iterator，但ArrayList似乎不太滿意，又重新實(shí)現(xiàn)了一遍。主要區(qū)別就是在獲取元素時(shí)，利用了數(shù)組結(jié)構(gòu)的優(yōu)勢(shì)，可以直接通過下標(biāo)獲取元素，而不必通過調(diào)用方法。

用Spliterator分割遍歷ArrayList

ArrayList理所當(dāng)然的實(shí)現(xiàn)了自己的Spliterator，也就是ArrayListSpliterator。分割的策略簡(jiǎn)而言之為：二分+延遲初始化。

ArrayListSpliterator有如下屬性:

this.list = list; // OK if null unless traversed 保存目標(biāo)list
this.index = origin; //起始位置
this.fence = fence;  //終止位置
this.expectedModCount = expectedModCount;  //期望修改次數(shù)，用來(lái)判斷運(yùn)行時(shí)是否有其它線程修改

每次從中間開始分裂。在進(jìn)行分裂時(shí)，原始spliterator保留中部至末尾的元素，新的spliterator保留原起始位置到中部的元素。

        public ArrayListSpliterator trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                new ArrayListSpliterator(list, lo, index = mid,
                                            expectedModCount);
        }

在第一次創(chuàng)建spliterator時(shí)，fence被初始為-1，所以在實(shí)際使用spliterator時(shí)，getFence才會(huì)被調(diào)用，從而fence才會(huì)被賦值為數(shù)組大小。同樣，expectedModCount也會(huì)進(jìn)行重新賦值，使得spliterator在使用前與list保持一致。

         private int getFence() { // initialize fence to size on first use
            int hi; // (a specialized variant appears in method forEach)
            ArrayList lst;
            if ((hi = fence) < 0) {
                if ((lst = list) == null)
                    hi = fence = 0;
                else {
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }

在遍歷list時(shí)，會(huì)調(diào)用方法tryAdvance，將動(dòng)作施加于元素之上。該方法會(huì)檢查是否有其它線程的修改，在ArrayList中，有大量方法都會(huì)使用modCount來(lái)記錄修改，或者判斷是否在方法執(zhí)行時(shí)有其它線程的修改，目前看來(lái)，用這個(gè)方法來(lái)檢測(cè)是否有并行修改使得list結(jié)構(gòu)變化是有效的，可以避免并行修改帶來(lái)的一些問題。

        public boolean tryAdvance(Consumer action) {
            if (action == null)
                throw new NullPointerException();
            int hi = getFence(), i = index;
            if (i < hi) {
                index = i + 1;
                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }