Java集合类源码解析：ArrayList

2022-01-22 09:07:21

前言
源码解析
为什么用 "transient" 修饰数组变量
总结

前言

今天学习一个Java集合类使用最多的类 ArrayList , ArrayList 继承了 AbstractList，并实现了List 和 RandomAccess 等接口，

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

是一个以数组形式存储数据的集合，它具有以下的特点：

集合中的数组是有序排列的；

允许元素为null；

允许重复的数据；

非线程安全；

针对它的这些特点，我们一步步跟进源码进行解析。

源码解析

基本成员变量

先看下ArrayList 的基本成员变量

transient Object[] elementData;

private static final int DEFAULT_CAPACITY = 10;

private int size;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

elementData ：一个object数组，组成了ArrayList 的底层数据结构，由于数组类型为 Object，所以允许添加 null 。值得注意的是，变量的修饰符是 transient ，这说明这个数组无法被序列化，但是之前ArrayList却实现了序列化接口，是可以被初始化，这不是互相矛盾了吗，关于这个原因，下面会说到，别急。

DEFAULT_CAPACITY : 数组的初识容量

size ：数组元素个数

MAX_ARRAY_SIZE：数组最大容量

说完变量后，开始学习ArrayList 的基本方法，我们都知道，一个集合最重要的方法就是对元素的增删改查操作，了解了这些操作的方法，也就基本了解了容器的运作机制。

添加元素

ArrayList 中最基础的添加元素方法是 add(E e)

public boolean add(E e) {

	//调整容量

    ensureCapacityInternal(size + 1);  // Increments modCount!!

    elementData[size++] = e;

    return true;

}

源码逻辑比较简单，主要是先做了调整容量处理，并把元素存入数组的最后一个位置。

来看一下调整容量的方法 ensureCapacityInternal()，源码如下：

private void ensureCapacityInternal(int minCapacity) {

	//如果是空数组，初始化容量，取默认容量和 当前元素个数 最大值

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    ensureExplicitCapacity(minCapacity);

}

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    	//容量不够，做扩容

        grow(minCapacity);

}

private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length;

        //新容量为旧容量的1.5倍

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

    }

可以看到，调整容量的过程其实是扩容了数组的容量，并在最后调用了Arrays的copyOf方法，等于把元素组里面的内容复制到新的数组里面去，

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;

}

用一张图来表示是这样的

除了上面的add 方法外，ArrayList还提供了几个添加操作的方法，分别是

//在指定位置添加元素

public void add(int index, E element) {

	//判断index是否在size范围内

    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!

    //整体复制，并后移一位

    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;

    ensureCapacityInternal(size + numNew);  // Increments modCount

    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);  // Increments modCount

        int numMoved = size - index;

        if (numMoved > 0)

            System.arraycopy(elementData, index, elementData, index + numNew,

                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);

        size += numNew;

        return numNew != 0;

    }

这三个方法虽然也是插入的操作，但其实最后都是调用 System 的 arraycopy 方法做一个整体的复制，这是一个native的方法，功能就是把数组做一个整体的复制，并向后移了一位。如果要复制的元素很多，那么就比较耗费性能，这是比较不好的一点。

所以，一般情况下，ArrayList适合顺序添加的情景。

查询元素

E elementData(int index) {

        return (E) elementData[index];

}

public E get(int index) {

    rangeCheck(index);

    return elementData(index);

}

查询的代码比较简单，都是直接返回数组对应位置的元素，充分利用了数组根据索引查询元素的优势吗，因此效率较高。

扩展：说到查询，来提一个知识点，那就是遍历元素的效率问题，前面说了，ArrayList 实现了RandomAccess 接口，所以遍历ArrayList 的元素 get() 获取元素在效率上是优于迭代器的，至于原因，在《Java集合类："随机访问" 的RandomAccess接口》有介绍，这里不进行叙述了。

修改元素

public E set(int index, E element) {

    rangeCheck(index);

    E oldValue = elementData(index);

    elementData[index] = element;

    return oldValue;

}

也是根据索引操作数组，不多说。

删除元素

ArrayList删除元素的方法比较多，但说起来无非是三类，

1、按照下标删除元素

2、按照元素删除，这会删除ArrayList中与指定要删除的元素匹配的第一个元素

3、清除数组元素

前面两种虽然功能不同，但代码的最终调用是差不多的，都是引用类似这段代码来解决问题：

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

这段代码的逻辑大概就是把指定元素后面的所有元素整体复制并向前移动一个位置，然后最后一个元素置为null，跟插入中的部分方法逻辑很像，都是调用 System.arraycopy 来做数组操作，所以说，删除元素的效率其实也是不高的。

而第三类删除的方法其实是调用 clear ，

public void clear() {

    modCount++;

    // clear to let GC do its work

    for (int i = 0; i < size; i++)

        elementData[i] = null;

    size = 0;

}

把数组的每个元素都置为null，并把size置为0，就这么简单。

为什么用 "transient" 修饰数组变量

最后一个问题，之前说了ArrayList 可以被序列化，但其数组变量却是用transient 修饰，这是为什么呢？按照五月的仓颉大神这篇文章的解释就是：

序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法：

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

    // Write out all elements in the proper order.

    for (int i=0; i<size; i++) {

        s.writeObject(elementData[i]);

    }

    if (modCount != expectedModCount) {

        throw new ConcurrentModificationException();

    }

}

每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素，这样：

1、加快了序列化的速度

2、减小了序列化之后的文件大小

不得不说，设计者还是很用心良苦的。

总结

ArrayList 的源码分析就到这里了，因为其底层只有数组，所以源码的逻辑还是比较简单，比起HashMap这样的学习起来要轻松多了 (HashMap源码学习过程回想起来真是痛苦啊

码农公寓

前言