ArrayList详解

ArrayList详解

List中使用最多的就是ArrayList，基本上大家在实例化一个List的时候都是

List list = new ArrayList();

所以在这里了解一下ArrayList的实现过程(以java8为例)

主要特点

• 有序存储元素
• 允许元素重复，允许存储null值
• 支持动态扩容，相当于一个动态的数组
• 非线程安全

继承关系

List接口扩充了Collection接口

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

继承了AbstractList类，实现了List接口、RandomAccess接口、Cloneable接口和Serializable接口，所以ArrayList是支持随机访问、克隆和序列化的

源码分析

关键变量

/**
* 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 默认的空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 默认无参构造器使用的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* ArrayList底层用来存储数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* ArrayList实际的长度
*/
private int size;

/**
* 可分配的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

/**
 * 自定义初始化容量，根据传入的初始化容量来确定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() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 通过集合来进行初始化，使用了Arrays.copyOf来将集合中的数据copy到数组中
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

public boolean add(E e) {
      // 在添加元素之前先确认一下容量是否足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// minCapacity为当前所需要的最小容量
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 如果在进行初始化的时候使用的无参构造器，此时才会给赋初始容量为10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  // 计算修改次数
  modCount++;

  // 需要的容量大于数组容量的话，需要进行扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  // 扩容1.5倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 当原数组为空数组时，newCapacity为0，是小于minCapacity 10 的
  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:
  elementData = Arrays.copyOf(elementData, newCapacity);
}

remove方法

public E remove(int index) {
      // 数组下标检查
    rangeCheck(index);
        // 计算修改次数
    modCount++;
      // 获取该所索引位置下原来的的元素
    E oldValue = elementData(index);
        // 所要移动的数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
          // 第一个参数为源数据
          // 第二个参数为从源数据的哪个位置开始复制
          // 第三个参数为目标数据
          // 第四个参数为从目标数据的哪个位置开始被复制
          // 第五个参数为被复制的元素数量
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved); // index所对应的元素被删除，后续所有的元素向前移动一位
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

其他的方法都是中规中矩的操作数组

如:

// get
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

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

迭代器

在使用foreach循环遍历的时候实际上是使用的迭代器，对于ArrayList而言，使用普通的for循环会比使用foreach效率更高

ArrayList中的迭代器是Fail-Fast迭代器，快速失败，该迭代器对象一旦发现另一个对象在结构上修改这一集合就会马上报错ConcurrentModificationException

接下来看一下ArrayList的迭代器

public Iterator<E> iterator() {
    return new Itr();
}

Itr是ArrayList的内部类，实现了Iterator接口

private class Itr implements Iterator<E> {
      // 游标
    int cursor;       // index of next element to return
      // 最后一次返回的索引位置
    int lastRet = -1; // index of last element returned; -1 if no such
      // 当Itr被实例化的时候，记录一下迭代器被实例化时ArrayList的修改次数(在用ArrayList进行add/remove操作时modCount每次都加一)
    int expectedModCount = modCount;

    Itr() {}

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

    @SuppressWarnings("unchecked")
    public E next() {
          // 检查是否被修改了
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
          // 游标加一，指向下一个元素位置
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
          // 检查是否被修改了
        checkForComodification();

        try {
              // list移除元素
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
              // 移除之后会将修改次数modCount重新赋给expectedModCount
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
          // 检查是否被修改了
        checkForComodification();
    }

      // 检查是否被修改了
    final void checkForComodification() {
          // 当修改次数与Itr被实例化时的修改次数不一致时，说明在进行迭代操作的时候其他线程进行了ArrrayList的add/remove操作，此时抛出ConcurrentModificationException，即为fast-fail快速失败机制
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

使用说明

• 由于ArrayList的默认初始值为10，扩容为1.5倍，如果集合中所需要存储的元素数量多的话，需要进行多次扩容，重新申请内存并进行赋值，比较耗时，如果在进行实例化时指定初始容量，可以减少扩容次数，提升性能

• 在遍历删除的时候注意了，不要使用foreach来循环遍历list删除数据，最好使用iterator进行遍历删除，否则会报ConcurrentModificationException

• ArrayList是线程不安全的，并发情况下可能会导致ArrayIndexOutOfBoundsException，在扩容时，由于没有锁的保护，使得一个线程访问到了另一个线程的不一致状态，导致越界