前言 ArrayList
作为我们开发中最常用的集合,作为极高频次使用的类,我们不妨阅读源码一谈究竟。
介绍 ArrayList
继承关系如下
AaaryList
主要实现了List
接口,同时标记为可以序列化Serializable
、可复制CloneAble
、支持随机访问RandomAccess
。
几个重要的成员变量 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 private static final int DEFAULT_CAPACITY = 10 ;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; private int size;
数据结构 ArrayList
底层就是一个数组,数组会随着数据的增长而扩容,数组的扩容就是建立一个新的容量大的数组,然后把旧数组上面的数据复制进新数组。关于扩容,后面会详细讲解。
因为是数组,所以支持随机访问,且有序。
常用方法 ArrayList()
无参构造方法1 2 3 public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
初始化数组为一个空数组。与空元素数据区分开来,以了解添加第一个元素时要膨胀多少。
add(E e) 添加元素 将指定的元素追加到此列表的末尾
1 2 3 4 5 public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 private static int calculateCapacity (Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureCapacityInternal (int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity (int minCapacity) { modCount++; if (minCapacity - elementData.length > 0 ) grow(minCapacity); }
当添加元素,会先检查是否超出容量,如果超出,则需要扩容。
当第一次添加元素时,size
为默认值0,会计算出一个最小容量minCapacity
,如果是无参构造创建的,则会取默认的容量10
,
Math.max(DEFAULT_CAPACITY, minCapacity),这里传入的minCapacity为0,所以获取更大的10。
如果计算出的最小容量大于原容量minCapacity - elementData.length > 0
,则会进行扩容。
1 2 3 4 5 6 7 8 9 10 11 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); elementData = Arrays.copyOf(elementData, newCapacity); }
扩容算法是,扩为老容量的1.5倍,如果扩容后的容量仍然小于需要的最小容量minCapacity
,则新的容量就取最小容量。
如果扩容后的大小超过最大容量,则会进行下面的操作
1 2 3 4 5 6 7 private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
计算出扩容后的容量后,进行扩容,也就是,新建一个数组初始化为新容量,然后复制旧元素到新数组。elementData = Arrays.copyOf(elementData, newCapacity);
1 2 3 public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); }
1 2 3 4 5 6 7 8 9 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0 , copy, 0 , Math.min(original.length, newLength)); return copy; }
为什么不能在forEach里面修改列表 ArrayList
在新增、删除元素都会执行**modCount++
**
modCount
定义在ArrayList
的父类AbstractList
。
1 2 3 4 5 protected transient int modCount = 0 ;
然后我们来看下forEach
的实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 @Override public void forEach (Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this .elementData; final int size = this .size; for (int i=0 ; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
在遍历前,会暂存modCount值,每次循环都判断下modCount是否有更改,若更改了,里面跳出循环,随后抛出异常。