ArrayList源碼分析--jdk1.8

JDK1.8

ArrayList源碼分析--jdk1.8
LinkedList源碼分析--jdk1.8
HashMap源碼分析--jdk1.8
AQS源碼分析--jdk1.8
ReentrantLock源碼分析--jdk1.8

ArrayList概述

??1. ArrayList是可以動態(tài)擴容和動態(tài)刪除冗余容量的索引序列，基于數(shù)組實現(xiàn)的集合。
??2. ArrayList支持隨機訪問、克隆、序列化，元素有序且可以重復(fù)。
??3. ArrayList初始默認(rèn)長度10，超出擴容1.5倍，使用Object[]存儲各種數(shù)據(jù)類型。

ArrayList數(shù)據(jù)結(jié)構(gòu)

??數(shù)據(jù)結(jié)構(gòu)是集合的精華所在，數(shù)據(jù)結(jié)構(gòu)往往也限制了集合的作用和側(cè)重點，了解各種數(shù)據(jù)結(jié)構(gòu)是我們分析源碼的必經(jīng)之路。
??ArrayList的數(shù)據(jù)結(jié)構(gòu)如下：

ArrayList源碼分析

/*
 * 用數(shù)組實現(xiàn)的集合，支持隨機訪問，元素有序且可以重復(fù)
 * RandomAccess(ArrayList) 支持快速隨機訪問，使用for循環(huán)更加快速
 * LinkedList 使用 iterator迭代器更加 快速
 * RandomAccess 這是一個標(biāo)記接口，一般此標(biāo)記接口用于 List 實現(xiàn)，以表明它們支持快速（通常是恒定時間）的隨機訪問。
 * 該接口的主要目的是允許通用算法改變其行為，以便在應(yīng)用于隨機或順序訪問列表時提供良好的性能
 * 包含類中的基礎(chǔ)屬性和3個構(gòu)造方法
 */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 /**
     * 默認(rèn)長度  10
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 默認(rèn)空的數(shù)組
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * ArrayList中的元素  是Object[]類型的數(shù)組
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * 動態(tài)數(shù)組的實際大小 ，默認(rèn)為0
     * @serial
     */
    private int size;
     /**
     * 最大數(shù)組容量2147483639
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * 集合長度構(gòu)造函數(shù)
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    /**
     * 無參構(gòu)造函數(shù)，設(shè)置元素數(shù)組為空 注意此時初始容量是0，而不是大家以為的 10
     */
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    /**
     * 集合參數(shù)構(gòu)造函數(shù)
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); // 轉(zhuǎn)化為數(shù)組
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class) //是否成功轉(zhuǎn)化為Object類型數(shù)組
            elementData = Arrays.copyOf(elementData, size, Object[].class); //不為Object數(shù)組的話就進行復(fù)制
    }

ArrayList繼承和實現(xiàn)分析

?? ArrayList extends AbstractList
?? AbstractList extends AbstractCollection
??java中所有類都繼承Object，所以ArrayList的繼承結(jié)構(gòu)如上圖。
?? 1. AbstractList是一個抽象類，實現(xiàn)了List<E>接口，List<E>定義了一些List通用方法，而AbstractList抽象類中可以有抽象方法，還可以有具體的實現(xiàn)方法，AbstractList實現(xiàn)接口中一些通用的方法，實現(xiàn)了基礎(chǔ)的add/get/indexOf/iterator/subList/RandomAccessSubList方法，ArrayList再繼承AbstractList，拿到通用基礎(chǔ)的方法，然后自己在實現(xiàn)一些自己特有的方法，這樣的好處是：讓代碼更簡潔，繼承結(jié)構(gòu)最底層的類中通用的方法，減少重復(fù)代碼。
?? 2.ArrayList實現(xiàn)了List<E>、RandomAccess、Cloneable、Serializable接口
?? ??1)List<E>接口，ArrayList既然繼承自AbstractList抽象類，而AbstractList已 經(jīng)實現(xiàn)了List接口，那么ArrayList類為何還要再實現(xiàn)List接口呢？我們帶著疑問往下看：

public class Demo1 extends ArrayList {
    public static void main(String[] args) {
                //返回[]
        System.out.println(Arrays.toString(Demo1.class.getInterfaces()));
    }
public class Demo2 implements Serializable {
    public static void main(String[] args) {
                //返回[interface java.io.Serializable]
        System.out.println(Arrays.toString(Demo2.class.getInterfaces()));
    }
public class Test{
    public static void main(String[] args) {
                Serializable c1 = new Demo1();//未顯示實現(xiàn)接口
                Serializable c2 = new Demo2();//顯示實現(xiàn)接口
                Serializable proxy2 = createProxy(c2);
                proxy2.foo();
                Serializable proxy1 = createProxy(c1);
                proxy1.foo();
 }

private static <T> T createProxy(final T obj) {
        final InvocationHandler handler = new InvocationHandler() {
            @Override
            public Object invoke(Object proxy, Method method, Object[] args)
                    throws Throwable {
                return method.invoke(obj, args);
            }
        };
                //實現(xiàn)接口代理，Demo1報錯，Demo2成功
                //java.lang.ClassCastException: $Proxy1 cannot be cast to
                //example.Test$Serializable
        return (T) Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj
                .getClass().getInterfaces(), handler);
    }

可以看出這樣這樣設(shè)計是有道理的，因此，這并不是一個錯誤，很可能是作者Josh Bloch為了便于實現(xiàn)代理而精心設(shè)計的。
參考與：開發(fā)collection 的作者Josh說
?? ??2)RandomAccess接口，這是一個標(biāo)記接口，一般此標(biāo)記接口用于 List 實現(xiàn)，以表明它們支持快速（通常是恒定時間）的隨機訪問，該接口的主要目的是允許通用算法改變其行為，以便在應(yīng)用于隨機或順序訪問列表時提供良好的性能，實現(xiàn)了該接口的話使用普通的for循環(huán)來遍歷，性能更高，而沒有實現(xiàn)該接口的話，使用Iterator來迭代，這樣性能更高，例如linkedList。所以這個標(biāo)記性只是為了讓我們知道我們用什么樣的方式去獲取數(shù)據(jù)性能更好
?? ??3)Cloneable接口，可以使用Object.Clone()方法。
?? ??4)Serializable接口，序列化接口，表明該類可以被序列化，什么是序列化？簡單的說，就是能夠從類變成字節(jié)流傳輸，反序列化，就是從字節(jié)流變成原來的類

ArrayList核心方法分析

1. add方法(4種重載實現(xiàn))--增?? ?

?? ??1)add(E)；//默認(rèn)直接在末尾添加元素

/**
 * 新增元素
 */
public boolean add(E e) {
    //賦值初始長度  或者擴容,新增元素，當(dāng)前實際size+1的長度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加元素
        elementData[size++] = e;
        return true;
}
    /**
     * 確保elemenData數(shù)組有合適的大小
     * 如果元素為空，則復(fù)制長度默認(rèn)為10 或者更大
    * @author jiaxiaoxian
    * @date 2019年2月12日 
     */
    private void ensureCapacityInternal(int minCapacity) {
            if (elementData == EMPTY_ELEMENTDATA) {//如果數(shù)組為空，則從size+1的值和默認(rèn)值10中取最大的
                    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
    }
/**
* 確保elemenData數(shù)組有合適的大小
* @author jiaxiaoxian
* @date 2019年2月12日 
* 如果長度大于元素長度則擴容
 */
private void ensureExplicitCapacity(int minCapacity) {
    //記錄修改次數(shù)，迭代中不一致會觸發(fā)fail-fast機制,因此在遍歷中刪除元素的正確做法應(yīng)該是使用Iterator.remove()
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); //擴容
}
/**
 * 擴容
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length; // 舊容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為舊容量的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于參數(shù)指定容量，修改新容量
        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);
}
    //如果小于0 就報錯，如果大于最大值 則取最大值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

?? ??2)add(int index, E element)；//給指定下標(biāo)，添加元素

/**
 * 給指定下標(biāo)，添加元素
 */
public void add(int index, E element) {
    //判斷下標(biāo)是否越界
    rangeCheckForAdd(index);
    //賦值初始長度  或者擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //將源數(shù)組中從index位置開始后的size-index個元素統(tǒng)一后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //賦值
    elementData[index] = element;
    size++;
}
/**
 * 判斷下標(biāo)是否越界
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 *     src:源數(shù)組
 * 　　srcPos:源數(shù)組要復(fù)制的起始位置
 * 　　dest:目的數(shù)組
 * 　　destPos:目的數(shù)組放置的起始位置
 * 　　length:復(fù)制的長度
 * 　　注意：src 和 dest都必須是同類型或者可以進行轉(zhuǎn)換類型的數(shù)組
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

?? ??3)addAll(Collection<? extends E> c)；//添加Collection類型元素

/**
 * 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //將數(shù)組a[0,...,numNew-1]復(fù)制到數(shù)組elementData[size,...,size+numNew-1]
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

?? ??4)addAll(int index, Collection<? extends E> c)；//指定位置，添加Collection類型元素

/**
 * 從指定的位置開始，將指定collection中的所有元素插入到此列表中，新元素的順序為指定collection的迭代器所返回的元素順序
 */
public boolean addAll(int index, Collection<? extends E> c) {
    //判斷下標(biāo)是否越界
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    int numMoved = size - index;
    //先將數(shù)組elementData[index,...,index+numMoved-1]復(fù)制到elementData[index+numMoved,...,index+2*numMoved-1]
    //即，將源數(shù)組中從index位置開始的后numMoved個元素統(tǒng)一后移numNew位
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

總結(jié)：
? ?正常情況下會擴容1.5倍，特殊情況下（新擴展數(shù)組大小已經(jīng)達到了最大值）則只取最大值。
? ?

2.remove方法(4種重載實現(xiàn))--刪

?? ??1)remove(int index); //根據(jù)指定下標(biāo) 刪除元素?? ??

/**
 * 根據(jù)指定下標(biāo) 刪除元素
 */
public E remove(int index) {
    //判斷索引是否越界
    rangeCheck(index);
    modCount++;
    //獲取舊元素
    E oldValue = elementData(index);
    //將數(shù)組elementData中index位置之后的所有元素向前移一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //將原數(shù)組最后一個位置置為null，由GC清理
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}   ?  ?

?? ??2)remove(Object o); //根據(jù)指定元素 刪除元素?

 /**
 * 移除ArrayList中首次出現(xiàn)的指定元素(如果存在)，ArrayList中允許存放重復(fù)的元素
 */
public boolean remove(Object o) {
    // 由于ArrayList中允許存放null，因此下面通過兩種情況來分別處理。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //私有的移除方法，跳過index參數(shù)的邊界檢查以及不返回任何值
                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)快速刪除元素
 */
private void fastRemove(int index) {
    modCount++;
    //將數(shù)組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
}
 /**
 * 清空ArrayList，將全部的元素設(shè)為null，等待垃圾回收將這個給回收掉，所以叫clear
 */
public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

?

?? ??3)removeAll(Collection<?> c); //刪除包含在指定容器c中的所有元素?

/**
 * 刪除ArrayList中包含在指定容器c中的所有元素
 */
public boolean removeAll(Collection<?> c) {
    //檢查指定的對象c是否為空
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
 /**
 * 刪除全部
* @author jiaxiaoxian
* @date 2019年2月12日 
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0; //讀寫雙指針
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement) //判斷指定容器c中是否含有elementData[r]元素
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

?? ??4)removeIf(Predicate<? super E> filter); //按照一定規(guī)則過濾(刪除)集合中的元素?

/**
 * 按照一定規(guī)則過濾(刪除)集合中的元素
 * 如：idList.removeIf(id -> id == nul);
    *   去掉 List idList 集合中id 為 null 的
 * @param filter
 * @return
 */
@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

總結(jié)：
? ?remove函數(shù)用戶移除指定下標(biāo)的元素，此時會把指定下標(biāo)到數(shù)組末尾的元素向前移動一個單位，并且會把數(shù)組最后一個元素設(shè)置為null，這樣是為了方便之后將整個數(shù)組不被使用時，會被GC，可以作為小的技巧使用。

3.set方法--改

/**
 * 覆蓋指定下標(biāo)元素
 */
public E set(int index, E element) {
    //判斷索引是否越界
    rangeCheck(index);
    //獲取舊元素
    E oldValue = elementData(index);
    //覆蓋為新元素
    elementData[index] = element;
    //返回舊元素
    return oldValue;
}
/**
 * 判斷下標(biāo)是否越界
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.get方法--查

 /**
 * 返回指定索引的值
 */
public E get(int index) {
    //判斷索引是否越界
    rangeCheck(index);
    return elementData(index);
}
/**
* @author jiaxiaoxian
* @date 2019年2月12日 
* 返回下標(biāo)元素的 值
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

5.indexOf方法--查找下標(biāo)

/**
 * 查找下標(biāo)， 如果為null,直接和null比較，返回下標(biāo)
 */
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;
}
/**
 * 查找最后出現(xiàn)的下標(biāo)，從大往下循環(huán)查找
 */
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

6.clone方法--克隆

 /**
 * 復(fù)制，返回此ArrayList 的淺拷貝
 */
public Object clone() {
    try {
        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);
    }
}

7.trimToSize方法--刪除冗余容量

/**
 * 判斷數(shù)據(jù)實際容量大小，刪除自動增長后冗余的容量
 * 該方法用于回收多余的內(nèi)存。也就是說一旦我們確定集合不在添加多余的元素之后，調(diào)用 trimToSize() 方法會將實現(xiàn)集合的數(shù)組大小剛好調(diào)整為集合元素的大小。
 * 　　注意：該方法會花時間來復(fù)制數(shù)組元素，所以應(yīng)該在確定不會添加元素之后在調(diào)用
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

8.Itr內(nèi)部類--類似Iterator，可以幫我們對List進行遍歷，增刪改查等

/**
 * 實例化一個Itr對象，并返回
 */
public Iterator<E> iterator() {
    return new Itr();
}

/**
 * 內(nèi)部類，類似Iterator，可以幫我們對List進行遍歷，增刪改查等
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return 下一個元素
    int lastRet = -1; // index of last element returned; -1 if no such 當(dāng)前元素
    int expectedModCount = modCount; //modCount，就是為了判斷是否有多個線程訪問修改

    public boolean hasNext() {
        return cursor != size;
    }

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

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

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}   

9.ListItr內(nèi)部類--繼承了內(nèi)部類Itr，還在此基礎(chǔ)上增加了向前遍歷，增加元素，更改元素內(nèi)容等功能

/**
 * 這個類繼承了內(nèi)部類Itr
 * 除了擁有上一個類的功能，還增加了向前遍歷，增加元素，更改元素內(nèi)容等功能
 */
private class ListItr extends Itr implements ListIterator<E> {
    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();
        }
    }
}   

10.SubList內(nèi)部類--基于ArrayList建一個子集類

/**
 * 雖然這個類很長，其實里面的大部分方法調(diào)用都是ArrayList中的
 * ListIterator在這個類中采用匿名內(nèi)部類做了一點更改，不過也很類似
 * 畢竟這個類就是根據(jù)ArrayList建一個子集類，就不贅述了
 */
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) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
         // 檢驗索引是否合法
        rangeCheck(index);
        //實現(xiàn)fail-fast機制  (迭代中不允許操作增刪改)
        checkForComodification();
        // 舊值
        E oldValue = ArrayList.this.elementData(offset + index);
        // 賦新值
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }

    public E get(int index) {
         // 檢驗索引是否合法
        rangeCheck(index);
        //實現(xiàn)fail-fast機制  (迭代中不允許操作增刪改)
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }

    public int size() {
        checkForComodification();
        return this.size;
    }

    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        parent.removeRange(parentOffset + fromIndex,
                           parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);
        final int offset = this.offset;

        return new ListIterator<E>() {
            int cursor = index;
            int lastRet = -1;
            int expectedModCount = ArrayList.this.modCount;

            public boolean hasNext() {
                return cursor != SubList.this.size;
            }

            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= SubList.this.size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[offset + (lastRet = i)];
            }

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

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

            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
                Objects.requireNonNull(consumer);
                final int size = SubList.this.size;
                int i = cursor;
                if (i >= size) {
                    return;
                }
                final Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
                    consumer.accept((E) elementData[offset + (i++)]);
                }
                // update once at end of iteration to reduce heap write traffic
                lastRet = cursor = i;
                checkForComodification();
            }

            public int nextIndex() {
                return cursor;
            }

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

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

                try {
                    SubList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

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

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

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

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

            final void checkForComodification() {
                if (expectedModCount != ArrayList.this.modCount)
                    throw new ConcurrentModificationException();
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+this.size;
    }

    /**
     * 實現(xiàn)fail-fast機制 
     * 線程不安全    迭代中不允許修改
    * @author jiaxiaoxian
    * @date 2019年2月12日 
     */
    private void checkForComodification() {
        if (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }

    public Spliterator<E> spliterator() {
        checkForComodification();
        return new ArrayListSpliterator<E>(ArrayList.this, offset,
                                           offset + this.size, this.modCount);
    }
}

11.ArrayListSpliterator內(nèi)部類--并行迭代，基于索引的二分裂，懶惰初始化的Spliterator

/**
 * @since 1.8
 * 實例化一個ArrayListSpliterator對象，并返回
 */
@Override
public Spliterator<E> spliterator() {
    return new ArrayListSpliterator<>(this, 0, -1, 0);
}

/**
 * Index-based split-by-two, lazily initialized Spliterator
 * 并行迭代
 * 基于索引的二分裂，懶惰初始化的Spliterator
 * */
static final class ArrayListSpliterator<E> implements Spliterator<E> {

    private final ArrayList<E> list;
    private int index; // current index, modified on advance/split
    private int fence; // -1 until used; then one past last index
    private int expectedModCount; // initialized when fence set

    /** Create new spliterator covering the given  range */
    ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                         int expectedModCount) {
        this.list = list; // OK if null unless traversed
        this.index = origin;
        this.fence = fence;
        this.expectedModCount = expectedModCount;
    }

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

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

    public boolean tryAdvance(Consumer<? super E> 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;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        int i, hi, mc; // hoist accesses and checks from loop
        ArrayList<E> lst; Object[] a;
        if (action == null)
            throw new NullPointerException();
        if ((lst = list) != null && (a = lst.elementData) != null) {
            if ((hi = fence) < 0) {
                mc = lst.modCount;
                hi = lst.size;
            }
            else
                mc = expectedModCount;
            if ((i = index) >= 0 && (index = hi) <= a.length) {
                for (; i < hi; ++i) {
                    @SuppressWarnings("unchecked") E e = (E) a[i];
                    action.accept(e);
                }
                if (lst.modCount == mc)
                    return;
            }
        }
        throw new ConcurrentModificationException();
    }

    public long estimateSize() {
        return (long) (getFence() - index);
    }

    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}

ArrayList總結(jié)

1）ArrayList可以存放null，本質(zhì)是Object[]類型的數(shù)組。
2）ArrayList區(qū)別于數(shù)組的地方在于能夠自動擴展大小，其中關(guān)鍵的方法就是gorw()方法。
3）ArrayList由于本質(zhì)是數(shù)組，所以它在數(shù)據(jù)的查詢方面會很快，而在插入刪除這些方面，性能下降很多，
有移動很多數(shù)據(jù)才能達到應(yīng)有的效果，而LinkedList則相反。
4）ArrayList實現(xiàn)了RandomAccess，所以在遍歷它的時候推薦使用for循環(huán)。
5）初始化數(shù)組時推薦給初始長度，反復(fù)擴容會增加時耗，影響性能效率。
6)   Arrays工具類用來處理數(shù)組的工具類，Arrays.asList()方法返回的 ArrayList 數(shù)組是一個定長列表，
7)   我們只能對其進行查看或者修改，但是不能進行添加或者刪除操作，不能執(zhí)行影響長度的操作，
8)   因為此ArrayList是Arrays中內(nèi)部靜態(tài)類，只實現(xiàn)了部分查看修改方法，添加和刪除方法是
9)   繼承AbstractList父類的空方法，此ArrayList非彼ArrayList。