转载

Java ArrayList源码分析

ArrayList介绍

List 接口的一个实现类，内部是用一个数组存储元素值，相当于一个可变大小的数组。

签名

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

可以看到 ArrayList 继承了 AbstractList 抽象类，它实现了 List 接口的大多数方法。如果要实现一个不可变的 List ，只要继承这个类并且实现 get(int) 和 size 方法。如果要实现可变的 List ，需要覆盖 set(int, E) 。另外，如果 List 的大小是可变的，还要覆盖 add(int, E) 和 remove() 方法。

构造器

ArrayList 提供了三个构造器：

ArrayList() ArrayList(Collection<? extends E> c) ArrayList(int initialCapacity)

Collection 接口约定，每个集合类应该提供两个”标准”构造器，一个是无参数的构造器（上面第一个），另外一个是拥有单个参数（类型为 Collettion ）的构造器（上面第二个）。ArrayList还提供了第三个构造器，其接受一个int值，用于设置ArrayLi的初始大小（默认大小为10）。

相关方法

`trimToSize`

public void trimToSize() {         modCount++;         int oldCapacity = elementData.length;         if (size < oldCapacity) {             elementData = Arrays.copyOf(elementData, size);         }     }

用于把 ArrayList 的容量缩减到当前实际大小，减少存储容量。其中的变量 modCount 由 AbstracList 继承而来，记录List发生结构化修改（structurally modified）的次数。 elementData 中实际存储了 ArrayList 的元素，在 ArrayList 中声明为： private transient Object[] elementData; 变量 size 是 ArrayList 的元素数量，当 size < oldCapacity 时，调用 Arrays.copyOf 方法实现缩减。

`indexOf` 和 `lasIndexOf`

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

这两个方法返回指定元素的下标，要区分参数是否为 null 。 lastIndexOf 和 indexOf 类似，只不过是从后往前搜索。

`ensureCapacity`

public void ensureCapacity(int minCapacity) {        if (minCapacity > 0)     ensureCapacityInternal(minCapacity);    } private void ensureCapacityInternal(int minCapacity) {  modCount++;  // overflow-conscious code  if (minCapacity - elementData.length > 0)      grow(minCapacity);     } private void grow(int minCapacity) {  // overflow-conscious code  int oldCapacity = elementData.length;  int newCapacity = oldCapacity + (oldCapacity >> 1);  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);     }

这个方法可以确保 ArrayList 的大小

`add` 和 `addAll`

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

add(int index, E element) 向指定位置添加元素，首先调用 rangeCheckForAdd 检查 index 是否有效，如果 index > size || index < 0 将抛出异常。然后确保容量加1，调用 System.arraycopy 把从 index 开始的元素往后移动一个位置。最后把 index 处的值设置为添加的元素。还有一个重载的 add(E e) 方法是直接把元素添加到末尾。

addAll(Collection<? extends E> c) 和 addAll(int index, Collection<? extends E> c) 则分别是向末尾和指定位置添加 Collection 中的所有元素。

`remove` 和 `removeAll`

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(Object o) 方法删除指定的元素。首先是查找元素位置，然后调用 fastRemove(index) 删除，其代码如下：

private void fastRemove(int index) {  modCount++;  int numMoved = size - index - 1;  if (numMoved > 0)   //把index+1往后的元素都往前移动一个位置   System.arraycopy(elementData, index+1, elementData, index,        numMoved);  elementData[--size] = null; // Let gc do its work }

重载的 remove(int index) 方法用于删除指定位置的元素。 removeRange(int fromIndex, int toIndex) 用于删除指定位置之间的所有元素。

removeAll(Collection<?> c) 和 retainAll(Collection<?> c) 代码如下：

public boolean removeAll(Collection<?> c) {         Objects.requireNonNull(c);         return batchRemove(c, false);     } public boolean retainAll(Collection<?> c) {         Objects.requireNonNull(c);         return batchRemove(c, true);     }

它们都是通过调用 batchRemove 方法实现的，其代码如下：

private boolean batchRemove(Collection<?> c, boolean complement) {  final Object[] elementData = this.elementData;  int r = 0, w = 0;  boolean modified = false;  try {   for (; r < size; r++)    if (c.contains(elementData[r]) == complement)     elementData[w++] = elementData[r];  } finally {   // Preserve behavioral compatibility with AbstractCollection,   // even if c.contains() throws.   if (r != size) {    System.arraycopy(elementData, r,         elementData, w,         size - r);    w += size - r;   }   if (w != size) {    // clear to let GC do its work    for (int i = w; i < size; i++)     elementData[i] = null;    modCount += size - w;    size = w;    modified = true;   }  }  return modified; }

这个方法有两个参数，第一个是操作的 Collection ，第二个是一个布尔值，通过设置为 true 或 false 来选择是 removeAll 还是 retainAll 。 try 里面的语句是把留下来的放在0到w之间，然后在 finally 中第二个 if 处理w之后的空间，第一个是在 c.contains() 抛出异常时执行。

正文到此结束