ArrayList 源码解析

ArrayList 源码解析

学问勤中得,萤窗万卷书

距离上一篇String源码浅析已经过去了4个月了,今天就来说说我们开发中常用的ArrayList源码

ArrayList几个重要的成员变量

String源码解析开篇一样,我们还是先来看看ArrayList类的基本结构。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 数组第一个 add 时候的长度,默认是 10,;
    private static final int DEFAULT_CAPACITY = 10;
  
    //表示当前数组的长度;
 		private int size;
  
  	// 保存集合数据的数组
    transient Object[] elementData; // non-private to simplify nested class access
  
    //  这个集合修改结构的次数
    protected transient int modCount = 0;
}

这里来说说这几个成员变量具体代表什么意思。

DEFAULT_CAPACITY: 数组的初始大小

size: 当前数组的大小(实时),类型 int,没有使用 volatile 修饰,非线程安全的

elementData: 用来保存集合数据的数组,从这个成员变量我们就可以看出来ArrayList的本质就是一个数组。

modCount: 数组结构发生改变的次数。比如说:扩容

如果ArrayList的本质是一个数组,数组结果一旦被创建之后就不能被改变了,那么ArrayList是怎么实现动态扩容的

从上文的分析可以得到ArrayList的本质就是一个数组,初始为空数组,当第一次add 的时候会变成一个长度为10 的数组,那么我们可以得到下图的ArrayList结构图示。

ArrayList的结构

ArrayList的类注释

要看一个类的源码,就必须的先看看这个类的类注释。由于ArrayList的类注释很长,且都是英文的,为了节省大家的时间,我将其翻译成英文并提取出重要信息如下。

  • ArrayList继承自List接口,且可以存储null值,可自动扩容;
  • size、isEmpty、get、set、iterator和listIterator几个方法的时间复杂度都是O(1);
  • ArrayList不是线程安全的,推荐使用线程安全类:Collections#synchronizedList;
  • 增强 for 循环,或者使用迭代器迭代过程中,如果数组大小被改变,会快速失败,抛出异常。

ArrayList类注释大概的意思就是上述的几条,后续涉及的我们在后面详细讲解。

初始化 ArrayList

ArrayList 类有三个重载构造函数:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认构造器, 直接初始化, 默认大小为空
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 使用已存在的集合初始化ArrayList
public ArrayList(Collection<? extends E> c) {
  // elementData 是保存数组的容器,默认为 null
  elementData = c.toArray();
  // 给定的集合 c 有值
  if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    // 如果给定的集合不是 Object 类型, 我们会转成 Object 
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // 给定集合无值,则默认空数组
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

// 指定 ArrayList 初始长度
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);
  }
}

构造函数说明

  1. 默认构造函数初始化的时候,会指定 ArrayList 的长度为0, 也就是说初始时候的数组是空数组,而不是10, 10 是第一次 add 的时候数组的长度。

  2. 第 12 行的时候,有一行注释。这行注释表示这里有一个bug,大致的意思就是。当给定集合内的元素不是 Object 类型时,我们会转化成 Object 的类型。一般情况下都不会触发此 bug,只有在下列场景下才会触发:ArrayList 初始化之后(ArrayList 元素非 Object 类型),再次调用 toArray 方法,得到 Object 数组,并且往 Object 数组赋值时,才会触发此 bug,代码和原因如图:

    ArrayList 报错

15行的地方打印出了String[], 说明这个 arr的泛型是 String

官方查看文档地址:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652,问题在 Java 9 中被解决。

ArrayList 的 add 方法和 扩容

新增有两步:

  1. 确保数组的长度是否足够,如果不够,则需要扩容至原先长度的1.5倍
  2. 新增数据到数组

这两步我们可以直接从下面源码中体现。

public boolean add(E e) {
  // 确保数组长度足够, size 是数组的长度
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 数组新增数据
  elementData[size++] = e;
  return true;
}

注重来看第一步,这一步主要是一个方法 ensureCapacityInternal(size),我们现在来看看这个方法。

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

看到这里主要使用了两个方法calculateCapacityensureExplicitCapacitycalculateCapacity方法是获当前数组的容量;ensureExplicitCapacity方法是确保数组的容量足够。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

calculateCapacity方法比较简单,如果是空集合的时候,我们会将容量设定为DEFAULT_CAPACITY也就是10。构造就直接返回minCapacity, 也就是当前数组大小 size + 1。minCapacity 的意思是 当前数组的最小容量。

下面来看 ensureExplicitCapacity 这个方法,这个方法的作用是确保数组容量足够。

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 如果期望的最小容量小于目前数组的长度,就需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

由于是对数组的容量做修改,这里modCount会加1,modCount 的作用主要是记录数组被修改,在类的其他方法中也会有用处。

接下来的操作就是grow(minCapacity)方法,这个方法的作用就是扩容,我们接下来来看看 grow方法。

// 扩容数组,扩容至原先容量的 1.5 倍
private void grow(int minCapacity) {
  // 原先的容量
  int oldCapacity = elementData.length;
  // 新容量
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) 
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

˙这个方法还是很简单的,主要分为下面几步:

  1. 得到当前数组的容量
  2. 计算出新的容量, oldCapacity + (oldCapacity >> 1)这句话的意思是扩容至当前容量的 1.5倍。oldCapacity >> 1表示右移一位,也就是除以2的意思。
  3. 如果扩容后的容量 < 我们期望的最小的容量,那么扩容后的值就是期望的最小容量
  4. 如果扩容后的容量 > jvm 所能分配的数组的最大值,就使用 Integer 的最大值。
  5. 最后我们将原数组的值 copy 到新数组。

虽然代码很简单,但是这里有几点需要注意的。

  • 扩容后的容量是原先容量的 1.5倍,也就是 原先容量大小 + 原先容量大小的一半
  • 扩容后的数组数据其实是复制了原先数组数据,也就是说前后的数组并不是同一个数组。也可以说Arrays.copyOf就是扩容的本质。
  • ArrayList 允许 null 值
  • ArrayList 最大容量是 Integer.MAX_VALUE
  • add 方法并不是线程安全的。

ArrayList 的 remove 方法

ArrayList 的删除方法实现有两个重载方法,一个根据索引删除(remove(index)),一个根据值删除(remove(Object))。我们只讲其中一个方法的源码来分析,我们讲解根据值删除方法。

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

这里的 remove 方法主要分为两块,一个是值为 null 的时候,和值不为 null 的时候。

o == null 的时候

  • 遍历整个数组,找到第一个值为null 的下标
  • 调用 fastRemove 方法删除 下标值,然后返回 true
  • 找不到就返回 false

o != null 的时候

  • 遍历整个数组,找到满足o.equals(elementData[index])的下标
  • 调用 fastRemove 方法删除 下标值,然后返回 true
  • 找不到就返回 false

fastRemove方法

上面两种情况都调用了 fastRemove 方法,下面我就来看看这个方法.

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
}
  • 第一步呢,这里还是 modCount++, 说明结构发生了改变
  • numMoved 表示删除 index 位置的元素后,需要从 index 后移动多少个元素到前面去。减 1 的原因,是因为 size 从 1 开始算起,index 从 0开始算起。
  • 调用 System.arraycopy从 index +1 位置开始被拷贝,拷贝的起始位置是 index,长度是 numMoved
  • 最后一步,数组最后一个位置赋值 null,帮助 GC

以上的步骤可以总结为下面的动态图,

删除数组元素

简单总结一下,ArrayList有三个构造函数,通过这三个构造函数,使用者可以灵活初始化一个数组容器。在使用默认构造器初始化的数组的时候,数组是一个空数组。只有在第一次add的时候,才会见数组容量变为10。add 方法的本质是调用了 Arrays.copyOf() 方法。不管是 add 还是 remove 每次改变数组结构之前,都有一个变量 modCount 记录改变的次数。ArrayList可以运行null值且最大长度为 Integer.MAX_VALUE

迭代器

如果要自己实现迭代器,实现 java.util.Iterator 类就好了,ArrayList 也是这样做的,我们来看下迭代器的几个总要的参数:

int cursor;// 迭代过程中,下一个元素的位置,默认从 0 开始。
int lastRet = -1; // 新增场景:表示上一次迭代过程中,索引的位置;删除场景:为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中,期望的版本号;modCount 表示数组实际的版本号。

迭代器一般来说有三个方法:

  • hasNext 还有没有值可以迭代
  • next 如果有值可以迭代,迭代的值是多少
  • remove 删除当前迭代的值

我们来分别看下三个方法的源码:

###hasNext

 public boolean hasNext() {
   return cursor != size;
 }

cursor 表示下一个元素的位置,size 表示实际大小,如果两者相等,说明已经没有元素可以迭代了,如果不等,说明还可以迭代

next

 public E next() {
   //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
   checkForComodification();
   //本次迭代过程中,元素的索引位置
   int i = cursor;
   if (i >= size)
     throw new NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
     hrow new ConcurrentModificationException();
   // 下一次迭代时,元素的位置,为下一次迭代做准备
   cursor = i + 1;
   return (E) elementData[lastRet = i];
 }

// 版本号比较
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

看到这里,我们更能理解 cursor的含义了,就是一个计数器,指向下一个元素的位置。可以通过JVM 的程序计数器来类比,当然了,这里的含义更简单。

remove

public void remove() {
  	// 如果上一次操作时,数组的位置已经小于 0 了,说明数组已经被删除完了
    if (lastRet < 0)
        throw new IllegalStateException();
     //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
      	// -1 表示元素已经被删除,这里也防止重复删除
        lastRet = -1;
      // 删除元素时 modCount 的值已经发生变化,在此赋值给 expectedModCount
    	// 这样下次迭代时,两者的值是一致的了
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

删除元素成功,数组当前 modCount 就会发生变化,这里会把 expectedModCount 重新赋值,下次迭代时两者的值就会一致了。

写到最后

ArrayList 并不是线程安全的,如果想要使用线程安全的 ArrayList ,可以使用开篇提到的 Collections#synchronizedList。我们来看看他的 add源码:

public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}

以上就是 ArrayList 的几个基础类和迭代器,由于篇幅问题,并没有深入说明 ArrayList 的使用。但我也相信大家已经能很熟练的使用 ArrayList 了。

如果有读者对本文有什么问题,请在留言中提出,有什么好的建议也请在留言中提出,后面也会慢慢更新关于源码的文章,谢谢大家。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/2020/02/13/java-arraylist-use

Buy me a cup of coffee ☕.