集合源码-ArrayList

1、 ArrayList

1.1 简介

ArrayList是一种以动态数组实现的List集合。其中，元素可以为空值或重复，当元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组；其次，ArrayList 是非线程安全类。

1.2 继承关系

List 提供了基础的添加、删除、遍历等操作。RandomAccess 提供了随机访问的能力。Cloneable，可以被克隆。Serializable，可以被序列化。

1.3 源码解析

1.3.1 属性

// 默认初始化长度 private static final int DEFAULT_CAPACITY = 10; // 空的数组，这种是通过new ArrayList(0)创建时用的是这个空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组，传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 实际添加元素数组，transient序列化特殊处理，不序列化空值 transient Object[] elementData; // 实际元素个数 private int size;

1.3.2 构造函数

// 带参数容量大小 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; } // 传入集合并初始化elementData public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 空数组 this.elementData = EMPTY_ELEMENTDATA; } } 补充：数组拷贝 Arrays.copyOf()： public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } System.arraycopy(): public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

1.3.3 添加元素

add(E e)方法: 尾部插入 public boolean add(E e) { // 判断容量 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 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) { // 扩容为1.5倍 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果溢出，新容量为当前大小+1 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // MAX_ARRAY_SIZE = 2^31-1-8 if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果newCapacity 小于0抛出异常，否则2^31 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } add(int index, E element):其他位置插入 public void add(int index, E element) { // 判断是否越界 rangeCheckForAdd(index); // 判断及扩容 ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

1.3.4 获取元素

public E get(int index) { // 判断是否越界 rangeCheck(index); return elementData(index); }

1.3.5 删除元素

remove(Object o)方法 public boolean remove(Object o) { // 为空时逐个遍历，删除第一个null 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; } // 快速删除，不做边界检查，也不返回删除的元素值 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 } remove(int index)方法 public E remove(int index) { // 检查是否越界 rangeCheck(index); modCount++; E oldValue = elementData(index); // 获取index位置的元素 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 最后一个元素置为null, GC elementData[--size] = null; return oldValue; }

1.3.6 手动缩容

public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

1.4 总结

ArrayList 具有随机访问的能力，如果在一些效率要求比较高的场景下： for (int i = 0; i < list.size(); i++) foreach 最终会被转换成迭代器遍历的形式，效率不如上面的遍历方式

ArrayList 迭代器中的方法都是均具有快速失败的特性，当遇到并发修改的情况时，迭代器会快速失败，以避免程序在将来不确定的时间里出现不确定的行为

remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。