ArrayList源码阅读

2020-02-07 本文已影响0人骑牛上青山

概述

ArrayList是JAVA集合类中一个最为基础最为使用广泛的集合，本文将基于JDK1.8来解读ArrayList的源码实现

ArrayList的底层数据结构与基本原理

ArrayList的基础结构是数组，所以ArrayList和数组具有同样的性质：

数据插入数据删除效率较低
数据查询效率较高

那么问题来了，数组是固定大小的，ArrayList大小是可变的，内部是如何维护，如何实现的呢。其是从原理上来说很简单，那就是如果内部数组长度不够了，那就创建一个新的更大的数组，把原来的数据拷过去即可，具体代码如何实现，那就让我们来详细的看一下源码吧。

ArrayList源码

继承关系

ArrayList继承关系如下图:

ArrayList类继承关系.png

继承：ArrayList继承了AbstractList，这是list的一个基础抽象类，AbstractList则继承了AbstractCollection。AbstractCollection是所有集合类的父类。从图中我们可以看到所有的集合类都继承了Iterable类，这个类是迭代器类，为所有的集合类都提供了ForEach方法。
实现：ArrayList实现了以下几个类：
1. List：这里很奇怪，因为AbstractList也实现了List，在这里重复实现究竟有什么用意呢？
2. Serializable：这个类是为了序列化
3. RandomAccess：这个类是用来标记使用，具有这个标记的类具备以下特点：可以快速访问，并且使用下标访问会更快。例如ArrayList就实现了这个类，而LinkedList则没有。这个标记在某些情况下会有作用：例如在实现二分查找的时候，如果所传入的集合类实现了这个类则直接使用下标访问元素，使得算法实现效率更高，否则用迭代器来访问元素，会比下标访问更加快。比如Collections里的二分查找方法，就进行了这样的判断：
```
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}
```
4. Cloneable：实现该接口以使用clone方法

类属性

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 序列化序号
    private static final long serialVersionUID = 8683452581122892189L;

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

    // 空数组用于给初始化大小为0的情况进行直接赋值，或者是进行清空list操作时候直接进行赋值
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 默认容量空数组，用于无参构造函数的初始化中
    // 在有了EMPTY_ELEMENTDATA之后还要DEFAULTCAPACITY_EMPTY_ELEMENTDATA的原因是想要区分
    // 这两种情况：1.用无参构造函数初始化的空数组 
    // 2.用有参构造函数初始化，并且设定数组初始化大小为0的空数组
    // 如果不做区分这两种情况就会混在一起没法区分，然后会导致在扩容时产生出乎调用者意料的情况
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // ArrayList存储数据的数组，加上了transient进行修饰说明这个数组将不会被序列化
    // ArrayList的元素序列化反序列化是靠readObject和writeObject来实现的
    transient Object[] elementData;

    // ArrayList的大小
    private int size;
}

类构造函数

无参构造函数

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

数组容量初始化

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

用集合初始化
```
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;
    }
}
```
其余的两个构造函数比较简单就不赘述了，但是这个构造函数有一点特殊的地方。有人看到源码后，想问这句代码if (elementData.getClass() != Object[].class)究竟有什么用？我们看到注释上写了see 6260652，那就去java的官网一探究竟。看到官网给出的bug记录如下：

The Collection documentation claims that

collection.toArray()

is "identical in function" to

collection.toArray(new Object[0]);

However, the implementation of Arrays.asList does not follow this: If created with an array of a subtype (e.g. String[]), its toArray() will return an array of the same type (because it use clone()) instead of an Object[].

If one later tries to store non-Strings (or whatever) in that array, an ArrayStoreException is thrown.

简单翻译下就是collection.toArray()这个方法按照规范应该等价于collection.toArray(new Object[0])，但是各个collection有自己的实现可能会有一些意外情况出现，比如Arrays.asList，下面有一个例子：
```
    public static void main(String[] args) {
        String[] a = {"a", "b", "c"};

        List l = Arrays.asList(a);

        System.out.println(l.toArray());
        System.out.println(l.toArray(new Object[0]));
    }
```
l.toArray()返回类型是String[]，l.toArray(new Object[0])返回值则为Object[]。如果不加这句代码，内部的elementData就会被赋值为String数组，这是我们所不想看到的，所以需要多一层判断，保证这个数组的类型永远是Object[]。当然，这算是一个bug，并且在后续版本中（JAVA9）中被修复了。

核心方法

说到ArrayList的核心方法，那必须是他的扩容方法grow
```
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}   
```
这个方法是一个私有方法，当内部方法判断需要扩容的时候就会调用这个方法，那我们来看一下他的扩容机制。
1. oldCapacity是elementData的长度（注意elementData的长度是指内部数组的长度，size是list元素的数量，所以这两个数值往往是不一致的）
2. newCapacity是预计想要达到的数组容量大小，一般情况下是扩容1.5倍，即oldCapacity + (oldCapacity >> 1)，使用右移运算比乘法效率更高。
3. 接下来将预计扩容的大小与最小扩容值进行比较，取较大的值。这里有一个问题为什么比较大小不写成if (newCapacity < minCapacity)而要写成if (newCapacity - minCapacity < 0)，这是因为如果旧有的容量已经够大的话，进行1.5倍扩容后newCapacity可能已经因为数字过大溢出变成了负数，如果用newCapacity < minCapacity来比较的话那就会永远是true，这不符合我们的预期，我们的预想应该是既然新的容量已经溢出了，那么我们应该是取到溢出前的极大值，这么写，就会导致取到minCapacity。而newCapacity - minCapacity就不一样了，即使newCapacity溢出也不会影响判断。
4. 判断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;
}
```
5. 使用Arrays.copyOf方法来进行数组的扩容

在某些情况下每一次扩容1.5倍显然无法满足我们的需求，当我们预计一次性将插入大量数据的时候，频繁的扩容会导致频繁的创建新的数组，并且把旧数据迁移到新的数组之中。这个效率是非常低下的。所以我们有两种方法解决这个问题：一种就是在创建ArrayList的时候就直接用数组容量来创建数组，但是这种方法由于我们创建ArrayList的时候未必开始就会插入这么多数据，所以可能会导致内存的浪费，另一种方法就是使用ensureCapacity方法：

    public void ensureCapacity(int minCapacity) {

        // 最小容量扩展数，一般为DEFAULT_CAPACITY，也就是10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        // 如果需要的扩容大小大于minExpand，则扩容至minCapacity，否则就不进行扩容
        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;
        }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

ArrayList的添加方法如下，共有5种：

    public E set(int index, E element) {
        rangeCheck(index);

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

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

    public void add(int index, E element) {
        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;
    }

实现方法都比较简单，有几个地方需要注意一下：

在固定的index插入元素的方法都会在方法最开始调用一个名为rangeCheck的方法来检查是否越界，方法如下：
```
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
```
有人可能会好奇为什么要做这个校验，主要的原因其实在前面说过了，存储元素的数组大小不等于size的大小，举个例子，当你的ArrayList只有一个元素的时候，你的size为1，但是你的内部数组大小可能是default的10，这个校验可以避免你把数据插入到了奇怪的地方。
在插入大量数据的时候它会调用内部使用的ensureCapacityInternal来减少扩容

get方法：

    public E get(int index) {
        // 校验是否越界（校验理由同上）
        rangeCheck(index);

        // 获取元素
        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

删除方法：

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

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

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

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 {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

删除方法没什么特别的地方，无非是找到后删除，然后数组元素移动等，唯一的一个特别的地方是，删除的时候循环中是使用下标循环查找删除，而不是使用迭代器循环，原因就是，数组特性：使用下标访问更快，这也是为什么ArrayList实现了RandomAccess

序列化方法：

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

    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) {
            // be like clone(), allocate array based upon size not 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();
            }
        }
    }

集合元素存储在数组中在序列化的时候需要特殊处理，不然会有问题，因此把elementData设置为transient防止数组被序列化，并且自己实现readObject和writeObject来实现一个可以完美处理数组元素的序列化方法

总结

ArrayList是代码中出现率极高的数据结构，在日常使用中可以说是大量使用，并且本人也自认为对其了如指掌，但是直到慢慢沿袭它的源码，才发现他的很多设计理念以及一些不常用api于我来说其实是非常陌生的，因此，我一边查资料一边学习它的源码，试图能够学到一些东西。我在此把我阅读源码的一些体会和心得记录下来，希望能够与大家一起学习进步。