ArrayList 源码解析和设计思路

Arraylist源码分析

ArrayList 我们几乎每天都会使用到，但是通常情况下我们只是知道如何去使用，至于其内部是怎么实现的我们不关心，但是有些时候面试官就喜欢问与ArrayList 的源码相关的问题，今天我们就来看看和ArrayList 源码相关的问题。

一：整体架构

1.1、ArrayList 结构

ArrayList 整体架构比较简单，就是一个数组结构，比较简单，如下图：

图中展示是长度为 n 的数组，index 表示数组的下标，从 0 开始计数，elementData 表示数组本身，源码中除了这两个概念，还有以下三个基本概念：

1. DEFAULT_CAPACITY ，表示数组的初始大小，默认是 10；
2. size ，当前数组的大小，没有使用 volatile 修饰，非线程安全的；
3. modCount ，统计当前数组被修改的版本次数；

1.2、ArrayList 类注释

看源码，首先要看类注释，我们看看类注释上面都说了什么，部分截图如下图所示：

类注释主要讲了以下四点

1. 允许put null 值，会自动扩容 ；
2. size、isEmpty、get、set、add 等方法时间复杂度都是 O (1) ；
3. 是非线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList ；
4. 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常

二：源码解析

2.1、初始化

ArrayList 有三种初始化办法：无参数直接初始化、指定大小初始化、指定初始数据初始化，源码如下：

// 无参数直接初始化，数组大小为空
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;
   }
}

注意: ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值。

2.2、新增和扩容实现

新增方法主要分成两步：首先判断数组是否需要扩容，如果需要，执行扩容操作，否则，直接赋值。新增方法源码如下，其中ensureCapacityInternal()方法就是扩容操作。

public boolean add(E e) {
  //确保数组大小是否足够，不够执行扩容，size 为当前数组的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接赋值，线程不安全的
  elementData[size++] = e;
  return true;
}

扩容（ensureCapacityInternal）的源码：

private void ensureCapacityInternal(int minCapacity) {
  // 如果初始化数组大小时，有给定初始值，以给定的大小为准，不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  // 确保容积足够
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
  // 记录数组被修改
  modCount++;
  // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

// 扩容，并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

从扩容的源码我们可以看出：

1. 扩容的规则并不是翻倍，而是原来容量的 1.5 倍 ；
2. ArrayList 中的数组容量的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了 ；

2.3、删除

ArrayList 删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理和思路都差不多，我们选取根据值删除方式来进行源码说明：

public boolean remove(Object o) {
  // 如果要删除的值是 null，找到第一个值是 null 的删除
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果要删除的值不为 null，找到第一个和要删除的值相等的删除
    for (int index = 0; index < size; index++)
      // 这里是根据  equals 来判断值相等的，相等后再根据索引位置进行删除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

从上面的源码中我们可以看出：

1. 由于新增的时候没有对 null 值做出判断，所以是可以删除 null 值的 ;
2. 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型，我们需要关注 equals 的具体实现；

删除的具体逻辑是在fastRemove()中实现的，源码如下所示

private void fastRemove(int index) {
  // 记录数组的结构要发生变动了
  modCount++;
  // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去
  // 减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //数组最后一个位置赋值 null，帮助 GC
  elementData[--size] = null;
}

2.4、复杂度分析

操作	时间复杂度
get()	根据下标直接查询 O(1)
add(E e)	直接尾部添加 O(1)
add(int index, E e)	插入后元素需要往后移动一个单位 O(n)
remove(E e)	删除后元素需要往前移动一个单位 O(n)

2.5、线程安全

我们需要强调的是，只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，是没有线程安全的问题的。

ArrayList 有线程安全问题的本质，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况。

类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全，SynchronizedList 是通过在每个方法上面加上锁来实现，虽然实现了线程安全，但是性能大大降低。

三：总结

从上面 ArrayList 的部分源码的分析中，我们可以发现 ArrayList 底层其实就是围绕数组结构，各个 API 都是对数组的操作进行封装，让使用者无需感知底层实现，只需关注如何使用即可。

本文地址：https://blog.csdn.net/weixin_38478780/article/details/107688462