ArrayList
ArrayList介绍
我们先看一下ArrayList的继承关系图:
源码解析
ArrayList字段
/** * 序列号 */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 空数组，定义容量为0的有参构造，返回此空数组public ArrayList(0) * 或者定义长度为0集合的有参构造，也会返回 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 默认的空数组，无参构造返回此空数组 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 保存添加到ArrayList中的元素，不可序列化，可以看出ArrayList基于数组实现 */ transient Object[] elementData; /** * ArrayList元素数量(非容量) */ private int size; /** * 最大容量，若还是不够用可以扩容最大Integer.MAX_VALUE * 因为索引是int型，所以最大容量为Integer.MAX_VALUE * 为什么减8，不是减其他数字？ *[有点偏而且我看得也很懵。。](https://stackoverflow.com/questions/35756277/why-the-maximum-array-size-of-arraylist-is-integer-max-value-8)， */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;复制代码 构造方法
/** * 若知道数组大小，可以直接用此构造 * 可能抛出java.lang.OutOfMemoryError: Requested array size exceeds VM limit * @param 初始容量 * @throws IllegalArgumentException 若容量为负则抛异常 */ public ArrayList(int initialCapacity) { // 容量大于0时 if (initialCapacity > 0) { // 创建一个此大小的Object数组赋给elementData this.elementData = new Object[initialCapacity]; // 容量为0时 } else if (initialCapacity == 0) { // 将空数组赋给elementData this.elementData = EMPTY_ELEMENTDATA; // 容量小于0时抛出IllegalArgumentException异常 } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } /** * 无参构造，在新增操作时当elementData为空数组时会初始化其容量设置成10 */ public ArrayList() { // 将空数组赋给elementData this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 参数Collection的构造方法 * * @param c 元素被放入此ArrayList中的集合c * @throws NullPointerException 若集合c为空则抛异常 */ public ArrayList(Collection c) { //集合转Object[]数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toarray可能不返回Object[]（见JAVA BUG编号6260652） if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 空数组赋给elementData this.elementData = EMPTY_ELEMENTDATA; } }复制代码 JAVA BUG编号6260652
/** List的toArray()方法 预期返回Object[]，可能向上转型返回子类型，如下面的返回 * String[]数组，这也就意味着我们只能往此数组里放入String类型元素 */ public static void main(String[] args) { List l = Arrays.asList(args); System.out.println(l.toArray().getClass()); //返回String[] }复制代码 CRUD
Create
ArrayList新增(public)有如下几个方法:
public boolean add(E e) //末尾插入某元素 public void add(int index, E element) //指定位置插入某元素 public boolean addAll(Collection<? extends E> c)//末尾插入集合(顺序不变) public boolean addAll(int index, Collection<? extends E> c)//指定位置插入集合ArrayList是一个动态数组，其容量会自动增长，那它如何实现的？我们来看一下add()方法，在其给当前末尾元素后一个位置添加元素时，先执行了ensureCapacityInternal方法:
public boolean add(E e) { //确定ArrayList容量大小 ensureCapacityInternal(size + 1); //ArrayList长度加一，在size+1位置上添加元素 elementData[size++] = e; return true; } 复制代码 在ensureCapacityInternal方法里会先调calculateCapacity计算所需容量，若elmentData为空数组时容量会设置成10，若不是返回操作所需容量.
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, intminCapacity){ if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }复制代码 最后调用ensureExplicitCapacity方法确认是否扩容.方法里先是将modCount加1(modCount记录ArrayList修改次数，用来实现fail-fast机制的).再判断所需容量是否超过当前容量，若大于则扩容
private void ensureExplicitCapacity(int minCapacity) { modCount++; // if (minCapacity - elementData.length > 0) grow(minCapacity); }复制代码 扩容方法:
private void grow(int minCapacity) { //获取ArrayList中elementData数组的内存空间长度 int oldCapacity = elementData.length; //扩容至原容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //若新容量小于所需容量，就将容量直接设置成所需容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //若新容量大于定义的最大值检查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //Arrays.copy进行数组拷贝(方法里面会会调用System.arraycopy属于浅拷贝) elementData = Arrays.copyOf(elementData, newCapacity); } /** * 检查是否溢出，若没有溢出，返回int最大值或定义的最大值 */ private static int hugeCapacity(int minCapacity) { //内存溢出 if (minCapacity < 0) throw new OutOfMemoryError(); //大于定义的最大值返回int最大值，小于返回定义的最大值 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }复制代码 其余新增方法类似，稍微略带下:
/** * 指定位置添加元素 */ public void add(int index, E element) { //判断index是否越界 rangeCheckForAdd(index); //判断是否需要扩容 ensureCapacityInternal(size + 1); //public static native void arraycopy(Object src, int srcPos, // Object dest, int destPos, int length); 本地方法 // src:源数组，srcPos:源数组要复制的起始位置，dest:目标数组 // destPos:目标数组放置的起始位置，length:复制长度 // index位置及其后面的元素往后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); //指定位置赋值 elementData[index] = element; //ArrayList长度加一 size++; } /** * 末尾依次添加集合所有元素，add(Collection)与addAll(Collection)区别在于add * 是添加集合，addAll是添加集合所有元素 */ public boolean addAll(Collection c) { //参数集合转为数组 Object[] a = c.toArray(); //获取数组长度 int numNew = a.length; //判断是否扩容 ensureCapacityInternal(size + numNew); // Increments modCount //将a的第0位开始拷贝至elementData的size位开始，拷贝长度为numNew System.arraycopy(a, 0, elementData, size, numNew); // size增加numNew size += numNew; //空集合返回false，不为空返回true return numNew != 0; } /** * 指定位置插入集合所有元素 */ public boolean addAll(int index, Collection c) { //判断index是否越界 rangeCheckForAdd(index); //参数集合转为数组 Object[] a = c.toArray(); //获取数组长度 int numNew = a.length; //判断是否扩容 ensureCapacityInternal(size + numNew); int numMoved = size - index; //若是末尾插入直接插入集合，若不是先移动原来集合中元素再插入以免被覆盖 if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); // size增加numNew size += numNew; //空集合返回false，不为空返回true return numNew != 0; }复制代码 Retrieve
ArrayList查询(public)有如下几个方法:
public boolean contains(Object o)//查询是否包含某元素 public int indexOf(Object o)//查询某元素首次出现在ArrayList的索引/** * 内部调用了indexOf，若-1则表示没有，不小于0表示有 */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * for循环从索引为0往后开始遍历ArrayList，返回元素首次出现位置，若不存在返回 -1 */ 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; } 复制代码 public E get(int index)//查询此索引位置的元素
public E get(int index) { // 检查是否越界 rangeCheck(index); // 返回ArrayList的elementData数组index位置的元素 return elementData(index); } 返回指定位置的值 E elementData(int index) { return (E) elementData[index]; } 复制代码 public boolean isEmpty() //查询ArrayList大小是否为0
/** * ArrayList大小为0返回true，否则返回false */ public boolean isEmpty() { return size == 0; } 复制代码 public int lastIndexOf(Object o) //查询某元素最后一次出现在ArrayList的索引
/** * for循环从索引为size-1往前开始遍历ArrayList，返回元素首次出现位置，若不存在返回 -1 */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size - 1; i >= 0; i--) if (elementData[i] == null) return i; } else { for (int i = size - 1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } 复制代码 public int size() //返回ArrayList的长度
/** * 直接返回size */ public int size() { return size; } 复制代码 public List subList(int fromIndex, int toIndex)
/** * 返回指定[fromIndex, toIndex)区间的集合视图，fromIndex == toIndex时返回空集合 * 此子集合具有集合所有操作 */ public List subList(int fromIndex, int toIndex) { //越界检查，非法参数检查 subListRangeCheck(fromIndex, toIndex, size); //返回subList有参构造 return new SubList(this, 0, fromIndex, toIndex); } /** * 内部类，实现了RandomAccess提供快速访问 */ private class SubList extends AbstractList implements RandomAccess { private final AbstractList parent; private final int parentOffset; private final int offset; int size; /** * 从这里可以看出，subList用的是父集合引用，即对subList操作的同时会影父集合 */ SubList(AbstractList parent, int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } }复制代码 Update
ArrayList更新(public)有如下几个方法:
public void ensureCapacity(int minCapacity)/** * 此方法用于若添加大量元素，可以先调用此方法分配多点内存，从而避免多次重新分配内存 */ public void ensureCapacity(int minCapacity) { // 最小扩充容量，默认是 10 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } 复制代码 public E set(int index, E element)
/** * 设置index位置元素的值，返回被替换元素 */ public E set(int index, E element) { //校验是否越界 rangeCheck(index); //取出旧值 E oldValue = elementData(index); //替换元素 elementData[index] = element; //返回被替换元素 return oldValue; }复制代码 public void trimToSize()
/** * 将容量修改成ArrayList实际大小，用来减少内存空间资源浪费 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } 复制代码 Delete
ArrayList删除(public)有如下几个方法:
public E remove(int index)/** * 删除指定索引位置元素 */ 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; return oldValue; } 复制代码 public boolean remove(Object o) //删除某元素，只会删除第一次出现的
/** * for循环遍历ArrayList，若集合存在此元素调用fastRemove快速移除 */ 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(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; }复制代码 public boolean removeAll(Collection<?> c) //删除ArrayList与c中的相同元素
public boolean removeAll(Collection c) { //当c为null抛空指针异常 Objects.requireNonNull(c); return batchRemove(c, false); } /** * 批量移除 * complement为true时保留ArrayList与集合c的相同元素 * false时移除相同元素 */ 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++) //false记录不同值，true记录相同值 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 防止抛出异常没有遍历完，保留未遍历的元素 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // 若不是全被替换，将w及其位置后面的元素置为null if (w != size) { for (int i = w; i < size; i++) elementData[i] = null; //记录改变次数 modCount += size - w; //设置大小 size = w; //修改成功 modified = true; } } return modified; }复制代码 public boolean retainAll(Collection<?> c) //保留ArrayList和集合c中的相同元素`
public boolean retainAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, true); } 复制代码 public void clear()
/** * 清空所有元素 */ public void clear() { modCount++; for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } 复制代码 转换数组
/** * 用Arrays.copyOf()转为数组 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * @param 数组a * @return 将ArrayList里元素赋值到数组中 * @throws NullPointerException a为null * @throws ArrayStoreException a的运行时类型不是ArrayList中每个元素的运行时类型的超类型 */ public T[] toArray(T[] a) { if (a.length < size) // 创建一个新的a的运行时类型数组，内容不变 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }复制代码 序列化
我们知道ArrayList实现了Serializable，其elementData是一个缓存数组，其容量少数情况会满，只需要序列化实际存储的元素即可，所以用transient修饰标记不可序列化.ArrayList通过独特方式完成序列化，在序列化时会调用定义的writeObject，将size和element写入对象输出流中.
/** * 序列化 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ int expectedModCount = modCount; //默认序列化方法，将当前类的非静态和非transient字段写入流中 s.defaultWriteObject(); // 写入大小 s.writeInt(size); // for循环写入ArrayList中所有元素 for (int i=0; i < size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * 反序列化 */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // 默认反序列化方法 s.defaultReadObject(); // 读取长度 s.readInt(); // ignored if (size > 0) { // 像clone()方法 ，根据大小而不是容量分配数组 int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; //读取所有元素 for (int i=0; i < size; i++) { a[i] = s.readObject(); } } } 复制代码 遍历
在简述中提到了ArrayList实现了RandomAccess接口，其有一段英文注释
As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop: for (int i=0, n=list.size(); i < n; i++) list.get(i); runs faster than this loop: for (Iterator i=list.iterator(); i.hasNext(); ) i.next();复制代码
for循环遍历效率高过foreach，在Collections工具类中个方法:
private static final int FILL_THRESHOLD = 25; public static void fill(List list, T obj) { int size = list.size(); if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i itr = list.listIterator(); for (int i=0; i < size; i++) { itr.next(); itr.set(obj); } } }复制代码 我们可以从这个方法可以看出若是实现了RandomAccess用了for循环遍历.
ArrayList的iterator与listIterator区别
iterator与listIterator都是迭代器，不同的是listIterator可以指定位置开始，拥有hasPrevious()和previous()方法能逆向遍历，可以对集合本身进行新增，修改不过必须要next()过且不能连续操作，还可以返回当前遍历位置nextIndex()，previousIndex()当前遍历位置前一个.
手撕简单实现
public class ArrayList { private Object[] elementData; private int size; public ArrayList(int capacity){ this.elementData = new Object[capacity]; } public ArrayList(){ this.elementData = new Object[10]; } public void add(Object obj){ isExpanse(size + 1); elementData[size++] = obj; } private void isExpanse(int minCapacity){ int oldCapacity = elementData.length; if(minCapacity > oldCapacity){ int newCapacity = oldCapacity + oldCapacity >> 1; elementData = Arrays.copyOf(elementData, newCapacity); } } public Object get(int index){ checkLength(index); return elementData[index]; } public void set(int index, Object obj){ checkLength(index); elementData[index] = obj; } private void checkLength(int index){ if(index < 0 || index >= size) { throw new IndexOutOfBoundsException("越界"); } } public void remove(int index){ checkLength(index); int moveNum = size - index - 1; if(moveNum > 0 ){ System.arraycopy(elementData, index + 1, elementData, index, moveNum); } elementData[size--] = null; }}复制代码