JDK源码分析－－ArrayList深入理解

港控/mmm° 2022-03-18 10:37 338阅读 0赞

## **一、实现原理** ##

以**JDK1.8.0\_74**源码为基础进行分析。

1、基于数组的实现，是一个容量能自动增长的动态数组。

2、ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

3、随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。

## **二、关键源码** ##

**（一）属性**

1、默认初始容量

/**
    * Default initial capacity.
    */
    private static final int DEFAULT_CAPACITY = 10;

2、默认的空实例赋值

/**
    * Shared empty array instance used for empty instances.
    */
    private static final Object[] EMPTY_ELEMENTDATA = {};

3、顾名思义，含有默认值的空实例。其和EMPTY\_ELEMENTDATA有什么区别呢？

其在添加第一个元素时，会默认将Object数组的容量扩展到默认大小，即10；依个人理解，好处就是在添加10以内的元素时不需要频繁扩容；具体在下面讲构造方法时予以说明。

/**
    * 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.
    */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

4、实际存放元素的Object数组

/**
    * 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 Object[] elementData; // non-private to simplify nested class access

5、存放元素的数量

/**
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
    private int size;

**（二）构造方法**

1、包含初始容量的构造方法。数组大小为指定容量，如果指定为0，则数组赋值为EMPTY\_ELEMENTDATA；**在添加第1个元素时，仅扩展容量为1；**继续添加元素怎么扩容呢，请看“二.（三）”。

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

2、不含初始容量的构造方法。默认赋值为DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA；**在添加第1个元素时，会扩展容量为默认值10。**

public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3、构造包含指定元素的列表，不解释。

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

**（三）研究下add(E e)方法**

源码：

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

讲一下第1行的“扩容”：ensureCapacityInternal(size + 1)

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

这里的“扩容”方法并非是一定有扩容的操作；如果数组为空实例且等于DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA时，取默认容量10和扩容参数值的最大值；然后执行容量确认方法ensureExplicitCapacity(minCapacity)。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时，它的值都会加1；记录ArrayList结构性变化的次数；在迭代器执行next()方法时，判断了当前的modCount跟初始化Itr时的expectedModCount是否相同，不同则说明列表数据进行了结构性改变，此时就会抛出ConcurrentModificationException。
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//要“扩容”的值大于当前容量时，执行扩容操作
           grow(minCapacity);
    }

特此说明modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时，它的值都会加1；记录ArrayList结构性变化的次数；在迭代器执行next()方法时，判断了当前的modCount跟初始化Itr时的expectedModCount是否相同，不同则说明列表数据进行了结构性改变，此时就会抛出ConcurrentModificationException。

真正的扩容方法：

private void grow(int minCapacity) {
 // overflow-conscious code
 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);//将原数据复制到扩容后的数组中，赋值给elementData。
 }

扩容规律，总结：**当添加元素后的需要的容量X大于原容量Y时进行扩容，首先将Y扩大约1.5倍（取整）得到Z，取X和Z中的最大值作为此次扩容的实际容量。**

用一个表格来展示（请先弄懂有参和无参构造方法的区别，前面有讲到）：

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:82.85pt;"> 元素个数（size） </td> 
 <td style="vertical-align:top;width:22.4pt;"> 0 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 1 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 2 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 3 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 4 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 5 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 6 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 7 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 8 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 9 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 11 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 12 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 13 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 14 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 16 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:82.85pt;"> new ArrayList() </td> 
 <td style="vertical-align:top;width:22.4pt;"> 0 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 10 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 15 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 22 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:82.85pt;"> new ArrayList(0) </td> 
 <td style="vertical-align:top;width:22.4pt;"> 0 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 1 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 2 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 3 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 4 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 6 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 6 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 9 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 9 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 9 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 13 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 13 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 13 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 13 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 19 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 19 </td> 
 <td style="vertical-align:top;width:22.85pt;"> 19 </td> 
 </tr> 
 </tbody> 
</table>

**（四）Arrays.copyOf(elementData, newCapacity)**

Arrays类与ArrayList处在同一个包下，源码中对该类的注释为：该类包含用于操作数组的各种方法(例如排序和搜索)。该类还包含一个静态工厂允许将数组视为列表。

扩容时用到此类的copyOf()方法，源码如下：

public static <T> T[] copyOf(T[] original, int newLength) {
 return (T[]) copyOf(original, newLength, original.getClass());
 }
 public static <T,U> T[] copyOf(U[] original, int newLength, 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));
 return copy;
 }
 public static native void arraycopy(Object src, int srcPos,
 Object dest, int destPos,
 int length);

通过源码可以看到，扩容的原理其实是在创建具有新长度的数组，调用System.arraycopy()方法将原数组中的内容复制到新数组中；System.arraycopy()方法使用**native**修饰，调用的是系统本地方法；在openJDK中可以看到其实际是调用的是C语言的函数；memmove()函数复制效率高，Java强烈推荐在复制大批量数组元素时使用此方法。

## **三、应用技巧** ##

1、元素个数确定或可预知范围时，可使用有参构造方法构造实例列表。ArrayList的频繁扩容对时间和空间都会有较大的效率影响。

2、为了避免空间浪费，在对List操作完成后可以执行trimToSize()方法，将其处理成刚好填满的状态，即容量大小为元素个数。（需要注意的是，这里不会处理掉值为null的元素）

## **四、其他知识** ##

1、线程不安全。因此多线程环境下请使用如下列表：

（1）使用Collections的以下方法返回线程安全的ArrayList类

public static <T> List<T> synchronizedList(List<T> list) {
 return (list instanceof RandomAccess ?
 new SynchronizedRandomAccessList<>(list) :
 new SynchronizedList<>(list));
 }

（2）使用concurrent并发包下的CopyOnWriteArrayList类

2、Fail-Fast机制。

ArrayList采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败。是对不支持并发操作的快速响应。

3、ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

4、ArrayList自己实现了序列化和反序列化的方法，通过实现 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法来对自身被transient修饰的属性进行序列化和反序列化。

## **五、知识延伸：几种列表实现的泛解** ##

需要对比的列表实现：ArrayList、Vector、CopyOnWriteArrayList、Collections.synchronizedList(list)

**（一）ArrayList**

非线程安全，在一个线程遍历，另一个线程修改时，会报ConcurrentModificationException异常。除此之外，由于未做同步处理，可能导致数据不一致。

**（二）Vector**

线程安全，同样采用数组实现。其实现线程安全的的方式是在方法上添加synchronized关键字，这种方式严重影响执行效率，因此不推荐使用。

**（三）Collections.synchronizedList**

这个方法的源码见**四.1.（1）**。我们这里讨论的是ArrayList，而ArrayList实现了RandomAccess接口，因此通过Collections的这个方法返回的是SynchronizedRandomAccessList类的实例。

SynchronizedRandomAccessList继承于SynchronizedList，SynchronizedList继承于SynchronizedCollection；在SynchronizedCollection中有2个成员变量，如下：

final Collection<E> c;  // Backing Collection

final Object mutex;     // Object on which to synchronize

Collection<E> c 为实际的集合；Object mutex 用于同步加锁，在每个方法中通过对mutex的加锁，达到操作c线程安全的目的。

**（四）CopyOnWriteArrayList**

先看源码，成员变量有2个：

/\*\* The lock protecting all mutators \*/

final transient ReentrantLock lock = new ReentrantLock();

/\*\* The array, accessed only via getArray/setArray. \*/

private transient volatile Object\[\] array;

1、关键字transient，被修饰属性不参与默认序列化，其序列化的实现通过writeObject方法和readObject方法实现。

2、使用ReentrantLock重入锁，实现线程安全。

官方说明：一个可重入的互斥锁定 Lock，它具有与使用 synchronized 方法和语句所访问的隐式监视器锁定相同的一些基本行为和语义，但功能更强大。ReentrantLock 将由最近成功获得锁定，并且还没有释放该锁定的线程所拥有。当锁定没有被另一个线程所拥有时，调用 lock 的线程将成功获取该锁定并返回。如果当前线程已经拥有该锁定，此方法将立即返回。可以使用 isHeldByCurrentThread() 和 getHoldCount() 方法来检查此情况是否发生。

3、来自网上的一段解释

CopyOnWriteArrayList:CopyOnWriteArrayList这是一个ArrayList的线程安全的变体，其原理大概可以通俗的理解为:初始化的时候只有一个容器，很常一段时间，这个容器数据、数量等没有发生变化的时候，大家(多个线程)，都是读取(假设这段时间里只发生读取的操作)同一个容器中的数据，所以这样大家读到的数据都是唯一、一致、安全的，但是后来有人往里面增加了一个数据，这个时候CopyOnWriteArrayList 底层实现添加的原理是先copy出一个容器(可以简称副本)，再往新的容器里添加这个新的数据，最后把新的容器的引用地址赋值给了之前那个旧的的容器地址，但是在添加这个数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器里的数据。

**（五）CopyOnWriteArrayList和Collections.synchronizedList性能说明**

CopyOnWriteArrayList，发生修改时候做copy，新老版本分离，保证读的高性能，适用于以读为主，读操作远远大于写操作的场景中使用，比如缓存。而Collections.synchronizedList则可以用在CopyOnWriteArrayList不适用，但是有需要同步列表的地方，读写操作都比较均匀的地方。