ArrayList概述

ArrayList相当于实现了动态数组，并且具备数组的查找快、增删慢的特点

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
  3.     ...        
  4. }
  • 从上述代码可以看到，ArrayList继承于AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable接口。
  • RandomAccess是一个标志接口，表明实现这个接口的List是支持快速随机访问的。
  • ArrayList实现了Cloneable接口，即重写了clone()方法，能被克隆。
  • ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化。

ArrayList源码解读

成员变量

5个成员变量

  • transient Object[] elementData;
  • **private static final int DEFAULT_CAPACITY = 10;**
  • private static final Object[] EMPTY_ELEMENTDATA = {};
  • private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  • private int size; ```java //☆☆☆ArrayList的底层数据结构☆☆☆ transient Object[] elementData; //用于保存ArrayList数据的数组

//☆☆☆默认初始容量大小☆☆☆ private static final int DEFAULT_CAPACITY = 10;

//用于容量为0的ArrayList实例的共享空数组（elementData在任何时候容量为0时，将被赋予该常量） private static final Object[] EMPTY_ELEMENTDATA = {};

//用于默认容量的ArrayList实例的共享空数组（在使用默认容量构造ArrayList时，elementData将被赋予该常量） private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList实际包含的元素个数（size ≤ elementData.length） private int size;

//modCount是AbstractList的成员变量，ArrayList将继承这个变量，所以下面的定义实际并不存在 //modCount记录着集合元素个数修改的次数，即每次增删元素，modCount都会加1 //modCount主要用于多线程 protected transient int modCount = 0;

  2. <a name="YbIOD"></a>
  3. #### 构造方法
  4. 3个构造方法
  6. - `public ArrayList(int initialCapacity)`
  7. - `public ArrayList()`
  8. - `public ArrayList(Collection<? extends E> c)`
  9. ```java
  10. //带初始容量参数的构造函数，即用户可以在创建ArrayList对象时指定集合的初始大小
  11. //初始容量大于0时，根据初始大小实例化底层数组
  12. //初始容量为0，赋予elementData共享空数组
  13. //初始容量为负数时，抛出异常
  14. public ArrayList(int initialCapacity) {
  15.     if (initialCapacity > 0) {
  16.         this.elementData = new Object[initialCapacity];
  17.     } else if (initialCapacity == 0) {
  18.         this.elementData = EMPTY_ELEMENTDATA;
  19.     } else {
  20.         throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  21.     }
  22. }
  24. //默认无参构造函数
  25. //虽然ArrayList的默认容量为10，但是初始化时其实直接赋予空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  26. //为ArrayList添加第一个元素时，底层数组才真正实例化，此时数组容量才真正变成默认容量
  27. public ArrayList() {
  28.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  29. }
  31. //构造一个ArrayList，其元素是实现了Collection接口的实现类的所有元素
  32. //ArrayList元素的顺序按照它们由集合的迭代器返回的顺序。
  33. //如果elementData不是Object[]类型数据（c.toArray可能返回的不是Object[]类型）
  34. //则将原来不是Object[]类型的elementData，赋值给新的Object[]类型的elementData
  35. public ArrayList(Collection<? extends E> c) {
  36.     //将指定集合转换为数组，赋给底层数组
  37.     elementData = c.toArray();
  38.     if ((size = elementData.length) != 0) {
  39.         if (elementData.getClass() != Object[].class)            
  40.             elementData = Arrays.copyOf(elementData, size, Object[].class);
  41.     } else {
  42.         this.elementData = EMPTY_ELEMENTDATA;
  43.     }
  44. }

工具方法

  • 工具方法基本都是public修饰的实例方法，能获取ArrayList实例的相关信息或修改ArrayList实例的内容 ```java //修改ArrayList实例的容量为当前大小，可以使用此方法来最小化ArrayList实例的容量。 //modCount是AbstractList的成员变量，记录列表容量变化的次数，主要用于多线程相关 public void trimToSize() { modCount++;
    if (size < elementData.length) {
    1.   elementData = (size == 0)
    2.     ? EMPTY_ELEMENTDATA
    3.     : Arrays.copyOf(elementData, size);
    } }

//返回ArrayList实例的元素数量 public int size() { return size; }

//如果ArrayList实例不包含元素，则返回true。 public boolean isEmpty() { //注意=和==的区别 return size == 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; }

//返回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; }

//如果ArrayList实例包含指定的元素，则返回true。 public boolean contains(Object o) { return indexOf(o) >= 0; }

//返回ArrayList实例的浅拷贝 //Arrays.copyOf()方法的功能是实现数组的复制，并返回复制后的数组。参数是被复制的数组和复制的长度 public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(e); } }

//以正确的顺序（从第一个到最后一个元素）返回一个包含ArrayList实例中所有元素的数组 //注意：返回的数组类型是Object[]，因为底层数组elementData的类型是Object[] public Object[] toArray() { return Arrays.copyOf(elementData, size); }

//以正确的顺序返回一个包含ArrayList实例中所有元素的数组 //返回的数组的运行时类型是数组a的运行时类型 //如果数组a容量小于ArrayList实例元素的个数，则分配一个新数组，该数组的大小为ArrayList实例元素的个数，类型为a的运行时类型 //如果数组a容量小于ArrayList实例元素的个数，则将ArrayList实例的元素拷贝至数组a并返回 @SuppressWarnings(“unchecked”) public T[] toArray(T[] a) { if (a.length < size) //新建一个数组，类型是a的运行时类型，内容是ArrayList实例的内容 return (T[]) Arrays.copyOf(elementData, size, a.getClass());

  1. //调用System提供的arraycopy()方法实现数组之间的复制
  2. System.arraycopy(elementData, 0, a, 0, size);
  3. if (a.length > size)
  4.     a[size] = null;
  5. return a;

}

//返回底层数组中指定位置的元素，注意并不是公共接口 @SuppressWarnings(“unchecked”) E elementData(int index) { return (E) elementData[index]; }

//返回ArrayList实例中指定位置的元素。 public E get(int index) { rangeCheck(index); return elementData(index); }

//检查给定的索引是否在合法范围内 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //add和addAll使用的rangeCheck的一个版本 private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

//用指定的元素替换此列表中指定位置的元素并返回旧元素 public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }

//将指定的元素追加到此列表的末尾 public boolean add(E e) { //调用该方法，保证ArrayList的容量足够大（足够添加一个元素） ensureCapacityInternal(size + 1); //方法中包括modCount++操作 //这里看到ArrayList添加元素的实质就相当于为数组赋值 elementData[size++] = e; //注意这里，相当于size=size+1 return true; } //在此列表中的指定位置插入指定的元素。 //需要将列表中index以及index之后的所有元素向后移动一位 public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //确保ArrayList容量足够大，方法中包括modCount++操作 //使用System.arraycopy()方法实现数组自己复制自己，实现元素后移 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

//删除该列表中index处的元素，并将index之后的所有元素向左移动一位 public E remove(int index) { rangeCheck(index);

  1. modCount++;
  2. E oldValue = elementData(index);
  4. int numMoved = size - index - 1;
  5. if (numMoved > 0)
  6.     System.arraycopy(elementData, index+1, elementData, index, numMoved);
  8. elementData[--size] = null;
  9. return oldValue;

}

//快速删除，跳过了范围检查，并且不返回删掉的值 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; }

//从列表中删除第一个出现的指定元素（如果存在）。 //如果ArrayList存在指定元素，则删除并返回true，否则返回false 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的所有元素 //并不改变当前ArrayList的容量 public void clear() { modCount++; for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }

//将指定集合中的所有元素追加到ArrayList的末尾。 public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); //将数组a的所有元素复制到ArrayList的末尾 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }

//将指定集合中的所有元素插入到ArrayList的指定位置。 //需要先移位再复制 public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index);

  1. Object[] a = c.toArray();
  2. int numNew = a.length;
  3. ensureCapacityInternal(size + numNew);  // Increments modCount
  5. int numMoved = size - index;
  6. if (numMoved > 0)
  7.     System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
  9. System.arraycopy(a, 0, elementData, index, numNew);
  10. size += numNew;
  11. return numNew != 0;

}

//从此列表中删除索引fromIndex至toIndex之间的所有元素，包括索引为fromIndex的元素 //将所有后续元素向左移动 protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

  1. // clear to let GC do its work
  2. int newSize = size - (toIndex-fromIndex);
  3. for (int i = newSize; i < size; i++) {
  4.     elementData[i] = null;
  5. }
  6. size = newSize;

}

//从ArrayList中删除指定集合中包含的所有元素。 public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); //调用batchRemove()，如果ArrayList被修改则返回true return batchRemove(c, false); }

//仅保留ArrayList中包含在指定集合中的元素，或者说从ArrayList中删除其中不包含在指定集合中的所有元素。 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true, 0, size); }

//从ArrayList中批量删除元素方法，是removeAll和retainAll执行的主体代码 //该方法如果删除了元素则返回true，否则返回false //complement参数可以指定c是需要保留的元素还是需要删除的元素 boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) { Objects.requireNonNull(c); final Object[] es = elementData;

  1. int r;
  2. //判断是否需要执行删除操作，如果不需要则返回false
  3. for (r = from;; r++) {
  4.     if (r == end)
  5.         return false;
  6.     if (c.contains(es[r]) != complement)
  7.         break;
  8. }
  10. //批量删除元素
  11. int w = r++;
  12. try {
  13.     for (Object e; r < end; r++)
  14.         if (c.contains(e = es[r]) == complement)
  15.             es[w++] = e;
  16. } catch (Throwable ex) {
  17.     System.arraycopy(es, r, es, w, end - r);
  18.     w += end - r;
  19.     throw ex;
  20. } finally {
  21.     modCount += end - w;
  22.     shiftTailOverGap(es, w, end);
  23. }
  24. return true;

}

//返回ArrayList的列表迭代器（按适当的顺序）。 //返回的列表迭代器是fail-fast 。 public ListIterator listIterator() { return new ListItr(0); }

//从ArrayList的指定位置开始，返回ArrayList的列表迭代器。 //指定的索引表示初始调用next将返回的第一个元素索引为index，初始调用previous将返回索引为index-1的元素 //返回的列表迭代器是fail-fast public ListIterator listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(“Index: “+index); return new ListItr(index); }

//以正确的顺序返回该列表中的元素的迭代器。 //返回的迭代器是fail-fast 。 public Iterator iterator() { return new Itr(); }

  2. <a name="mYnJD"></a>
  3. #### ☆☆☆扩容机制☆☆☆
  5. - ArrayList的扩容机制是：**每当ArrayLisst容量不足时，容量增加当前容量的50%**
  7. 如果每次只扩充一个容量，那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
  8. ```java
  9. // 主动检查ArrayList的容量是否满足最小容量minCapacity，如果不满足，则扩容
  10. public void ensureCapacity(int minCapacity) {
  11.     //这里判断，如果底层数组仍是默认空数组，并且最小容量不大于默认容量，则不需要进行扩容，即使minCapacity > elementData.length
  12.     if (minCapacity > elementData.length && 
  13.         !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA && minCapacity <= DEFAULT_CAPACITY)) {
  14.         modCount++;
  15.         grow(minCapacity);
  16.     }
  17. }
  19. //得到最小容量，在添加元素时会调用该方法
  20. //这一方法主要实现了ArrayList在第一次添加元素时（扩容时），最小容量设置为默认容量10，而不是size + 1
  21. private void ensureCapacityInternal(int minCapacity) {
  22.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  23.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  24.     }
  25.     ensureExplicitCapacity(minCapacity);
  26. }
  28. //判断ArrayList容量是否满足最小容量，不满足则扩容
  29. private void ensureExplicitCapacity(int minCapacity) {
  30.     modCount++;
  31.     if (minCapacity - elementData.length > 0)
  32.         grow(minCapacity);
  33. }
  35. //ArrayList的最大容量
  36. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  38. //扩容的核心方法。
  39. private void grow(int minCapacity) {
  40.     int oldCapacity = elementData.length;
  42.     //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
  43.     //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
  44.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  46.     //检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
  47.     if (newCapacity - minCapacity < 0)
  48.         newCapacity = minCapacity;
  50.     //最后检查新容量是否超出了ArrayList的最大容量
  51.     //若超出了，则调用hugeCapacity()来比较minCapacity和MAX_ARRAY_SIZE，
  52.     //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为MAX_ARRAY_SIZE。
  53.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  54.         newCapacity = hugeCapacity(minCapacity);
  56.     // 进行扩容
  57.     // Arrays.copyOf()方法会创建一个新的容量为newCapacity的方法，并把elementData中的元素填入其中并返回
  58.     elementData = Arrays.copyOf(elementData, newCapacity);
  59. }
  61. //比较minCapacity和 MAX_ARRAY_SIZE
  62. private static int hugeCapacity(int minCapacity) {
  63.     if (minCapacity < 0) //最小容量溢出了
  64.         throw new OutOfMemoryError();
  65.     return (minCapacity > MAX_ARRAY_SIZE) ?
  66.         Integer.MAX_VALUE :
  67.         MAX_ARRAY_SIZE;
  68. }