⚽ ArrayList

1. 类注释

1. 概述

• ArrayList 是实现 List 接口的可自动扩容的数组
• 实现了所有的 List 操作
• 允许所有的元素，包括 null 值
• ArrayList 大致和 Vector 相同，除了 ArrayList 是非线程安全的

2. 复杂度

• O(1): size isEmpty get set iterator listIterator
• 均摊 O(N): add n 个元素
• O(N): 其他 method

3. capacity

• 每一个 ArrayList 实例都有一个 capacity
• capacity == 存储元素的数组 elementData 的长度
• capacity 至少和 List 的 size 一样大
• 当执行 add() 时会自动扩容

2. 类图

1. 源码

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // ......
    }

2. 分析

• List Interface

  • List的实现类之一

• RandomAccess Interface

  • 支持随机访问

• Cloneable Interface

  • 支持克隆

• Serializable Interface

  • 支持 序列化 & 反序列化 [实际上实现了自己的序列化方式]

• Collection Interface

  • 属于 集合的一种

• Iterable Interface

  • 可以使用 for-each

---

3. 属性

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

    /**
     * 默认的初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例
     * 针对 new ArrayList(0);
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于提供默认大小的实例的共享空数组实例
     * 针对 new ArrayList();
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区
     * 在elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 状态下，
     * 只要有元素填充进来，
     * 那么 原空数组长度就会填充为 DEFAULT_CAPACITY[10]
     */
    transient Object[] elementData; // 不用 private 修饰，从而简化内部类的访问

    /**
     * ArrayList中元素的数量
     */
    private int size;

---

4. 构造函数

    /**
     *  带一个初始容量参数的构造方法
     *
     * @param  initialCapacity  初始容量
     * @throws 初始容量非法 [initialCapacity < 0] => 抛出 IllegalArgumentException
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 无参构造方法
     * 初始容量为 10 [容量 != size 而 == capacity]
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 带一个集合参数的构造方法
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws 如果集合为空，抛出NullPointerException
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray 可能不返回 Object[]
            // 例子：Arrays.asList(tmpList) 返回的是内部类，
            // 调用 toArray() 后返回的类取决于 tmpList 元素所在的类，例如 java.lang.String形成的数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 将EMPTY_ELEMENTDATA 赋值给 elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

---

5. 常用方法

1. 插入元素

1) add(E e)

    /**
     * 在列表最后添加指定元素
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1); // 扩容判断
        elementData[size] = e; // 最后一个下标插入元素
        size ++;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
     
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // new ArrayList() 情况下 add() 后，capacity == 10 而非 1
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // new ArrayList(0) 情况下 add() 后，capacity == 1 
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 当前所需最小容量 > 现有数组长度 -- 需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /**
     * ArrayList 可分配最大 size
     * 一些虚拟机在数组中预留一些header words
     * 此时 可能导致OutOfMemoryError
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    /**
     * 扩容
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
        // 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();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

2) add(int index, E element)

    /**
     * 在指定位置添加指定元素
     * 若该位置已经有元素，就将该元素和随后的元素移动到右面一位
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index); // 下标判断

        ensureCapacityInternal(size + 1);  // 扩容判断
        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(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

2. 删除元素

1) remove(int index)

    /**
     * 移除指定下标元素
     * 将所有的后续元素，向左移动
     *
     * @param index the index of the element to be removed
     * @return 返回被移除的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    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;
    }
    
    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

2) remove(Object o)

    /**
     * 移除指定元素
     * 如果存在，移除返回true
     * 否则，返回false
     *
     * @param o element to be removed from this list, if present
     * @return if this list contained the specified element
     */
    public boolean remove(Object o) {
        // 这里说明 ArrayList 中可以存放 null 元素值，且从 add() 方法中可以看出，存放 null 值数量不限
        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;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

3. 修改元素

    /**
     * 修改元素没有修改 modCount 
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);

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

4. 查找元素

1) get(int index)

    /**
     * 返回指定位置元素值
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

2) indexOf(Object o)

    /**
     * 返回指定元素所在下标
     * 如果不存在该元素，返回 -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;
    }

5. 序列化 & 反序列化

1) writeObject(java.io.ObjectOutputStream s)

    /**
     * 将ArrayLisy实例的状态保存到一个流里面
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    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);

        // 只序列化数组中有值的部分，即 size 大小，而非 capacity
        // 从而节省了 时间 & 空间
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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

2) readObject(java.io.ObjectInputStream s)

    /**
     * 根据一个流(参数)重新生成一个ArrayList
     */
    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) {
            // 为数组分配空间，基于 size 而非 capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
            }
        }
    }

6. Iterator

1) 源码

    /**
     * 返回 一个 迭代器 => 【fail-fast ！！！】
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

2) 分析 [fail-fast]

• 迭代器私有内部类 Itr 在初始化时，会 得到当前状态下的 expectedModCount = modCount;
• 迭代器在进行 next() 遍历的过程中，首先会进行 checkForComodification();
• 而只要在此过程中对 ArrayList 进行了 增删 等操作，就会修改 modCount 值
• 从而导致 modCount != expectedModCount

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

---

6. Arrays.asList

1. 返回 Arrays.ArrayList 类，是一个 数组构成的集合，与 ArrayList 类还是存在一些区别的：
   • Arrays.ArrayList 没有重写 AbstractList 的 add() & remove()，因此直接是父类的该方法，会抛出 UnsupportedOperationException 异常
   • Arrays.ArrayList 返回的集合，数组长度固定不变
   • Arrays.ArrayList 只能执行 get() & set()，适用于 初始化完成后，不需要增删元素的情况
   • Arrays.ArrayList 对其中元素进行修改，直接修改的是 原传入数组

/*
 * 将一个数组或者一个用逗号分隔的元素列表（使用的可变参数）转化为一个 固定大小的 List对象
 */
public class Arrays {
    @SafeVarargs
    @SuppressWarnings("varargs")
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

    /**
     * @serial include
     */
    private static class ArrayList<E> extends AbstractList<E> 
                                      implements RandomAccess, java.io.Serializable // 与 ArrayList 缺少了 Cloneable 接口
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return a.clone();
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size, (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) { // 可以修改指定下标的值
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

        @Override
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }

        @Override
        public Spliterator<E> spliterator() {
            return Spliterators.spliterator(a, Spliterator.ORDERED);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            for (E e : a) {
                action.accept(e);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            E[] a = this.a;
            for (int i = 0; i < a.length; i++) {
                a[i] = operator.apply(a[i]);
            }
        }

        @Override
        public void sort(Comparator<? super E> c) {
            Arrays.sort(a, c);
        }
    }
}