源码分析笔记ArrayList(JDK1.8)

终于开始写博客了，前面想了很多次写博客，但是都没有动笔，苦于不知如何表述，最近开始复习集合，想通过写博客加深自己的印象，记录自己的理解，该篇文章从构造方法入手，然后到常用的一些方法，摘取JDK中源码，在上面加上自己的理解，有不对的不严谨的地方还望大佬们多多指正

概述

继承AbstractList抽象类，实现List接口底层用数组存放数据，默认容量大小为10扩容倍数为1.5倍线程不安全的支持随机访问，查看元素较为简单添加、删除操作较为烦琐

底层源码

相关属性

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //序列化ID 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 = {}; //实际存放数据的数组，transient关键字修饰 transient Object[] elementData; // non-private to simplify nested class access //元素个数 private int size; //方法 }

构造方法

/** * 有參构造方法，判断传入的容量大小是否合法 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //传入容量为0，则为空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 无参构造方法，默认容量为10 */ public ArrayList() { //指向容量为0的默认空数组对象 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 传入另一个集合对象 */ public ArrayList(Collection<? extends E> c) { //数组对象指向传入集合对象的装换而来的数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // 如果传入的集合装换的数组元素类型不是Object类型，则转换为Object类型 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 集合装换的数组没有元素，则替换成空数组 this.elementData = EMPTY_ELEMENTDATA; } }

添加操作

/** * 默认在数组尾部添加元素 */ public boolean add(E e) { //检查是否需要扩容 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } /** * 在指定的位置插入新元素 */ 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++; }

关于arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 方法 将原数组的指定一段拷贝到目标数组的指定位置

src 原数组int 原数组开始拷贝的位置dest 目标数组destPos 目标数组接收拷贝的位置length 拷贝的长度

扩容相关操作

/** *计算所需要的容量大小 */ private void ensureCapacityInternal(int minCapacity) { //判断当前用的数组是否是默认容量大小的的数组 //如果是，则计算当前需要的容量的大小 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } /** *判断是否需要扩容 */ private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果需要的最小容量大于当前的数组容量 // 即数组容量不够，则需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** *扩容操作 */ private void grow(int minCapacity) { // 计算当前数组长度 int oldCapacity = elementData.length; // 计算新数组数组长度，为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 判断新的数的容量是否满足所需的容量大小 if (newCapacity - minCapacity < 0) //如果不满足，则直接扩成所需的容量 newCapacity = minCapacity; //不能一直无限扩容，当容量超过Integer.MAX_VALUE - 8时，直接扩成Integer.MAX_VALUE-8大小 //最大为Integer.MAX_VALUE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 将原数组数据复制到扩容后的新数组中 // Arrays.copyOf()代价很高，所以尽量在ArrayList创建时指定数组大小 elementData = Arrays.copyOf(elementData, newCapacity); } //能分配的最大数组大小，再大可能会出现内存溢出异常 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** *当数组扩容超过一定门限，直接括成Integer.MAX_VALUE大小 */ private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

关于Arrays.copyOf(Object[] original,int newLength)方法 将指定数组的长度改变为newLength

original 原数组newLength 新数组的长度，该长度可能小于原数组长度，所以该方法也可以缩容也可以扩容

删除元素

/** * 删除指定位置的元素 */ public E remove(int index) { //检查下标是否大于size rangeCheck(index); modCount++; //记录要删除的值 E oldValue = elementData(index); //计算要移动的长度 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //将新空出来的位置设置为null，让GC可以回收这些空间 elementData[--size] = null; // clear to let GC do its work return oldValue; } /** *传入对象删除 */ 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; }

手动缩容

/** *手动缩容，将内部数组的容量降为size大小，如果size为0，则指向空数组 *JDK内部没有调用该方法 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

清空操作

public void clear() { modCount++; //将整个存放过数据的部分全部置null，让GC可以释放这些内存空间 // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }

迭代器相关

/** *创建一个迭代器对象 */ public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { //下一个元素对象的下标 int cursor; // index of next element to return //最后一个元素对象下标 int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } /** *返回当前元素对象 */ @SuppressWarnings("unchecked") 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]; } /** *删除当前元素 */ public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }

总结

modCount字段记录内部结构发生修改的次数，元素添加、删除次数添加元素顺序：计算所需的最小容量（size+1）->判断是否需要扩容->进行扩容->添加元素扩容时进行判断，如果1.5倍的容量大小不能满足，则直接扩容成size+1大小，最大容量为Integer.MAX_VALUE提供了手动缩容方法，但内部没有调用（我没找到），将内部数组大小缩为size大小对于序列化这个问题，还不是很理解，所以就没有写出来了