ArrayList底层实现机制(快速失败与安全失败、扩容机制)

程序员文章站 2024-03-06 09:09:13

...

读完本篇文章将会了解以下问题

1.ArrayList基本属性及常用方法

2.Java中的快速失败与安全失败

3.ArrayList扩容检测

---------------------------------------------------------------------------------------------------------------------------
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式：

一种是顺序存储结构
另一种是链式存储结构

数组，是一种典型的顺序存储结构。具有以下特点：

是物理存储连续、逻辑存储连续的顺序表。
利于查询。这种存储方式的优点是查询的时间复杂度为O(1)，通过首地址和偏移量就可以直接访问到某元素。
不利于修改。插入和删除的时间复杂度最坏能达到O(n)，如果你在第一个位置插入一个元素，你需要把数组的每一个元素向后移动一位，如果你在第一个位置删除一个元素，你需要把数组的每一个元素向前移动一位。
容量的固定性。就是当你不确定元素的数量时，你开的数组必须保证能够放下元素最大数量，遗憾的是如果实际数量比最大数量少很多时，你开的数组没有用到的内存就只能浪费掉了。

ArrayList作为List的典型实现，完全实现了List的全部接口功能，它是基于数组实现的List类，它封装了一个Object[]类型的数组，长度可以动态的增长。如果在创建ArrayList时没有指定Object[]数组的长度，它默认创建一个长度为10的数组，当新添加的元素已经没有位置存放的时候,ArrayList就会自动进行扩容，扩容的长度为原来长度的1.5倍。ArrayList是线程不安全的list集合（Vector为线程安全）。

public class ArrayList<E>
  extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, Serializable

List接口：继承自Collection接口，有序集合

RandomAccess接口：支持快速随机访问，indexedBinarySerach(list,key)；

Cloneable接口：克隆标志性接口，允许使用clone();

Serializable接口：序列化标志接口，支持序列化。

1.ArrayList基本属性及常用方法

基本属性

  transient Object[] elementData;
  private int size;

elementData：存放元素的数组

size：存入数组中元素个数(非数组长度)。

常用方法

  public ArrayList()

  public ArrayList(int paramInt)

  public ArrayList(Collection<? extends E> paramCollection)
  {
    this.elementData = paramCollection.toArray();
    if ((this.size = this.elementData.length) != 0)
    {
      if (this.elementData.getClass() != [Ljava.lang.Object.class) {
        this.elementData = Arrays.copyOf(this.elementData, this.size,         
        [Ljava.lang.Object.class);
      }
    }
    else {
      this.elementData = EMPTY_ELEMENTDATA;
    }
  }

ArrayList构造方法有三种：无参构造，带默认空间构造和带collection参数构造。

带collection参数构造过程：先调用集合的toArray()方法，并赋值给elementData ，然后进行类型的判断，是如果类型不是Object[]类型，那么将使用反射生成一个Object[]的数组，并重新赋值给elementData。

public boolean add(E paramE)
  {
    ensureCapacityInternal(this.size + 1);//容量+1 判断是否需要扩容
    this.elementData[(this.size++)] = paramE;//将元素添加到数组内 
    return true;
  }

public boolean add(E paramE):先调用ensureCapacityInternal()方法，使modCount+1(记录集合修改次数变量)，然后判断是否需要进行扩容。然后将数据存入数组，元素数量+1；

public E get(int paramInt)
    {
      rangeCheck(paramInt);//判断输入下标是否合法
      checkForComodification();//用于实现java快速失败
      return ArrayList.this.elementData(this.offset + paramInt);//线程检测没问题后添加数据
    }

private void checkForComodification()
    {
      if (ArrayList.this.modCount != this.modCount) {
        throw new ConcurrentModificationException();
      }
    }

private class Itr
    implements Iterator<E>
  {
    ...
    int expectedModCount = AbstractList.this.modCount;
    ...
  }

public E get(int paramInt)：首先检测输入数组下标是否合法。checkForComodification();方法比较重要，它的目的是为了实现Java快速失败机制(fail—fast)。

2.Java的快速失败（fail—fast）与安全失败（fail—safe）机制

快速失败（fail—fast）

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理：假设有两个线程（线程A，线程B），其中线程A负责遍历list、线程B修改list。在使用迭代器遍历时，AbstractList类的内部类Itr中定义了变量expectedModCount，初始值为集合的modCount值。在线程A在遍历list过程中，线程启动，同时线程B增加一个元素，这时modCount的值发生改变（modCount = N + 1）。线程A继续遍历执行next方法，checkForComodification方法发现expectedModCount = N ，而modCount = N + 1，两者不等，这时就抛出ConcurrentModificationException 异常，从而产生fail-fast机制。

注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改。

安全失败（fail—safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容*问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但是需要复制集合，产生大量的无效对象，内存消耗大，同时迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

public E remove(int paramInt)
  {
    rangeCheck(paramInt);//检测输入下标是否合法
    this.modCount += 1;//操作次数+1
    Object localObject = elementData(paramInt);//获取存储的元素
    int i = this.size - paramInt - 1;
    if (i > 0) {
      //移动数组中其他元素位置
      System.arraycopy(this.elementData, paramInt + 1, this.elementData, paramInt, i);
    }
    this.elementData[(--this.size)] = null;//将最后一个元素设置为null
    return localObject;
  }

//迭代器中的remove方法
public void remove()
        {
          if (this.lastRet < 0) {
            throw new IllegalStateException();
          }
          checkForComodification();
          try
          {
                ArrayList.this.remove(this.lastRet);//调用ArrayList的remove
                this.cursor = this.lastRet;//cursor
                this.lastRet = -1;//避免同时调用两次remove
                this.expectedModCount = ArrayList.this.modCount;//更新数组长度
          }
          catch (IndexOutOfBoundsException localIndexOutOfBoundsException)
          {
            throw new ConcurrentModificationException();
          }
        }

public E remove(int paramInt)：先检测数组下标是否合法，之后操作次数变量+1，然后获取对应下标的元素将其余的元素移动(当i<0时为第一个元素或最后一个元素，就不需要移动其他元素了)，最后将最后一个元素设置为空。移动图解：

ArrayList底层实现机制(快速失败与安全失败、扩容机制)

第二个方法为迭代器中的remove方法。当我们在 for 循环里面对集合进行了remove操作时，有时候最后的结果和我们期望的不一样，因为如果想使用remove的话，需要用iterator操作。ArrayList.Iterator 就是一个对数组的遍历，较之直接 for（）循环ArrayList，优点是做了 fail-fast 检查，并且增加了在遍历过程中删除的功能。再来详细讲一下for（）循环里面不能用list.remove（i）的原因。因为在 for(int i=0; i<list.size();i++) 语句中，假设 list 有4个元素，假如果在 i ＝ 0 的时候调用了list.remove(i),此时就出现了取值错位并且漏值的情况。但是在Iterator 里面，我们可以看到有一行这样的代码 this.cursor = this.lastRet 改变了当前数组的角标。

public void set(E paramE)
    {
      if (this.lastRet < 0) {
        throw new IllegalStateException();
      }
      checkForComodification();
      try
      {
        ArrayList.this.set(this.lastRet, paramE);
      }
      catch (IndexOutOfBoundsException localIndexOutOfBoundsException)
      {
        throw new ConcurrentModificationException();
      }
    }
public int size()
    {
      checkForComodification();
      return this.size;
    }

public void set(E paramE)：同理set里面也做了fail-fast 检查，检查通过后添加元素。

public int size()：获取数组元素个数。

3.ArrayList扩容检测

数组有个明显的特点就是它的容量是固定不变的，一旦数组被创建则容量则无法改变。所以在往数组中添加指定元素前，首先要考虑的就是其容量是否饱和。若接下来的添加操作会时数组中的元素超过其容量，则必须对其进行扩容操作。受限于数组容量固定不变的特性，扩容的本质其实就是创建一个容量更大的新数组，再将旧数组的元素复制到新数组当中去。 ArrayList 在进行添加操作前，会检验内部数组容量并选择性地进行数组扩容。在 ArrayList 中，通过私有方法 ensureCapacityInternal 来进行数组的扩容操作。下面来看具体的实现过程：

首先调用add()后，判断当前 ArrayList 内部数组是否为空，为空则将最小容量 minCapacity 设置为 10，不为空则获取oldCapacity值。

// 内部数组的默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空的内部数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数 
  private static int calculateCapacity(Object[] paramArrayOfObject, int paramInt)
  {
    if (paramArrayOfObject == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(10, paramInt);
    }
    return paramInt;
  }

接着判断添加操作会不会导致内部数组的容量饱和。

private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	// 判断结果为 true，则表示接下来的添加操作会导致元素数量超出数组容量
	if (minCapacity - elementData.length > 0){
		// 扩容
		grow(minCapacity);
	}
}

数组容量不足，则进行扩容操作，成功后复制数组元素。


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

总结：add元素时的扩容流程：

添加一个元素，首先计算当前的list所需最小的容量大小，是否需要扩容等。当需要扩容时：

1.得到当前的ArrayList的容量(oldCapacity)。

2.计算除扩容后的新容量(newCapacity)，其值(oldCapacity + (oldCapacity >> 1))约是oldCapacity 的1.5倍。

3.当newCapacity小于所需最小容量，那么将所需最小容量赋值给newCapacity。

4.newCapacity大于ArrayList的所允许的最大容量,处理。

5.最后进行数据的复制。