一、介绍

一般来讲我们所说的ArrayList指的是java.util包下的类，除此之外我们可以看一下jdk为我们提供了哪些同名不同包的ArrayList:

不同的ArrayList.jpg

(同名不同包的ArrayList)

从上图可以看到，两个ArrayList都从属于java.util包，但第二个是Arrays类的内部类，因此这两个类有什么区别我们后面聊，本文主要说一下java.util包下的ArrayList。

ArrayList是我们日常编码中使用非常多的一个集合类，通过数组来保存一组对象，是jdk为我们提供的一种可以动态扩容的数组，它的出现弥补了原始数组长度固定不变的缺陷。

继承关系图.jpg

继承关系图

① 实现了List接口，表示实现了List接口所定义的规范

② 继承自AbstractList抽象类，AbstractList同时也实现了List接口，表示继承了AbstractList对List的默认实现

① 实现了Cloneable接口，表示具有克隆的功能

② 实现了Serializable接口，表示具有序列化的功能

③ 实现了RandomAccess接口，表示具有随机访问的功能

二、成员变量

// 默认初始容量为10
private static final int DEFAULT_CAPACITY = 10;
// 空数组，没有实际意义，仅作为一个标志
private static final Object[] EMPTY_ELEMENTDATA = {
   
   };
// 默认容量的空数组，没有实际意义，仅作为一个标志
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
   
   };
// 对象数组，具有实际意义，用于保存ArrayList的元素，由此说明ArrayList是通过数组保存元素的
transient Object[] elementData;
// elementData中对象的数量
private int size;


// 继承父类AbstractList的变量
// 在使用迭代器遍历过程中，对结构修改的次数，通过该字段可以实现fail-fast快速失败
protected transient int modCount = 0;

三、存储结构

ArrayList底层结构是通过数组来保存数据的，且默认情况下该数组长度为10，即

// 默认初始容量为10
private static final int DEFAULT_CAPACITY = 10;

// 对象数组，具有实际意义，用于保存ArrayList的元素，由此说明ArrayList是通过数组保存元素的
transient Object[] elementData;

四、构造函数

① 无参构造

public ArrayList() {
   
   
    // 构造一个初始容量为 10 的空列表
    // 虽然在成员变量中我们看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA只是一个没有指定长度的空数组，可以理解为具有默认长度的空数组
    // 看到他我们就应该联想到他的长度为10
    // 从calculateCapacity方法中我们就可以理解了
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

② 指定初始容量构造函数

/**
 *    构造一个初始容量大小为 initialCapacity 的 ArrayList
 *    当initialCapacity>0时，new一个对象数组赋值给elementData，并指定数组长度为initialCapacity
 *    当initialCapacity=0时，就new一个空数组赋值给elementData
 *    其他情况下说明initialCapacity<0，此时直接抛出异常
**/
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) {
   
   
    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;
    }
}

首先将传入的集合转为对象数组，如果该数组长度为0，则直接将空数组EMPTY_ELEMENTDATA赋值给elementData，否则，如果传入的集合为ArrayList，则直接将其转换的对象数组赋值给elementData，如果不是ArrayList，则需要将对象数组的元素重新放在一个新的对象数组中。

五、扩容原理

其实ArrayList的扩容原理相当简单，只要四句话就可以说的清楚：何时、何处、怎么扩，扩了多少

① 何时（扩容的时机）

当elementData数组的长度无法满足我们继续向其添加元素时

用源码表示就是

public boolean add(E e) {
   
   
    // size表示的就是我们向elementData数组中添加的元素数量，
    // 当size+1>elementData.length时，表示当前elementData的长度已无法继续添加元素
    // 因此需要一个长度更大的elementData数组
    ensureCapacityInternal(size + 1);

    elementData[size++] = e;
    return true;
}

② 何处（针对什么进行扩容）

由于ArrayList实际是用其内部的elementData数组保存对象的，因此扩容针对的是elementData数组

用源码表示就是

private void grow(int minCapacity) {
   
   
    // 省略一些确定长度的操作...

    // 将elementData的引用指向扩容后长度更大的数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

③ 怎么扩

通过调用native修饰的jvm本地方法arraycopy，获取一个保持原数组中元素顺序，且长度更大的数组

用源码表示就是

public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

在这里需要说明的是，扩容后的elementData和扩容前的elementData其实并不是同一个数组对象，他们在内存中引用的对象地址是不同的，只是用了同一个变量来表示而已，这在源码中也是有体现的

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
   
   
    // 按照新长度的要求，new出来一个新的数组对象
    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;
}

④ 扩了多少

扩了1.5倍，即扩容前数组长度 * 1.5 = 扩容后的数组长度

用源码表示为

private void grow(int minCapacity) {
   
   
    // ...
    // 将旧的数组长度按二进制向右移一位，得到旧数组长度的一半，再加上旧数组长度，就得到了新数组长度
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // ...
    elementData = Arrays.copyOf(elementData, newCapacity);
}

六、重要方法

① 扩容

private void grow(int minCapacity)

② 数组复制，此方法在ArrayList中使用频率相当大，他是扩容的最最最核心方法

public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length)

七、基本操作 - 新增

ArrayList为我们提供的添加元素的方法有四个：直接添加、在指定位置添加、直接批量添加、在指定位置批量添加，

单个添加都是先扩容，再顺序地向element数组添加元素

而批量添加先扩容，再直接通过System.arraycopy方法将元素批量复制到element数组中

// 1、直接添加
public boolean add(E e) {
   
   
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
// 2、在指定位置添加
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++;
}
// 3、直接批量添加
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;
}
// 4、在指定位置批量添加
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方法将原数组中要删除的元素之外的元素按顺序拷贝到一个新的数组中

// 1、根据下标删除元素
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;
}
// 2、删除指定元素
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
}
// 3、根据指定集合删除交集
public boolean removeAll(Collection<?> c) {
   
   
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
// @param complement true-补集，false-交集
private boolean batchRemove(Collection<?> c, boolean complement){
   
   
    // ...
}
// 4、根据条件删除
public boolean removeIf(Predicate<? super E> filter){
   
   
    // 该方法传入一个Predicate断言函数，删除当前集合中符合传入断言的元素
    // ...省略一大堆
}
// 5、根据范围删除，删除下标fromIndex与下标toIndex之间的元素
protected void removeRange(int fromIndex, int toIndex) {
   
   
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
   
   
        elementData[i] = null;
    }
    size = newSize;
}

九、基本操作 - 修改

修改元素的方法有一个：将指定下标的元素修改为另一个元素

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

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

十、基本操作 - 查询

查询元素的方法有两个：判断是否包含指定元素、获取指定下标的元素

// 1、判断是否包含指定元素
public boolean contains(Object o) {
   
   
    return indexOf(o) >= 0;
}
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;
}
// 2、获取指定下标的元素
public E get(int index) {
   
   
    rangeCheck(index);

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

十一、内部类 - 迭代器Itr

ArrayList为我们提供了一个迭代器Itr供我们单向遍历集合

// 迭代器的属性定义
private class Itr implements Iterator<E> {
   
   
    int cursor;       // 当前遍历过程所处的下标
    int lastRet = -1; // 上一个元素的下标
    int expectedModCount = modCount; // 期望的修改次数，初始值为modCount

    // 构造方法
    Itr() {
   
   }

    // 单向遍历
    public E next(){
   
   
        checkForComodification();
        // ...省略实现
    }
    final void checkForComodification() {
   
   
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
// 获取迭代器的方法
public Iterator<E> iterator() {
   
   
    return new Itr();
}

Itr迭代器实现了fail-fast快速失败的功能，解释出来就是在使用迭代器遍历过程中如果element数组的结构发生了变化（即经过了扩容），那么就直接抛出异常，这么做的原因是为了防止多线程环境下多个线程对同一个ArrayList实例进行并发操作而导致的线程不安全问题。

回到上面的新增或删除方法中，不难发现在一旦涉及到数组结构或数组元素数量发生变化的场景，modCount都会自增，表示集合修改次数+1；

fail-fast快速失败是如何实现的？

1、获取迭代器时，迭代器内部维护了一个属性expectedModCount，初始值为modCount

2、调用ArrayList对象的新增、删除方法时，对modCount进行加一操作，即modCount++;

3、调用迭代器的next方法进行遍历时，会调用checkForComodification方法判断modCount与expectedModCount是否相等，如果不相等，则直接抛并发修改异常ConcurrentModificationException

十二、内部类 - 列表迭代器ListItr

ArrayList为我们提供了一个列表迭代器ListItr，他继承了迭代器Itr，因此他拥有Itr的所有功能；另外它实现了ListIterator接口，所以他具备了在迭代过程中对集合进行增删改查的功能，且支持双向遍历

与Itr相同，ListItr也具备fail-fast快速失败的功能

private class ListItr extends Itr implements ListIterator<E> {
   
   
    ListItr(int index) {
   
   
        super();
        cursor = index;
    }
}

public interface ListIterator<E> extends Iterator<E> {
   
   
    // 查询
    boolean hasNext();
    // 获取下一个元素
    E next();

    boolean hasPrevious();
    // 获取上一个元素
    E previous();

    int nextIndex();

    int previousIndex();
    // 删除
    void remove();
    // 修改
    void set(E e);
    // 新增
    void add(E e);
}

十三、内部类 - 子集合(视图)SubList

ArrayList为我们提供了一个子集合SubList作为ArrayList的视图，由源码可知，SubList同ArrayList一样继承了AbstractList，因此可能会提供增删改查的具体实现，另外也实现了RandomAccess表明可以根据数组下标随机访问。

private class SubList extends AbstractList<E> implements RandomAccess {
   
   
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
   
   
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
}

类似的，SubList类也支持fail-fast快速失败，只是内部维护的不是expectedModCount，而是modCount，在对SubList对象进行操作时，也会根据其内部的modCount和ArrayList的modCount进行比较，如果不相等，则直接抛异常。

十四、内部类 - 分离器ArrayListSpliterator

这个内部类的原理在这里就不讲了，就当给各位小伙伴留一个家庭作业吧~~

十五、Arrays内部类ArrayList

当我们通过Arrays.asList(T... a)方法获取集合时，发现这个方法返回的也是一个ArrayList实例，但这个实例是java.util.Arrays.ArrayList对象，并非java.util.ArrayList对象。源码如下：

public class Arrays {
   
   
    // ...

    public static <T> List<T> asList(T... a) {
   
   
        return new ArrayList<>(a);
    }
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
   
   
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
   
   
            a = Objects.requireNonNull(array);
        }
        @Override
        public int size() {
   
   
            //...
        }

        @Override
        public Object[] toArray() {
   
   
            //...
        }

        @Override
        public <T> T[] toArray(T[] a) {
   
   
            //...
        }

        @Override
        public E get(int index) {
   
   
            //...
        }

        @Override
        public E set(int index, E element) {
   
   
            //...
        }

        @Override
        public int indexOf(Object o) {
   
   
            //...
        }

        @Override
        public boolean contains(Object o) {
   
   
            //...
        }

        @Override
        public Spliterator<E> spliterator() {
   
   
            //...
        }

        @Override
        public void forEach(Consumer<? super E> action) {
   
   
            //...
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
   
   
            //...
        }

        @Override
        public void sort(Comparator<? super E> c) {
   
   
            //...
        }
    }
}

从上面源码可以看出，Arrays内部类ArrayList重写了AbstractList中查询、修改以及其他不修改结构的方法，而新增、修改这种修改结构的方法则是使用AbstractList提供的默认实现，而默认实现则是直接抛异常UnsupportedOperationException，我们来看一下

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
   
   
    protected AbstractList() {
   
   
    }

    public void add(int index, E element) {
   
   
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
   
   
        throw new UnsupportedOperationException();
    }
}

因此，Arrays.asList的返回对象是一个Arrays内部类,并没有实现集合的修改方法。Arrays.asList 体现的是适配器模式,只是转换接口,后台的数据仍是数组。

至此，我们已经把java.util.ArrayList的源码从头撸到尾了，一共1478行代码，也很简单。

如果有想入门源码阅读的小伙伴，真心推荐就从ArrayList开始。

在一件事上如果别人不愿听取你的建议，那就让自己强大起来，强大到你说的每一句话在别人眼里都是真理。

ArrayList源码学习

一、介绍

二、成员变量

三、存储结构

四、构造函数

① 无参构造

② 指定初始容量构造函数

③ 通过一个集合构造

五、扩容原理

六、重要方法

七、基本操作 - 新增

八、基本操作 - 删除

九、基本操作 - 修改

十、基本操作 - 查询

十一、内部类 - 迭代器Itr

十二、内部类 - 列表迭代器ListItr

十三、内部类 - 子集合(视图)SubList

十四、内部类 - 分离器ArrayListSpliterator

十五、Arrays内部类ArrayList

热门文章

最新文章

相关电子书