摘要：隨機(jī)訪問數(shù)據(jù)是相對(duì)于順序訪問數(shù)據(jù)而言，例如鏈表的形式。方法將容器中的元素轉(zhuǎn)化為數(shù)組的形式。在函數(shù)中，對(duì)容量每次擴(kuò)展的大小，并且會(huì)檢查是否會(huì)超過設(shè)定的最大數(shù)組長度。如果長度超過了限定值，則以原容量為底線，返回一個(gè)最大容量。

ArrayList繼承自AbstractList，AbstractList為“random access”的數(shù)組提供了基本的實(shí)現(xiàn)。隨機(jī)訪問數(shù)據(jù)是相對(duì)于順序訪問數(shù)據(jù)而言，例如鏈表的形式。AbstractSequentialList為鏈表形式的順序訪問提供了基本實(shí)現(xiàn)。AbstractList提供了默認(rèn)的隨機(jī)訪問數(shù)據(jù)的iterator。AbstractList繼承自AbstractCollection，AbstractCollection為Collection提供了基本實(shí)現(xiàn)。

java.util.AbstractCollection

AbstractCollection實(shí)現(xiàn)了查詢是否包含某一個(gè)元素的方法。最好使用Iterator遍歷集合中的元素，因?yàn)榭梢云帘渭蟽?nèi)部元素存儲(chǔ)的具體實(shí)現(xiàn)，并且根據(jù)不同的數(shù)據(jù)存儲(chǔ)特點(diǎn)，優(yōu)化訪問策略。這里還可以正確查找null元素，需要注意的是對(duì)null元素的查詢需要特別的處理，有時(shí)候自己實(shí)現(xiàn)方法時(shí)，往往會(huì)忽略傳入?yún)?shù)為null時(shí)的處理，導(dǎo)致方法無法處理特殊情況。

    public boolean contains(Object o) {
        Iterator it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

toArray方法將容器中的元素轉(zhuǎn)化為數(shù)組的形式。這里元素的復(fù)制，采用的是直接復(fù)制引用。這里還考慮到了并發(fā)運(yùn)算時(shí)，元素?cái)?shù)量在復(fù)制時(shí)產(chǎn)生變化的情況，當(dāng)數(shù)量減少時(shí)，就用Arrays.copy()截取結(jié)果。當(dāng)數(shù)量增加時(shí)，會(huì)調(diào)用finishToArray函數(shù)擴(kuò)容。

    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

在finishToArray函數(shù)中，對(duì)容量每次擴(kuò)展1/2+1的大小，并且會(huì)檢查是否會(huì)超過設(shè)定的最大數(shù)組長度MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。如果長度超過了限定值，則以原容量+1為底線，返回一個(gè)最大容量。最后返回的數(shù)組也會(huì)修剪掉多余的位置。

    private static  T[] finishToArray(T[] r, Iterator it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // overflow-conscious code
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                ("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

這里有一個(gè)toArray的重載，需要傳入一個(gè)數(shù)組作為參數(shù)，據(jù)我觀察，目的是將集合中的元素存入指定的數(shù)組，重利用已有數(shù)組的存儲(chǔ)。如果元素過多，而目標(biāo)數(shù)組容納不下，只能重新申請(qǐng)數(shù)組來進(jìn)行存儲(chǔ)。

    public  T[] toArray(T[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a == r) {
                    //利用的原數(shù)組，且元素不足，則補(bǔ)null表示結(jié)束
                    r[i] = null; // null-terminate
                } else if (a.length < i) {
                    //元素較少，但數(shù)量超過原始數(shù)組，只能用新數(shù)組
                    return Arrays.copyOf(r, i);
                } else {
                    //元素減少，導(dǎo)致原始數(shù)組可以容納下，則copy回原始數(shù)組，折騰唄
                    System.arraycopy(r, 0, a, 0, i);
                    if (a.length > i) {
                        a[i] = null;
                    }
                }
                return a;
            }
            r[i] = (T)it.next();
        }
        // more elements than expected
        return it.hasNext() ? finishToArray(r, it) : r;
    }

removeAll方法刪除目標(biāo)集合中的所有重疊元素。Iterator可以做到在遍歷時(shí)，安全的刪除元素，而通過index循環(huán)刪除則可能導(dǎo)致index偏移。

    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

AbstractCollection的toString實(shí)現(xiàn)，比較令我震驚的是e == this的作用。這里為什么要判斷打印的內(nèi)容是否為自己本身？因?yàn)?b>sb.append(e == this ? "(this Collection)" : e);會(huì)調(diào)用e的toString函數(shù)來生成字符串，若不加判斷，則會(huì)形成無限的toString遞歸調(diào)用。我猜想一下，估計(jì)當(dāng)時(shí)toString的實(shí)現(xiàn)者沒有注意到該問題的存在，直到該bug出現(xiàn)，腦洞不大還真難想起來這個(gè)問題。

    public String toString() {
        Iterator it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append("]").toString();
            sb.append(",").append(" ");
        }
    }