likes
comments
collection
share

比较详细的ArrayList源码解析

作者站长头像
站长
· 阅读数 14

ArrayList源码解析

ArrayList是数组结构，是一块连续的内存空间，我们从数组初始化来开始阅读源码：

初始化

ArrayList<Integer> arrayList = new ArrayList<>();

源码解析

// 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// transient关键字表示修饰的变量会在序列化时被忽略，即仅存在于内存而不会在磁盘里持久化
transient Object[] elementData; 

public ArrayList() {
    // 初始化的时候赋予空内容，所以初始长度为0
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList初始化的代码很简单，就是赋予一个空数组，此时的数组长度是0。

为什么elementData要用transient修饰？

出于效率的考虑，数组长度范围可能分配了100，但是实际只用了50，剩下的50不需要进行序列化，所以先用transient修饰，然后重写readObject和writeObject方法来自定义序列化和反序列化策略。

序列化的时候ObjectStream会看类中有没有自定义序列化方法，有就用自定义的，没有则使用默认的序列化。

源码解析

// 自定义数组的写序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    int expectedModCount = modCount;
    // 对没有被transient修饰的变量进行默认的序列化
    s.defaultWriteObject();

    // 数组元素数量序列化
    s.writeInt(size);

    // 将数组里面不为空的元素序列化，而不是整个数组空间，避免浪费
    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;

    // 对没有被transient修饰的变量进行默认的序列化
    s.defaultReadObject();

    // 读数组元素数量
    s.readInt();

    if (size > 0) {
        // 计算数组所需的最小容量
        int capacity = calculateCapacity(elementData, size);
        // 检查数组中是否包含非法元素
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 保证数组有足够的容量
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 遍历读取数组元素
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

添加元素

添加元素有4种方式：

  1. 添加元素到数组末尾

    arrayList.add(1);

  2. 添加元素到指定位置

    arrayList.add(1, 0);

  3. 添加多个元素到数组末尾

    arrayList.addAll(list);

  4. 添加多个元素到指定位置

    arrayList.addAll(0, list);

源码解析

添加单个元素
// 数组允许的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

// 记录数组的元素数量
private int size;

public boolean add(E e) {
    // 添加元素后size加一，要保证数组有足够的容量组装载
    ensureCapacityInternal(size + 1);
    // 将新元素放到数组末尾
    elementData[size++] = e;
    return true;
}

// 保证数组的容量是足够的
// minCapacity：数组所需的最小容量，通过上级调用层可知值等于size+1
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 先做一层判断，如果数组刚刚初始化，那么将数组容量设置为默认值DEFAULT_CAPACITY，即10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // Fail-Fast（快速失败机制）
    modCount++;

    // 如果所需容量大于数组当前容量，那么就去进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 数组容量不够添加元素了，这里进行扩容
// minCapacity：数组需要的最小容量
private void grow(int minCapacity) {
    // 记录原有容量
    int oldCapacity = elementData.length;
    // 计算出1.5倍的容量作为新容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量小于所需最小容量，那么新容量等于所需最小容量，保证够用
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新容量大于允许的最大数量，处理一下，保证在允许的范围内，不然就抛出OutOfMemoryError异常
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 处理过程
        newCapacity = hugeCapacity(minCapacity);
    // 调用Arrays.copyOf()方法进行数组拷贝，产生新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 容量小于0，抛出OutOfMemoryError异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 容量大于最大值，令其等于最大值
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

数组添加元素的源码也不难理解，每次添加新元素的时候，判断一下数组容量是否够用，够用就将新元素放到数组末尾，不够就进行扩容。

指定索引添加单个元素
// index：索引位置
public void add(int index, E element) {
    // 索引位置合法性检查
    rangeCheckForAdd(index);
	
    // 添加元素后size加一，要保证数组有足够的容量组装载
    ensureCapacityInternal(size + 1);
    
    // 数据拷贝，将索引位置及后面的元素向右移，将位置留给新添加的元素
    // System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
    // 从原数组src的srcPos位置开始向目标数组dest的destPos位置复制length个元素
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// 指定的插入位置必须在合法的范围内，否则抛出IndexOutOfBoundsException异常
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 异常描述文本
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

指定索引位置添加元素的方式会使用System.arraycopy()进行数组复制，这是Java种最快的数组复制方式，比循环复制数组元素要快。

和第一种添加元素的方式类似，但是会多一个操作：将索引位置之后的元素右移一位。

批量添加元素
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    // 拷贝集合参数到目标数组
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    // 如果集合参数是空数组，那么返回false，表示没有元素插入也就没有成功
    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);
	
    // 需要移动的元素数量 = 数组元素数量 - 指定索引位置
    int numMoved = size - index;
    // 有要移动的元素，使用System.arraycopy()复制数组
    if (numMoved > 0)
        // 假设原有数组：[1,2,3,4,5]
        // 参数数组：[a,b,c]
        // 所以：numMoved = 5 - 3 = 2；numNew = 3
        // 索引位置：2，也就是原有数组的第3个元素，即elementData[2] = 3
        // 从elementData的第三个元素开始拷贝到elementData的第2+3个元素上，拷贝numNew(3)个
        // 这里的执行效果：[1,2,(3),(4),(5),3,4,5]，小括号包着表示即将被覆盖
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
	// 将a集合的所有元素拷贝到elementData的index位置上，拷贝numNew(3)个
    // 最终得到elementData：[1,2,a,b,c,3,4,5]
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

这时候看源码其实很好理解了，然后我们学到了一个复制数组的方法：System.arraycopy()

结论

数组添加元素的源码也不难理解，每次添加新元素的时候，判断一下数组容量是否够用，够用就将新元素放到数组末尾，不够就进行扩容。

至于modCount属性，后面会说。

为什么刚初始化的数组添加元素时要设置容量为10？

这是一种性能优化的做法，从源码中可知，数组添加元素时如果容量不够，会进行扩容操作，扩容操作会产生新数组，为了避免在刚开始的时候频繁添加元素导致扩容，所以默认会设置一个初始值10，这个10不是硬性要求，是一个经验，能提高ArrayList的性能。

为什么扩容倍数是1.5倍？

这同样是一种经验法则，在内存使用和性能之间取的中间值：

  • 如果扩容倍数太大，扩容次数就会降低，这样可以提高性能，但是内存会被浪费掉
  • 如果扩容倍数太小，扩容次数就会增加，这样性能就下降了，当然内存利用率会提高
  • 所以取一个两边都平衡的值1.5倍，新的内存块比当前块大，但是不会浪费。

查找元素

arrayList.get(0);

源码解析

// 根据索引下标查找元素
public E get(int index) {
    // 索引范围是否合法检查
    rangeCheck(index);

    return elementData(index);
}

private void rangeCheck(int index) {
    // 索引大于数组元素数量，抛出IndexOutOfBoundsException异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 返回索引元素
E elementData(int index) {
    return (E) elementData[index];
}

查找元素也很简单，没有什么需要说明的。

查找元素索引

arrayList.indexOf(1);
arrayList.lastIndexOf(1);

源码解析

// 返回元素第一次出现的索引位置
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;
}

// 返回元素最后一次出现的索引位置
public int lastIndexOf(Object o) {
    if (o == null) {
        // 同理，只是循环反过来遍历
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

删除元素

源码解析

删除指定索引的元素
public E remove(int index) {
    // 索引范围合法性检查
    rangeCheck(index);

    // Fail-Fast
    modCount++;
    E oldValue = elementData(index);

    // 需要左移一位的元素数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 通过数组复制方法来移动元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 删除元素，使其不被引用，让GC在合适的时间回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
删除指定元素
public boolean remove(Object o) {
    if (o == null) {
        // 找到第一个出现的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 boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

// 保证参数不为空，否则抛出我们最爱的空指针异常
public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

// 批量删除
// complement：一个为false的标记
private boolean batchRemove(Collection<?> c, boolean complement) {
    // 用final修饰，避免中途修改
    final Object[] elementData = this.elementData;
    // 循环记录
    int r = 0, w = 0;
    // 修改标记，有删除操作就设置成true，没有删除操作就是false
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 标记出原数组中不包含删除数组中的元素，被标记的元素是不存在的，也就不需要删除
            // 假设原数组：element:[1,2,3,4,5]
            // 删除数组：c:[2,3]
            // 第一次循环：r=0，element[0]不是c中元素，进入if，element[0]=element[0]，w=1，element:[1,2,3,4,5]
            // 第二次循环：r=1，element[1]是c中元素，w=1；
            // 第三次循环：r=2，element[2]是c中元素，w=1；
            // 第四次循环：r=3，element[3]不是c中元素，进入if，element[1]=element[3]，w=2，element:[1,4,3,4,5]
            // 第五次循环：r=4，element[4]不是c中元素，进入if，element[2]=element[4]，w=3，element:[1,4,5,4,5]
            // 循环结束，此时element:[1,4,5,4,5]，r=5，w=3；
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 正常情况r是等于size的，这个if处理的是异常情况：contains()抛出异常时循环中断
        if (r != size) {
            // 虽然被中断了，但是得做一些处理，保证删除操作继续进行，这是一个兼容异常的处理，保证前面被识别出来需要删除的元素能被正常删除，后面的元素因为中途抛出异常的缘故就没办法了
            // 假设场景：
            // 第一次循环：r=0，element[0]不是c中元素，进入if，element[0]=element[0]，w=1，element:[1,2,3,4,5]，该次循环成功执行
            // 第二次循环：r=1，element[1]是c中元素，w=1；
            // 第三次循环：r=2，element[2]是c中元素，w=1；
            // 第四次循环：r=3，该次循环if语句的contains方法抛出异常
            // 此时：r=3,w=1,element:[1,2,3,4,5]
            // 数组复制：将element的第r开始，拷贝(size-r)个元素到element的第w位
            // 也就是：将element的第3位开始，拷贝2个元素到element的第1位
            // 结果：element:[1,(4),(5),4,5]
            // 简单说就是将剩下没有处理的元素拷贝到前面来，避免被后面的操作删除掉
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            // 加上剩下没有处理的元素数量
            w += size - r;
        }

        // 如果w = size，表示上面循环的每一个if语句都执行了，也就是所有元素都不用删除
        if (w != size) {
            // 删除索引w之后的所有元素，因为不需要删除的已经被移动到数组前面了，后面的都是要删除的
            for (int i = w; i < size; i++)
                // 删除引用，让GC去回收他
                elementData[i] = null;
            // 修改modCount，Fail-Fast机制，后面会说
            modCount += size - w;
            // 修改数组元素数量
            size = w;
            // 标记数组被修改了
            modified = true;
        }
    }
    return modified;
}

以上代码的优点是支持快速失败也就是Fail-Fast机制，后面会说明这个机制的好处。

清空元素
public void clear() {
    modCount++;

    // 全部置空
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    
    size = 0;
}

包含元素

源码解析

public boolean contains(Object o) {
    // 索引值大于0表示找到该元素
    return indexOf(o) >= 0;
}

// 找第一个符合条件的元素
public int indexOf(Object o) {
    if (o == null) {
        // 查找对象是null，遍历出一个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;
    }
    // 找不到就返回小于0的数
    return -1;
}

// 默认是指针比较，如果元素重写了equals方法则走重写的
public boolean equals(Object obj) {
    return (this == obj);
}

替换元素

源码解析

public E set(int index, E element) {
    // 索引范围合法性检查
    rangeCheck(index);
	
    // 取旧值
    E oldValue = elementData(index);
    // 替换新值
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

什么是Fail-Fast

集合Collection中的一种错误机制，集合类中有一个modCount属性，当集合进行add/remove等操作时会发生改变，集合通过迭代器遍历元素时会检查这个元素，当遍历时modCount发生了改变，就会抛出ConcurrentModificationException异常。

Fail-Fast有什么好处？

当发现异常时立即停止，避免执行缺陷代码而导致更多的异常，可以尽早的发现故障。

如何避免Fail-Fast发生的异常

  1. 在迭代过程中使用迭代器的remove()方法，但是这种方式有局限性，只能删除当前遍历的元素

  2. 使用Java并发包（java.util.concurrent）中的类来代替ArrayList或者HashMap。比如使用CopyOnWriteArrayList代替ArrayList，它是写时复制的容器，在读写时是线程安全的，在进行add/remove等操作时，并不是在原数组上进行修改，而是将原数组拷贝一份，在新数组上修改，待完成后才将指向旧数组的引用指向新数组，所以对于CopyOnWriteArrayList在迭代过程并不会发生fail-fast。但CopyOnWriteArrayList容器只能保证数据的最终一致性，不能保证数据的实时一致性。

    ConcurrentHashMap代替HashMap，它采用了锁机制，是线程安全的。在迭代中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，而是在改变时new新的数据从而不影响原有的数据，iterator完成后再将头指针替换为新的数据，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变，但同样不能保证数据的实施一致性。

知识点

  • CopyOnWriteArrayList
  • ConcurrentHashMap
  • 数据的最终一致性和实施一致性

Fail-Fast总结

  1. 在集合进行增删改查或其他修改集合元素的方法时，会记录修改次数即modCount的值
  2. 在调用迭代器时，会将这个modCount值赋予给迭代器中的expectedModCount
  3. 在调用迭代器的过程中，每次执行next()都会检测expectedModCount和modCount是否相等
  4. 在迭代过程中调用迭代器的remove()方法不会造成ConcurrentModificationException异常
  5. 在迭代过程中调用集合的remove()方法会造成ConcurrentModificationException异常