java源码-ArrayList

开篇

ArrayList主要由如下特性：

• ArrayList实际上是通过一个数组去保存数据的，当我们构造ArrayList时，如果使用默认构造函数，ArrayList的默认容量大小是10。

• 当ArrayList容量不足以容纳全部元素时，ArrayList会自动扩张容量，新的容量 = 1.5*原始容量。

• ArrayList的克隆函数，将全部元素克隆到一个数组中，采用Arrays.copyOf方法实现。

• ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

• 在做ArrayList的遍历的时候有3中遍历的方法，分别是随机访问遍历，用迭代器遍历和强制for循环遍历，按照效率来说最快的是随机访问遍历，最差的是迭代器遍历。

• ArrayList的遍历是不安全的，在遍历的时候如果改变了集合的结构会抛出ConcurrentModificationException异常。

ArrayList类图

ArrayList类定义

ArrayList的类定义比较简单，基本上可以看出来默认值数组大小为10，数据存储通过elementData变量。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; // 默认初始化大小 private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //默认是package-private access，保存数据 transient Object[] elementData; //实际保存的数据量大小 private int size; } 

ArrayList构造函数

ArrayList的构造数非常简单，根据传入的参数initialCapacity初始化数组大小。如果不传参数就默认构建空数组。

 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; } public ArrayList(Collection<? extends E> c) { elementData = 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; } } 

ArrayList常用操作

ArrayList的add操作

ArrayList的add操作其实就是分两步走：

• 以size+1的大小去看下是否容纳的下新元素，否则就以1.5的原有空间扩容。
• 在扩容后的新数组的index位置插入新元素。
• grow()方法内部实现扩容和旧元素的拷贝，采用Arrays.copyOf(elementData, newCapacity)实现。

 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 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++; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(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的remove操作

ArrayList的remove操作分两步走：

• 将待移除的index往后的元素拷贝至index开始的位置。
• 将最后一位元素置null并且size-1即可。
  ArrayList的clear操作负责将数组全部置null即可。

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); elementData[--size] = null; // clear to let GC do its work return oldValue; } public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } 

ArrayList迭代器

ArrayList的迭代器实现很简单，通过创建Itr对象。在Itr类当中将cursor初始化为0，next过程中就是返回变量同时将cursor+1，hasNext()方法只是判断cursor是否等于size的值。

public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; // 默认初始化值为0 int lastRet = -1; // 上一个返回值的下标 int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } 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]; } } 

参考文章

ArrayList的特性