面试官:说说你对ArrayList的了解……
整体架构
ArrayList 整体架构就是一个数组结构:
- index 表示数组下标,从 0 开始计数,elementDatda 表示数组本身
DEFAULT_CAPACITY
表示数组的初始化大小,默认是10- size 表示数组的大小,int 类型,没有使用 volatile 修饰,非线程安全
- modCount 统计当前数组被修改的版本次数,数组结构有变动,就会
+1
类注释
- 允许 put null 值,会自动扩容
- size、isEmpty、get、set、add 等方法的时间复杂度都是
O(1)
- 不是线程安全的,多线程情况下,推荐使用线程安全类:
Collections#synchronizedList
- 增强 for 循环,或者使用迭代器迭代过程中,如果数组大小被改变,会快速失败,抛出异常
源码解析
1、初始化
三种方法:无参数直接初始化、指定大小初始化、指定初始数据初始化。
源码
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 保存数组的容器,默认是null transient Object[] elementData; // 无参数直接初始化 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 指定大小初始化 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(Collection<? extends E> c) { Object[] a = c.toArray(); // 如果给定的集合不为空 if ((size = a.length) != 0) { // 传入的集合类型为ArrayList时,数组直接地址指向a,否则拷贝数据 if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // 给定的集合数据为空时,默认空数组 elementData = EMPTY_ELEMENTDATA; } }
从源码中可以得到以下几点:
- ArrayList 无参构造器初始化时,默认大小是空数组,数组大小 10 是在第一次 add 的时候扩容的数组值。
- 指定数据初始化的时候,在传入的数据为空时,依旧会初始化为空数组。当传入的集合类型为ArrayList 时,elementData 会直接使用 toArray 生成的数组。
2、新增和扩容
添加元素时进行了两步操作:
- 判断是否需要扩容
- elementData 数组赋值,这里是非线程安全的
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { // 判断数组的大小是否还够存放新数据,不够则扩容,size是当前数组存放元素的个数 ensureCapacityInternal(size + 1); // 数组赋值,线程不安全 elementData[size++] = e; return true; }
扩容(ensureCapacityInternal)的源码
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // 计算数组需要的最小容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果是初始化时未指定大小,则使用默认的大小 10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } // 否则返回存放当前元素需要的最小容量值 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { // 数组改变的标志+1 modCount++; // 数组需要的最小容量大于数组的长度,数组需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // 记录旧的数组长度 int oldCapacity = elementData.length; // 新的数组长度等于旧的数组长度的 1.5 倍,oldCapacity >> 1相当于除以 2 int newCapacity = oldCapacity + (oldCapacity >> 1); // 新的数组长度小于需要的最小容量时,扩容值修改为最小容量值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 新的数组长度超过最大值时,MAX_ARRAY_SIZE 的值为 Integer 表示的最大值-8 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 数组的复制 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { // 内存溢出 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 需要的最小容量超过最大值时,返回Integer 表示的最大值 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
Java 的源码有一些需要注意的点:
- 初始化未指定大小的集合,第一次扩容的大小为 10
- 添加元素时,不管数组有没有扩容,modCount 都会
+1
- 数组容量的最大值是 Integer.MAX_VALUE,超过这个值,JVM 就不会给数组分配内存空间了
- 新增元素时,没有对值进行严格的校验,所以 ArrayList 可以添加
null
值。
源码中值得我们去学习的地方:
- 代码书写很优雅,一个方法只做一件事,便于理解
- 要有边界意识,数组的下标最大不超过 Integer 最大值,最小不能小于 0
3、扩容的本质
ArrayList 中的数组扩容是通过调用 Arrays 的 copyOf 方法。先创建一个符合我们预期容量的新数组,然后把旧数组的元素拷贝过去。通过调用 System.arraycopy
方法进行拷贝,此方法是 native 修饰的方法
/** * @param src 被拷贝的数组 * @param srcPos 从数组那里开始 * @param dest 目标数组 * @param destPos 从目标数组那个索引位置开始拷贝 * @param length 拷贝的长度 * 此方法是没有返回值的,通过 dest 的引用进行传值 */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
4、删除
在源码中关于删除的方法:
public boolean remove(Object o)
:删除第一个匹配的元素public E remove(int index)
:删除指定位置上的元素,并返回该元素private void fastRemove(int index)
:私有方法,被remove(Object o)
方法调用public boolean removeAll(Collection c)
:从此列表中删除包含在指定集合中的所有元素。public void clear()
:清空集合
/** * 移除此列表中指定位置的元素 */ public E remove(int index) { // 数组越界的检查,index 大于 size 时会抛 IndexOutOfBoundsException 异常 rangeCheck(index); modCount++; // 当 index 小于 0 时,在这里取值的时会抛出 ArrayIndexOutOfBoundsException 异常 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; } /** * 如果指定元素存在,则从此集合中删除第一次出现的指定元素,如果不存在,在保持不变,返回false */ public boolean remove(Object o) { // 如果要删除的元素为 null 时 if (o == null) { for (int index = 0; index < size; index++) // 判断元素是否为null if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) // 使用equals判断元素是否相等 if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { // 记录数组的结构变化 modCount++; // 需要移动的元素个数 // size 从 1 开始计算,index 从 0 开始,所以需要 -1 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 }
从源码可以看出一些注意点:
- 新增的时候没有对 null 做校验,删除的时候也是可以删除 null 值的
- 删除所有元素使用的是
clear()
方法 - 删除的时候,只做了 index 是否大于 size 的判断,index 为负值时在数组取值时抛出异常。小于 0 和大于 size 时的抛出异常不同。
- 元素相等的判断在不为 null 的情况下使用 equals 方法,自定义类型元素的删除要注意 equals 的具体实现。
5、迭代器
实现java.util.Iterator
接口类,迭代器中定义的几个参数:
int cursor;// 迭代过程中,下一个元素的位置,默认从 0 开始。 int lastRet = -1; // 新增场景:表示上一次迭代过程中,索引的位置;删除场景:为 -1。 int expectedModCount = modCount;// expectedModCount 表示迭代过程中,期望的版本号;modCount 表示数组实际的版本号。
常用的迭代器方法有三个:
hasNext
还有没有值可以迭代next
如果有值可以迭代,迭代的值是多少remove
删除当前迭代的值
hasNext 源码
public boolean hasNext() { // cursor 表示下一个元素的大小,size 表示实际存放的元素个数,两者相等时,表示没有元素可以便利了 return cursor != size; }
next源码
@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]; } // 判断是否修改了 elementData 数组 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
源码这一块里面,next 做了两件事,第一判断能不能继续迭代,第二找到需要迭代的值,并为下次迭代做准备。
这里面有个很有意思的点,在判断版本号和 i 是否超过元素个数以后,又做了一次是并发修改的判断。新建了一个本地变量,将地址指向 ArrayList 的数组 elementData。此时 elementData 如果修改地址对取值已经没什么影响了。然后判断 i 是否超过数组长度,保证代码正常运行能取值,但是多线程的情况下,取值不一定是对的。
remove源码
public void remove() { if (lastRet < 0) throw new IllegalStateException(); // 判断数组是否被修改 checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; // -1 表示元素已经被删除,防止重复删除 lastRet = -1; // 删除元素会修改modCount,需要给expectedModCount重新复制 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }
这里有两点需要注意的:
lastRet = -1
的操作是为了防止重复删除- 删除元素成功,数组的 modCount 会改变,需要同步修改 expectedModCount 的值。
6、线程安全
ArrayList 是线程不安全的,是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时,都没有加锁。要想保证线程安全,需要我们手动加锁,或者使用一些线程安全的集合类。