ArrayList源码阅读笔记

ArrayList

·长度不固定，元素有序、可重复。

·可以存null。

·size(), isEmpty(), get(), set(), iterator(), listIterator()操作时间复杂度都是O(1)。

·add() 添加操作的时间复杂度平均为O(n)。

·其他所有操作的时间复杂度几乎都是O(n)。

·底层数据结构是数组（Object[] elementData），线程不安全。如果多个线程同时访问一个ArrayList实例，至少线程结构性修改一个列表，它必须保持外部同步。（结构上的修改是指添加或删除一个或多个元素，或者是明确地调整大小操作;仅仅设置元素的值不是结构修改。）同步例如：List list = Collections.synchronizedList(new ArrayList(...));

常用方法

        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");

        list.add(3,"d"); // 指定索引新增元素
        System.out.println(list);        // [a, b, c, d]

        List<String> anolist = new ArrayList<>();
        anolist.add("1");
        anolist.add("2");
        list.addAll(anolist);  // 将另一个集合（Collection接口实现类的）对象元素全都添加到最后
        System.out.println(list); // [a, b, c, d, 1, 2]

        list.addAll(1,anolist); // 将另一个集合（Collection接口实现类的）对象元素全都添加指定位置
        System.out.println(list); // [a, 1, 2, b, c, d, 1, 2]

        list.set(0,"A");      // 设置指定索引元素（如果有则覆盖）
        System.out.println(list); // [A, 1, 2, b, c, d, 1, 2]

        System.out.println(list.get(3)); // b 获取指定索引的元素

        System.out.println(list.size()); // 8 获取列表元素个数

        System.out.println(list.contains("a")); //判断是否包含指定对象

        System.out.println(list.containsAll(anolist)); // 判断是否包含指定集合（Collection接口实现类的）对象中所有元素

        System.out.println(list.indexOf("A"));  // 返回指定对象的第一个索引

        System.out.println(list.lastIndexOf("A")); // 返回指定对象的最后一个索引

        System.out.println(list.isEmpty()); // 判断列表是否为空

        Object[] str = list.toArray(); // 转化为数组

        list.subList(1,3);  // 截取指定索引的子列表

        Iterator<String> iter = list.iterator(); // 返回iterator

        list.remove("A");  // 移除指定元素

        list.remove(1);  // 移除指定索引的元素

        list.removeAll(anolist); // 移除指定集合（Collection接口实现类的）对象中所有元素

        list.retainAll(anolist);  // 移除指定集合（Collection接口实现类的）对象以外的所有元素

源码阅读

ArrayList继承了AbstractList<E>，实现了implements List<E>, RandomAccess, Cloneable, java.io.Serializable

实现RandomAccess用来表明其支持快速随机访问。

实现Cloneable用来实现拷贝。

实现Serializable用来实现序列化。

成员变量

private static final long serialVersionUID = 8683452581122892189L; // 序列化UID

private static final int DEFAULT_CAPACITY = 10;      // 默认容量为10

private static final Object[] EMPTY_ELEMENTDATA = {};  // 用于空实例的共享空数组实例

// 用于默认大小空实例的共享空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。添加第一
// 元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的
// ArrayList都将扩展为DEFAULT_CAPACITY。
transient Object[] elementData;  // transient表示该变量不参与序列化

private int size;    // ArrayList数组大小

// 数组最大长度0x7fffffff - 8 = 2147483639（21亿多）
// 数组最大为Integer.MAX_VALUE-8，因为一些虚拟机会保留一些header words
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

构造器

public ArrayList(int initialCapacity) {  // 指定初始化容量创建列表
        if (initialCapacity > 0) {        // 初始容量>0，创建指定容量Object数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { // 初始容量=0，用空Object数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


    public ArrayList() {    // 创建默认容量（10）的空列表
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(Collection<? extends E> c) {  // 指定collection创建列表
        elementData = c.toArray();                // 转化为数组
        if ((size = elementData.length) != 0) {    // 空数组
            if (elementData.getClass() != Object[].class)  // 不是Object型数组
　　　　　　　　　　// 拷贝到elementData中
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

方法（部分）

涉及的System类中的方法：

public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

将src，从srcPos位置开始，拷贝length长度个元素到dest的destPos处。

　　// 将该ArrayList实例的容量调整为列表的当前大小。
    public void trimToSize() {
        modCount++;                // 改变次数加1（此变量继承自父类AbstractList）
        if (size < elementData.length) {  // 当前元素个数<数组长度
            elementData = (size == 0)  
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size); 
　　　　　　　　// 当前元素个数=0则用空数组赋给elementData 
　　　　　　　　// 当前元素个数!=0拷贝实际长度个元素赋给elementData
        }
    }


　　// 增加此ArrayList实例的容量，如果有必要，以确保它至少能够容纳最小容量元素
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // elementData 不是默认空数组，minExpand赋值为0
            ? 0
            // 是默认空数组，minExpand赋值为10
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {     // 指定的最小容量>minExpand
            ensureExplicitCapacity(minCapacity);
        }
    }


    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
　　　　　　　　//若 elementData是默认空数组，返回10和指定容量中最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity; // 若 elementData不是是默认空数组，返回指定容量值
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }


    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;      // 改变次数加1（此变量继承自父类AbstractList）

        if (minCapacity - elementData.length > 0) // 指定容量比elementData容量大
            grow(minCapacity);
    }


    private void grow(int minCapacity) {      // 以确保它能够至少容纳最小容量
        int oldCapacity = elementData.length; // 保存数组长度旧值
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 新值=旧值*1.5
        if (newCapacity - minCapacity < 0)  // 使新值最少等于指定值
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 新值超数组最大容量
            newCapacity = hugeCapacity(minCapacity); 
        elementData = Arrays.copyOf(elementData, newCapacity);// 扩容
    }


    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)                    // 指定值<0
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?  // 指定值>数组最大值
            Integer.MAX_VALUE :        // 返回整型最大值
            MAX_ARRAY_SIZE;        // 否则返回数组最大值
    }


　　public int size() {   // 返回数组大小
        return size;
    }


　　public boolean isEmpty() {  // 判断数组是否为空
        return size == 0;
    }


　　public boolean contains(Object o) {  // 判断是否包含指定元素
        return indexOf(o) >= 0;
    }


    public int indexOf(Object o) {     // 获取指定元素第一个索引位
        if (o == null) {              // 元素是null
            for (int i = 0; i < size; i++)      // 从前向后搜索
                if (elementData[i]==null)
                    return i;
        } else {                        // 元素不是null
            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 (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() {                // 深拷贝
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone(); // 调用父类clone方法
            v.elementData = Arrays.copyOf(elementData, size); // 实例类型需手动拷贝
            v.modCount = 0;            // 修改次数置零
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }


　　public Object[] toArray() {    // 将列表转化为数组
        return Arrays.copyOf(elementData, size);  // 返回底层数组的拷贝
    }


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


　　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);
        elementData[index] = element;
        return oldValue;                // 返回旧值
    }


    public boolean add(E e) {            // 增加元素
        ensureCapacityInternal(size + 1);  // 结构性修改， modCount加1
        elementData[size++] = e;
        return true;
    }


    public void add(int index, E element) { // 指定位置增加元素
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);   // 结构性修改， modCount加1
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);  // 指定索引位后面的所有元素向后移一位
        elementData[index] = element;  // 指定位置赋值
        size++;
    }


    public E remove(int index) {   // 移除指定索引位的元素
        rangeCheck(index);

        modCount++;          // 结构性修改， modCount加1
        E oldValue = elementData(index);  // 保存旧值

        int numMoved = size - index - 1;  // 索引位后面所有需移动的元素个数
        if (numMoved > 0)               // 索引位后面所有元素前移一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;   // 最后一个位置置null

        return oldValue;  // 返回旧值
    }


    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++;                // 结构性修改， modCount加1
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;
    }


    public void clear() {      // 清空 
        modCount++;     // 结构性修改， modCount加1

        for (int i = 0; i < size; i++)
            elementData[i] = null;  // 全部置null

        size = 0;
    }


   public boolean addAll(Collection<? extends E> c) {//将指定collection里面元素都加入
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 结构性修改， modCount加1
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }


　　// 将指定collection里面元素从指定索引位处都加入
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();   // 转化为数组（临时存储用的数组）
        int numNew = a.length;   // 数组长度
        ensureCapacityInternal(size + numNew); // 结构性修改， modCount加1

        int numMoved = size - index;  // 索引位后面所有需移动的元素个数
        if (numMoved > 0)  // 索引位后面所有元素后移numNew位
            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++;    // 结构性修改， modCount加1
        int numMoved = size - toIndex;  // 需移动元素个数 
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);  // 范围后面的所有元素前移numMoved位

        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {  // 后面置null
            elementData[i] = null;
        }
        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));
    }


    public boolean removeAll(Collection<?> c) {  // 批量移除指定的
        Objects.requireNonNull(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;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
　　　　　　　　　　　　// 包含则向前移动覆盖
                    elementData[w++] = elementData[r];
        } finally {
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                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) // 序列化保存对象
        throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();
        s.writeInt(size);
        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();

        if (size > 0) {
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);
            Object[] a = elementData;
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }


    public ListIterator<E> listIterator(int index) { // 从指定位置开始返回Iterator
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);     // ListItr是内部类
    }


　　public ListIterator<E> listIterator() {  // 返回内部类ListLtr()对象
        return new ListItr(0);
    }


　　public Iterator<E> iterator() {  // 返回内部类Itr对象
        return new Itr();