java 集合之 ArrayList 源码解读

    /**    * 序列化版本标识，序列化和反序列化时使用    */    private static final long serialVersionUID = 8683452581122892189L;
    /**     * 默认的数据容量     */    private static final int DEFAULT_CAPACITY = 10;
    /**     * 用于ArrayList空实例的共享空数组实例     */    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**      * 用于默认大小空实例的共享空数组实例。      * 我们将DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA区别开来      * 以便在添加第一个元素时知道要膨胀多少。     */    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**     * 存放元素的数组     * 备注：字段不设置为私有，是为了方便内部类的访问     * 思考：为什么不是E[]呢？     */    transient Object[] elementData; 
    /**     * 数组元素个数     */    private int size;

    /**    * 1、创建ArrayList强制使用范型，避免使用原生类型引起类型不安全的问题    * 2、java7之后的jdk增强了类型推导，建议使用new ArrayList<>()，最好不使用new ArrayList<E>    */   // 创建一个特定长度的ArrayList   // 如果可以预估容量，请使用本方法构建实例，避免扩容时数组拷贝带来的性能消耗    public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {            this.elementData = new Object[initialCapacity];        } else if (initialCapacity == 0) {             // 如果容量为0，则都指向同一个共享的空数组             // 减少内存的占用            this.elementData = EMPTY_ELEMENTDATA;        } else {            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        }    }

     // 创建一个容量为10的ArrayList     public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }      // 使用Collection的实现比如Set,List创建一个ArrayList     // 通常是Collection的实现进行相互转换    public ArrayList(Collection<? extends E> c) {        elementData = c.toArray();        if ((size = elementData.length) != 0) {            // c.toArray返回类型不一定Object[],具体见https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-6260652            if (elementData.getClass() != Object[].class)                elementData = Arrays.copyOf(elementData, size, Object[].class);        } else {            // 使用空数组替换            this.elementData = EMPTY_ELEMENTDATA;        }    }

/**  * 在ArrayList结尾添加元素  */public boolean add(E e) {    // 根据size处理容量    ensureCapacityInternal(size + 1);     elementData[size++] = e;    return true;}private void ensureCapacityInternal(int minCapacity) {    // 如果使用ArrayList()创建，默认容量=DEFAULT_CAPACITY=10    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    // minCapacity为此时elementData必须的最小长度    ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {    // 修改次数+1，用于fail-fast处理    modCount++;    // 如果minCapacity大于elementData的长度，则进行扩容处理    if (minCapacity - elementData.length > 0)        // 扩容，可能会引起溢出问题        grow(minCapacity);}// ArrayList动态扩容机制的核心private void grow(int minCapacity) {    // 可能存在整型溢出    int oldCapacity = elementData.length;    // 容量默认扩大1.5倍    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        // 可能1：newCapacity<0整型溢出        // 可能2：newCapacity<minCapacity        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)         // 说明已经整型溢出        throw new OutOfMemoryError();    return (minCapacity > MAX_ARRAY_SIZE) ?        Integer.MAX_VALUE :        MAX_ARRAY_SIZE;}/**  * 在ArrayList特定位置添加单个元素  * 思考：add(E e)没有调用add(int index, E element)，个人猜测是出于性能的考虑  * 毕竟基于数组进行插入操作可能存在性能问题  */public void add(int index, E element) {    // 检查位置是否合法    rangeCheckForAdd(index);
    // 跟add(E e)中处理方式类似    ensureCapacityInternal(size + 1);     // 将elementData中位置为index位置及其后面的元素都向后移动一个下标（底层是native方法，使用cpp直接操作内存。）    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    elementData[index] = element;    size++;}

    //    public boolean addAll(Collection<? extends E> c) {        // 集合转化成数组        Object[] a = c.toArray();        int numNew = a.length;        // 跟add(E e)中处理方式类似        ensureCapacityInternal(size + numNew);         // 将集合内的元素复制到elementData中，覆盖[size, size+numNew)的元素        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        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;        if (numMoved > 0)            // 将elementData中位置为index及其以后的元素都向后移动numNew个位置            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        // 将集合内的元素复制到elementData中，覆盖[index, index+numNew)的元素         System.arraycopy(a, 0, elementData, index, numNew);        size += numNew;        return numNew != 0;    }

    // 删除ArrayList中第一次出现的特定元素    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++)                // 比较对象时依赖equals方法                // 因此类型变量E对应的类注意重写equlas方法                // 重写时注意遵守规范，具体参考effective java第三版的第10、11两条规则                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)            // 将elemenData中index+1及其后面的元素都向前移动一个下标            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);        // 根据上一步的操作, size-1位置的对象向前移动了一个下标        // 如果没有elementData[--size]==null，可能会导致内存泄漏        // 试想，ArrayList被add了100个对象，然后被remove了100次。按照GC的机制来说，100个对象应该可以被GC掉（假设没有对象对象），但是由于还存在ArrayList的实例引用，对应的100个对象就无法删除        elementData[--size] = null;     }
    // 根据下标删除元素    // 注意：java5后引入自动装箱、拆箱的机制，因此产生了一个有趣的问题：    // 当类型变量为Integer的ArrayList调用remove时，可能调用remove(Object)，也可能调用remove(Index)    // 一定要注意测试是否符合自己的预期    public E remove(int index) {        rangeCheck(index);
        modCount++;        E oldValue = elementData(index);
        int numMoved = size - index - 1;        // 如果被删除元素不是ArrayList的最后一个元素        if (numMoved > 0)             // 对应下标之后的元素向前移动一个下标            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);        // 最后一个元素只为null，方便GC        elementData[--size] = null; 
        return oldValue;    }

    // 批量删除ArrayList和集合c都存在的元素    public boolean removeAll(Collection<?> c) {        // 非空校验        Objects.requireNonNull(c);        // 批量删除        return batchRemove(c, false);    }
    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 {            // 即使c.contains抛异常，也要保持跟AbstractCollection行为的兼容性            // 备注：ArrayList重写了AbstractCollection中的removeAll方法，removeAll调用了batchRemove            if (r != size) {                // 备注1：可能是上面的for循环出现了异常                // 备注2：可能是其它线程添加了元素。                System.arraycopy(elementData, r,                                 elementData, w,                                 size - r);                w += size - r;            }            if (w != size) {                for (int i = w; i < size; i++)                    // 跟fastRemove(int index)里面的操作类似，防止内存泄漏                    elementData[i] = null;                // 思考：为什么addAll的modCount+1，而removeAll的modCoun+size-w                // 个人以为modCount只是做标记做了结构的修改并且用来做校验。                // 因此+1，+2 +size-w并没有本质区别                modCount += size - w;                size = w;                modified = true;            }        }        return modified;    }
 // 思考：上面是按照元素进行批量删除，如何按照下标区间进行批量删除呢？批量保留
    public boolean retainAll(Collection<?> c) {        Objects.requireNonNull(c);        // 批量保留        return batchRemove(c, true);    }

    public void clear() {        modCount++;        // 清空ArrayList里面所有的元素        for (int i = 0; i < size; i++)            elementData[i] = null;
        size = 0;    }

    // 修改特定下标的值    public E set(int index, E element) {        rangeCheck(index);
        E oldValue = elementData(index);        elementData[index] = element;        return oldValue;    }
    @SuppressWarnings("unchecked")    E elementData(int index) {        return (E) elementData[index];    }

    // 返回元素第一次出现的下标    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 (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;    }

        List<String> strList = new ArrayList<String>(4);                   strList.add("1");                   strList.add("2");                   strList.add("3");
        // for遍历        for (int i = 0; i < strList.size(); i++) {            System.out.println(strList.get(i));        }
        // foreach        // 备注：只要实现Iterable接口，就能使用foreach       for (String s : strList) {            System.out.println(s);       }
       // foreach-lambda遍历       strList.forEach(System.out::println);
       // iterator遍历       Iterator<String> iterator = strList.iterator();       while (iterator.hasNext()){            String str = iterator.next();            System.out.println(str);            // 下一次出现ConcurrentModificationException            // 问题是因为list的iterator方法返回的是ArrayList的内部类Itr            // Itr里面的expectedModCount会与ArrayList的modCount进行比较            // 剩下的就不言而喻            strList.remove(str);            // 进行iterator遍历时，如果进行remove等操作，调用iterator的方法            // 而不是ArrayList的方法           //  iterator.remove();      }
      // ListIterator可以进行顺序、逆序遍历，可以指定index位置开始遍历      ListIterator<String> iterator = strList.listIterator();      while (iterator.hasNext()){          System.out.println(iterator.next());      }      iterator = strList.listIterator(strList.size());      while (iterator.hasPrevious()){          System.out.println(iterator.previous());          iterator.remove();      }
      // 使用并行遍历，可以将元素放在不同的迭代器进行并行遍历      Spliterator<String> spliterator = strList.spliterator();      // split，分而治之，类似算法里面的分治      Spliterator<String> otherSpliterator = spliterator.trySplit();      spliterator.forEachRemaining(System.out::println);      otherSpliterator.forEachRemaining(System.out::println);

    private void writeObject(java.io.ObjectOutputStream s)        throws java.io.IOException{        // fail-fast，后续判断是否有并发处理        int expectedModCount = modCount;        // 序列化没有标记为static、transient的字段，包括size等。        s.defaultWriteObject();
        // 没有意义，可以忽略        s.writeInt(size);
        // 序列化元素        for (int i=0; i<size; i++) {            s.writeObject(elementData[i]);        }
        if (modCount != expectedModCount) {            // ArrayList被并发处理，发生结构性修改            throw new ConcurrentModificationException();        }    }    private void readObject(java.io.ObjectInputStream s)        throws java.io.IOException, ClassNotFoundException {        elementData = EMPTY_ELEMENTDATA;
        // 反序列化没有标记为static、transient的字段，包括size等        s.defaultReadObject();
        // 可以忽略，跟writeObject里面的方法对应        s.readInt(); 
        if (size > 0) {            // 数组扩容            ensureCapacityInternal(size);
            Object[] a = elementData;            // 反序列化元素并填充到数组中            for (int i=0; i<size; i++) {                a[i] = s.readObject();            }        }    }

        List<String> strList = new ArrayList<String>(4);                   strList.add("1");                   strList.add("2");                   strList.add("3");
     // 可以使用以下三种排序方式     Collections.sort(strList);     Collections.sort(strList, String::compareTo);     strList.sort(String::compareTo);
     //java8 新增的排序方法     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++;    }

    public Object[] toArray() {        // 直接复制ArrayList的elementData        return Arrays.copyOf(elementData, size);    }
    public <T> T[] toArray(T[] a) {        if (a.length < size)            // 利用反射生成特定类型的数组并复制            // 备注：但是不知道为什么toArray的类型变量T跟ArrayList的不一致            return (T[]) Arrays.copyOf(elementData, size, a.getClass());        System.arraycopy(elementData, 0, a, 0, size);        if (a.length > size)            a[size] = null;        return a;   }   // 另外，除了根据ArrayList转化成数组，同样可以根据Arrays的asList将数组转换成List   // 备注：Arrays是数组操作的util类，可以进行排序、查找、复制、遍历等   // 注意：asList方法返回的私有静态内部类ArrayList，静态内部类ArrayList跟java.util.ArrayList不同   // 注意：静态内部类ArrayList没有重写java.util.AbstractList的remove、add等方法，默认实现是直接抛UnsupportedOperationException，因此调用会报错   List<String> strList = Arrays.asList("1", "2", "3");