天天看點
傳回

ArrayList jdk1.8源碼分析

ArrayList父類關系

ArrayList繼承AbstractList抽象類，實作了List，RandomAccess，Cloneable，Seriazable四個接口。

RandomAccess，Cloneable，Seriazable是标記接口，本身沒有内容。

RandomAccess用于标明實作該接口的List支援快速随機通路，主要目的是使算法能夠在随機和順序通路的list中表現的更加高效。

Cloneable 用于允許使用clone()方法進行克隆。

Seriazable 用于類可以實作序列化。

ArrayList成員變量

ArrayList本身有七個成員變量，還有AbstractList的成員變量 modCount。

1 serialVersionUID

2 DEFAULT_CAPACITY

3 EMPTY_ELEMENTDATA

4 DEFALUTCAPACITY_EMPTY_ELEMENTDATA

5 elementData

6 size

7 MAX_ARRAY_SIZE

serialVersionUID：序列化id，私有靜态不可變長整型（private static final long）

DEFAULT_CAPACITY：預設ArrayList大小，預設大小為10, 私有靜态不可變整型(private static final int)。

EMPTY_ELEMENTDATA:空執行個體，預設為{}，私有靜态不可變對象數組（private static final Object[]。構造方法帶參的時候，指派給elementData，即ArrayList(int initialCapacity)和ArrayList(Collection<? Extend E> c)。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA:采用ArrayList預設大小10建立的空執行個體，為{}。與EMPTY_ELEMENTDATA差別就是，後者知道初始化大小，前者初始化大小固定為10。

elementData:對象數組，用來存儲真正的資料，protected transient Object[],transient無法被序列化。

Size:Arraylist包含元素數量，不是ArrayList的長度，私有整形（private int）。

modCount:protected transien int,初始化大小為0，修改ArrayList的次數。

MAX_ARRAY_SIZE：ArrayList最大長度，為Integer最大值減去8。私有靜态不可變整型(private static final int)。

ArrayList構造方法

1 public ArrayList(int initialCapacity)

如果initialCapacity大于0，根據給定的清單大小，建立一個指定大小的清單。

如果initialCapacity等于0，則将EMPTY_ELEMENTDATA空清單指派給elementData。

如果initialCapacity小于0，則抛出IllegalArgumentException參數非法異常。

if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }

2 public ArryList()

将DEFAULTCAPACITY_EMPTY_ELEMENTDATA空清單指派給elementData。

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

3  public ArrayList(Collection<? Extends E> c)

根據給定的集合建立清單。

将給定的集合數組化，即調用集合的toArray()方法。

将elementData的長度指派給size。

如果size不大于0，将EPMTY_ELEMENTDATA指派給elementData。

如果size大于0，判斷elementData是不是Object[]類型，是則調用Arrays.copyOf(elementData,size,Object[].class)指派給elementData。

ArrayList調用Arrays的copyOf方法,

根據size建立一個Object數組，再調用

System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength)),original為elementData,copy即為建立的Object[]，newLength為size。

System.arraycopy（Object src,int srcPos,Object dest,int destPos,int length）方法5個參數分别為要拷貝的原始資料，原始資料拷貝的起始序号，目标資料，目标資料的起始序号，要拷貝的長度。

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

Arrays的copy方法

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

ArrayList成員方法

Public Void trimToSize()：移除未使用已申請記憶體的元素

增加modcount。

如果size比element長度小

當size為0時，element就指派為EMPTY_ELEMENTDATA；

否則就使用Arrays.copy拷貝數組傳回，Arrays.copy(elementData,size)。

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

Public Void ensureCapacity(int minCapacity):以minCapacity作為ArrayList最小容量擴充。

如果elementData是一個空清單，則minExpand為ArrayList預設大小，否則為0。

如果minCapacity大于minExpand,則需要擴充ArrayList。調用ensureExplicitCapacity（int minCapacity）方法。

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

Private void ensureCapacityInternal(int minCapacity): 以minCapacity作為ArrayList最小容量擴充

如果elementData為空清單，minCapacity重新指派為DEFAULT_CAPACITY和minCapacity中的最大值。再調用ensureExplicitCapacity（int minCapacity）方法。

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

Private Void ensureExplicitCapacity（int minCapacity）:擴充ArrarList。

增加修改次數modConut,如果minCapacity大于elementData的長度，則需要擴充，調用grow（int minCapacity）方法。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

Private Void grow(int minCapacity)：根據minCapacity擴充ArrayList

oldCapacity用來存儲原始elementData大小。

newCapacity用來存儲新elementData大,為oldCapacity+oldCapacity>>1,即加上原來的一半，>>1位運算右移，原來資料的一半。

如果newCapacity小于minCapacity，則将newCapacity指派為minCapacity。

如果newCapacity大于MAX_ARRAY_SIZE,則将newCapacity指派為hugeCapacity（int minCapacity）傳回值。

最後elementData為Arrays.copyof(elementData,newCapacity)。

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

Private static int hugeCapacity(int minCapacity)：傳回list最大容量

如果minCapacity小于0，抛出OutOfMemoryError。

如果minCapacity大于MAX_ARRAY_SIZE,則傳回Integer.MAX_VALUE,否則傳回MAX_ARRAY_SIZE。

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

Public int size():傳回ArrayList大小。 

public int size() {
        return size;
    }

Public Boolean isEmpty():判斷ArrayList是否為空。 

public boolean isEmpty() {
        return size == 0;
    }

Public Boolean contains(Object object):傳回ArrayList是否包含指定對象

調用indexOf(Object object)方法，傳回是否大于等于0。

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

Public int indexOf(Object o):傳回指定對象在ArrayList中第一次出現的下标

下标從0開始。

如果o是null，則循環ArrayList循環從0開始，判斷elementData[i]==null（null元素不能使用equals方法，傳回空指針異常）找到傳回i;

否則o.equals(elementData[i])，相等傳回i。

如果沒找到相同對象，傳回-1。

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

Public int lastIndexOf(Object o):傳回指定對象在ArrayList中最後一次出現的下标。

下标從size-1開始。其他和indexOf方法相似，找到傳回下标，找不到傳回-1。

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

Public Object clone():實作ArrayList的淺拷貝。

super.clone()調用Object的clone方法，克隆ArrayList，指派給ArrayList<?> v。再調用Arrays.copyOf(elementData,size)指派給v.elementData,并把v的修改次數modCount置為0。

傳回v。

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

public Object[] toArray():将elementData資料以Object數組形式傳回

調用Arrays.copyOf(elementData,size)。

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

public <T> T[] toArray(T[] a):将elementData以指定參數的類型傳回數組。

如果a.length小于elementData的size，傳回(T[]) Arrays.copyOf(elementData, size, a.getClass())。

如果a.length不小于elementData的size，則直接調用System.arraycopy(elementData,0,a,0,size);

如果a.length大于elementData的size，則a[size]=null。

@SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

E elementData(int index):傳回指定下标的元素。

不對外暴露，傳回elementData[index]。

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

public E get(int index)：真正對外暴露的傳回指定下标的元素的方法。

首先調用rangeCheck(int index)方法，判斷index是否越界。

如果index不小于size,則抛出IndexOutOfBoundsException(outOfBoundsMsg(index))異常；

否則調用E elementData方法傳回指定下标元素。

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

public E set(int index, E element):對指定下标設值。

首先調用rangeCheck(int index)方法，判斷index是否越界。

如果index不小于size,則抛出IndexOutOfBoundsException(outOfBoundsMsg(index))異常；

否則調用E elementData方法傳回指定下标原始元素，再将指定新元素指派給指定下标，傳回原始元素。

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

public boolean add(E e)：增加元素。

調用ensureCapacityInternal方法，判斷數組容量是否夠，不夠就擴充。elementData[size++]=e;如果沒有異常傳回true。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

public void add(int index, E element)：指定下标添加元素。

首先調用rangeCheckForAdd(int index)，判斷index是否大于size或者小于0。調用ensureCapacityInternal方法，判斷數組容量是否夠，不夠就擴充。再調用System.arraycopy(elementData,index,elementData,index+1,size-index);elementData[index]=element;size++。

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

public E remove(int index)：根據下标移除元素。

首先調用rangeCheck方法，判斷index是否越界。

增加modCount，存儲下标原始資料oldValue。

numMoved為需要移動的資料數量，numMoved=size-index-1。

如果numMoved大于0，說明需要移動，調用System.arraycopy(elementData,index+1,elementData,index,numMoved);

再将elementData最後一個元素指派為null,利于gc回收。

elementData[--size]=null,傳回原始資料。

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

public boolean remove(Object o)：根據指定對象移除元素。

如果o為null,循環list,如果list中元素==null，則調用fastRemove(int index)方法，移除元素，傳回true；

否則循環list，使用equals方法比對元素，如果equals傳回true,則調用fastRemove(int index)方法移除元素，傳回true。

如果沒有找到相同元素，傳回false。

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

private void fastRemove(int index)：根據下标快速删除元素。

增加modCount。

numMoved為需要移動的資料數量，numMoved=size-index-1。

如果numMoved大于0，說明需要移動，調用System.arraycopy(elementData,index+1,elementData,index,numMoved);

再将elementData最後一個元素指派為null,利于gc回收，elementData[--size]=null。

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
    }

public void clear()：移除所有list元素。

增加modCount。

所有elementData的元素都指派為null,循環根據size，最後将size指派為0。

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

public boolean addAll(Collection<? extends E> c)：添加集合清單。

首先将集合c通過toArray()方法，轉成Object對象數組a。

numNew為增加的長度即為a.length。

調用ensureCapacityInternal（size+numNew）確定list長度。

調用System.arrayCopy(a,0,elementData,size,numNew)拷貝數組。

size+=numNew,傳回numNew!=0。

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

public boolean addAll(int index, Collection<? extends E> c)：指定下标位置添加集合清單。

首先調用rangeCheckForAdd(int index)，判斷index是否大于size或者小于0。将集合c通過toArray()方法，轉成Object對象數組a。

numNew為增加的長度即為a.length，調用ensureCapacityInternal（size+numNew）, numMoved=size-index。

如果numMoved大于0，說明需要移動。

調用System.arraycopy(elementData,index+1,elementData,index+numNew，numMoved)移動list，騰出位置。

再調用System.arraycopy(a,0,elementData,index,numNew);size+=numNew,傳回numNew!=0。

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

protected void removeRange(int fromIndex, int toIndex)：範圍删除元素。

ModCount++,numMoved為size-toIndex。

調用System.arraycopy(element,toIndex,elementData,fromIndex,numMoves)。

NewSize=size-(toIndex-fromIndex),循環list,循環從newSize到size結束，elementData[i]指派為null，利于gc回收，最後size指派為newSize。

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

private void rangeCheck(int index)：判斷index是否越界。

index不小于size時，抛出IndexOutOfBoundsException(outOfBoundsMsg(index));

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

private void rangeCheckForAdd(int index)：添加元素時判斷index是否越界。

index大于size或者index小于0時，抛出IndexOutOfBoundsException(outOfBoundsMsg(index))。

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

private String outOfBoundsMsg(int index)：傳回return "Index: "+index+", Size: "+size。

public boolean removeAll(Collection<?> c)：删除list中存在于集合中元素。

首先調用Objects.requiredNonNull(c)方法，判斷c是否為null，傳回batchRemove（c,false）。

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

public boolean retainAll(Collection<?> c)：保留list中存在于集合c中元素，即删除不在c中元素。

首先調用Objects.requiredNonNull(c)方法，判斷c是否為null，傳回batchRemove（c,true）。

public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

private boolean batchRemove(Collection<?> c, boolean complement):根據條件删除或保留數組元素。

complement來決定是删除存在于c中的元素，還是删除不存在于c中的元素，complement為true，删除不存在的元素，否則為false删除存在元素。

定義一個final Object[] elementData指派為this.elementData。

定義r=0,w=0,r用來循環，w作為符合條件元素的下标位置。

定義boolean modified，初始化為false，預設沒有修改。

try中用r來作為循環的條件，c.contains（elementData[r]）==complement,如果滿足，elementData[w++]=elementData[r]。

finally 如果非正常結束，即r!=size，調用System.arraycopy(elementData,r,elementData,w,size-r),w+=size-r。

如果w!=size，則下标從w開始，到size-1結束，list元素指派為null,modCount+=size-w,size=w,modified=true。

最後傳回modified。

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

private void writeObject(java.io.ObjectOutputStream s)：将list寫入流中，即序列化。

定義一個expectedModCount，用來存儲modCount，防止并發的時候其他線程修改了modCount産生異常。

s.defaultWriteObject(),s.writeInt(size) 寫入list大小。

再通過循環調用s.writeObject寫入元素。

如果expectedModCount!=modCount則說明被其他線程修改了，抛出ConcurrentModificationException()。

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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

private void readObject(java.io.ObjectInputStream s)

        throws java.io.IOException, ClassNotFoundException：反序列化。

elementData指派為EMPTY_ELEMENTDATA。

s.defaultReadObject(),s.readInt()。

如果size大于0，ensureCapacityInternal(size);Object[] a = elementData;

再循環s.readObject()。

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

序列化反序列化

ArrayList<String> list = new ArrayList();

ObjectOutputStream o=new ObjectOutputStream(new FileOutputStream("1.txt"));

       o.writeObject(list);

       ObjectInputStream in=new ObjectInputStream(new FileInputStream("1.txt"));

       ArrayList<String> x= (ArrayList<String>) in.readObject();

public ListIterator<E> listIterator(int index)：從list下标從index開始傳回list疊代器。

如果index<0或者index>size抛出IndexOutOfBoundsException("Index: "+index)；否則傳回ListItr(index)。

public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

public ListIterator<E> listIterator()：傳回list疊代器。

傳回ListItr(0);

public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

public Iterator<E> iterator()：傳回疊代器。

傳回Itr()。

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

public List<E> subList(int fromIndex, int toIndex)：分割list，傳回從fromIndex到toIndex下标的list。

首先調用subListRangeCheck(fromIndex, toIndex, size)，判斷fromIndex,toIndex是否越界。

最後傳回new SubList(this, 0, fromIndex, toIndex)。

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

static void subListRangeCheck(int fromIndex, int toIndex, int size)：判斷fromIndex和toIndex是否符合規則。

如果fromIndex<0抛出IndexOutOfBoundsException("fromIndex = " + fromIndex)。如果toIndex>size，則抛出IndexOutOfBoundsException("toIndex = " + toIndex)。如果fromIndex>toIndex,則抛出IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")")。

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

public void forEach(Consumer<? super E> action):對list元素根據action函數式循環。

先判斷action是否為空。

再記錄modCount指派給expectedModCount,final int size=this.size,final E[] elementData=(E[])this.elementData。

根據size循環list，循環條件為expectedModCount==modCount&&i<index,防止并發的時候，modCount被其他線程修改。

循環體中，action.accept(elementData[i])。

最後判斷modCount==expectedModCount,不等的話抛出異常ConcurrentModificationException();

@Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

public Spliterator<E> spliterator()：傳回一個ArrayListSpliterator<>(this, 0, -1, 0)。 

@Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

public boolean removeIf(Predicate<? super E> filter)：根據Predicate條件删除list元素。

判斷filter是否為空。

removeCount為删除元素數量，初始值為0,。

removeSet為要删除的BitSet，初始化為new BitSet(size)。

記錄modCount指派給expectedModCount,final int size=this.size。

根據size循環list，循環條件為expectedModCount==modCount&&i<index,防止并發的時候，modCount被其他線程修改。

final E element為elementData[i],如果element滿足filter條件，removeSet.set(i),removeCount++。

判斷modCount==expectedModCount,不等的話抛出異常ConcurrentModificationException()。

final boolean anyToRemove為是否有元素删除标志，指派為removeCount>0。如果anyToRemove為true，newSize為size-removeCount,再進行循環。

循環條件為i<size&&j<newSize,

i=removeSet.nextClearBit(i),nextClearBit為傳回下一個false位置，elementData[j]=elementData[i],指派不滿足條件元素，即不需要删除的元素。

再循環将移除元素的位置置為null,利于gc回收，循環條件為k=newSize,k<newSize。

将size指派為newSize。

判斷modCount==expectedModCount,不等的話抛出異常ConcurrentModificationException()。

最後modCount++，傳回anyToRemove。

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

public void replaceAll(UnaryOperator<E> operator):根據UnaryOperator對象操作list。

先判斷operator是否為空，再記錄modCount指派給expectedModCount,final int size=this.size。

根據size循環list，循環條件為expectedModCount==modCount&&i<index,防止并發的時候，modCount被其他線程修改。

循環體中，elementData[i] = operator.apply((E) elementData[i])。

最後判斷modCount==expectedModCount,不等的話抛出異常ConcurrentModificationException();modCount++。

@Override
    @SuppressWarnings("unchecked")
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

public void sort(Comparator<? super E> c)：排序。

記錄modCount指派給expectedModCount。

再調用Arrays.sort(elementData,0,size,c)。

最後判斷modCount==expectedModCount,不等的話抛出異常ConcurrentModificationException();modCount++。

@Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

内部類

private class Itr implements Iterator<E>

成員變量

cursor：下一個傳回的下标。

LastRet:最後傳回的下标，初始化為-1。

expectedModCount：記錄modCount，防止并發造成的其他線程修改list，可以抛出異常。

成員方法

public boolean hasNext()：判斷是否還有下一個元素。

判斷條件為cursor是否等于size。

public E next()：傳回下一個疊代器元素。

首先調用checkForComdification(),判斷modConut是否被其他線程修改了。

I指派為cursor，即原先開始下标，i如果不小于size，抛出NoSuchElementException()。

Object[] elementData指派為ArrayList.this.elementData。

如果i不小于elementData.length，則抛出new ConcurrentModificationException()。Cursor=i+1,傳回(E) elementData[lastRet = i]，即傳回elementData[i],又将i指派給lastRet。

public void remove():删除上一次傳回元素，即下标為lastRet。

判斷lastRet是否小于0,如果小于0，抛出IllegalStateException()。

調用checkForComdification(),判斷modConut是否被其他線程修改了。

try 調用ArrayList.this.remove(lastRet)方法,删除下标為lastRet元素，再将cursor指向lastRet坐标，lastRet重新指派為-1, expectedModCount指派為modCount,因為ArrayList.this.remove()方法會修改modCount。

Catch捕獲IndexOutOfBoundsException異常，抛出ConcurrentModificationException()。

public void forEachRemaining(Consumer<? super E> consumer):根據consumer對list元素函數式操作。

先判斷consumer是否為空，i等于cursor，size=ArrayList.this.size,如果i不小于size，抛出異常，elementData指派為ArrayList.this.elementData,如果i不小于elementData.length，抛出異常。While循環條件為i不等于size，expectedModCount等于modCount,循環體内容為consumer.accept((E)elementData[i++]);循環結束，cursor=i+1,lastRet=i，最後調用checkForComdification()，判斷list是否被其他線程修改了。

final void checkForComodification()：判斷list是否被其他線程修改了，判斷條件為expectedModCount于modCount是否相等。

private class ListItr extends Itr implements ListIterator<E> list疊代器

構造方法

ListItr(int index)：super(),cursor=index。

public boolean hasPrevious()：是否先前的元素，傳回cursor!=0，即cursor不為0。

public int nextIndex()：傳回下一個元素的下标，傳回cursor。

public int previousIndex()：傳回先前元素下标，傳回cursor-1。

public E previous():傳回前一個元素。調用checkForComdification()方法，判斷list是否被其他線程修改了。I為前一進制素下标，值為cursor-1,如果i<0抛出異常NoSuchElementException();elementData指派為ArrayList.this.elementData，如果i不小于elementData.length,則抛出異常ConcurrentModificationException()。

Cursor=I,傳回elementData[lastRet=i]。

public void set(E e)：修改下标為lastRet元素的内容。先判斷lastRet是否小于0，如果是抛出IllegalStateException();調用checkForComdification()方法，判斷list是否被其他線程修改了，try 調用ArrayList.this.set(e),捕獲IndexOutOfBoundsException，抛出ConcurrentModificationException異常。

public void add(E e)：下一位置添加元素，即cursor位置添加元素。

調用checkForComdification()方法，判斷list是否被其他線程修改了，try i=cursor，調用ArrayList.this.add(I,e),cursor指向下一進制素，即cursor+1,lastRet置為-1，expectedModCount重新指派為modCount，因為add方法會修改modCount，捕獲IndexOutOfBoundsException，抛出ConcurrentModificationException異常。

static final class ArrayListSpliterator<E> implements Spliterator<E>

成員變量，private final ArrayList<E> list 用來存儲list;private int index 存儲起始下标;private int fence 結束下标; private int expectedModCount 修改次數modCount;

構造方法

ArrayListSpliterator(ArrayList<E> list, int origin, int fence,int expectedModCount)

成員方法：

private int getFence()：擷取fence。定義int hi ArrayList<E>lst。如果hi=fence 不小于0，說明fence已經指派過了，傳回hi；否則判斷lst=list 是否為null,如果是hi=fence=0,否則expectedModCount=lst.modCount,hi=fence=lst.size。

public ArrayListSpliterator<E> trySplit()：分割ArrayListSpliterator，取前半部分。

hi指派為getFence(),lo=index,mid=(hi+lo)>>>1(無符号右移，即原來一半)。

如果lo不小于mid，則傳回null,否則傳回ArrayListSpliterator(list,lo,index=mid,expectedModCount)。

public boolean tryAdvance(Consumer<? super E> action)：根據action對list 目前元素進行函數式操作。

先判斷action是否為空，int h=getFence(),i=index,如果i<h,傳回false；否則index指向下一個元素，e為list.elementData[i],action.accept(e),判斷list.expectedModCount是否與expectedModCount相等，不等抛出異常ConcurrentModificationException異常。

public void forEachRemaining(Consumer<? super E> action)：對list所有元素進行函數式操作。

I為index,hi為結束下标，mc為修改次數lst用來存儲list,a[]為elementData。判斷action是否為空。如果lst!=null&&a=lst.elementData!=null,執行下去，否則抛出異常ConcurrentModificationException()。執行如果hi=fence小于0，說明fence未被指派過，則hi=lst.size,mc=lst.modCount，否則mc=expectedModCount。

如果i=index不小于0并且index=hi小于a.length，執行循環，action.accept（）接受每一個元素。如果list.modCount==mc傳回。

public long estimateSize()：傳回長度。（long）(getFence()-index)。

public int characteristics():傳回Spliterator的ORDERED，SIZED,SUBSIZED。

傳回Spliterator.ORDERED|Spliterator.SIZED|Spliterator.SUBSIZED。

java基礎 ArrayList源碼
上一篇: ArrayList存放HashMap排序方法
下一篇: Java集合-ArrayListy（二）ArrayList源碼解析

繼續閱讀