java源码赏析--java.util.ArrayList

1. 简介 ArrayList 是可以动态增长和缩减的索引序列,它是基于数组实现的 List 类。
该类封装了一个动态再分配的 Object[] 数组,每一个类对象都有一个 capacity 属性,表示它们所封装的 Object[] 数组的长度,当向 ArrayList 中添加元素时,该属性值会自动增加。如果向 ArrayList 中添加大量元素,可使用 ensureCapacity 方法一次性增加 capacity ,可以减少增加重分配的次数提高性能。
ArrayList 的用法和 Vector 相类似,但是 Vector 是一个较老的集合,具有很多缺点,不建议使用。另外,ArrayListVector 的区别是:ArrayList 是线程不安全的,当多条线程访问同一个 ArrayList 集合时,程序需要手动保证该集合的同步性,而 Vector 则是线程安全的。
【java源码赏析--java.util.ArrayList】sizeisEmptygetsetiteratorlistIterator操作的运行时间是常量。add操作对于添加n个元素,需要O(n)的时间。其他的操作需要线性时间。
1.1 继承关系
java源码赏析--java.util.ArrayList
文章图片

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

  • 继承 AbstractList 抽象父类,AbstractList提供了List接口的默认实现(个别方法为抽象方法)。
  • 实现了 List 接口(规定了 List 的操作规范),List接口(extends Collection)定义了列表必须实现的方法。
  • RandomAccess(可随机访问),是一个标记接口,用来标记可适用与随机访问算法的类。
  • Cloneable(可拷贝),可以调用Object.clone方法返回该对象的浅拷贝。
  • Serializable(可序列化)。
2. 源码分析 2.1 属性
//默认初始容量 private static final int DEFAULT_CAPACITY = 10; //空数组 private static final Object[] EMPTY_ELEMENTDATA = https://www.it610.com/article/{}; //默认空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 不会被序列化 transient Object[] elementData; //ArrayList实际元素容量 private int size; //最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  • ArrayList的默认容量DEFAULT_CAPACITY为10。
  • 数据存放在elementData中,且访问级别为包内私有,是为了使内部类能够访问到其中的元素。并且被标记为transient,也就意味着在序列化的时候,此字段是不会被序列化的。
  • size表示数组中元素的个数
  • EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了在构造函数中初始化elementData使用的。
  • MAX_ARRAY_SIZEArrayList最大分配容量。
2.2 构造函数
public ArrayList() { this.elementData = https://www.it610.com/article/DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

无参构造函数,elementData中没有元素,size为0,且elementData的长度也为0。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATAelementData赋值。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = https://www.it610.com/article/new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } }

elementData中没有元素,size为0,不过elementData的长度有可能不同。使用EMPTY_ELEMENTDATAelementData赋值。
public ArrayList(Collection c) { elementData = https://www.it610.com/article/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; } }

首先将集合c转化为数组,然后检查转化的类型,如果不是 Object[] 类型,使用 Arrays 类中的 copyOf 方法进行复制;同时,如果 c 中没有元素,使用 EMPTY_ELEMENTDATA 初始化。
2.3 主要方法
2.3.1 boolean add(E e) 确保容量足够后,在尾部添加一个元素
public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }

动态扩容 ensureCapacityInternalArraylist 中多次使用,着重理解。
private void ensureCapacityInternal(int minCapacity) {//第一次添加元素时,如果是无参构造函数构造而来,那么所需最小容量为DEFAULT_CAPACITY if (elementData =https://www.it610.com/article/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }ensureExplicitCapacity(minCapacity); }

上面代码中if判断为了区分对象是由哪一种构造函数构造而来。第一次添加元素时需要确定最小扩容容量。而DEFAULTCAPACITY_EMPTY_ELEMENTDATAEMPTY_ELEMENTDATA用来区分三个构造函数。
private void ensureExplicitCapacity(int minCapacity) { modCount++; //列表修改次数加1//如果所需最小容量大于数组长度时,才许真正扩容。 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); } // minCapacity is usually close to size, so this is a win: elementData = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity); }

一般正常情况下,新的容量一般为旧容量的1.5倍(oldCapacity + (oldCapacity >> 1))。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) {// 这种情况,如何出现? throw new OutOfMemoryError(); } return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE; }

minCapacity 在超出最大限制时允许达到 Integer.MAX_VALUE,而不仅仅是Integer.MAX_VALUE - 8
2.3.2 void ensureCapacity(int minCapacity) 供外部调用的扩容方法。
在大致了解List大小时,可用此方法一次性增加minCapacity,这可以减少重分配次数,从而提高性能。
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }

  • 如果是通过无参构造函数构造且elementData中没有元素,则不需要扩容。
  • ensureExplicitCapacity方法中,如果扩容大小小于elementData长度,则不需要扩容。
2.3.3 void add(int index, E element)
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

检查 index 是否数组越界。
private void rangeCheckForAdd(int index) { if (index > size || index < 0) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; }

  1. 先调用 rangeCheckForAdd 检查索引是否合法。
  2. 合法再调用上面讲过的 ensureCapacityInternal 执行扩容。
  3. 调用系统的 arraycopy 函数将索引处及其后的元素后移一位。
  4. index 处插入该元素。
add(int index, E element)方法太耗时,主要体现在arraycopy上,一般别用。
2.3.4 boolean addAll(Collection c)
public boolean addAll(Collection c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }

  1. c 转换为数组 a
  2. 调用 ensureCapacityInternal 动态扩容。
  3. 调用系统函数 arraycopy
  4. 增加 elementDatasize
  5. 有意思的小细节,numNew != 0,则返回 true
疑惑点
  • 为什么不从一开始就判断 numNew 的值呢,如果等于0,直接返回,后面的函数也就不用执行了?
2.3.5 boolean addAll(int index, Collection c)
public boolean addAll(int index, Collection c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index; if (numMoved > 0){ System.arraycopy(elementData, index, elementData, index + numNew, numMoved); }System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

  1. add(int index, E element) 一样,先调用 rangeCheckForAdd 检查索引合法性。
  2. c 转换为数组 a
  3. 调用 ensureCapacityInternal 扩容。
  4. 如果插入位置不是 Arraylist 的末尾,则调用 arraycopy 将索引及其后的元素后移。
  5. a 的元素 arraycopyelementData 中。
  6. 增加 size
  7. numNew != 0,则返回true。
2.3.5 E get(int index)
public E get(int index) { rangeCheck(index); return elementData(index); }

注意和 rangeCheckForAdd的不同之处。
private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }

  1. 检查索引合法性。
  2. 返回指定数据。
2.3.6 void clear()
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++){ elementData[i] = null; }size = 0; }

  1. 从结构上修改 此列表的次数加1;
  2. for循环将每个元素置空;
  3. size 置为0,elementData 的长度并没有修改,如果确定不再修改 list 内容之后最好调用 trimToSize 来释放掉一些空间)。
2.3.7 void trimToSize() 返回一个新数组,新数组不含null,数组的 sizeelementData.length 相等,以节省空间。此函数可避免 size 很小但 elementData.length 很大的情况。
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = https://www.it610.com/article/(size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

2.3.8 int indexOf(Object o)
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; }

ArrayList 中可以添加 null,且可以在任意位置。
2.3.9 boolean contains(Object o)
public boolean contains(Object o) { return indexOf(o) >= 0; }

不建议使用 contains(Object o) 方法。效率极差。原因是通过for循环分别 equals
2.3.10 boolean containsAll(Collection c) 继承java.util.AbstractCollectioncontainsAll
public boolean containsAll(Collection c) { for (Object e : c) { if (!contains(e)) { return false; } } return true; }

不建议使用,效率更差。
2.3.11 int hashCode() 继承 java.util.AbstractListhashCode
public int hashCode() { int hashCode = 1; for (E e : this) { hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); } return hashCode; }

2.3.12 Object clone() 返回ArrayList实例的浅拷贝
public Object clone() { try { ArrayList v = (ArrayList) super.clone(); v.elementData = https://www.it610.com/article/Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }

2.3.13 boolean remove(int index)
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = https://www.it610.com/article/elementData(index); 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 workreturn oldValue; }

  • 检查索引合法性
  • 通过 System.arraycopy 挪动数组
  • size减一,并将elementData最后设为null
2.3.14 boolean remove(Object o)
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; }

由于 ArrayList 中可以存储 null,所以需要判断参数 o 是否为空的判断。
直观从代码上看,不建议使用此方法删除对象,性能太差。建议使用 boolean remove(int index)删除元素。
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 }

需要注意 fastRemove(int index)boolean remove(int index)的区别,仅仅是没有返回值,作者为什么将相同的代码写两遍呢?
2.3.15 boolean removeAll(Collection c)
public boolean removeAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, false); }

判断对象是否为空
public static T requireNonNull(T obj) { if (obj == null){ throw new NullPointerException(); } return obj; }

batchRemove 这个类中最精妙的代码
private boolean batchRemove(Collection c, boolean complement) { final Object[] elementData = https://www.it610.com/article/this.elementData; int r = 0, w = 0; // r 用来遍历整个数组的索引w 用来标记需要替换的索引 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) { // 如果 w != size, 则说明 w之后的元素都是需要丢弃掉的。而如果 w == size, 则说明没有发生替换,不需要删除。 // clear to let GC do its work for (int i = w; i < size; i++) { elementData[i] = null; } modCount += size - w; //本次修改次数就应该是 size - w size = w; //替换次数 = size modified = true; } } return modified; }

2.3.16 boolean retainAll(Collection c) 保留 c 中的元素,与 remoteAll 的区别在于 batchRemove(c, complement)
public boolean retainAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, true); }

2.3.17 E set(int index, E element) 替换对应索引的元素
public E set(int index, E element) { rangeCheck(index); E oldValue = https://www.it610.com/article/elementData(index); elementData[index] = element; return oldValue; }

2.3.18 Object[] toArray() 浅拷贝
public Object[] toArray() { return Arrays.copyOf(elementData, size); }

2.3.19 T[] toArray(T[] a)
public T[] toArray(T[] a) { if (a.length < size){ // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } System.arraycopy(elementData, 0, a, 0, size); if (a.length > size){ a[size] = null; } return a; }

2.3.20 void sort(Comparator c)
public void sort(Comparator c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }

ConcurrentModificationException 是用来判断在数组排序时是否被修改。

    推荐阅读