Java ArrayList源碼學(xué)習(xí)(學(xué)習(xí)記錄,可能有很多理解不對(duì)的地方,大佬勿噴,謝謝)

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/*
*是當(dāng)對(duì)象序列化的時(shí)候?qū)ο蟮囊粋€(gè)標(biāo)識(shí),作用是序列化時(shí)轉(zhuǎn)化為byte流，還能反序列化成原始類,主要用于版本控制
*/
private static final long serialVersionUID =8683452581122892189L;

/*
* 默認(rèn)初始容量為10
*/
private static final int DEFAULT_CAPACITY = 10;

/*
* 空數(shù)組，在調(diào)用無(wú)參構(gòu)造方法時(shí)默認(rèn)是這個(gè)空數(shù)組
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/*
* 用于保存數(shù)據(jù)的數(shù)組
*/
private trainsient Object[] elementData;、

/*
* 元素的數(shù)量
*/
private int size;

/*
* 通過(guò)構(gòu)造方法傳入默認(rèn)容量設(shè)置數(shù)組大小
*/
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {  //大于0新生成一個(gè)容量為傳入?yún)?shù)的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { //等于0時(shí)生成空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

/*
* 默認(rèn)生成空的數(shù)組
*/
 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

/*
* 把傳入的集合中的值復(fù)制到arryList里
*/
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();                //c轉(zhuǎn)為數(shù)組后傳遞給arayList
        if ((size = elementData.length) != 0) { //如果長(zhǎng)度不等于0
            if (elementData.getClass() != Object[].class)   //如果兩者的類型不一致
                elementData = Arrays.copyOf(elementData, size, Object[].class);  //把傳入的數(shù)組賦給arrayList數(shù)組
        } else { //如果長(zhǎng)度等于0,生成空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;  
        }
    }

/*
*  實(shí)際尺寸
*/
public void trimToSize() {
        modCount++; ///定義于ArrayList的父類AbstractList，用于存儲(chǔ)結(jié)構(gòu)修改次數(shù)
        if (size < elementData.length) { // 如果arrayList長(zhǎng)度小于數(shù)組長(zhǎng)度
            elementData = (size == 0)       //數(shù)據(jù)數(shù)組長(zhǎng)度是否為0?空數(shù)組:復(fù)制數(shù)組數(shù)據(jù)和長(zhǎng)度
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

/*
*   確保容量容納得下數(shù)據(jù)
*/
public void ensureCapacity(int minCapacity) { //所需最小的容量
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0 : DEFAULT_CAPACITY;    //如果 arrayList數(shù)據(jù)不為空數(shù)組？0 ：默認(rèn)值10

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

/*
*   計(jì)算容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果為空
            return Math.max(DEFAULT_CAPACITY, minCapacity);  //返回默認(rèn)容量和最小容量比較大那個(gè)
        }
        return minCapacity;
    }


/*
*  確保裝得下
*/
private void ensureCapacityInternal(int minCapacity) { 
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }


 private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;      //動(dòng)態(tài)增長(zhǎng)時(shí)的數(shù)
 
        if (minCapacity - elementData.length > 0)  如果最小容量比arrayList的容量大
            grow(minCapacity);            //增長(zhǎng)minCapacity
    }

/*
*  數(shù)組擴(kuò)充容量
*/
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;   //獲取數(shù)組長(zhǎng)度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量為舊容量的1.5倍
        if (newCapacity - minCapacity < 0)                //如果新容量小于傳入的容量
            newCapacity = minCapacity;                     //新容量等于傳入容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)   //如果新容量超過(guò)最大值
            newCapacity = hugeCapacity(minCapacity);  //判斷值是否大于最大容量
        elementData = Arrays.copyOf(elementData, newCapacity); //把元素和新容量賦給arrayList
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)  
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?  //最小容量是否超過(guò)最大容量?integer最大值:integer最大值-8
            Integer.MAX_VALUE :                
            MAX_ARRAY_SIZE;  
    }

/*
* 最大的數(shù)組容量,在jvm中獲取數(shù)組長(zhǎng)度使用了arraylength字節(jié)碼指令,
* 長(zhǎng)度8是用來(lái)記錄字節(jié)碼指令的,并不固定是8,為了減少內(nèi)存溢出(OOM)
*/
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/*
* 長(zhǎng)度
*/
public int size() {
        return size;
    }

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

/*
* 是否包含某個(gè)元素
*/
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

/*
* 獲得元素索引
*/
public int indexOf(Object o) {
        if (o == null) {     //如果為null,遍歷數(shù)組,查詢?yōu)閚ull的下標(biāo)，找到返回下標(biāo)
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {            //如果元素不為null,遍歷，如果找到返回下標(biāo)
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;    //沒(méi)找到返回-1
    }

/*
* 獲得最后一個(gè)元素的索引
*/
public int lastIndexOf(Object o) { //邏輯同上，只是把數(shù)組從后往前遍歷
        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;
    }

/*
* 復(fù)制，返回?cái)?shù)組實(shí)體，無(wú)值
*/
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);
        }
    }

/*
*  調(diào)用arrays的數(shù)組方法
*/
public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }


/*
* 如果列表適合指定數(shù)組，返回它，否則，創(chuàng)建一個(gè)新數(shù)組，分配
*指定數(shù)組的運(yùn)行時(shí)類型和大小
*/
public <T> T[] toArray(T[] a) {
        if (a.length < size)              
            return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
 
/*
* 根據(jù)索引獲得元素值
*/
 E elementData(int index) {
        return (E) elementData[index];
    }

/*
*  檢查索引范圍,返回元素值
*/
public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

/*
*  替換值
*/
 public E set(int index, E element) {
        rangeCheck(index);    //檢查范圍

        E oldValue = elementData(index);  //把索引為index的值得到
        elementData[index] = element;  //把元素設(shè)置到該位置
        return oldValue;
    }

/*
*  添加element
*/
 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //擴(kuò)充長(zhǎng)度
        elementData[size++] = e;    //插入在末尾
        return true;
    }

/*
*  根據(jù)索引添加element
*/
 public void add(int index, E element) {
        rangeCheckForAdd(index);   //檢查是否在范圍內(nèi)

        ensureCapacityInternal(size + 1);  //擴(kuò)充
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);     //復(fù)制指定的源數(shù)組的數(shù)組,把elementData中從index開(kāi)始以后的元素復(fù)制到elementData的index+1的位置上,個(gè)數(shù)為size-index個(gè)

        elementData[index] = element; //將elementData下邊index位置賦值目標(biāo)值
        size++;   //arrayList+1
    }



/*
*  根據(jù)索引刪除element
*/
public E remove(int index) {
        rangeCheck(index);     

        modCount++;      
        E oldValue = elementData(index);   //得到索引index的元素

        int numMoved = size - index - 1;   
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);              //把elementData中,index后的元素復(fù)制到數(shù)組中
        elementData[--size] = null;  
        return oldValue;
    }


/*
*  刪除元素,同 add
*/
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++;
        int numMoved = size - index - 1;  //得到刪除元素后的個(gè)數(shù)
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);    //把刪除元素之后的元素復(fù)制到數(shù)組中
        elementData[--size] = null;  // 數(shù)組前移一位，size自減，空出來(lái)的位置置null，具體的對(duì)象的銷毀由Junk收集器負(fù)責(zé)
    }


 public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)            
            elementData[i] = null;       清空數(shù)組，設(shè)置長(zhǎng)度為0
        size = 0;
    }

/*
* 把集合添加進(jìn)arrayList
*/

 public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();            //把C變成數(shù)組
        int numNew = a.length;            //獲取數(shù)組長(zhǎng)度
        ensureCapacityInternal(size + numNew);      //增加操作數(shù)
        System.arraycopy(a, 0, elementData, size, numNew);  //把新的數(shù)組復(fù)制到elementData中
        size += numNew;                         //更改elementData長(zhǎng)度
        return numNew != 0;
    }

/*
* 在指定的索引后添加集合
*/
 public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);   

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

        int numMoved = size - index;     //需要位移的元素個(gè)數(shù)
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);      //把元素放到移動(dòng)后的位置

        System.arraycopy(a, 0, elementData, index, numNew); //把集合放入elementData中
        size += numNew;
        return numNew != 0;
    }


/*
* 刪除索引之間的元素
*/
protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;         //需要移動(dòng)的元素是刪除元素后的元素
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);           將elementData從toIndex位置開(kāi)始的元素向前移動(dòng)到fromIndex
        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;          //把toIndex后的元素置空
        }
        size = newSize;     
    }


 private void rangeCheck(int index) {
        if (index >= size)
            throw new 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) {
        Objects.requireNonNull(c);     //判斷c是否為空
        return batchRemove(c, false);
    }

/*
*  保留集合
*/
public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }



private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;    
        int r = 0, w = 0;               //w為write,r為read
        boolean modified = false;         
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement) ; //若保留，就將相同元素移動(dòng)到前段，不刪除，就將不同元素移動(dòng)到前段
                    elementData[w++] = elementData[r];     //將原數(shù)組的r位置的數(shù)據(jù)覆蓋掉w位置的數(shù)據(jù)，r位置的數(shù)據(jù)不變，并其w自增，r自增。        
        } finally { 
            if (r != size) {   //確保異常拋出前的部分可以完成期望的操作，未遍歷的部分會(huì)接到后面
                System.arraycopy(elementData, r, 
                                 elementData, w,
                                 size - r);                  
                w += size - r;      
            } 
            if (w != size) {         //如果w == size ，表示全部元素被保留，那么沒(méi)有刪除操作，所以返回false,反之，返回true,沒(méi)有刪除操作。當(dāng)w != size的時(shí)候，即使拋出異常，也能正確處理拋出前的操作，所以w始終為保存的前段部分
                for (int i = w; i < size; i++)
                    elementData[i] = null;                 
                modCount += size - w;
                size = w;      //新的大小為保留元素個(gè)數(shù)
                modified = true;
            }
        }
        return modified;
    }

}