JDK源码阅读|非同步的动态数组ArrayList

迷南。 2022-09-03 14:28 79阅读 0赞

### ArrayList源码分析 ###

*   *  简介
     *  ArrayList类的注释
     *  ArrayList的继承体系
     *   *  RandomAccess接口：
         *  Cloneable接口
         *  浅拷贝和深拷贝的区别：
     *  ArrayList的关键属性
     *  ArrayList的3个构造方法
     *  ArrayList的其它方法
     *   *  关于容量操作的
         *  添加元素：
         *  增加一个集合的元素
         *  删除一个元素
         *  删除所有元素：
     *  modCount作用
     *  面试问题
     *   *  ArrayList如何扩容？
         *  ArrayList 频繁扩容导致添加性能急剧下降，如何处理？
         *  ArrayList插入或删除元素是否一定比LinkedList慢？
         *  ArrayList 是线程安全的吗？
         *  什么情况下不用给ArrayList加同步锁呢？
         *  如何复制某个ArrayList到另外一个ArrayList中去呢？你能列举几种？
         *  ArrayList如何做到并发修改，而不出现并发修改异常？
         *  ArrayList和LinkedList 的区别？

## 简介 ##

本文根据jdk中ArrayList的源码及源码中的注释做一些笔记，文中首先给出ArrayList源码中官方给该类的一个注释总结，然后分析该类的继承结构，关键属性，构造方法、其它的一些核心方法，最后文末补充一些收集的关于ArrayList的面试问题。文中提到的注释指源码中的英文注释。

## ArrayList类的注释 ##

*  ArrayList是List接口的一个Resizable-array实现。实现了列表所有可选的操作，允许包括null的所有元素。除了实现列表接口之外，这个类还提供了操作内部用于存储list的数组大小的方法。(这个类大致相当于Vector，只是它是不同步的。)
 *  size、isEmpty、get、set、iterator和listIterator等操作在固定时间内运行。add操作在摊销常数时间内运行，也就是说，添加n个元素需要O(N)时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedList的实现相比，常数系数较低。
 *  每个ArrayList实例都有一个容量。容量是用于在列表中存储元素的数组的大小。它总是至少和列表大小一样大。当元素被添加到ArrayList中时，它的容量会自动增长。增长政策的细节没有指定，但是添加一个元素有固定的摊销时间成本是明确的。
 *  在添加大量元素之前，可以使用ensureCapacity操作增加ArrayList实例的容量。这可能会减少增量分配的数量。请注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，并且至少有一个线程在结构上修改了列表，那么它必须在外部同步的。
    
    (结构修改是指任何添加或删除一个或多个元素的操作，是对底层数组进行重新调整；仅仅设置一个元素的值不是一个结构上的修改）这种同步通常是通过对一些自然封装列表的对象进行同步来实现的。如果不存在这样的对象，则应该使用Collections. synchronizedList方法“包装”列表。最好在创建时这样做，以防止意外地不同步地访问列表。比如下面这种方式：
    
    List list = Collections.synchronizedList(new ArrayList(… )) ;
 *  这个类的迭代器和listIterator方法返回的迭代器是快速失败的（fast-failed）–如果列表在创建迭代器之后的任何时候进行了结构上的修改，如果不是通过迭代器自己的Remove或Add方法，那么迭代器将抛出一个ConcurrentModificationException。因此，面对并发修改，迭代器会迅速而干净地失败。  
    请注意，迭代器的fast-failed行为无法保证，一般来说，不可能在存在不同步并发修改的情况下提供任何硬保证。迭代器在最大努力的基础上抛出ConcurrentModificationException。因此，如果程序的正确性依赖于这个异常是错误的：因为迭代器的快速失败行为应该只用于检测bug。

该类是Java Collection框架的成员。

## ArrayList的继承体系 ##

继承体系的diagram图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdoYW8yMDE2MDcwMzAxMDE_size_16_color_FFFFFF_t_70_pic_center]

可见其直接实现了Cloneable、Serializable、RandomAccess接口，并继承自AbstractList。

这里的3个接口都是起着标记作用，内部并不包含任何实现，只是通过这种标记，让实现了该接口的类要重写或含有某些方法，比如实现Cloneable接口一般要重写Object.clone()，而ArrayList为符合Serializable要求，实现了writeObject（ObjectOutputStream）和readObject（ObjectInputStream），并包含了一个序列化Id的类成员变量serialVersionUID。

下面就介绍ArrayList实现RandomAccess接口和Cloneable接口后的一些作用。

### RandomAccess接口： ###

该接口起到一个标记作用，标记实现该接口的List支持快速随机访问，这里的随机访问指list.get(index)这种操作。其首要作用是能让算法在随机或顺序访问时使用性能更优的方式。什么是更优的方式呢，其源代码中注释里提到：

//for typical instances of the class, thisloop:
    for (int i=0, n=list.size(); i < n; i++)
    	list.get(i) ;
    
    //runs faster than this loop:
    for (Iterator i=list.iterator() ; i.hasNext(): )
    	i.next() ;

所以实现了这个接口的List遍历时使用随机访问的速度更快。

### Cloneable接口 ###

其注释中提到该接口用于标记该类的实例能够用Object.clone()方法实现field-to-field的复制。实现该接口一般要重写Object.clone()方法。

ArrayList中的重写如下：

//返回ArrayList实例的一个浅拷贝。
    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);
        }
    }

### 浅拷贝和深拷贝的区别： ###

如果拷贝对象的元素或字段中有引用类型，浅拷贝直接把引用类型的地址复制到新对象，这使得原对象和新对象的字段或元素实际上是共享的，所以元对象的字段 或元素修改后，新对象也会改变。

而深拷贝中，如果拷贝对象的元素或字段中有引用类型，则会新创建一个引用类型对应的对象，然后也对该对象做递归的深拷贝。

简单来讲的话：浅拷贝就是虽是两个账号，但是账号里的钱是共享的，同步的。深拷贝则是两个账号的钱各不影响，隔离的。

## ArrayList的关键属性 ##

/** * Default initial capacity.集合的默认容量，默认为10，通过new ArrayList()创建List集合实例时的默认容量是10。 */
    private static final int DEFAULT_CAPACITY = 10;
    
    /** * Shared empty array instance used for empty instances. 空数组，通过new ArrayList(0)创建List集合实例时用的是这个空数组。 */
    private static final Object[] EMPTY_ELEMENTDATA = { };
    
    /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. 默认容量空数组，这种是通过new ArrayList()无参构造方法创建集合时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY(10)个元素 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. 存储数据元素的数组，使用transient修饰，该字段不被序列化。 */
    transient Object[] elementData; // non-private to simplify nested class access
    
    //The size of the ArrayList (the number of elements it contains).
    //存储数据元素的个数，注意是元素个数，不是底层数组elementData的长度。
    private int size;

## ArrayList的3个构造方法 ##

ArrayList有3个构造方法：带初始容量的有参构造、使用默认容量的无参构造、带集合参数的有参构造。

/**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
       
    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);
        }
    }
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

## ArrayList的其它方法 ##

### 关于容量操作的 ###

减小容量大小到实际的数组大小size来最小化存储空间。

public void trimToSize() {
        modCount++;//structural修改次数+1
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

**增加容量大小**

可以主动调用ensureCapacity(int minCapacity) 确保至少有能容纳minCapacity指定大小的容量。

由于增加容量属于structural修改，所以**modCount++**，标识结构化修改次数加一。

容量不能超过

//这个是给用户主动调用的
    public void ensureCapacity(int minCapacity) { 
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)     
            ? 0
            : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) { 
            ensureExplicitCapacity(minCapacity);
        }
    }
    
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    	//add（）方法调用这个扩容
        private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    	//容量不够时才会扩容
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++; //structural修改次数+1
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

而实际上真正执行扩容操作的是\*\*grow(int minCapacity)\*\*方法，**增加的容量的方式是：增加当前容量的一半，如果还没有minCapacity大，则直接增加到minCapacity。**

//核心的扩容代码
    private void grow(int minCapacity) { 
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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;
    }

### 添加元素： ###

增加一个元素

增加容量大小，并添加一个元素到list末尾。看其调用的方法可知，实际上只有容量不够时才会增加容量大小。

// Appends the specified element to the end of this list.
    
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

### 增加一个集合的元素 ###

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

### 删除一个元素 ###

删除指定index的元素如下，而删除指定元素remove(Object o) 的方法实际上也是先便利找到该元素的index，再使用一个和该方法差不多的根据index删除元素的方法完成删除。

当删除元素后，底层数组的长度会减一，让垃圾回收器回收堆空间。

public E remove(int index) { 
        rangeCheck(index);
        modCount++;//structural修改次数+1
        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;
    }

### 删除所有元素： ###

public void clear() { 
        modCount++;//结构化修改次数+1
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

小结：

其它的方法大体都是这个模式，不复杂，只要涉及到插入元素需要移动大量数组元素、或者是需要添加大量元素的，都是调用的一个底层函数**System.arraycopy**（sourceArr,startIndex,length,aimArr,startIndex,length）完成的.

而本质上涉及到结构化修改的操作，一般就包含这几个操作：  
扩容（可选，如果是增加就需要）、modCount++（如果没有扩容则需要单独执行）、找到修改的位置（index）、check Index范围、修改底层数组elementData。

## modCount作用 ##

该类的注释中就已经提到过了，modCount是记录结构化修改的次数的，比如再迭代器iterator执行过程中或者是sort（）方法中都会check这个modCount的值，如果中间有做结构化修改导致modCout不一致，则会报错ConcurrentModificationException（），即并发修改异常。我把它看作一个乐观锁的标志位，它默认在迭代或是sort等操作时可以访问list做一些非结构化的修改。

## 面试问题 ##

### ArrayList如何扩容？ ###

第一次扩容10，以后每次都扩容原容量的1.5倍，扩容通过位运算右移动1位。

### ArrayList 频繁扩容导致添加性能急剧下降，如何处理？ ###

提前定义ArrayList集合的初始容量，从而不用花费大量时间在自动扩容上，即初始化时构造函数中指定容量。

### ArrayList插入或删除元素是否一定比LinkedList慢？ ###

从二者底层数据结构上来说：

ArrayList是实现了基于动态数组的数据结构  
LinkedList基于链表的数据结构。  
**效率对比：**

首部插入：LinkedList首部插入数据很快，因为只需要修改插入元素前后节点的prev值和next值即可。ArrayList首部插入数据慢，因为数组复制的方式移位耗时多。  
中间插入：LinkedList中间插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList中间插入数据快，因为定位插入元素位置的速度快，移位操作的元素没那么多。  
尾部插入：LinkedList尾部插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList尾部插入数据快，为定位插入元素位置的速度快，插入后移位操作的数据量少；  
**总结：**

在集合里面插入元素速度比对结果是：首部插入，LinkedList更快；中间和尾部插入，ArrayList更快；  
在集合里面删除元素类似，首部删除，LinkedList更快；中间删除和尾部删除，ArrayList更快；  
因此，**数据量不大的集合**，主要进行插入、删除操作，建议使用LinkedList；**数据量大的集合**，使用ArrayList就可以了，不仅查询速度快，并且插入和删除效率也相对较高。

### ArrayList 是线程安全的吗？ ###

正如源码的注释中提到的，ArrayList并不是线程安全的集合！如果需要保证线程安全，建议使用**Vector**集合，其是线程安全的，但是相对于ArrayList来说，效率比较低。Vector为什么是线程安全的呢，因为它在所有结构化操作上都加了**synchronized**锁，synchronized锁效率低，Vector可以看作一个带有同步锁的ArrayList版本。

也可以使用 List list = Collections.synchronizedList(new ArrayList(…));来封装list来实现ArrayList的同步操作。

### 什么情况下不用给ArrayList加同步锁呢？ ###

第一，在单线程情况下不需要加锁，为效率问题考虑！  
第二，当ArrayList作为局部变量的时候不需要加锁，因为局部变量属于某一线程，而我们上述例子中是吧ArrayList作为成员变量来使用，成员变量的集合是需要被所有线程共享的，这是需要加锁！（深入理解JVM中提到过。）

### 如何复制某个ArrayList到另外一个ArrayList中去呢？你能列举几种？ ###

1.  使用clone()方法，因为ArrayList实现了Cloneable接口，可以被克隆
2.  使用ArrayList构造方法，ArrayList(Collection<? extends E> c)
3.  使用addAll(Collection<? extends E> c)方法
4.  自己写循环去一个一个add()

### ArrayList如何做到并发修改，而不出现并发修改异常？ ###

问题：已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时，如何保证还可以正常的写入数据到集合？  
新建一个线程任务类：

public class CollectionThread implements Runnable{ 
    private static ArrayList<String> list = new ArrayList<>();
    static { 
        list.add("Jack");
        list.add("Amy");
        list.add("Lucy");
    }
    
    @Override
    public void run() { 
        for (String value : list){ 
            System.out.println(value);
            // 在读取数据的同时又向集合写入数据
            list.add("Coco");// 会出现并发修改异常
        }
    }
    }

测试在多线程条件下读取共享集合数据的同时向其写入：

public class Test03 { 
        public static void main(String[] args) { 
            // 创建线程任务
            CollectionThread collectionThread = new CollectionThread();
    
            // 开启10条线程
            for (int i = 0; i < 10; i++) { 
                new Thread(collectionThread).start();
            }
        }
    }

现然这样来遍历list的时候会读取到修改后的modCount，从而报并发修改错误。

结果报错：java.util.ConcurrentModificationException

为解决此问题呢，java引入了一个可以保证读和写都是线程安全的集合(读写分离集合)：**CopyOnWriteArrayList**

所以解决方案就是：

// private static ArrayList<String> list = new ArrayList<>();
        // 使用读写分离集合替换掉原来的ArrayList
        private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
        static { 
            list.add("Jack");
            list.add("Amy");
            list.add("Lucy");
        }
        @Override
        public void run() { 
            for (String value : list){ 
                System.out.println(value);
                // 在读取数据的同时又向集合写入数据
                list.add("Coco");// 会出现并发修改异常
            }
        }

成功解决并发修改异常！

### ArrayList和LinkedList 的区别？ ###

ArrayList  
基于动态数组的数据结构  
对于随机访问的get和set，其效率优于LinkedList  
对于随机操作的add和remove，ArrayList不一定比LinkedList慢(ArrayList底层由于是动态数组，因此并不是每一次add和remove都需要创建新数组)  
LinkedList  
基于链表的数据结构  
对于顺序操作，LinkedList 不一定比ArrayList慢  
对于随机操作，LinkedList 效率明显低于LinkedList

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdoYW8yMDE2MDcwMzAxMDE_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/5767f3a31c89420cbf0775897544b5f7.png