Java集合系列——ArrayList源码详解

时间：2021-05-07 17:53:12

上篇https://blog.csdn.net/friendlychen/article/details/79965762介绍了Java集合大家族的基本介绍，这里将具体介绍下ArrayList这个常用的List接口的实现类。

1、ArrayList概述

ArrayList作为Java集合的一个成员，是List接口的一个具体实现，底层是由数组的形式实现的，接下来从ArrayList源码角度分析下，JDK中每个版本对ArrayList都做了不同的优化，比如一个初始化的集合长度，在JDK1.8之后，默认是空的，在add的时候，会自动填充到10，而1.8之前是在初始化的时候就给了默认长度10。这里主要讨论1.8中的源码。
ArrayList是List的实现类。包含了添加，删除，替换等行为，ArrayList允许为null

2、可用的操作

**添加**
添加单个元素到尾部
public boolean add(E e) {}
添加单个元素到特定的位置
public void add(int index, E element) {}
添加整个集合到尾部
public boolean addAll(Collection<? extends E> c) {}
添加整个集合到特定的位置
public boolean addAll(int index, Collection<? extends E> c) {}

**删除**
删除对应下标的元素
public E remove(int index) {}
删除对应的元素
public boolean remove(Object o) {}
删除所有元素
public void clear() {}
删除集合中的跟参数集合中一样的元素
public boolean removeAll(Collection<?> c) {}
保留集合中的元素，删除其他。
public boolean retainAll(Collection<?> c) {}

**查询**
查询对应下标的元素
public E get(int index) {}
查询是否包含当前元素
public boolean contains(Object o) {}
查询元素的第一次出现的下标
public int indexOf(Object o) {}
查询元素最后一次出现的下标
public int lastIndexOf(Object o) {}

**替换**
public E set(int index, E element) {}


**其他常用接口**
返回当前数组元素数量
public int size() {}
判断当前数组元素是否为空
public boolean isEmpty() {}
转换成数组的形式
public Object[] toArray() {
转换成对象数组并且复制到原有数组中，若长度超过，则丢弃
public <T> T[] toArray(T[] a) {
两种迭代器
public ListIterator<E> listIterator() {
public Iterator<E> iterator() {
上面是双向迭代，下面是从开始到末尾一个个来

3、源码分析

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ }

ArrayList继承了AbstractList抽象类，AbstractList抽象类实现了List接口。
ArrayList实现了RandomAccess随机访问，Clone克隆，Serializable序列化和List的接口
RandomAccess就是个没有任何方法的接口，看源码注解，就是专门为List实现类使用的，用于支持快速随机访问的意思，就相当于实现了Serializable就等于支持序列化和反序列化，这是个标准。里面没有任何方法的。

public ArrayList(int initialCapacity) {
    super();
//判断参数合法性，必须是大于0的
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() {
    super();
//这里EMPTY_ELEMENTDATA是空集合
    this.elementData = EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

三个构造方法，一个无参构造方法，无参默认是空集合，add添加的时候集合长度自动填充到10，一个int类型参数的构造方法,可以指定初始化数量，一个集合参数的构造方法
三个参数都对elementData进行初始化，那么这个elementData是什么呢?看变量声明，这就是一个数组，这就是为什么我们说ArrayList底层是数组结构的原因，我们操作ArrayList其实就是对这个elementData数组进行操作。

两个常量，一个是默认容量10
private static final int DEFAULT_CAPACITY = 10;

空集合
private static final Object[] EMPTY_ELEMENTDATA = {};

DEFAULT_CAPACITY，就是默认的容量，数组长度默认是10。
接下来是对集合的各种操作，添加，删除，查询，修改等等。
添加数据

**添加一个数据**
public boolean add(E e) {
//扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
//典型的数组操作，把e元素添加到数组的第size++个位置上，
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
//做了初始化操作，如果为空的话，则要么10 ，要么minCapacity，最少10
    if (elementData == EMPTY_ELEMENTDATA) {  
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
//扩容
    ensureExplicitCapacity(minCapacity);
}
//扩容的操作
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  //fail-fast机制需要
//与原来数组长度比较，如果长了，则扩容
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
//扩容
        grow(minCapacity);
}

扩容的详细源码
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //原来数组长度加上现有数组长度除以2。>> 右移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:
//真正的数组拷贝，调用的是System.arraycopy（）方法，这其实是相当于重新建一个数组，这种速度是很慢的，浪费时间空间。
    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;
}
**删除源码**
public E remove(int index) {
//判断下标合法性
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//fail-fast机制需要
    modCount++;
//获取到相应的元素，就是从数组中取出
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
//数组新建，
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
//这里把最后一个元素置为null，就是移出了最后一个元素坐在的位置
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

**查找**
public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//这里很简单就是elementData这个数组中下标为index的元素
    return (E) elementData[index];
}
**查找元素下标**
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
//其实也是循环数组，如果匹配，则返回下标，否则不匹配，返回的是-1
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

**替代**
public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//找出那个对应的原色，然后进行替换
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}

4、总结

最后看看modCount这个参数
我们知道ArrayList是线程不安全的，当多线程进行迭代操作时可能会产生冲突，此时，fail-fast，也就是错误检测机制，就可以预防这种错误。
modCount顾名思义就是修改次数；
当一个线程进行遍历集合时，另外一个线程修改了结构，比如添加add，删除remove元素时，modCount会自增1，这时程序每次迭代操作时，都会检测到这个modCount已经有变化了，有变化会抛出个ConcurrentModificationException异常，一般查询元素和修改元素是不会有这种异常的。（也就是如果不引起ArrayList结构变化的操作，一般是没问题的，删除和新增元素都引起了ArrayList结构的变化了）。

我们简单回顾下ArrayList源码，基本都是对elementData这个数组进行操作，比如新增元素时，其实调用的是Arrays.copyOf(elementData, newCapacity)，我们知道已经分配好的数组的长度是不能变得，因此这个方法其实是新建了一个数组，然后把原来的数组的元素在复制一份过来，在把新元素插进去。这样我们就实现了ArrayList元素的增加。相信大家可以理解为什么我们说ArrayList底层是数组实现的原因了吧。接下来作为对比，看看底层作为链表形式的LinkedList的使用和源码简单分析。

标签：

相关文章