ArrayList源码分析（jdk1.8）

AbstractList提供了List接口的默认实现（个别方法为抽象方法）。

    List接口（extends Collection）定义了列表必须实现的方法。

    RandomAccess是一个标记接口，接口内没有定义任何内容。

    实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝。

    通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
publicclass TestTransient {
    public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
        A a = new A(25, "张三");
        System.out.println(a);
        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("d://mm.txt"));
        oos.writeObject(a);
        oos.close();
        ObjectInputStream ois = new ObjectInputStream(new FileInputStream("d://mm.txt"));
        a = (A) ois.readObject();
        System.out.println(a);
    }
}
classAimplements Serializable {
    inta;
    transient String b;
    public A(inta, String b) {
        this.a = a;
        this.b = b;
    } 
    public String toString() {
        return"a = " + a + ",b = " + b;
    }
}

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

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //容量为10
    }

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

public static <T,U> T[] copyOf(U[] original, intnewLength, 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));
        //System.arraycopy详见add(int index, E element)方法
        return copy;
    }

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

private void ensureCapacityInternal(int minCapacity) { //确保内部容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0) 
      // 超出了数组可容纳的长度，则进行动态扩展
//个人理解:elementData每次扩展为1.5倍，当minCapacity达到临界值，上式if成立
            grow(minCapacity);
    }

<span style="font-family: Consolas;"></span><pre name="code" class="java" style="font-size: 15px; line-height: 21px;"><span style="font-family: Consolas; background-color: rgb(255, 255, 51);"><strong>动态扩展核心</strong></span>

<pre name="code" class="java">private void grow(int minCapacity) { // 动态扩展核心
        // overflow-conscious code
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5倍(15 >> 1=7)
        // 再次判断新数组的容量够不够
        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) {
        if (minCapacity < 0) // overflow 溢出，貌似不可能有这种情况吧？？
            throw new OutOfMemoryError();
// 也就是说minCapacity在超出最大限制时允许达到Integer.MAX_VALUE，
// 而不仅仅是Integer.MAX_VALUE-8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

public void add(intindex, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index+1,
                         size-index);
        elementData[index] = element;
        size++;
    }

/**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(intindex) {
        if (index > size || index < 0)
            thrownew IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

// java.lang.System
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, intdestPos,
                                        intlength);
// src 原数组，srcPos原数组开始位置
// dest目标数组，destPos目标数组开始位置
// length：the number of array elements to be copied.即要复制的数组元素的数目

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

public boolean addAll(intindex, Collection<? extends E> c) {
        rangeCheckForAdd(index); //检查索引合法性
        Object[] a = c.toArray();
        intnumNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        intnumMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        returnnumNew != 0;
    }

public void clear() {
        modCount++; // 从结构上修改此列表的次数加1
        // clear to let GC do its work
        for (inti = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

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

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) {
        if (o == null) {
            for (inti = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    returni;
        } else {
            for (inti = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    returni;
        }
        return -1;
    }

public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(null);
        arrayList.add(null);
        System.out.println(arrayList.contains(null));
        System.out.println(arrayList.size());
    }

输出：
true
4

// 调用java.util.AbstractCollection的containsAll
public boolean containsAll(Collection<?> c) { // ArrayList没有此方法
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

public boolean contains(Object o) { // ArrayList的方法
    return indexOf(o) >= 0; // 调用11的indexOf方法
}

// 再对比看一下package org.apache.commons.collections的containsAll
public boolean containsAll(Collection collection)
    {
        if(fast)
            return list.containsAll(collection);
        ArrayList arraylist = list;
        JVM INSTR monitorenter ;
        return list.containsAll(collection);
        Exception exception;
        exception;
        throw exception;
    } //这块源码，表示看不懂。求大神讲解

// java.util.AbstractList
public int hashCode() {
        inthashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        returnhashCode;
    }

public static void main(String[] args) {
        ArrayList List1 = new ArrayList();
        List1.add(1);
        ArrayList List2 = (ArrayList) List1.clone();
        System.out.println("未修改值(==)\t" + (List1 == List2));
        System.out.println("未修改值(equals)\t" + List1.equals(List2));
        List2.set(0, 2);
        System.out.println("list2--" + List2.hashCode() + "--" + List2.get(0));
        System.out.println("list1--" + List1.hashCode() + "--" + List1.get(0));
    }

未修改值(==)    false
未修改值(equals)    true
list2--33--2
list1--32--1

浅拷贝(影子克隆):只复制基本类型。

深拷贝(深度克隆):基本类+对象。

public E remove(int index) {
        rangeCheck(index); // 检查索引合法性，详见get方法
        modCount++;
        E oldValue = elementData(index); 
        intnumMoved = size - index - 1; // 要移动的元素个数
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
        returnoldValue;
    }

protected void removeRange(intfromIndex, inttoIndex) {
        modCount++;
        intnumMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // clear to let GC do its work
        intnewSize = size - (toIndex-fromIndex);
        for (inti = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

public static void main(String[] args) {
        ArrayList List1 = new ArrayList();
        ArrayList List2 = new ArrayList();
        List1.add(1);
        List1.add(2);
        List1.add(3);
        List2.add(4);
        System.out.println(List1.removeAll(List2));
        for (Object object : List1) {
            System.out.println(object);
        }
    }

false
1
2
3

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

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

// Arrays.sort,一直在用 Arrays.sort(arr)，总算看到他兄弟的真面目了
/* @param<T> the class of the objects to be sorted
     * @param a the array to be sorted
     * @param fromIndex the index of the first element (inclusive) to be sorted
     * @param toIndex the index of the last element (exclusive) to be sorted
     * @param c the comparator to determine the order of the array.  A
     *        {@code null} value indicates that the elements'
     *        {@linkplain Comparable natural ordering} should be used.
*/
public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                Comparator<? super T> c) {
        if (c == null) {
            sort(a, fromIndex, toIndex);
        } else {
            rangeCheck(a.length, fromIndex, toIndex);
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, fromIndex, toIndex, c);
            else
                TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); //暂不分析
        }
    }

// Array的sort方法
public static void sort(Object[] a, intfromIndex, inttoIndex) {
        rangeCheck(a.length, fromIndex, toIndex); // 检查参数合法性
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex);
        else
            ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
    }

// Array 的 rangeCheck方法
private static void rangeCheck(intarrayLength, intfromIndex, inttoIndex) {
        if (fromIndex > toIndex) {
            thrownew IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            thrownew ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            thrownew ArrayIndexOutOfBoundsException(toIndex);
        }
    }

// 这个表示看不懂
static final class LegacyMergeSort {
        privatestaticfinalbooleanuserRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

/** To be removed in a future release. */
    privatestatic <T> void legacyMergeSort(T[] a, intfromIndex, inttoIndex,
                                            Comparator<? super T> c) {
        T[] aux = copyOfRange(a, fromIndex, toIndex);
        if (c==null)
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
        else
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
    }

// Array的copyRange方法
@SuppressWarnings("unchecked")
    publics tatic <T> T[] copyOfRange(T[] original, intfrom, intto) {
        return copyOfRange(original, from, to, (Class<? extends T[]>) original.getClass());
    }
public static <T,U> T[] copyOfRange(U[] original, intfrom, intto, Class<? extendsT[]> newType) {
        intnewLength = to - from;
        if (newLength < 0)
            thrownew IllegalArgumentException(from + " > " + to);
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, from, copy, 0,
                         Math.min(original.length - from, newLength));
        returncopy;
    }

 // Array 的 mergeSort 方法
/**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset into src corresponding to low in dest //何用？？？？？
     * To be removed in a future release.
     */
    @SuppressWarnings({"rawtypes", "unchecked"})
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  intlow, inthigh, intoff,
                                  Comparator c) { //off即传来的-fromIndex
        intlength = high - low;
        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (inti=low; i<high; i++)
//没有比较器c时，代码为
//for (intj=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                for (intj=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                    swap(dest, j, j-1); // 源码这里新建了临时变量 Object t
            return;
        } 
        // Recursively sort halves of dest into src
        intdestLow  = low;
        intdestHigh = high;
        low  += off;
        high += off;
        intmid = (low + high) >>> 1; //
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);
        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        
        // 没有比较器c时，代码为
        // if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0)
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }
        // Merge sorted halves (now in src) into dest
        for(inti = destLow, p = low, q = mid; i < destHigh; i++) {
               //没有比较器时，为 && ((Comparable)src[p]).compareTo(src[q])<=0
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }